Spanning trees¶
This module is a collection of algorithms on spanning trees. Also included in the collection are algorithms for minimum spanning trees. See the book [JoynerNguyenCohen2010] for descriptions of spanning tree algorithms, including minimum spanning trees.
See also
Todo
- Rewrite
kruskal()
to use priority queues. Once Cython has support for generators and theyield
statement, rewritekruskal()
to useyield
. - Prim’s algorithm.
- Boruvka’s algorithm.
- Parallel version of Boruvka’s algorithm.
- Randomized spanning tree construction.
REFERENCES:
[Aldous90] | D. Aldous, ‘The random walk construction of uniform spanning trees’, SIAM J Discrete Math 3 (1990), 450-465. |
[Broder89] | A. Broder, ‘Generating random spanning trees’, Proceedings of the 30th IEEE Symposium on Foundations of Computer Science, 1989, pp. 442-447. doi:10.1109/SFCS.1989.63516, <http://www.cs.cmu.edu/~15859n/RelatedWork/Broder-GenRanSpanningTrees.pdf>_ |
[CormenEtAl2001] | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. 2nd edition, The MIT Press, 2001. |
[GoodrichTamassia2001] | Michael T. Goodrich and Roberto Tamassia. Data Structures and Algorithms in Java. 2nd edition, John Wiley & Sons, 2001. |
[JoynerNguyenCohen2010] | David Joyner, Minh Van Nguyen, and Nathann Cohen. Algorithmic Graph Theory. 2010, http://code.google.com/p/graph-theory-algorithms-book/ |
[Sahni2000] | Sartaj Sahni. Data Structures, Algorithms, and Applications in Java. McGraw-Hill, 2000. |
Methods¶
-
sage.graphs.spanning_tree.
kruskal
(G, wfunction=None, check=False)¶ Minimum spanning tree using Kruskal’s algorithm.
This function assumes that we can only compute minimum spanning trees for undirected simple graphs. Such graphs can be weighted or unweighted.
INPUT:
G
– A graph. This can be an undirected graph, a digraph, a multigraph, or a multidigraph. Note the following behaviours:- If
G
is unweighted, then consider the simple version ofG
with all self-loops and multiple edges removed. - If
G
is directed, then we only consider its undirected version. - If
G
is weighted, we ignore all of its self-loops. Note that a weighted graph should only have numeric weights. You cannot assign numeric weights to some edges ofG
, but haveNone
as a weight for some other edge. If your input graph is weighted, you are responsible for assign numeric weight to each of its edges. Furthermore, we remove multiple edges as follows. First we convertG
to be undirected. Suppose there are multiple edges fromto
. Among all such multiple edges, we choose one with minimum weight.
- If
wfunction
– A weight function: a function that takes an edge and returns a numeric weight. Default:None
. The default is to assign each edge a weight of 1.check
– Whether to first perform sanity checks on the input graphG
. Default:check=False
. If we togglecheck=True
, the following sanity checks are first performed onG
prior to running Kruskal’s algorithm on that input graph:- Is
G
the null graph? - Is
G
disconnected? - Is
G
a tree? - Is
G
directed? - Does
G
have self-loops? - Does
G
have multiple edges? - Is
G
weighted?
By default, we turn off the sanity checks for performance reasons. This means that by default the function assumes that its input graph is simple, connected, is not a tree, and has at least one vertex. If the input graph does not satisfy all of the latter conditions, you should set
check=True
to perform some sanity checks and preprocessing on the input graph. To further improve the runtime of this function, you should call it directly instead of using it indirectly viasage.graphs.generic_graph.GenericGraph.min_spanning_tree()
.- Is
OUTPUT:
The edges of a minimum spanning tree of
G
, if one exists, otherwise returns the empty list.- If
G
is a tree, return the edges ofG
regardless of whetherG
is weighted or unweighted, directed or undirected. - If
G
is unweighted, default to using unit weight for each edge ofG
. The default behaviour is to use the already assigned weights ofG
provided thatG
is weighted. - If
G
is weighted and a weight function is also supplied, then use the already assigned weights ofG
, not the weight function. If you really want to use a weight function forG
even ifG
is weighted, first convertG
to be unweighted and pass in the weight function.
EXAMPLES:
An example from pages 727–728 in [Sahni2000].
sage: from sage.graphs.spanning_tree import kruskal sage: G = Graph({1:{2:28, 6:10}, 2:{3:16, 7:14}, 3:{4:12}, 4:{5:22, 7:18}, 5:{6:25, 7:24}}) sage: G.weighted(True) sage: E = kruskal(G, check=True); E [(1, 6, 10), (3, 4, 12), (2, 7, 14), (2, 3, 16), (4, 5, 22), (5, 6, 25)]
Variants of the previous example.
sage: H = Graph(G.edges(labels=False)) sage: kruskal(H, check=True) [(1, 2, None), (1, 6, None), (2, 3, None), (2, 7, None), (3, 4, None), (4, 5, None)] sage: H = DiGraph(G.edges(labels=False)) sage: kruskal(H, check=True) [(1, 2, None), (1, 6, None), (2, 3, None), (2, 7, None), (3, 4, None), (4, 5, None)] sage: G.allow_loops(True) sage: G.allow_multiple_edges(True) sage: G Looped multi-graph on 7 vertices sage: for i in range(20): ... u = randint(1, 7) ... v = randint(1, 7) ... w = randint(0, 20) ... G.add_edge(u, v, w) sage: H = copy(G) sage: H Looped multi-graph on 7 vertices sage: def sanitize(G): ... G.allow_loops(False) ... E = {} ... for u, v, _ in G.multiple_edges(): ... E.setdefault(u, v) ... for u in E: ... W = sorted(G.edge_label(u, E[u])) ... for w in W[1:]: ... G.delete_edge(u, E[u], w) ... G.allow_multiple_edges(False) sage: sanitize(H) sage: H Graph on 7 vertices sage: kruskal(G, check=True) == kruskal(H, check=True) True
Note that we only consider an undirected version of the input graph. Thus if
G
is a weighted multidigraph andH
is an undirected version ofG
, then this function should return the same minimum spanning tree for bothG
andH
.sage: from sage.graphs.spanning_tree import kruskal sage: G = DiGraph({1:{2:[1,14,28], 6:[10]}, 2:{3:[16], 1:[15], 7:[14], 5:[20,21]}, 3:{4:[12,11]}, 4:{3:[13,3], 5:[22], 7:[18]}, 5:{6:[25], 7:[24], 2:[1,3]}}, multiedges=True) sage: G.multiple_edges(to_undirected=False) [(1, 2, 1), (1, 2, 14), (1, 2, 28), (5, 2, 1), (5, 2, 3), (4, 3, 3), (4, 3, 13), (3, 4, 11), (3, 4, 12), (2, 5, 20), (2, 5, 21)] sage: H = G.to_undirected() sage: H.multiple_edges(to_undirected=True) [(1, 2, 1), (1, 2, 14), (1, 2, 15), (1, 2, 28), (2, 5, 1), (2, 5, 3), (2, 5, 20), (2, 5, 21), (3, 4, 3), (3, 4, 11), (3, 4, 12), (3, 4, 13)] sage: kruskal(G, check=True) [(1, 2, 1), (1, 6, 10), (2, 3, 16), (2, 5, 1), (2, 7, 14), (3, 4, 3)] sage: kruskal(G, check=True) == kruskal(H, check=True) True sage: G.weighted(True) sage: H.weighted(True) sage: kruskal(G, check=True) [(1, 2, 1), (2, 5, 1), (3, 4, 3), (1, 6, 10), (2, 7, 14), (2, 3, 16)] sage: kruskal(G, check=True) == kruskal(H, check=True) True
An example from pages 599–601 in [GoodrichTamassia2001].
sage: G = Graph({"SFO":{"BOS":2704, "ORD":1846, "DFW":1464, "LAX":337}, ... "BOS":{"ORD":867, "JFK":187, "MIA":1258}, ... "ORD":{"PVD":849, "JFK":740, "BWI":621, "DFW":802}, ... "DFW":{"JFK":1391, "MIA":1121, "LAX":1235}, ... "LAX":{"MIA":2342}, ... "PVD":{"JFK":144}, ... "JFK":{"MIA":1090, "BWI":184}, ... "BWI":{"MIA":946}}) sage: G.weighted(True) sage: kruskal(G, check=True) [('JFK', 'PVD', 144), ('BWI', 'JFK', 184), ('BOS', 'JFK', 187), ('LAX', 'SFO', 337), ('BWI', 'ORD', 621), ('DFW', 'ORD', 802), ('BWI', 'MIA', 946), ('DFW', 'LAX', 1235)]
An example from pages 568–569 in [CormenEtAl2001].
sage: G = Graph({"a":{"b":4, "h":8}, "b":{"c":8, "h":11}, ... "c":{"d":7, "f":4, "i":2}, "d":{"e":9, "f":14}, ... "e":{"f":10}, "f":{"g":2}, "g":{"h":1, "i":6}, "h":{"i":7}}) sage: G.weighted(True) sage: kruskal(G, check=True) [('g', 'h', 1), ('c', 'i', 2), ('f', 'g', 2), ('a', 'b', 4), ('c', 'f', 4), ('c', 'd', 7), ('a', 'h', 8), ('d', 'e', 9)]
TESTS:
The input graph must not be empty.
sage: from sage.graphs.spanning_tree import kruskal sage: kruskal(graphs.EmptyGraph(), check=True) [] sage: kruskal(Graph(), check=True) [] sage: kruskal(Graph(multiedges=True), check=True) [] sage: kruskal(Graph(loops=True), check=True) [] sage: kruskal(Graph(multiedges=True, loops=True), check=True) [] sage: kruskal(DiGraph(), check=True) [] sage: kruskal(DiGraph(multiedges=True), check=True) [] sage: kruskal(DiGraph(loops=True), check=True) [] sage: kruskal(DiGraph(multiedges=True, loops=True), check=True) []
The input graph must be connected.
sage: def my_disconnected_graph(n, ntries, directed=False, multiedges=False, loops=False): ... G = Graph() ... k = randint(1, n) ... G.add_vertices(range(k)) ... if directed: ... G = G.to_directed() ... if multiedges: ... G.allow_multiple_edges(True) ... if loops: ... G.allow_loops(True) ... for i in range(ntries): ... u = randint(0, k-1) ... v = randint(0, k-1) ... G.add_edge(u, v) ... while G.is_connected(): ... u = randint(0, k-1) ... v = randint(0, k-1) ... G.delete_edge(u, v) ... return G sage: G = my_disconnected_graph(100, 50, directed=False, multiedges=False, loops=False) # long time sage: kruskal(G, check=True) # long time [] sage: G = my_disconnected_graph(100, 50, directed=False, multiedges=True, loops=False) # long time sage: kruskal(G, check=True) # long time [] sage: G = my_disconnected_graph(100, 50, directed=False, multiedges=True, loops=True) # long time sage: kruskal(G, check=True) # long time [] sage: G = my_disconnected_graph(100, 50, directed=True, multiedges=False, loops=False) # long time sage: kruskal(G, check=True) # long time [] sage: G = my_disconnected_graph(100, 50, directed=True, multiedges=True, loops=False) # long time sage: kruskal(G, check=True) # long time [] sage: G = my_disconnected_graph(100, 50, directed=True, multiedges=True, loops=True) # long time sage: kruskal(G, check=True) # long time []
If the input graph is a tree, then return its edges.
sage: T = graphs.RandomTree(randint(1, 50)) # long time sage: T.edges() == kruskal(T, check=True) # long time True
-
sage.graphs.spanning_tree.
random_spanning_tree
(self, output_as_graph=False)¶ Return a random spanning tree of the graph.
This uses the Aldous-Broder algorithm ([Broder89], [Aldous90]) to generate a random spanning tree with the uniform distribution, as follows.
Start from any vertex. Perform a random walk by choosing at every step one neighbor uniformly at random. Every time a new vertex
is met, add the edge
to the spanning tree, where
is the previous vertex in the random walk.
INPUT:
output_as_graph
– boolean (default:False
) whether to return a list of edges or a graph.
See also
EXAMPLES:
sage: G = graphs.TietzeGraph() sage: G.random_spanning_tree(output_as_graph=True) Graph on 12 vertices sage: rg = G.random_spanning_tree(); rg # random [(0, 9), (9, 11), (0, 8), (8, 7), (7, 6), (7, 2), (2, 1), (1, 5), (9, 10), (5, 4), (2, 3)] sage: Graph(rg).is_tree() True
A visual example for the grid graph:
sage: G = graphs.Grid2dGraph(6, 6) sage: pos = G.get_pos() sage: T = G.random_spanning_tree(True) sage: T.set_pos(pos) sage: T.show(vertex_labels=False)
TESTS:
sage: G = Graph() sage: G.random_spanning_tree() Traceback (most recent call last): ... ValueError: works only for non-empty connected graphs sage: G = graphs.CompleteGraph(3).complement() sage: G.random_spanning_tree() Traceback (most recent call last): ... ValueError: works only for non-empty connected graphs