codexgraph-articulation-versus-bridge.py
graph-articulation-versus-bridge.py
"""Compute every deletion and DFS lowpoints for triangles joined by CD.
Tested with Python 3.14.4, numpy 2.3.5 and matplotlib 3.10.7.
Run from _media: MPLCONFIGDIR=/tmp/matplotlib python3 ../graph-articulation-versus-bridge.py
Writes graph-articulation-versus-bridge.png in the current working directory.
"""
import json
from pathlib import Path
import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
import numpy as np
VERTICES = "ABCDEF"
EDGES = ("AB", "AC", "BC", "CD", "DE", "DF", "EF")
POSITIONS = dict(zip(VERTICES, np.array([
[-1.65, 0.9], [-1.65, -0.9], [-0.55, 0], [0.55, 0], [1.65, 0.9], [1.65, -0.9]
])))
DARK, BLUE, GREEN, RED = "#263747", "#326f9c", "#25846a", "#bd3f43"
def adjacency(vertices, edges):
return {v: sorted(b if a == v else a for a, b in edges if v in (a, b))
for v in vertices}
def components(vertices, edges, removed_vertex=None, removed_edge=None):
remaining = set(vertices) - {removed_vertex}
kept = [e for e in edges if (removed_vertex is None or removed_vertex not in e)
and frozenset(e) != frozenset(removed_edge or ())]
neighbours = adjacency(sorted(remaining), kept)
groups = []
while remaining:
start = min(remaining)
remaining.remove(start)
pending, group = [start], []
while pending:
v = pending.pop()
group.append(v)
for w in neighbours[v]:
if w in remaining:
remaining.remove(w)
pending.append(w)
groups.append(sorted(group))
return groups
def dfs_criteria(vertices, edges):
"""For undirected simple graphs; skip the unique parent edge."""
neighbours = adjacency(vertices, edges)
discovery, low, parents, cuts, bridges = {}, {}, {}, set(), []
def visit(v, parent):
parents[v] = parent
discovery[v] = low[v] = len(discovery) + 1
children = 0
for w in neighbours[v]:
if w not in discovery:
children += 1
visit(w, v)
low[v] = min(low[v], low[w])
if parent is not None and low[w] >= discovery[v]:
cuts.add(v)
if low[w] > discovery[v]:
bridges.append("".join(sorted((v, w))))
elif w != parent:
low[v] = min(low[v], discovery[w])
if parent is None and children >= 2:
cuts.add(v)
for v in sorted(vertices):
if v not in discovery:
visit(v, None)
return {"discovery": discovery, "low": low, "parents": parents,
"cut_vertices": sorted(cuts), "bridges": sorted(bridges)}
def compute():
original = components(VERTICES, EDGES)
deletions = {v: components(VERTICES, EDGES, removed_vertex=v) for v in VERTICES}
edge_counts = {e: len(components(VERTICES, EDGES, removed_edge=e)) for e in EDGES}
cuts = [v for v in VERTICES if len(deletions[v]) > len(original)]
bridges = [e for e in EDGES if edge_counts[e] > len(original)]
dfs = dfs_criteria(VERTICES, EDGES)
assert original == [list(VERTICES)]
assert deletions["C"] == [list("AB"), list("DEF")]
assert deletions["D"] == [list("ABC"), list("EF")]
assert components(VERTICES, EDGES, removed_edge="CD") == [list("ABC"), list("DEF")]
assert [len(deletions[v]) for v in VERTICES] == [1, 1, 2, 2, 1, 1]
assert cuts == dfs["cut_vertices"] == ["C", "D"]
assert bridges == dfs["bridges"] == ["CD"]
assert list(dfs["discovery"].values()) == [1, 2, 3, 4, 5, 6]
assert [dfs["low"][v] for v in VERTICES] == [1, 1, 1, 4, 4, 4]
return {"adjacency": adjacency(VERTICES, EDGES), "components": original,
"vertex_deletions": deletions, "edge_deletion_counts": edge_counts,
"cut_vertices": cuts, "bridges": bridges, "dfs": dfs}
def draw(ax, removed_vertex=None, removed_edge=None):
groups = components(VERTICES, EDGES, removed_vertex, removed_edge)
colors = {v: (BLUE if i == 0 else GREEN) for i, group in enumerate(groups) for v in group}
for a, b in EDGES:
if removed_vertex in (a, b) or a + b == removed_edge:
continue
p, q = POSITIONS[a], POSITIONS[b]
color = RED if a + b == "CD" else colors[a]
ax.plot([p[0], q[0]], [p[1], q[1]], color=color, lw=2.6, zorder=1)
for v in VERTICES:
if v == removed_vertex:
continue
x, y = POSITIONS[v]
color = RED if removed_vertex is None and removed_edge is None and v in "CD" else colors[v]
ax.scatter(x, y, s=800, color="white", edgecolor=color, linewidth=2.6, zorder=2)
ax.text(x, y, v, ha="center", va="center", fontsize=14, weight="bold", color=color)
ax.set_xlim(-2.1, 2.1)
ax.set_ylim(-1.35, 1.35)
ax.set_aspect("equal")
ax.axis("off")
return len(groups), sum((removed_vertex is None or removed_vertex not in e)
and e != removed_edge for e in EDGES)
def main():
result = compute()
plt.rcParams.update({"font.family": "DejaVu Sans", "font.size": 11})
fig, axes = plt.subplots(2, 2, figsize=(8.4, 6.1), facecolor="white")
fig.suptitle("One bridge; two cut vertices; different deletions", fontsize=15, color=DARK, y=0.975)
cases = [(None, None, "Original graph"), (None, "CD", "Delete only edge CD"),
("C", None, "Delete vertex C and its incident edges"),
("D", None, "Delete vertex D and its incident edges")]
for ax, (vertex, edge, title) in zip(axes.flat, cases):
count, edge_count = draw(ax, vertex, edge)
ax.set_title(title, fontsize=12, color=DARK, pad=10)
ax.text(0.5, -0.06, f"{len(VERTICES) - bool(vertex)} vertices; {edge_count} edges; "
f"{count} component{'s' if count != 1 else ''}",
ha="center", color=DARK, fontsize=11, transform=ax.transAxes)
fig.text(0.5, 0.035, "Original cut vertices: C, D Original bridge: CD",
ha="center", color=DARK, fontsize=12)
fig.subplots_adjust(left=0.035, right=0.965, top=0.865, bottom=0.12, wspace=0.15, hspace=0.4)
fig.savefig(Path.cwd() / "graph-articulation-versus-bridge.png", dpi=140, facecolor="white",
transparent=False)
plt.close(fig)
print(json.dumps(result, sort_keys=True))
if __name__ == "__main__":
main()