Graph
simple graph: Graph does not have parallel edges or self-loops.
simple path: vertices on the path are distinct.
simple cycle: vertices on the cycle are distinct except the first and last one.
A directed graph is acyclic if it has no directed cycles.
\(\vec{G}\) is strongly connected if for any two vertices \(u\) and \(v\) of \(\vec{G}\), \(u\) reaches \(v\) and \(v\) reaches \(u\).
Subgraph of a graph \(G\) is a graph \(H\) whose vertices and edges are subsets of the vertices and edges of \(G\).
A spanning subgraph of G is a subgraph of G that contains all the vertices of the graph G.
If G is not connected, its maximal connected subgraphs are called the connected components of G.
A forest is a graph without cycles.
A tree is a connected forest, that is, a connected graph without cycles.
A spanning tree of a graph is a spanning subgraph that is a tree.
Strongly Connected Components
from graph import G
def test_scc():
g = G()
g.add_direct(1, 2)
g.add_direct(2, 3)
g.add_direct(3, 1)
g.add_direct(1, 4)
g.add_direct(5, 4)
g.add_direct(4, 5)
assert g.timestamp() == {1: [1, 10], 2: [2, 5], 3: [3, 4], 4: [6, 9], 5: [7, 8]}
assert set(g.scc()) == set([(1,2,3), (4,5)])
test_scc()
graph implementation
'''
G(V, E)
adjacency-list:
- representation for sparse graphs (E << V^2)
adjacency-matrix:
- representation for dense graphs (E ~ V^2)
- or when we need quick answer of has_edge(v1, v2)
Personally I prefer to use a map of map structure.
'''
from stack import Stack
class G:
'''
a map of map structure representing edges as weight[u][v]
'''
def __init__(self):
self.weights = {}
@property
def V(self):
'''
return all vertices
'''
vertices = set(self.weights.keys())
for d in self.weights.values():
vertices |= d.keys()
return vertices
@property
def E(self):
'''
return all edges
'''
return [(u, v, self.weights[u][v]) for u in self.weights for v in self.weights[u]]
def add_direct(self, u, v):
self.weights.setdefault(u, {})[v] = 1
def add_edge(self, u, v):
self.add_direct(u, v)
self.add_direct(v, u)
def __str__(self):
ans = []
vertices = sorted(self.V)
for u in vertices:
line = []
for v in vertices:
if u in self.weights and v in self.weights[u]:
line.append(str(self.weights[u][v]))
else:
line.append('0')
ans.append(', '.join(line))
return '\n'.join(ans)
def transpose(self):
transpose = G()
for u in self.weights:
for v in self.weights[u]:
transpose.add_direct(v, u)
return transpose
def timestamp(self):
'''
DFS timestamp
'''
visited = set()
def dfs(u):
nonlocal count
if u in visited: return
# found time
visited.add(u)
timestamp.setdefault(u, [0, 0])[0] = count
count += 1
for v in self.weights.get(u, []):
dfs(v)
# finish time
timestamp[u][1] = count
count += 1
timestamp = {}
count = 1
for u in self.V:
dfs(u)
return timestamp
def scc(self):
def dfs(u):
if u in visited: return
# found time
visited.add(u)
for v in self.weights.get(u, []):
dfs(v)
# finish time
timestamp_stack.push(u)
timestamp_stack = Stack()
visited = set()
for u in self.V:
dfs(u)
# DFS G.transpose to get SCCs
def dfs2(u, scc, visited):
if u in visited: return
visited.add(u)
scc.add(u)
for v in transpose.weights.get(u, []):
dfs2(v, scc, visited)
transpose = self.transpose()
visited = set()
for u in timestamp_stack:
if u not in visited:
scc = set()
dfs2(u, scc, visited)
yield tuple(scc)