Utility Algorithms

Graph manipulation and analysis tools that don’t fit into a specific algorithm family.

Graph transformations

Algorithm What it does

Algorithm	What it does
Copy Graph	Deep copy of a graph.
Transpose Graph	Reverse all edges (creates a new graph, unlike `reverse_graph` adaptor).
Transitive Closure	Add edges so that if u reaches v through any path, edge (u,v) exists.
Transitive Reduction	Remove redundant transitive edges. The opposite of transitive closure.

Deep copy of a graph.

Reverse all edges (creates a new graph, unlike reverse_graph adaptor).

Add edges so that if u reaches v through any path, edge (u,v) exists.

Remove redundant transitive edges. The opposite of transitive closure.

Algorithm	What it does
Dominator Tree	Compute the dominator tree of a directed graph (used in compiler analysis).
Maximum Adjacency Search	Visit vertices in order of connectivity to the already-visited set.
Betweenness Centrality Clustering	Remove high-betweenness edges to partition a graph into clusters.
Metric TSP Approximation	2-approximation for the Travelling Salesman Problem on complete metric graphs.
Graph Statistics	Degree distribution, duplicate edge count, weighted degree distribution.
Smallest Last Ordering	Vertex ordering by minimum degree. Good heuristic for graph coloring.

Algorithm

What it does

Compute the dominator tree of a directed graph (used in compiler analysis).

Visit vertices in order of connectivity to the already-visited set.

Remove high-betweenness edges to partition a graph into clusters.

2-approximation for the Travelling Salesman Problem on complete metric graphs.

Degree distribution, duplicate edge count, weighted degree distribution.

Vertex ordering by minimum degree. Good heuristic for graph coloring.

Algorithm	What it does
Neighbor BFS	BFS that follows both in-edges and out-edges on directed graphs.
Loop-Erased Random Walk	Building block for Wilson’s random spanning tree algorithm.
Disjoint Sets	Union-find data structure used by Kruskal and incremental components.
Incident	Returns both endpoints of an edge as a pair.
Opposite	Given an edge and one endpoint, returns the other.

Algorithm

What it does

BFS that follows both in-edges and out-edges on directed graphs.

Building block for Wilson’s random spanning tree algorithm.

Union-find data structure used by Kruskal and incremental components.

Returns both endpoints of an edge as a pair.

Given an edge and one endpoint, returns the other.