spqrtree package

Module contents

SPQR-Tree: a pure Python implementation.

This package provides an SPQR-Tree data structure for biconnected graphs, based on the algorithm by Gutwenger & Mutzel (2001) with corrections to Hopcroft-Tarjan (1973), and data structure definitions from Di Battista & Tamassia (1996).

Public API:

from spqrtree import Edge, MultiGraph
from spqrtree import NodeType, SPQRNode, build_spqr_tree
from spqrtree import (
    ComponentType,
    TriconnectedComponent,
    find_triconnected_components,
)

class spqrtree.ComponentType(*values)

Bases: Enum

Classification of a triconnected split component.

Variables:

BOND – A bond - two vertices connected by multiple parallel edges.
POLYGON – A simple cycle - every vertex has degree 2 in the component.
TRICONNECTED – A 3-connected subgraph.

BOND = 'bond': A bond component: two vertices connected by parallel edges.

POLYGON = 'polygon': A polygon component: a simple cycle.

TRICONNECTED = 'triconnected': A triconnected component: a 3-connected subgraph.

class spqrtree.Edge(id: int, u: Hashable, v: Hashable, virtual: bool = False)

Bases: object

An edge in a multigraph, identified by a unique integer ID.

Supports parallel edges (multiple edges between the same pair of vertices) and virtual edges used internally by the SPQR-Tree algorithm.

endpoints() → tuple[Hashable, Hashable]

Return both endpoints as a tuple.

Returns:: A tuple (u, v) of the two endpoints.

id: int: Unique integer identifier for this edge.

other(vertex: Hashable) → Hashable

Return the endpoint opposite to the given vertex.

Parameters:: vertex – One endpoint of this edge.
Returns:: The other endpoint.
Raises:: ValueError – If vertex is not an endpoint of this edge.

u: Hashable: One endpoint of the edge.

v: Hashable: The other endpoint of the edge.

virtual: bool = False: Whether this is a virtual edge (used in SPQR skeletons).

class spqrtree.MultiGraph

Bases: object

An undirected multigraph supporting parallel edges and virtual edges.

Vertices are arbitrary hashable values. Edges are identified by unique integer IDs. Supports parallel edges (multiple edges between the same vertex pair).

add_edge(u: Hashable, v: Hashable, virtual: bool = False) → Edge

Add an edge between two vertices and return it.

Automatically adds vertices u and v if not already present.

Parameters:

u – One endpoint vertex.
v – The other endpoint vertex.
virtual – Whether this is a virtual edge.

Returns:

The newly created Edge object.

add_vertex(v: Hashable) → None

Add a vertex to the graph. No-op if already present.

Parameters:: v – The vertex to add.
Returns:: None

adj_edge_ids(v: Hashable) → list[int]

Return the list of edge IDs in the adjacency list of v.

The order reflects the current adjacency list ordering, which may be modified by the palm tree construction for algorithmic correctness.

Parameters:: v – A vertex.
Returns:: List of edge IDs adjacent to v, in adjacency list order.
Raises:: KeyError – If vertex v does not exist.

copy() → MultiGraph

Return a shallow copy of this graph with independent structure.

Vertices and edge IDs are preserved. Edge objects are copied.

Returns:: A new MultiGraph with the same structure.

degree(v: Hashable) → int

Return the degree of vertex v (number of incident edges).

Parameters:: v – A vertex.
Returns:: The number of edges incident to v.
Raises:: KeyError – If vertex v does not exist.

property edges: list[Edge]

Return a list of all edges in the graph.

Returns:: List of Edge objects.

edges_between(u: Hashable, v: Hashable) → list[Edge]

Return all edges between vertices u and v.

Parameters:

u – One vertex.
v – The other vertex.

Returns:

List of Edge objects between u and v.

get_edge(edge_id: int) → Edge | None

Return the edge with the given ID, or None if not found.

Parameters:: edge_id – The integer ID of the edge to look up.
Returns:: The Edge object, or None if no such edge exists.

has_edge(edge_id: int) → bool

Check whether an edge with the given ID exists.

Parameters:: edge_id – The integer ID to check.
Returns:: True if the edge exists, False otherwise.

incident_edges(v: Hashable) → list[Edge]

Return all edges incident to vertex v.

Parameters:: v – A vertex.
Returns:: List of Edge objects incident to v.
Raises:: KeyError – If vertex v does not exist.

neighbors(v: Hashable) → list[Hashable]

Return a list of distinct vertices adjacent to v.

Parameters:: v – A vertex.
Returns:: List of adjacent vertices (no duplicates).
Raises:: KeyError – If vertex v does not exist.

num_edges() → int

Return the number of edges in the graph.

Returns:: Edge count.

num_vertices() → int

Return the number of vertices in the graph.

Returns:: Vertex count.

remove_edge(edge_id: int) → None

Remove an edge from the graph by its ID.

Parameters:: edge_id – The integer ID of the edge to remove.
Returns:: None
Raises:: KeyError – If the edge ID does not exist.

remove_vertex(v: Hashable) → None

Remove a vertex and all its incident edges from the graph.

Parameters:: v – The vertex to remove.
Returns:: None
Raises:: KeyError – If the vertex does not exist.

set_adj_order(v: Hashable, edge_ids: list[int]) → None

Set the adjacency list order for vertex v.

Used by the palm tree algorithm to reorder edges for correct DFS traversal order per Gutwenger-Mutzel Section 4.2.

Parameters:

v – A vertex.
edge_ids – The ordered list of edge IDs for v’s adjacency.

Returns:

None

Raises:

KeyError – If vertex v does not exist.

property vertices: set[Hashable]

Return the set of all vertices.

Returns:: The set of vertices.

class spqrtree.NodeType(*values)

Bases: Enum

SPQR-tree node types.

Variables:

Q – A Q-node represents a single edge (degenerate bond).
S – An S-node represents a simple cycle (series).
P – A P-node represents parallel edges (parallel).
R – An R-node represents a 3-connected subgraph (rigid).

P = 'P': P-node: parallel edges (bond with 3+ real edges).

Q = 'Q': Q-node: a single real edge.

R = 'R': R-node: a 3-connected subgraph.

S = 'S': S-node: a simple cycle (polygon).

class spqrtree.SPQRNode(type: ~spqrtree._spqr.NodeType, skeleton: ~spqrtree._graph.MultiGraph, poles: tuple[~collections.abc.Hashable, ~collections.abc.Hashable], parent: ~spqrtree._spqr.SPQRNode | None, children: list[~spqrtree._spqr.SPQRNode] = <factory>)

Bases: object

A node in the SPQR-tree.

Parameters:

type – The node type (Q, S, P, or R).
skeleton – The skeleton graph for this node, containing the real and virtual edges of the component.
poles – The pair of poles (u, v) for this node, i.e., the two vertices of the virtual edge connecting this node to its parent (or the two endpoints for the root).
parent – The parent SPQRNode, or None if this is the root.
children – Ordered list of child SPQRNodes.

children: list[SPQRNode]: Child nodes in the SPQR-tree.

parent: SPQRNode | None: Parent node, or None if this is the root.

poles: tuple[Hashable, Hashable]: The two pole vertices of this node.

skeleton: MultiGraph: The skeleton graph of this node.

type: NodeType: The SPQR-tree node type.

class spqrtree.SPQRTree(graph: MultiGraph | dict)

Bases: object

An SPQR-Tree for a biconnected graph.

Constructs the SPQR-Tree from a biconnected multigraph, using the Gutwenger-Mutzel triconnected components algorithm.

nodes() → list[SPQRNode]

Return all nodes of the SPQR-Tree in BFS order.

Returns:: A list of all SPQRNode objects.

property root: SPQRNode

Return the root node of the SPQR-Tree.

Returns:: The root SPQRNode.

class spqrtree.TriconnectedComponent(type: ComponentType, edges: list[Edge])

Bases: object

A single triconnected split component.

Parameters:

type – Classification as BOND, POLYGON, or TRICONNECTED.
edges – All edges in this component (real and virtual). Virtual edges are shared with exactly one other component.

edges: list[Edge]: All edges in this component (real and virtual).

type: ComponentType: Classification of this component.

spqrtree.build_spqr_tree(graph: MultiGraph) → SPQRNode

Build an SPQR-tree for a biconnected multigraph.

Decomposes the graph into triconnected split components, then assembles them into an SPQR-tree. Each component becomes a node with type Q (degenerate bond of 2 edges), P (bond of 3+ edges), S (polygon), or R (triconnected).

Parameters:: graph – A biconnected multigraph.
Returns:: The root SPQRNode of the SPQR-tree.

spqrtree.find_triconnected_components(graph: MultiGraph) → list[TriconnectedComponent]

Find all triconnected split components of a biconnected multigraph.

The input must be a biconnected multigraph (possibly with parallel edges). Returns a list of TriconnectedComponent objects, each classified as BOND, POLYGON, or TRICONNECTED.

Each real (non-virtual) edge of the input appears in exactly one component. Each virtual edge (added by the algorithm) appears in exactly two components, representing the two sides of a separation pair.

Parameters:: graph – A biconnected multigraph.
Returns:: A list of TriconnectedComponent objects.
Raises:: ValueError – If the graph is not connected or has a cut vertex.