Skip to content

Instantly share code, notes, and snippets.

@mjdominus
Created May 10, 2019 20:21
Show Gist options
  • Save mjdominus/239b8c7022e40928e08e653162154335 to your computer and use it in GitHub Desktop.
Save mjdominus/239b8c7022e40928e08e653162154335 to your computer and use it in GitHub Desktop.
Calculate topological sortings of a graph
#!/usr/bin/python3
class Graph():
def __init__(self, edge_list):
self.E = set(edge_list)
self.V = range(self._n_vertices())
def _n_vertices(self):
max = 0
for edge in self.E:
a, b = edge
if a > max: max = a
if b > max: max = b
return max+1
def sources(self):
not_sources = set()
for e in self.E:
source, target = e
not_sources.add(target)
return set(self.V) - not_sources
def without_vertex(self, v):
new_graph = Graph({ e for e in self.E if e[0] != v and e[1] != v })
new_graph.V = set(self.V) - {v}
return new_graph
def topological_sortings(self):
if len(self.V) == 0: # no vertices
yield []
return
# otherwise there might be some source vertices
for source in self.sources():
g = self.without_vertex(source)
for ts in g.topological_sortings():
yield [source] + ts
return
def number_of_topological_sortings(graph):
if len(graph.V) == 0: return 1
return sum([ graph.without_vertex(source).number_of_topological_sortings()
for source in graph.sources() ])
G4 = Graph({(0, 1), (2, 3), (0,4), (4,3)})
for ts in G4.topological_sortings():
print(ts)
print("Count", G4.number_of_topological_sortings())
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment