Source code for tryalgo.biconnected_components
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
bi-connected components, cut vertices and cut cut-nodes
jill-jenn vie, christoph durr et louis abraham - 2015-2019
"""
from sys import getrecursionlimit, setrecursionlimit
# snip{
# to ease readiness, variables do not have dfs_ prefix
# pylint: disable=too-many-locals
# pylint: disable=too-many-nested-blocks
# pylint: disable=too-many-branches
[docs]
def cut_nodes_edges(graph):
"""Bi-connected components
:param graph: undirected graph. in listlist format.
Cannot be in listdict format.
:returns: a tuple with the list of cut-nodes and the list of cut-edges
:complexity: `O(|V|+|E|)`
"""
n = len(graph)
time = 0
num = [None] * n
low = [n] * n
parent = [None] * n # parent[v] = None if root else parent of v
critical_children = [0] * n # cc[u] = #{children v | low[v] >= num[u]}
times_seen = [-1] * n
for start in range(n):
if times_seen[start] == -1: # init DFS path
times_seen[start] = 0
to_visit = [start]
while to_visit:
node = to_visit[-1]
if times_seen[node] == 0: # start processing
num[node] = time
time += 1
low[node] = float('inf')
children = graph[node]
if times_seen[node] == len(children): # end processing
to_visit.pop()
up = parent[node] # propagate low to parent
if up is not None:
low[up] = min(low[up], low[node])
if low[node] >= num[up]:
critical_children[up] += 1
else:
child = children[times_seen[node]] # next arrow
times_seen[node] += 1
if times_seen[child] == -1: # not visited yet
parent[child] = node # link arrow
times_seen[child] = 0
to_visit.append(child) # (below) back arrow
elif num[child] < num[node] and parent[node] != child:
low[node] = min(low[node], num[child])
cut_edges = []
cut_nodes = [] # extract solution
for node in range(n):
if parent[node] is None: # characteristics
if critical_children[node] >= 2:
cut_nodes.append(node)
else: # internal nodes
if critical_children[node] >= 1:
cut_nodes.append(node)
if low[node] >= num[node]:
cut_edges.append((parent[node], node))
return cut_nodes, cut_edges
# snip}
[docs]
def cut_nodes_edges2(graph):
"""Bi-connected components, alternative recursive implementation
:param graph: undirected graph. in listlist format. Cannot be in listdict
format.
:assumes: graph has about 5000 vertices at most, otherwise memory limit is
reached
:returns: a tuple with the list of cut-nodes and the list of cut-edges
:complexity: `O(|V|+|E|)` in average, `O(|V|+|E|^2)` in worst case due to
use of dictionary
"""
N = len(graph)
assert N <= 5000
recursionlimit = getrecursionlimit()
setrecursionlimit(max(recursionlimit, N + 42))
edges = set((i, j) for i in range(N) for j in graph[i] if i <= j)
nodes = set()
NOT = -2 # not visited yet; -1 would be buggy `marked[v] != prof - 1`
FIN = -3 # already visited
marked = [NOT] * N # if >= 0, it means depth within the DFS
# pylint: disable=inconsistent-return-statements
def DFS(n, prof=0):
"""
Recursively search graph, update edge list and returns the first
node the first edge within search to which we can come back.
"""
if marked[n] == FIN:
return # only when there are several connected components
if marked[n] != NOT:
return marked[n]
marked[n] = prof
m = float('inf')
count = 0 # useful only for prof == 0
for v in graph[n]:
if marked[v] != FIN and marked[v] != prof - 1:
count += 1
r = DFS(v, prof+1)
if r <= prof:
edges.discard(tuple(sorted((n, v))))
if prof and r >= prof: # only if we are not at root
nodes.add(n)
m = min(m, r)
# root is an articulation point iff it has more than 2 childs
if prof == 0 and count >= 2:
nodes.add(n)
marked[n] = FIN
return m
for r in range(N):
DFS(r) # we can count connected components by nb += DFS(r)
setrecursionlimit(recursionlimit)
return nodes, edges