A strategy to perform a search in the graph. Sorts the nodes of the Directed Acyclic Graph such that for every directed edge $uv$, vertex $u$ comes before vertex $v$ in ordering.
import numpy as np
## declaring the directed graph with weights
## g[i] = [(j,k)] - a graph has an edge from node i to node j with weight k
g = dict()
g[0] = [(1,1), (2,2), (3,3)]
g[1] = [(4,2), (5,1)]
g[2] = [(4,2), (5,1), (6,2)]
g[3] = [(5,1), (6,2)]
g[4] = [(7,0)]
g[5] = [(7,0)]
g[6] = [(7,0)]
g[7] = []
print("Given graph\n", g)
Given graph {0: [(1, 1), (2, 2), (3, 3)], 1: [(4, 2), (5, 1)], 2: [(4, 2), (5, 1), (6, 2)], 3: [(5, 1), (6, 2)], 4: [(7, 0)], 5: [(7, 0)], 6: [(7, 0)], 7: []}
def constructIncomingGraph(og):
## og - graph with ougoing edges
## returns the same graph structure but with incoming edges
## no weights preserved
# ig[i] = j, there is an edge from node j to node i
ig = dict()
for node_from, nodes_to in og.items():
for node_to in nodes_to:
if node_to[0] in ig:
ig[node_to[0]].append(node_from)
else:
ig[node_to[0]] = [node_from]
return ig
## Checking that graph of incoming edges is properly constructed
ig = constructIncomingGraph(g)
print("Graph of incoming edges\n", ig)
Graph of incoming edges {1: [0], 2: [0], 3: [0], 4: [1, 2], 5: [1, 2, 3], 6: [2, 3], 7: [4, 5, 6]}
from collections import deque
def topologicalSorting(g, start_node):
ig = constructIncomingGraph(g)
# queue of sorted nodes (result)
sorted_nodes = deque([])
## queue of nodes with no incoming edges
I = deque([start_node])
while(I): ## I is not empty
n = I.popleft()
# if out of I than no incoming
sorted_nodes.append(n)
if n not in g:
print("Your graph is missing node", n)
children = g[n] ## children of type [(j,k)]
for child in children:
## remove an incoming edge (release the node from a parent :))
child_id = child[0]
ig[ child_id ].remove(n)
if not ig[ child_id ]:
## no incoming edges -> add to I
I.append(child_id)
print("sorting done")
return sorted_nodes
## testing sorting
S = topologicalSorting(g, 0)
print(S)
sorting done deque([0, 1, 2, 3, 4, 5, 6, 7])
Well-well it seems like working, the only problem to implement this is normal cofing language is line 19. To make it efficient the list of children should be implemented as list :) Otherwise of vector will need to remove from the beginning or from the middle of the vector, which involves copying the whole vector. BAD :(
Let's now try to find the shortest path
import math
def shortestPath(g, S):
# Incoming: g - graph with outgoing edges
# S - queue of sorted nodes
N = len(S) ## total number of nodes in S
dist = N * [math.inf]
p = N * [None]
dist[S[0]] = 0
# print("Graph\n", g)
# print("sorted\n", S)
for el in S:
u = el
children = g[u]
for child in children:
v = child[0] ## node to
w = child[1] ## weight between u and v
# print("Edge", u,"->", v, ":", w)
if (dist[v] > dist[u] + w):
dist[v] = dist[u] + w
p[v] = u
# print("Distance: ", dist)
# print("Parent: ",p)
## reverting path
path = []
par_id = len(p)-1
path.append(par_id)
while par_id:
par_id = p[par_id]
path.append(par_id)
return path
shortestPath(g, S_test)
## Assuming the graph is given
S = topologicalSorting(g, 0)
print("Sorted nodes: ", S)
path = shortestPath(g,S)
print("given graph\n", g)
print("Shortest path\n", path)
sorting done Sorted nodes: deque([0, 1, 2, 3, 4, 5, 6, 7]) given graph {0: [(1, 1), (2, 2), (3, 3)], 1: [(4, 2), (5, 1)], 2: [(4, 2), (5, 1), (6, 2)], 3: [(5, 1), (6, 2)], 4: [(7, 0)], 5: [(7, 0)], 6: [(7, 0)], 7: []} Shortest path [7, 5, 1, 0]