I wrote a program for DFS traversal, topological sort, find all vertices, and has_cycle methods.
Can you please suggest more elegant and eloquent ways for this program?
(Perhaps better ways to represent a graph with vertices and edges?)
NOTE: dfs and has_cycle implementation is inspired by the book "Algorithm Design Manual".
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)])))
Topological Sort
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)
Find all vertices
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)
Has cycle (inspired by Algorithm Design Manual)
def has_cycle(edges, directed):
for v in range(len(edges)):
entered = set()
exited = set()
tree_edges = {} # keyed by children; also called parents map.
back_edges = {} # keyed by ancestors, or the other end-point.
may_enter = lambda v: v not in entered and not entered.add(v)
exit = lambda v: exited.add(v)
def cross(e, x):
if e.y not in entered:
tree_edges[e.y] = x
elif (not directed and tree_edges.get(x, None) != e.y) \
or (directed and e.y not in exited):
back_edges.setdefault(e.y, []).append(x) # x = 1, e.y = 0
Graph.dfs(v, edges, may_enter, cross, exit)
if back_edges:
return True
else:
return False
Has cycle in Directed Graph
# directed graph: B1 ← C2 → A0
# ↓ ↗
# D3 ← E4
edges = [[]] * 5
edges[0] = [] # out-degree of 0
edges[1] = [Edge(3, 4)] # B1 → D3
edges[2] = [Edge(0, 4), Edge(1, 6)] # C2 → A0, C2 → B1
edges[3] = [Edge(2, 9)] # D3 → C2
edges[4] = [Edge(3, 3)] # E4 → D3
assert has_cycle(edges, True)
# directed graph: B1 ← C2 → A0
# ↓ ↓
# D3 ← E4
edges = [[]] * 5
edges[0] = []
edges[1] = [Edge(3)]
edges[2] = [Edge(0), Edge(1), Edge(4)]
edges[3] = []
edges[4] = [Edge(3)]
assert not has_cycle(edges, True)
Has cycle in Undirected Graph
# 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)