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 [JNC2010] for descriptions of spanning tree algorithms, including minimum spanning trees.

See also

Todo

  • Rewrite kruskal() to use priority queues.

  • Parallel version of Boruvka’s algorithm.

  • Randomized spanning tree construction.

Methods

sage.graphs.spanning_tree.boruvka(G, wfunction=None, check=False, by_weight=True)

Minimum spanning tree using Boruvka’s algorithm.

This function assumes that we can only compute minimum spanning trees for undirected graphs. Such graphs can be weighted or unweighted, and they can have multiple edges (since we are computing the minimum spanning tree, only the minimum weight among all \((u,v)\)-edges is considered, for each pair of vertices \(u\), \(v\)).

INPUT:

  • G – an undirected graph.

  • wfunction – weight function (default: None); a function that inputs an edge e and outputs its weight. An edge has the form (u,v,l), where u and v are vertices, l is a label (that can be of any kind). The wfunction can be used to transform the label into a weight. In particular:

    • if wfunction is not None, the weight of an edge e is wfunction(e);

    • if wfunction is None (default) and g is weighted (that is, g.weighted()==True), the weight of an edge e=(u,v,l) is l, independently on which kind of object l is: the ordering of labels relies on Python’s operator <;

    • if wfunction is None and g is not weighted, we set all weights to 1 (hence, the output can be any spanning tree).

  • check – boolean (default: False); 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 Boruvka’s algorithm on that input graph:

    • Is G the null graph or graph on one vertex?

    • Is G disconnected?

    • Is G a tree?

    By default, we turn off the sanity checks for performance reasons. This means that by default the function assumes that its input graph is connected, and has at least one vertex. Otherwise, you should set check=True to perform some sanity checks and preprocessing on the input graph.

  • by_weight – boolean (default: False); whether to find MST by using weights of edges provided. Default: by_weight=True. If wfunction is given, MST is calculated using the weights of edges as per the function. If wfunction is None, the weight of an edge e=(u,v,l) is l if graph is weighted, or all edge weights are considered 1 if graph is unweighted. If we toggle by_weight=False, all weights are considered as 1 and MST is calculated.

OUTPUT:

The edges of a minimum spanning tree of G, if one exists, otherwise returns the empty list.

See also

EXAMPLES:

An example from pages 727–728 in [Sah2000]:

sage: from sage.graphs.spanning_tree import boruvka
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 = boruvka(G, check=True); E
[(1, 6, 10), (2, 7, 14), (3, 4, 12), (4, 5, 22), (5, 6, 25), (2, 3, 16)]
sage: boruvka(G, by_weight=True)
[(1, 6, 10), (2, 7, 14), (3, 4, 12), (4, 5, 22), (5, 6, 25), (2, 3, 16)]
sage: sorted(boruvka(G, by_weight=False))
[(1, 2, 28), (1, 6, 10), (2, 3, 16), (2, 7, 14), (3, 4, 12), (4, 5, 22)]

An example with custom edge labels:

sage: G = Graph([[0,1,1],[1,2,1],[2,0,10]], weighted=True)
sage: weight = lambda e:3-e[0]-e[1]
sage: boruvka(G, wfunction=lambda e:3-e[0]-e[1], by_weight=True)
[(0, 2, 10), (1, 2, 1)]
sage: boruvka(G, wfunction=lambda e:float(1/e[2]), by_weight=True)
[(0, 2, 10), (0, 1, 1)]

An example of disconnected graph with check disabled:

sage: from sage.graphs.spanning_tree import boruvka
sage: G = Graph({1:{2:28}, 3:{4:16}}, weighted=True)
sage: boruvka(G, check=False)
[]
sage.graphs.spanning_tree.filter_kruskal(G, threshold=10000, weight_function=None, check=False)

Minimum spanning tree using Filter Kruskal algorithm.

This function implements the variant of Kruskal’s algorithm proposed in [OSS2009]. Instead of directly sorting the whole set of edges, it partitions it in a similar way to quicksort and filter out edges that connect vertices of the same tree to reduce the cost of sorting.

This function assumes that we can only compute minimum spanning trees for undirected graphs. Such graphs can be weighted or unweighted, and they can have multiple edges (since we are computing the minimum spanning tree, only the minimum weight among all \((u,v)\)-edges is considered, for each pair of vertices \(u\), \(v\)).

INPUT:

  • G – an undirected graph

  • weight_function – function (default: None); a function that inputs an edge e and outputs its weight. An edge has the form (u,v,l), where u and v are vertices, l is a label (that can be of any kind). The weight_function can be used to transform the label into a weight. In particular:

    • if weight_function is not None, the weight of an edge e is weight_function(e);

    • if weight_function is None (default) and g is weighted (that is, g.weighted()==True), the weight of an edge e=(u,v,l) is l, independently on which kind of object l is: the ordering of labels relies on Python’s operator <;

    • if weight_function is None and g is not weighted, we set all weights to 1 (hence, the output can be any spanning tree).

  • threshold – integer (default: 10000); maximum number of edges on

    which to run kruskal algorithm. Above that value, edges are partitioned into sets of size at most threshold

  • check – boolean (default: False); 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:

    • Is G the null graph?

    • Is G disconnected?

    • Is G a tree?

    • Does G have self-loops?

    • Does G have multiple edges?

OUTPUT:

The edges of a minimum spanning tree of G, if one exists, otherwise returns the empty list.

See also

EXAMPLES:

sage: from sage.graphs.spanning_tree import filter_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: filter_kruskal(G, check=True)
[(1, 6, 10), (3, 4, 12), (2, 7, 14), (2, 3, 16), (4, 5, 22), (5, 6, 25)]

sage: filter_kruskal(Graph(2), check=True)
[]
sage.graphs.spanning_tree.filter_kruskal_iterator(G, threshold=10000, weight_function=None, check=False)

Return an iterator implementation of Filter Kruskal’s algorithm.

OUTPUT:

The edges of a minimum spanning tree of G, one by one.

See also

EXAMPLES:

The edges of a minimum spanning tree of G, if one exists, otherwise returns the empty list.

sage: from sage.graphs.spanning_tree import filter_kruskal_iterator
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: list(filter_kruskal_iterator(G, threshold=3, check=True))
[(1, 6, 10), (3, 4, 12), (2, 7, 14), (2, 3, 16), (4, 5, 22), (5, 6, 25)]

The weights of the spanning trees returned by kruskal_iterator() and filter_kruskal_iterator() are the same:

sage: from sage.graphs.spanning_tree import kruskal_iterator
sage: G = graphs.RandomBarabasiAlbert(50, 2)
sage: for u, v in G.edge_iterator(labels=False):
....:     G.set_edge_label(u, v, randint(1, 10))
sage: G.weighted(True)
sage: sum(e[2] for e in kruskal_iterator(G)) == sum(e[2] for e in filter_kruskal_iterator(G, threshold=20))
True
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 graphs. Such graphs can be weighted or unweighted, and they can have multiple edges (since we are computing the minimum spanning tree, only the minimum weight among all \((u,v)\)-edges is considered, for each pair of vertices \(u\), \(v\)).

INPUT:

  • G – an undirected graph.

  • weight_function – function (default: None); a function that inputs an edge e and outputs its weight. An edge has the form (u,v,l), where u and v are vertices, l is a label (that can be of any kind). The weight_function can be used to transform the label into a weight. In particular:

    • if weight_function is not None, the weight of an edge e is weight_function(e);

    • if weight_function is None (default) and g is weighted (that is, g.weighted()==True), the weight of an edge e=(u,v,l) is l, independently on which kind of object l is: the ordering of labels relies on Python’s operator <;

    • if weight_function is None and g is not weighted, we set all weights to 1 (hence, the output can be any spanning tree).

  • check – boolean (default: False); 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:

    • Is G the null graph?

    • Is G disconnected?

    • Is G a tree?

    • Does G have self-loops?

    • Does G have multiple edges?

    By default, we turn off the sanity checks for performance reasons. This means that by default the function assumes that its input graph is connected, and has at least one vertex. Otherwise, you should set check=True to perform some sanity checks and preprocessing on the input graph. If G has multiple edges or self-loops, the algorithm still works, but the running-time can be improved if these edges are removed. 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.

See also

EXAMPLES:

An example from pages 727–728 in [Sah2000].

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: 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)
....:     G.allow_multiple_edges(False, keep_label='min')
sage: sanitize(H)
sage: H
Graph on 7 vertices
sage: sum(e[2] for e in kruskal(G, check=True)) == sum(e[2] for e in kruskal(H, check=True))
True

An example from pages 599–601 in [GT2001].

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 [CLRS2001].

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: T = Graph(kruskal(G, check=True), format='list_of_edges')
sage: sum(T.edge_labels())
37
sage: T.is_tree()
True

An example with custom edge labels:

sage: G = Graph([[0,1,1],[1,2,1],[2,0,10]], weighted=True)
sage: weight = lambda e:3-e[0]-e[1]
sage: sorted(kruskal(G, check=True))
[(0, 1, 1), (1, 2, 1)]
sage: sorted(kruskal(G, wfunction=weight, check=True))
[(0, 2, 10), (1, 2, 1)]
sage: sorted(kruskal(G, wfunction=weight, check=False))
[(0, 2, 10), (1, 2, 1)]
sage.graphs.spanning_tree.kruskal_iterator(G, wfunction=None, check=False)

Return an iterator implementation of Kruskal algorithm.

OUTPUT:

The edges of a minimum spanning tree of G, one by one.

See also

kruskal()

EXAMPLES:

sage: from sage.graphs.spanning_tree import kruskal_iterator
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: next(kruskal_iterator(G, check=True))
(1, 6, 10)
sage.graphs.spanning_tree.kruskal_iterator_from_edges(edges, union_find, weighted=False, weight_function=None)

Return an iterator implementation of Kruskal algorithm on list of edges.

INPUT:

  • edges – list of edges

  • union_find – a DisjointSet_of_hashables encoding a forest

  • weighted – boolean (default: False); whether edges are weighted, i.e., the label of an edge is a weight

  • weight_function – function (default: None); a function that inputs an edge e and outputs its weight. See kruskal() for more details.

OUTPUT:

The edges of a minimum spanning tree of G, one by one.

See also

EXAMPLES:

sage: from sage.graphs.spanning_tree import kruskal_iterator_from_edges
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: union_set=DisjointSet(G.order())
sage: next(kruskal_iterator_from_edges(G.edges(sort=False), union_set, weighted=G.weighted()))
(1, 6, 10)
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 ([Bro1989], [Ald1990]) 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:

  • output_as_graph – boolean (default: False); whether to return a list of edges or a graph

See also

spanning_trees_count() and spanning_trees()

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)
sage.graphs.spanning_tree.spanning_trees(g, labels=False)

Return an iterator over all spanning trees of the graph \(g\).

A disconnected graph has no spanning tree.

Uses the Read-Tarjan backtracking algorithm [RT1975a].

INPUT:

  • labels – boolean (default: False); whether to return edges labels in the spanning trees or not

EXAMPLES:

sage: G = Graph([(1,2),(1,2),(1,3),(1,3),(2,3),(1,4)], multiedges=True)
sage: len(list(G.spanning_trees()))
8
sage: G.spanning_trees_count()
8
sage: G = Graph([(1,2),(2,3),(3,1),(3,4),(4,5),(4,5),(4,6)], multiedges=True)
sage: len(list(G.spanning_trees()))
6
sage: G.spanning_trees_count()
6

See also