109 lines
3.0 KiB
Python
109 lines
3.0 KiB
Python
"""Undirected graph: bridges (cut edges) and articulation points (iterative Tarjan)."""
|
|
from __future__ import annotations
|
|
|
|
|
|
def _normalize(graph):
|
|
from collections import Counter
|
|
counts = Counter()
|
|
for u, nbrs in (graph or {}).items():
|
|
for v in (nbrs or ()):
|
|
counts[frozenset((u, v))] += 1
|
|
edge_list = []
|
|
for e, c in counts.items():
|
|
if c <= 1:
|
|
mult = 1
|
|
elif c % 2 == 0:
|
|
mult = c // 2
|
|
else:
|
|
mult = c
|
|
edge_list.extend([e] * mult)
|
|
# nodes
|
|
nodes = set((graph or {}).keys())
|
|
for e in edge_list:
|
|
for n in e:
|
|
nodes.add(n)
|
|
# build adj with unique edge ids by index
|
|
adj = {n: [] for n in nodes}
|
|
for i, e in enumerate(edge_list):
|
|
els = tuple(e)
|
|
if len(els) == 1:
|
|
a = els[0]
|
|
adj[a].append((a, i))
|
|
else:
|
|
a, b = els
|
|
adj[a].append((b, i))
|
|
adj[b].append((a, i))
|
|
return nodes, adj, edge_list
|
|
|
|
|
|
def analyze(graph):
|
|
nodes, adj, edge_list = _normalize(graph)
|
|
if not nodes:
|
|
return set(), set()
|
|
|
|
disc = {}
|
|
low = {}
|
|
timer = [0]
|
|
bridges = set()
|
|
art = set()
|
|
children_root = {}
|
|
|
|
for start in sorted(nodes, key=lambda x: (type(x).__name__, repr(x))):
|
|
if start in disc:
|
|
continue
|
|
root = start
|
|
children_root[root] = 0
|
|
disc[root] = low[root] = timer[0]
|
|
timer[0] += 1
|
|
stack = [root]
|
|
parent_node = {root: None}
|
|
parent_edge = {root: None}
|
|
frames = {root: 0} # next child index
|
|
cur = root
|
|
while True:
|
|
if frames[cur] < len(adj[cur]):
|
|
nbr, eid_ = adj[cur][frames[cur]]
|
|
frames[cur] += 1
|
|
if eid_ == parent_edge[cur]:
|
|
continue
|
|
if nbr not in disc:
|
|
parent_node[nbr] = cur
|
|
parent_edge[nbr] = eid_
|
|
disc[nbr] = low[nbr] = timer[0]
|
|
timer[0] += 1
|
|
stack.append(nbr)
|
|
frames[nbr] = 0
|
|
if cur == root:
|
|
children_root[root] += 1
|
|
cur = nbr
|
|
else:
|
|
if nbr in stack:
|
|
low[cur] = min(low[cur], disc[nbr])
|
|
else:
|
|
stack.pop()
|
|
if stack:
|
|
pnode = stack[-1]
|
|
low[pnode] = min(low[pnode], low[cur])
|
|
if low[cur] > disc[pnode]:
|
|
bridges.add(edge_list[parent_edge[cur]])
|
|
if pnode != root and low[cur] >= disc[pnode]:
|
|
art.add(pnode)
|
|
del frames[cur]
|
|
if not stack:
|
|
break
|
|
cur = stack[-1]
|
|
if children_root.get(root, 0) > 1:
|
|
art.add(root)
|
|
|
|
return bridges, art
|
|
|
|
|
|
def bridges(graph):
|
|
b, _ = analyze(graph)
|
|
return b
|
|
|
|
|
|
def articulation_points(graph):
|
|
_, a = analyze(graph)
|
|
return a
|