Return to Question

def topological_sort(edges):
 sort = []
  entered = set()
 may_enter = lambda v: v not in entered and not entered.add(v)
 for v in range(len(edges)):
 if v not in entered:
 Graph.dfs(v, edges, may_enter, None, lambda v: sort.append(v))
 return sort
# graph: D3 ⇾ H7
# ↑
# ┌──────── B1 ⇾ F5
# ↓ ↑ ↑
# J9 ⇽ E4 ⇽ A0 ⇾ C2 ⇾ I8
# ↓
# G6
edges = [[]] * 10
edges[0] = [Edge(1), Edge(2), Edge(4), Edge(6)] # 1, 2, 4, and 6
edges[1] = [Edge(3), Edge(5), Edge(9)] # 3, 5, and 9
edges[2] = [Edge(5), Edge(8)] # 5, 8
edges[3] = [Edge(7)] # 7
edges[4] = [Edge(9)] # 9
assert [7, 3, 5, 9, 1, 8, 2, 4, 6, 0] == topological_sort(edges)

def find_all(source, edges):
 reached = set()
 cross = lambda e, x: reached.add(e.y)
 Graph.dfs(source, edges, None, cross, None) 
 return reached
def can_reach(source, sink):
 reached = find_all(source, edges)
 return sink in reached
# graph: B1 ← C2 → A0
# ↓ ↗
# D3 ← E4
edges = [[]] * 5
edges[0] = [] # out-degree of 0
edges[1] = [Edge(3)] # B1 → D3
edges[2] = [Edge(0), Edge(1)] # C2 → A0, C2 → B1
edges[3] = [Edge(2)] # D3 → C2
edges[4] = [Edge(3)] # E4 → D3
assert can_reach(4, 0)
assert not can_reach(0, 4)
assert not can_reach(3, 4)
assert {0, 1, 2, 3} == find_all(4, edges)
assert {0, 1, 2, 3} == find_all(3, edges)
assert {0, 1, 2, 3} == find_all(2, edges)
assert set() == find_all(0, edges)

def topological_sort(edges):
 sort, entered = [], set()
 may_enter = lambda v: v not in entered and not entered.add(v)
 leave = lambda v: sort.append(v)
 for v in range(len(edges)):
 if v not in entered:
 Graph.dfs(v, edges, may_enter, leave=leave)
 return sort
# graph: D3 ⇾ H7
# ↑
# ┌──────── B1 ⇾ F5
# ↓ ↑ ↑
# J9 ⇽ E4 ⇽ A0 ⇾ C2 ⇾ I8
# ↓
# G6
edges = [[]] * 10
edges[0] = [Edge(1), Edge(2), Edge(4), Edge(6)] # 1, 2, 4, and 6
edges[1] = [Edge(3), Edge(5), Edge(9)] # 3, 5, and 9
edges[2] = [Edge(5), Edge(8)] # 5, 8
edges[3] = [Edge(7)] # 7
edges[4] = [Edge(9)] # 9
assert [7, 3, 5, 9, 1, 8, 2, 4, 6, 0] == topological_sort(edges)

def find_all(source, edges):
 reached = set()
 cross = lambda e, x: reached.add(e.y)
 Graph.dfs(source, edges, None, cross, None) 
 return reached
def can_reach(source, sink):
 return sink in find_all(source, edges)
# graph: B1 ← C2 → A0
# ↓ ↗
# D3 ← E4
edges = [[]] * 5
edges[0] = [] # out-degree of 0
edges[1] = [Edge(3)] # B1 → D3
edges[2] = [Edge(0), Edge(1)] # C2 → A0, C2 → B1
edges[3] = [Edge(2)] # D3 → C2
edges[4] = [Edge(3)] # E4 → D3
assert can_reach(4, 0)
assert not can_reach(0, 4)
assert not can_reach(3, 4)
assert {0, 1, 2, 3} == find_all(4, edges)
assert {0, 1, 2, 3} == find_all(3, edges)
assert {0, 1, 2, 3} == find_all(2, edges)
assert set() == find_all(0, edges)

# undirected graph: A0 - B1 - C2
edges = [[]] * 3
edges[0] = [Edge(1)] # A0 - B1
edges[1] = [Edge(0), Edge(2)] # B1 - A0, B1 - C2
edges[2] = [Edge(1)] # C2 - B1
assert not has_cycle(edges, False)
# undirected graph: A0 - B1 - C2 - A0
edges[0].append(Edge(2)) # A0 - C2
edges[2].append(Edge(0)) # C2 - A0
assert has_cycle(edges, False)

# undirected graph: A0 - B1 - C2
edges = [[]] * 3
edges[0] = [Edge(1)] # A0 - B1
edges[1] = [Edge(0), Edge(2)] # B1 - A0, B1 - C2
edges[2] = [Edge(1)] # C2 - B1
assert not has_cycle(edges, False)
# undirected graph: A0 - B1
#  \ /
# C2
edges[0].append(Edge(2)) # A0 - C2
edges[2].append(Edge(0)) # C2 - A0
assert has_cycle(edges, False)

from itertools import dropwhile
class Graph(object):
 @staticmethod
 def dfs(v, edges, may_enter=None, cross=None, leave=None):
 if may_enter is None:
 may_enter = lambda v, entered=set(): v not in entered and not entered.add(v)
 if may_enter(v):
 for e in (edges[v] or []):
 cross is not None and cross(e, v)
 Graph.dfs(e.y, edges, may_enter, cross, leave)
 leave is not None and leave(v)
class Edge(object): # wegith is None in unweighted graph
 def __init__(self, y=None, weight=None):
 self.y, self.weight = y, weight
 def __repr__(self):
 attrs = (self.weight, self.y)
 return "Edge({0})".format(', '.join(reversed( \
 [repr(e) for e in dropwhile(lambda e: e is None, attrs)])))

from itertools import dropwhile
class Graph(object):
 @staticmethod
 def dfs(v, edges, may_enter=None, cross=None, leave=None):
 if may_enter is None:
 may_enter = lambda v, entered=set(): v not in entered and not entered.add(v)
 if may_enter(v):
 for e in (edges[v] or []):
 cross is not None and cross(e, v)
 Graph.dfs(e.y, edges, may_enter, cross, leave)
 leave is not None and leave(v)
class Edge(object): # weight is None in unweighted graph
 def __init__(self, y=None, weight=None):
 self.y, self.weight = y, weight
 def __repr__(self):
 attrs = (self.weight, self.y)
 return "Edge({0})".format(', '.join(reversed( \
 [repr(e) for e in dropwhile(lambda e: e is None, attrs)])))