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
Parallel version of Boruvka’s algorithm.
Methods#
- sage.graphs.spanning_tree.boruvka(G, by_weight=True, weight_function=None, check_weight=True, check=False)#
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.by_weight
– boolean (default:True
); ifTrue
, the edges in the graph are weighted; ifFalse
, all edges have weight 1.weight_function
– function (default:None
); a function that takes as input an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
, ifl
is notNone
, else1
as a weight.check_weight
– boolean (default:False
); whether to check that theweight_function
outputs a number for each edgecheck
– boolean (default:False
); 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 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.
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, weight_function=lambda e:3-e[0]-e[1], by_weight=True) [(0, 2, 10), (1, 2, 1)] sage: boruvka(G, weight_function=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.edge_disjoint_spanning_trees(G, k, by_weight=False, weight_function=None, check_weight=True)#
Return \(k\) edge-disjoint spanning trees of minimum cost.
This method implements the Roskind-Tarjan algorithm for finding \(k\) minimum-cost edge-disjoint spanning trees in simple undirected graphs [RT1985]. When edge weights are taken into account, the algorithm ensures that the sum of the weights of the returned spanning trees is minimized. The time complexity of the algorithm is in \(O(k^2n^2)\) for the unweighted case and otherwise in \(O(m\log{m} + k^2n^2)\).
This method raises an error if the graph does not contain the requested number of spanning trees.
INPUT:
G
– a simple undirected graphk
– the requested number of edge-disjoint spanning treesby_weight
– boolean (default:False
); ifTrue
, the edges in the graph are weighted, otherwise all edges have weight 1weight_function
– function (default:None
); a function that takes as input an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
, ifl
is notNone
, else1
as a weight.check_weight
– boolean (default:True
); ifTrue
, we check that theweight_function
outputs a number for each edge
EXAMPLES:
Example from [RT1985]:
sage: from sage.graphs.spanning_tree import edge_disjoint_spanning_trees sage: G = Graph({'a': ['b', 'c', 'd', 'e'], 'b': ['c', 'e'], 'c': ['d'], 'd': ['e']}) sage: F = edge_disjoint_spanning_trees(G, 2) sage: F [Graph on 5 vertices, Graph on 5 vertices] sage: [f.is_tree() for f in F] [True, True]
This method raises an error if the graph does not contain the required number of trees:
sage: edge_disjoint_spanning_trees(G, 3) Traceback (most recent call last): ... EmptySetError: this graph does not contain the required number of trees/arborescences
A clique of order \(n\) has \(\lfloor n/2 \rfloor\) edge disjoint spanning trees:
sage: for n in range(1, 10): ....: g = graphs.CompleteGraph(n) ....: F = edge_disjoint_spanning_trees(g, n//2)
The sum of the weights of the returned spanning trees is minimum:
sage: g = graphs.CompleteGraph(5) sage: for u, v in g.edges(sort=True, labels=False): ....: g.set_edge_label(u, v, 1) sage: g.set_edge_label(0, 1, 33) sage: g.set_edge_label(1, 3, 33) sage: F = edge_disjoint_spanning_trees(g, 2, by_weight=True) sage: sum(F[0].edge_labels()) + sum(F[1].edge_labels()) 8
- sage.graphs.spanning_tree.filter_kruskal(G, threshold=10000, by_weight=True, weight_function=None, check_weight=True, 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 graphthreshold
– integer (default: 10000); maximum number of edges onwhich to run kruskal algorithm. Above that value, edges are partitioned into sets of size at most
threshold
by_weight
– boolean (default:True
); ifTrue
, the edges in the graph are weighted; ifFalse
, all edges have weight 1.weight_function
– function (default:None
); a function that takes as input an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
, ifl
is notNone
, else1
as a weight.check_weight
– boolean (default:False
); whether to check that theweight_function
outputs a number for each edgecheck
– boolean (default:False
); 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?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, by_weight=True, weight_function=None, check_weight=True, check=False)#
Return an iterator implementation of Filter Kruskal’s algorithm.
INPUT:
G
– an undirected graphthreshold
– integer (default: 10000); maximum number of edges onwhich to run kruskal algorithm. Above that value, edges are partitioned into sets of size at most
threshold
by_weight
– boolean (default:True
); ifTrue
, the edges in the graph are weighted; ifFalse
, all edges have weight 1.weight_function
– function (default:None
); a function that takes as input an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
, ifl
is notNone
, else1
as a weight.check_weight
– boolean (default:False
); whether to check that theweight_function
outputs a number for each edgecheck
– boolean (default:False
); 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?Does
G
have self-loops?Does
G
have multiple edges?
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()
andfilter_kruskal_iterator()
are the same:sage: # needs networkx 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, by_weight=True, weight_function=None, check_weight=False, 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 graphby_weight
– boolean (default:True
); ifTrue
, the edges in the graph are weighted; ifFalse
, all edges have weight 1.weight_function
– function (default:None
); a function that takes as input an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
, ifl
is notNone
, else1
as a weight.check_weight
– boolean (default:False
); whether to check that theweight_function
outputs a number for each edgecheck
– boolean (default:False
); 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?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. IfG
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 viasage.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(sort=True, 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, weight_function=weight, check=True)) [(0, 2, 10), (1, 2, 1)] sage: sorted(kruskal(G, weight_function=weight, check=False)) [(0, 2, 10), (1, 2, 1)]
- sage.graphs.spanning_tree.kruskal_iterator(G, by_weight=True, weight_function=None, check_weight=False, check=False)#
Return an iterator implementation of Kruskal algorithm.
INPUT:
G
– an undirected graphby_weight
– boolean (default:True
); ifTrue
, the edges in the graph are weighted; ifFalse
, all edges have weight 1.weight_function
– function (default:None
); a function that takes as input an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
, ifl
is notNone
, else1
as a weight.check_weight
– boolean (default:False
); whether to check that theweight_function
outputs a number for each edgecheck
– boolean (default:False
); 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?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. IfG
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 viasage.graphs.generic_graph.GenericGraph.min_spanning_tree()
.
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 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, by_weight=True, weight_function=None, check_weight=False)#
Return an iterator implementation of Kruskal algorithm on list of edges.
INPUT:
edges
– list of edgesunion_find
– aDisjointSet_of_hashables
encoding a forestby_weight
- boolean (default:True
); ifTrue
, the edges in the graph are weighted; ifFalse
, all edges have weight 1.weight_function
– function (default:None
); a function that takes as input an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
, ifl
is notNone
, else1
as a weight.check_weight
– boolean (default:False
); whether to check that theweight_function
outputs a number for each edge
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) sage: next(kruskal_iterator_from_edges(G.edges(sort=False), union_set, by_weight=G.weighted())) (1, 6, 10)
Check that the method is robust to incomparable vertices:
sage: G = Graph([(1, 2, 10), (1, 'a', 1), ('a', 'b', 1), ('b', 2, 1)]) sage: union_set = DisjointSet(G) sage: E = list(kruskal_iterator_from_edges(G.edges(sort=False), union_set, by_weight=True)) sage: sum(w for _, _, w in E) 3
- sage.graphs.spanning_tree.random_spanning_tree(G, output_as_graph=False, by_weight=False, weight_function=None, check_weight=True)#
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.
When
by_weight
isTrue
or a weight function is given, the selection of the neighbor is done proportionaly to the edge weights.INPUT:
G
– an undirected graphoutput_as_graph
– boolean (default:False
); whether to return a list of edges or a graphby_weight
– boolean (default:False
); ifTrue
, the edges in the graph are weighted, otherwise all edges have weight 1weight_function
– function (default:None
); a function that takes as input an edge(u, v, l)
and outputs its weight. If notNone
,by_weight
is automatically set toTrue
. IfNone
andby_weight
isTrue
, we use the edge labell
, ifl
is notNone
, else1
as a weight. Theweight_function
can be used to transform the label into a weight (note that, if the weight returned is not convertible to a float, an error is raised)check_weight
– boolean (default:True
); whether to check that theweight_function
outputs a number for each edge.
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) # needs sage.plot
We can also use edge weights to change the probability of returning a spanning tree:
sage: def foo(G, k): ....: S = set() ....: for _ in range(k): ....: E = G.random_spanning_tree(by_weight=True) ....: S.add(Graph(E).graph6_string()) ....: return S sage: K3 = graphs.CompleteGraph(3) sage: for u, v in K3.edges(sort=True, labels=False): ....: K3.set_edge_label(u, v, randint(1, 2)) sage: foo(K3, 100) == {'BW', 'Bg', 'Bo'} # random True sage: K4 = graphs.CompleteGraph(4) sage: for u, v in K4.edges(sort=True, labels=False): ....: K4.set_edge_label(u, v, randint(1, 2)) sage: print(len(foo(K4, 100))) # random 16
Check that the spanning tree returned when using weights is a tree:
sage: # needs networkx 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: T = G.random_spanning_tree(by_weight=True, output_as_graph=True) sage: T.is_tree() True
- 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() # needs sage.modules 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() # needs sage.modules 6
See also
spanning_trees_count()
– counts the number of spanning treesrandom_spanning_tree()
– returns a random spanning tree