|
|
Post by Łukasz on Jan 21, 2019 7:32:05 GMT
from collections import deque
class Node:
def __init__(self, name):
self.name = name
self.connections = []
self.visited = False
def add_connection(self, node):
self.connections.append(node.name)
class Graph:
def __init__(self):
self.node = {}
def add_node(self, node):
self.node[node.name] = node
def get_graph(self):
return self.node
def bfsearch(self, element):
queue = deque([])
lmbd = lambda x: [queue.appendleft(y) for y in x]
result = self.node[element]
while True:
element = self.node[element]
if not element.visited:
print(element.name)
for e in element.connections:
lmbd(e)
result = element
element.visited = True
if len(queue) != 0:
element = queue.pop()
else:
break
return result.name
def dfsearch(self, element):
queue = deque([element])
lmbd = lambda x: [queue.append(y) for y in x]
result = self.node[element]
while True:
if len(queue) != 0:
element = queue.pop()
else:
break
element = self.node[element]
if not element.visited:
print(element.name)
for e in element.connections:
lmbd(e)
result = element
element.visited = True
return result.name
node1 = Node('A')
node2 = Node('B')
node3 = Node('C')
node4 = Node('D')
node5 = Node('E')
node1.add_connection(node2)
node1.add_connection(node3)
node2.add_connection(node3)
node3.add_connection(node1)
node3.add_connection(node4)
node4.add_connection(node4)
graph = Graph()
graph.add_node(node1)
graph.add_node(node2)
graph.add_node(node3)
graph.add_node(node4)
graph.add_node(node5)
print(graph.bfsearch('C'))
Graph algorithms. |
|
|
|
Post by Łukasz on Jan 21, 2019 19:51:13 GMT
import sys
from collections import deque
from heapq import *
class Edge:
def __init__(self, weight, start_vertex, target_vertex):
self.weight = weight
self.start_vertex = start_vertex
self.target_vertex = target_vertex
class Node:
def __init__(self, name):
self.name = name
self.connections = []
self.visited = False
self.distance = sys.maxsize
self.predacessor = None
def add_connection(self, edge):
self.connections.append(edge)
class Graph:
def __init__(self):
self.node = {}
def add_node(self, node):
self.node[node.name] = node
def get_graph(self):
return self.node
def bfsearch(self, element):
queue = deque([])
lmbd = lambda x: [queue.appendleft(y) for y in x]
result = self.node[element]
while True:
element = self.node[element]
if not element.visited:
for e in element.connections:
lmbd(e)
result = element
element.visited = True
if len(queue) != 0:
element = queue.pop()
else:
break
return result.name
def dfsearch(self, element):
queue = deque([element])
lmbd = lambda x: [queue.append(y) for y in x]
result = self.node[element]
while True:
if len(queue) != 0:
element = queue.pop()
else:
break
element = self.node[element]
if not element.visited:
for e in element.connections:
lmbd(e)
result = element
element.visited = True
return result.name
def dijkstra(self, vertex):
queue = []
self.node[vertex].distance = 0
heappush(queue, self.node[vertex])
while len(queue) > 0:
actual_vertex = heappop(queue)
for e in actual_vertex.connections:
u = e.start_vertex
v = e.target_vertex
new_distance = u.distance + e.weight
if new_distance < v.distance:
v.predacessor = u.name
v.distance = new_distance
heappush(queue, v)
def dijkstra_print(self, target_vertex):
print(self.node[target_vertex].distance)
pred = self.node[target_vertex].predacessor
while pred is not None:
print(pred)
pred = self.node[pred].predacessor
node1 = Node('A')
node2 = Node('B')
node3 = Node('C')
node4 = Node('D')
node5 = Node('E')
node6 = Node('F')
node7 = Node('G')
node8 = Node('H')
edge1 = Edge(5, node1, node2)
edge2 = Edge(8, node1, node8)
edge3 = Edge(9, node1, node5)
edge4 = Edge(15, node2, node4)
edge5 = Edge(12, node2, node3)
edge6 = Edge(4, node2, node8)
edge7 = Edge(7, node8, node3)
edge8 = Edge(6, node8, node6)
edge9 = Edge(5, node5, node8)
edge10 = Edge(4, node5, node6)
edge11 = Edge(20, node5, node7)
edge12 = Edge(1, node6, node3)
edge13 = Edge(13, node6, node7)
edge14 = Edge(3, node3, node4)
edge15 = Edge(11, node3, node7)
edge16 = Edge(9, node4, node7)
node1.add_connection(edge1)
node1.add_connection(edge2)
node1.add_connection(edge3)
node2.add_connection(edge4)
node2.add_connection(edge5)
node2.add_connection(edge6)
node8.add_connection(edge7)
node8.add_connection(edge8)
node5.add_connection(edge9)
node5.add_connection(edge10)
node5.add_connection(edge11)
node6.add_connection(edge12)
node6.add_connection(edge13)
node3.add_connection(edge14)
node7.add_connection(edge15)
node4.add_connection(edge16)
graph = Graph()
graph.add_node(node1)
graph.add_node(node2)
graph.add_node(node3)
graph.add_node(node4)
graph.add_node(node5)
graph.add_node(node6)
graph.add_node(node7)
graph.add_node(node8)
graph.dijkstra('A')
graph.dijkstra_print('G')
Added Dijkstra algorithm.
|
|
|
|
Post by Łukasz on Jan 22, 2019 18:21:12 GMT
import sys
from collections import deque
from heapq import *
class Edge:
def __init__(self, weight, start_vertex, target_vertex):
self.weight = weight
self.start_vertex = start_vertex
self.target_vertex = target_vertex
class Node:
def __init__(self, name):
self.name = name
self.connections = []
self.visited = False
self.distance = sys.maxsize
self.predacessor = None
def add_connection(self, edge):
self.connections.append(edge)
class Graph:
def __init__(self):
self.node = {}
self.edge = []
self.negative_cycle = None
def add_node(self, node):
self.node[node.name] = node
def add_edge(self, edge):
self.edge.append(edge)
def clean(self):
for n in self.node:
self.node[n].visited = False
self.node[n].predacessor = None
self.node[n].distance = sys.maxsize
def search(self, element, weight):
queue = deque([element])
while len(queue) != 0:
element = queue.popleft()
element = self.node[element]
for e in element.connections:
if not e.target_vertex.visited:
e.target_vertex.predacessor = e.start_vertex.name
if e.weight == weight:
print(e.start_vertex.name + ' -> ' + e.target_vertex.name)
queue.append(e.target_vertex.name)
e.target_vertex.visited = True
def dijkstra(self, vertex):
queue = []
self.node[vertex].distance = 0
heappush(queue, self.node[vertex])
while len(queue) > 0:
actual_vertex = heappop(queue)
for e in actual_vertex.connections:
u = e.start_vertex
v = e.target_vertex
new_distance = u.distance + e.weight
if new_distance < v.distance:
v.predacessor = u.name
v.distance = new_distance
heappush(queue, v)
def bellman_ford(self, vertex):
self.node[vertex].distance = 0
for _ in range(0, len(self.node) - 1):
for e in self.edge:
u = e.start_vertex
v = e.target_vertex
new_distance = u.distance + e.weight
if new_distance < v.distance:
v.predacessor = u.name
v.distance = new_distance
for e in self.edge:
if e.start_vertex.distance + e.weight < e.target_vertex.distance:
self.negative_cycle = True
def gprint(self, target_vertex):
if not self.negative_cycle:
print(self.node[target_vertex].distance)
pred = self.node[target_vertex].predacessor
while pred is not None:
print(pred)
pred = self.node[pred].predacessor
else:
print('Has negative cycle')
node1 = Node('A')
node2 = Node('B')
node3 = Node('C')
node4 = Node('D')
node5 = Node('E')
node6 = Node('F')
node7 = Node('G')
node8 = Node('H')
edge1 = Edge(5, node1, node2)
edge2 = Edge(8, node1, node8)
edge3 = Edge(9, node1, node5)
edge4 = Edge(15, node2, node4)
edge5 = Edge(12, node2, node3)
edge6 = Edge(4, node2, node8)
edge7 = Edge(7, node8, node3)
edge8 = Edge(6, node8, node6)
edge9 = Edge(5, node5, node8)
edge10 = Edge(4, node5, node6)
edge11 = Edge(20, node5, node7)
edge12 = Edge(1, node6, node3)
edge13 = Edge(13, node6, node7)
edge14 = Edge(3, node3, node4)
edge15 = Edge(11, node3, node7)
edge16 = Edge(9, node4, node7)
edge17 = Edge(1, node1, node2)
edge18 = Edge(1, node2, node3)
edge19 = Edge(-3, node3, node1)
node1.add_connection(edge1)
node1.add_connection(edge2)
node1.add_connection(edge3)
node2.add_connection(edge4)
node2.add_connection(edge5)
node2.add_connection(edge6)
node8.add_connection(edge7)
node8.add_connection(edge8)
node5.add_connection(edge9)
node5.add_connection(edge10)
node5.add_connection(edge11)
node6.add_connection(edge12)
node6.add_connection(edge13)
node3.add_connection(edge14)
node7.add_connection(edge15)
node4.add_connection(edge16)
graph = Graph()
graph.add_node(node1)
graph.add_node(node2)
graph.add_node(node3)
graph.add_node(node4)
graph.add_node(node5)
graph.add_node(node6)
graph.add_node(node7)
graph.add_node(node8)
graph.add_edge(edge1)
graph.add_edge(edge2)
graph.add_edge(edge3)
graph.add_edge(edge4)
graph.add_edge(edge5)
graph.add_edge(edge6)
graph.add_edge(edge7)
graph.add_edge(edge8)
graph.add_edge(edge9)
graph.add_edge(edge10)
graph.add_edge(edge11)
graph.add_edge(edge12)
graph.add_edge(edge13)
graph.add_edge(edge14)
graph.add_edge(edge15)
graph.add_edge(edge16)
graph.add_edge(edge17)
graph.add_edge(edge18)
graph.add_edge(edge19)
graph.search('A', 20)
graph.clean()
graph.bellman_ford('A')
graph.gprint('G')
I added Bellman Ford algorithm and repaired bugs.
|
|
|
|
Post by Ł on Feb 2, 2019 7:18:09 GMT
class Node:
def __init__(self, name, value=None):
self.name = name
self.value = value
self.visited = False
self.connection = []
def add_connection(self, node):
self.connection.append(node)
class Graph:
def __init__(self):
self.nodes = {}
def add_node(self, node):
self.nodes[node.name] = node
def multiply(self, cols, rows):
i = 0
g = Graph()
for n in self.nodes.values():
if n.value and n.visited == False:
for c in n.connection:
if self.nodes[c].visited == False:
tmp = Node(self.nodes[c].name, n.value * self.nodes[c].value)
g.add_node(tmp)
self.nodes[c].visited == True
n.visited = True
i += 1
m1 = [[2,1,3],[-1,4,0]]
m2 = [[1,3,2],[-2,0,1],[5,-3,2]]
g = Graph()
n0 = Node('N0')
g.add_node(n0)
counter = 1
g_n0 = len(g.nodes)
for i in range(0, len(m1)):
tmp = Node('N' + str(counter))
g.add_node(tmp)
n0.add_connection(tmp.name)
counter += 1
g_n1 = len(g.nodes)
for i in range(g_n0, g_n1):
for k in range(0, len(m1[(i - g_n0)])):
tmp = Node('N' + str(counter), m1[(i - g_n0)][k])
g.add_node(tmp)
g.nodes['N' + str(i)].add_connection(tmp.name)
counter += 1
g_n2 = len(g.nodes)
for i in range(g_n1, g_n2):
for k in range(0, len(m2[(i - g_n1) % g_n1])):
tmp = Node('N' + str(counter), m2[(i - g_n1) % g_n1][k])
g.add_node(tmp)
g.nodes['N' + str(i)].add_connection(tmp.name)
counter += 1
multiply = g.multiply(len(m2), len(m1))
print(multiply)
Graph-matrix multiplication algorithm, code is a bit incomplete but you have idea.
|
|
|
|
Post by Ł on Feb 2, 2019 13:08:53 GMT
class Node:
def __init__(self, name, value=None, col=None, row=None):
self.name = name
self.value = value
self.visited = False
self.connection = []
self.col = col
self.row = row
def add_connection(self, node):
self.connection.append(node)
class Graph:
def __init__(self):
self.nodes = {}
def add_node(self, node):
self.nodes[node.name] = node
def multiply(self, cols, rows):
i = 0
g = Graph()
for n in self.nodes.values():
if n.value and n.visited == False:
for c in n.connection:
if self.nodes[c].visited == False:
tmp = Node(self.nodes[c].name, n.value * self.nodes[c].value, n.col, n.row)
g.add_node(tmp)
self.nodes[c].visited == True
n.visited = True
i += 1
tmp = list(g.nodes.values())
parts = len(tmp) / cols
completed = False
val = {}
i = 0
while i < len(tmp):
l = i
last_mod = l % parts % rows
if not val.get('D'+str(last_mod)):
val['D'+str(last_mod)] = 0
while l < len(tmp):
counter = 0
next_mod = l % parts % rows
if last_mod == next_mod and val.get('D'+str(next_mod)):
val['D'+str(next_mod)] += tmp[l].value
else:
if not val.get('D'+str(next_mod)):
val['D'+str(next_mod)] = tmp[l].value
if l == len(tmp) - 1:
completed = True
last_mod = next_mod
print(val)
if completed:
break
l += rows
if completed:
break
i += 1
m1 = [[2,1,3],[-1,4,0]]
m2 = [[1,3,2],[-2,0,1],[5,-3,2]]
g = Graph()
n0 = Node('N0')
g.add_node(n0)
counter = 1
g_n0 = len(g.nodes)
for i in range(0, len(m1)):
tmp = Node('N' + str(counter))
g.add_node(tmp)
n0.add_connection(tmp.name)
counter += 1
g_n1 = len(g.nodes)
for i in range(g_n0, g_n1):
for k in range(0, len(m1[(i - g_n0)])):
tmp = Node('N' + str(counter), m1[(i - g_n0)][k], (i - g_n0), k)
g.add_node(tmp)
g.nodes['N' + str(i)].add_connection(tmp.name)
counter += 1
g_n2 = len(g.nodes)
for i in range(g_n1, g_n2):
for k in range(0, len(m2[(i - g_n1) % g_n1])):
tmp = Node('N' + str(counter), m2[(i - g_n1) % g_n1][k])
g.add_node(tmp)
g.nodes['N' + str(i)].add_connection(tmp.name)
counter += 1
multiply = g.multiply(len(m1), len(m2))
print(multiply)
Almost ready T-Matrix multiplication algorithm.
|
|
