Topological sorting

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.

In [1]:
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: []}
In [2]:
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
In [3]:
## 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]}
In [4]:
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
In [5]:
## 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 :(

Searching for the shortest path

Let's now try to find the shortest path

In [7]:
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
In [ ]:
shortestPath(g, S_test)

Making a proper example

In [9]:
## 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]
In [ ]: