Topological sort python

Question

I coded a solution for DFS non-recursive, but i can't modify it to make a topological sort:

def dfs(graph,start):
    path = []
    stack = [start]    
    while stack != []: 
        v = stack.pop()
        if v not in path: path.append(v)
        for w in reversed(graph[v]): 
            if w not in path and not w in stack:
                stack.append(w) 
    return path

Any ideas how to modify it?

With the recursive version i can easy have the sorting:

def dfs_rec(graph,start,path):
    path = path + [start]
    for edge in graph[start]: 
        if edge not in path:
            path = dfs_rec(graph, edge,path)
    print start
    return path

Input:

>>> graph = {
        1: [2, 3],
        2: [4, 5, 6],
        3: [4,6],
        4: [5,6],
        5: [6],
        6: []
    }
>>> dfs_rec(graph,1,[])
6
5
4
2
3
1
[1, 2, 4, 5, 6, 3]
>>> dfs(graph,1)
[1, 2, 4, 5, 6, 3]
>>> graph = {
        1: [3],
        3: [5,6],
        5: [4],
        4: [7],
        7: [],
        6: []
    }
>>> print dfs_rec(graph,1,[])
7
4
5
6
3
1
[1, 3, 5, 4, 7, 6]
>>> print dfs(graph,1)
[1, 3, 5, 4, 7, 6]

so i need to get this ordering in the non-recursive also.

Non-recursive solution:

I think that this also could be the solution, mark me if i am wrong.

def dfs(graph,start):
    path = []
    stack = [start]
    label = len(graph)
    result = {}  
    while stack != []:
        #this for loop could be done in other ways also
        for element in stack:
            if element not in result:
                result[element] = label
                label = label - 1

        v = stack.pop()
        if v not in path: path.append(v)
        for w in reversed(graph[v]): 
            if w not in path and not w in stack:
                stack.append(w) 

    result = {v:k for k, v in result.items()}
    return path,result

Input:

graph = { 1: [3], 3:[5,6] , 5:[4] , 4:[7], 7:[],6:[]}
print dfs(graph,1) 

Output:

([1, 3, 5, 4, 7, 6], {1: 7, 2: 4, 3: 5, 4: 6, 5: 3, 6: 1})

        1
       / 
      3
     /\
    5  6
   /
  4
 /
7    

Answer 1

For my own purposes (竜 TatSu) I took Kahn's algorithm as described in Wikipedia and wrote this version in Python:

def topsort[T](nodes: Iterable[T], edges: Iterable[tuple[T, T]]) -> list[T]:
    # https://en.wikipedia.org/wiki/Topological_sorting#Kahn's_algorithm

    order = set(edges)
    result: list[T] = []  # Empty list that will contain the sorted elements

    def with_incoming() -> set[T]:
        return {m for (_, m) in order}

    # Set of all nodes with no incoming edges
    pending = list(set(nodes) - with_incoming())
    while pending:
        n = pending.pop()
        result.append(n)

        # nodes m with an edge from n to m
        outgoing = {m for (x, m) in order if x == n}
        order -= {(n, m) for m in outgoing}
        pending.extend(outgoing - with_incoming())

    if order:
        raise ValueError('There are cycles in the topological order')

    return result  # a topologically sorted list

I thought about possible optimizations (with_incoming() and outgoing may be expensive), but the graphs I need to deal with are small, so I preferred the simplicity and clarity.

Answer 2

    from collections import defaultdict  # importing defaultdict      
    def topological_sort(graph,b,a):     # defining function
        T = []
        visited = []
        in_degree = []
        for i in range(a+1):            
                in_degree.append(0)     # initialising the degree of each vertex =0
                visited.append(0)       # initialising all the vertics unvisited
        for i in range(1,a+1):
                for j in graph[i]:
                    in_degree[j] = in_degree[j] + 1  # now assigning and incrementing 
        Queue=[]                                     # the degree of each vertex acc.
        for i in range(1,a+1):
                if in_degree[i]==0:
                        Queue.append(i)         # appending those vertices which have zero 
                        visited[i] = 1          # degree and making it as visited   
        while Queue :
                vertex = Queue.pop(Queue.index(min(Queue))) # popping each element in 
                T.append(vertex)                            # lexicographical order and 
                for j in graph[vertex]:                     # appending to T
                        if visited[j]==0:
                            in_degree[j] = in_degree[j] - 1
                            if in_degree[j] == 0:          
                                    Queue.append(j)       #according to each popped vertex
                                    visited[j] = 1        #as key in graph check whether
        return T                                          #in list corresponding to key 
                                                          # as value,is it not visited and 
                                                          #decreasing its value when it 
                                                          #becomes zero,append it to queue
                                                          #and mark it as visited
    graph=defaultdict(list)    
    a,b=list(map(int,input().split())) #a=no. of vertices  
    for i in range(b):                 #b=no. of edges
        p,q=list(map(int,input().split())) 
        graph[p].append(q)      # we take input in graph as DAG
    ss=topological_sort(graph,b,a) # calling function
    for i in ss:
        print(i,end=" ")
'''Input
    5 6
    1 2
    1 3
    2 3
    2 4
    3 4
    3 5
  Your Code's Output
    1 2 3 4 5
  Expected Correct Output
    1 2 3 4 5 '''

Answer 3

from collections import defaultdict, deque


class Graph:
    def __init__(self, directed=False, nodes=None, edges=None):
        self.graph = defaultdict(list)
        self.directed = directed
        self.add_nodes(nodes)
        self.add_edges(edges)

    @property
    def nodes(self):
        if not self.directed:
            return list(self.graph.keys())
        elif self.directed:
            nodes = set()
            nodes.update(self.graph.keys())
            for node in self.graph.keys():
                for neighbor in self.graph[node]:
                    nodes.add(neighbor)
            return list(nodes)

    def add_node(self, node):
        if node not in self.nodes:
            self.graph[node] = list()

    def add_nodes(self, nodes):
        if nodes is None:
            return None
        for node in nodes:
            self.add_node(node)

    @property
    def edges(self):
        edges = list()
        for source, neighbors in self.graph.items():
            for neighbor in neighbors:
                edges.append((source, neighbor))
        return edges

    def add_edge(self, edge):
        node1, node2 = edge
        self.graph[node1].append(node2)
        if not self.directed:
            self.graph[node2].append(node1)

    def add_edges(self, edges):
        if edges is None:
            return None
        for edge in edges:
            self.add_edge(edge)

    def topological_util(self, node, visited, label):
        visited[node] = True
        for edge in self.graph[node]:
            if not visited[edge]:
                self.topological_util(edge, visited, label)
        label.appendleft(node)

    def topological_sort(self):
        visited = dict.fromkeys(self.nodes, False)
        # store all nodes in topological order, the index is the position
        label = deque()
        for node in self.nodes:
            if not visited[node]:
                self.topological_util(node, visited, label)
        return label

Answer 4

    #this algorithm gives the logic of topological sorting..if u want to run this 
    #give adjacency mat of your choice and this algorithm works on graph elements ranging from 0 to n 

    a=[[0,0,1,0,0,0],[0,0,1,0,0,0],[0,0,0,1,1,0],[0,0,0,0,1,0],[0,0,0,0,0,0],[0,0,1,0,0,0]]
    vis=[0 for i in range(0,len(a))]
    s=[]

    orderstack=[]#stores the reverse order of topological sorted elements

    def dfs_for_topological_sorting(a,vis,i):

        vis[i]=1
        x=0
        for j in range(0,len(a[0])):
            if(a[i][j]==1 and vis[j]==0):
                x=1
                s.append(j)
                #print(s)
                dfs_for_topological_sorting(a,vis,j)
        if(x==0 and len(s)!=0):

            orderstack.append(s[len(s)-1])
        if(len(s)>0):
            dfs_for_topological_sorting(a,vis,s.pop())

    for i in range(0,len(a)):
        if(i not in orderstack):
            s.append(i)
            dfs_for_topological_sorting(a,vis,i)
    print(orderstack[len(orderstack)-1::-1])        

Answer 5

FWIW, here is some code I worked up for a non-recursive topological sort.

from collections import defaultdict, namedtuple
from itertools import islice

Results = namedtuple('Results', ['sorted', 'cyclic'])

def topological_sort(dependency_pairs):
    'Sort values subject to dependency constraints'
    num_heads = defaultdict(int)   # num arrows pointing in
    tails = defaultdict(list)      # list of arrows going out
    heads = []                     # unique list of heads in order first seen
    for h, t in dependency_pairs:
        num_heads[t] += 1
        if h in tails:
            tails[h].append(t)
        else:
            tails[h] = [t]
            heads.append(h)

    ordered = [h for h in heads if h not in num_heads]
    for h in ordered:
        for t in tails[h]:
            num_heads[t] -= 1
            if not num_heads[t]:
                ordered.append(t)
    cyclic = [n for n, heads in num_heads.items() if heads]
    return Results(ordered, cyclic)

if __name__ == '__main__':
    print( topological_sort('aa'.split()) )
    print( topological_sort('ah bg cf ch di ed fb fg hd he ib'.split()) )