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
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. |
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:
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 graph G. Default: check=False. If we toggle check=True, the following sanity checks are first performed on G prior to running Kruskal’s algorithm on that input graph:
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 via sage.graphs.generic_graph.GenericGraph.min_spanning_tree().
OUTPUT:
The edges of a minimum spanning tree of G, if one exists, otherwise returns the empty list.
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 and H is an undirected version of G, then this function should return the same minimum spanning tree for both G and H.
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
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 \(j\) is met, add the edge \((i, j)\) to the spanning tree, where \(i\) is the previous vertex in the random walk.
INPUT:
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