| Title: | Spanning Tree Methods for Graphs |
|---|---|
| Description: | Implements spanning tree algorithms for undirected graphs represented as 'adj' adjacency lists. Provides enumeration of all spanning trees via Winter's (1986) contraction-based algorithm <doi:10.1007/BF01939361>, counting via Kirchhoff's matrix tree theorem, minimum spanning trees via Kruskal's algorithm, uniform random sampling via Wilson's (1996) loop-erased random walk <doi:10.1145/237814.237880>, and structural utilities including fundamental cycles and cuts. |
| Authors: | Christopher T. Kenny [aut, cre] (ORCID: <https://orcid.org/0000-0002-9386-6860>) |
| Maintainer: | Christopher T. Kenny <[email protected]> |
| License: | MIT + file LICENSE |
| Version: | 0.0.1 |
| Built: | 2026-05-31 06:18:44 UTC |
| Source: | https://github.com/christopherkenny/crann |
Counts the number of spanning trees of a connected undirected graph using Kirchhoff's matrix tree theorem: the count equals the determinant of any (n-1) x (n-1) cofactor of the graph Laplacian.
count_spanning_trees(graph)count_spanning_trees(graph)
graph |
An |
A numeric scalar. (Integer-valued but returned as numeric since
counts can exceed .Machine$integer.max for dense graphs.)
enumerate_spanning_trees() to list all spanning trees.
# Triangle: 3 spanning trees g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) count_spanning_trees(g)# Triangle: 3 spanning trees g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) count_spanning_trees(g)
Enumerates all spanning trees of a connected undirected graph using Winter's (1986) contraction-based algorithm. The algorithm has worst-case time complexity O(n + m + nt) and space complexity O(n^2), where n is the number of vertices, m the number of edges, and t the number of spanning trees.
enumerate_spanning_trees(graph)enumerate_spanning_trees(graph)
graph |
An |
A list of adj objects, one per spanning tree.
Winter, P. (1986). An algorithm for the enumeration of spanning trees. BIT Numerical Mathematics, 26(1), 44–62. doi:10.1007/BF01939361
# Triangle: 3 spanning trees g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) trees <- enumerate_spanning_trees(g) length(trees)# Triangle: 3 spanning trees g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) trees <- enumerate_spanning_trees(g) length(trees)
Returns a compact integer matrix encoding all spanning trees of a connected undirected graph. The matrix has n-1 rows and 2t columns, where n is the number of vertices and t is the number of spanning trees. For spanning tree k (1-indexed), columns 2k-1 and 2k hold the u and v endpoints (1-indexed vertex IDs) of each of the n-1 edges.
enumerate_spanning_trees_edges(graph)enumerate_spanning_trees_edges(graph)
graph |
An |
This function is substantially faster than
enumerate_spanning_trees() for graphs with many spanning trees
because it avoids per-tree R memory allocation: the entire output is
a single integer matrix allocation.
An integer matrix with n-1 rows and 2t columns.
Winter, P. (1986). An algorithm for the enumeration of spanning trees. BIT Numerical Mathematics, 26(1), 44–62. doi:10.1007/BF01939361
# Triangle: 3 spanning trees, 2 edges each -> 2 x 6 matrix g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) enumerate_spanning_trees_edges(g)# Triangle: 3 spanning trees, 2 edges each -> 2 x 6 matrix g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) enumerate_spanning_trees_edges(g)
Returns the fundamental cuts of a spanning tree with respect to the original graph. There is one fundamental cut per tree edge (n - 1 total), consisting of all edges in the graph that cross the bipartition induced by removing that tree edge.
fundamental_cuts(graph, tree)fundamental_cuts(graph, tree)
graph |
An |
tree |
An |
A list of adj objects, one per tree edge. Each adj represents
the cut as a subgraph of graph.
g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) t <- minimum_spanning_tree(g) fundamental_cuts(g, t)g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) t <- minimum_spanning_tree(g) fundamental_cuts(g, t)
Returns the fundamental cycles of a spanning tree with respect to the original graph. There is one fundamental cycle per non-tree edge (m - n + 1 total), formed by adding that edge to the unique path between its endpoints in the spanning tree.
fundamental_cycles(graph, tree)fundamental_cycles(graph, tree)
graph |
An |
tree |
An |
A list of adj objects, one per non-tree edge. Each adj
represents the cycle as a subgraph of graph.
g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) t <- minimum_spanning_tree(g) fundamental_cycles(g, t)g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) t <- minimum_spanning_tree(g) fundamental_cycles(g, t)
Returns TRUE if tree is a spanning tree: a connected acyclic graph with
exactly n-1 edges. To additionally check that tree uses only edges from a
reference graph, see is_spanning_tree_of().
is_spanning_tree(tree)is_spanning_tree(tree)
tree |
An |
A logical scalar.
is_spanning_tree_of(), minimum_spanning_tree(),
enumerate_spanning_trees()
g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) t <- minimum_spanning_tree(g) is_spanning_tree(t)g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) t <- minimum_spanning_tree(g) is_spanning_tree(t)
Returns TRUE if tree is a spanning tree of graph: a connected acyclic
subgraph that spans all vertices and uses only edges present in graph.
is_spanning_tree_of(tree, graph)is_spanning_tree_of(tree, graph)
tree |
An |
graph |
An |
A logical scalar.
is_spanning_tree(), minimum_spanning_tree(),
enumerate_spanning_trees()
g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) t <- minimum_spanning_tree(g) is_spanning_tree_of(t, g)g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) t <- minimum_spanning_tree(g) is_spanning_tree_of(t, g)
Finds a minimum spanning tree of a connected undirected graph using
Kruskal's algorithm. When weights is NULL (the default), all edges are
treated as having equal weight and any spanning tree is returned.
minimum_spanning_tree(graph, weights = NULL)minimum_spanning_tree(graph, weights = NULL)
graph |
An |
weights |
A numeric vector of edge weights, one per edge. Edges are
ordered by iterating vertices |
An adj object representing the minimum spanning tree.
is_spanning_tree() to validate a spanning tree.
g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) minimum_spanning_tree(g)g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) minimum_spanning_tree(g)
Samples a spanning tree uniformly at random from the set of all spanning trees using Wilson's (1996) loop-erased random walk algorithm.
sample_spanning_tree(graph)sample_spanning_tree(graph)
graph |
An |
An adj object representing a spanning tree of graph.
Wilson, D.B. (1996). Generating random spanning trees more quickly than the cover time. Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 296–303. doi:10.1145/237814.237880
enumerate_spanning_trees(), minimum_spanning_tree()
set.seed(1) g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) sample_spanning_tree(g)set.seed(1) g <- adj::adj(list(c(2L, 3L), c(1L, 3L), c(1L, 2L))) sample_spanning_tree(g)