Perform topolical sort on a directed acyclic graph.
(start, visited, sort)
| 9 | |
| 10 | |
| 11 | def topological_sort(start, visited, sort): |
| 12 | """Perform topolical sort on a directed acyclic graph.""" |
| 13 | current = start |
| 14 | # add current to visited |
| 15 | visited.append(current) |
| 16 | neighbors = edges[current] |
| 17 | for neighbor in neighbors: |
| 18 | # if neighbor not in visited, visit |
| 19 | if neighbor not in visited: |
| 20 | sort = topological_sort(neighbor, visited, sort) |
| 21 | # if all neighbors visited add current to sort |
| 22 | sort.append(current) |
| 23 | # if all vertices haven't been visited select a new one to visit |
| 24 | if len(visited) != len(vertices): |
| 25 | for vertice in vertices: |
| 26 | if vertice not in visited: |
| 27 | sort = topological_sort(vertice, visited, sort) |
| 28 | # return sort |
| 29 | return sort |
| 30 | |
| 31 | |
| 32 | sort = topological_sort('a', [], []) |