r"""
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.
**Todo**
* Rewrite :func:`kruskal` to use priority queues. Once Cython has support
for generators and the ``yield`` statement, rewrite :func:`kruskal` to use
``yield``.
* Prim's algorithm.
* Boruvka's algorithm.
* Parallel version of Boruvka's algorithm.
* Randomized spanning tree construction.
REFERENCES:
.. [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
-------
"""
include "../ext/cdefs.pxi"
include "../ext/interrupt.pxi"
include "../ext/stdsage.pxi"
cpdef kruskal(G, wfunction=None, bint check=False):
r"""
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 of ``G``
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 of ``G``, but have ``None`` 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 convert
``G`` to be undirected. Suppose there are multiple edges from `u` to
`v`. Among all such multiple edges, we choose one with minimum weight.
- ``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:
- 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
via :meth:`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.
- If ``G`` is a tree, return the edges of ``G`` regardless of whether
``G`` is weighted or unweighted, directed or undirected.
- If ``G`` is unweighted, default to using unit weight for each edge of
``G``. The default behaviour is to use the already assigned weights of
``G`` provided that ``G`` is weighted.
- If ``G`` is weighted and a weight function is also supplied, then use
the already assigned weights of ``G``, not the weight function. If you
really want to use a weight function for ``G`` even if ``G`` is
weighted, first convert ``G`` to be unweighted and pass in the weight
function.
.. seealso::
- :meth:`sage.graphs.generic_graph.GenericGraph.min_spanning_tree`
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
"""
g = G
sortedE_iter = None
if check:
if G.order() == 0:
return []
if not G.is_connected():
return []
if G.num_verts() == G.num_edges() + 1:
return G.edges()
g = G.to_undirected()
g.allow_loops(False)
if g.weighted():
if g.allows_multiple_edges():
uniqE = set()
for u, v, _ in iter(g.multiple_edges(to_undirected=True)):
uniqE.add((u, v))
for u, v in uniqE:
W = sorted(g.edge_label(u, v))
for w in W[1:]:
g.delete_edge(u, v, w)
assert g.multiple_edges() == []
g.allow_multiple_edges(False)
from operator import itemgetter
sortedE_iter = iter(sorted(g.edges(), key=itemgetter(2)))
else:
g = g.to_simple()
if wfunction is None:
sortedE_iter = iter(sorted(g.edges()))
else:
sortedE_iter = iter(sorted(g.edges(), key=wfunction))
else:
if wfunction is None:
sortedE_iter = iter(sorted(g.edges()))
else:
sortedE_iter = iter(sorted(g.edges(), key=wfunction))
T = []
cdef int n = g.order()
cdef int m = n - 1
cdef int i = 0
union_find = dict()
while i < m:
e = sortedE_iter.next()
components = []
for startv in iter(e[0:2]):
v = startv
children = []
while v in union_find:
children.append(v)
v = union_find[v]
for c in children:
union_find[c] = v
components.append(v)
if components[0] != components[1]:
i += 1
T.append(e)
union_find[components[0]] = components[1]
return T
