rs_graph/mst/
kruskal.rs

1// Copyright (c) 2016-2022 Frank Fischer <frank-fischer@shadow-soft.de>
2//
3// This program is free software: you can redistribute it and/or
4// modify it under the terms of the GNU General Public License as
5// published by the Free Software Foundation, either version 3 of the
6// License, or (at your option) any later version.
7//
8// This program is distributed in the hope that it will be useful, but
9// WITHOUT ANY WARRANTY; without even the implied warranty of
10// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
11// General Public License for more details.
12//
13// You should have received a copy of the GNU General Public License
14// along with this program.  If not, see  <http://www.gnu.org/licenses/>
15//
16
17//! Implementation of Kruskal's algorithm
18
19use crate::traits::IndexGraph;
20
21/// Run Kruskal's algorithm to solve the *Minimum Spanning Tree*
22/// problem on a graph.
23///
24/// * `g` is the undirected graph `weights` the edge weights
25///
26/// The algorithm actually solves a minimum spanning *forest* problem
27/// if the graph is not connected. This can easily be verified by
28/// checking the number of returned edges.
29///
30/// # Example
31///
32/// ```
33/// use rs_graph::{Net, traits::*};
34/// use rs_graph::mst::kruskal;
35/// use rs_graph::string::{Data, from_ascii};
36///
37/// let Data { graph, weights, nodes } = from_ascii::<Net>(r"
38///            ------9-----
39///           /            \
40///       ---a---9--   --2--b
41///      /   |\     \ /     |\
42///     4    5 \     c      4 6
43///    /     |  -7-  |\     |  \
44///   d---1--e-    \ 8 --2--f-3-g
45///    \     | \    \|     /|   |
46///     4    |  -9---h---9- |   |
47///      \   3      / \     9  /
48///       \  | -10--   -8-- | 9
49///        \ |/            \|/
50///         -i------18------j
51///     ").unwrap();
52/// let a = nodes[&'a'];
53/// let b = nodes[&'b'];
54/// let c = nodes[&'c'];
55/// let d = nodes[&'d'];
56/// let e = nodes[&'e'];
57/// let f = nodes[&'f'];
58/// let g = nodes[&'g'];
59/// let h = nodes[&'h'];
60/// let i = nodes[&'i'];
61/// let j = nodes[&'j'];
62///
63/// // run the algorithm
64/// let tree = kruskal(&graph, |e| weights[graph.edge_id(e)]);
65///
66/// // check the results
67/// let mut sum = 0;
68/// for &e in &tree { sum += weights[graph.edge_id(e)]; }
69/// assert_eq!(sum, 38);
70///
71/// let mut tree = tree.into_iter()
72///      .map(|e| graph.enodes(e))
73///      .map(|(u,v)| (graph.node_id(u), graph.node_id(v)))
74///      .map(|(u,v)| if u > v { (v,u) } else { (u,v) })
75///      .collect::<Vec<_>>();
76/// tree.sort();
77///
78/// assert_eq!(tree, vec![(a,d), (a,h), (b,c), (c,f), (c,h), (d,e), (e,i), (f,g), (h,j)]);
79/// ```
80pub fn kruskal<'a, 'b, G, W, F>(g: &'a G, weights: F) -> Vec<G::Edge<'a>>
81where
82    G: IndexGraph,
83    W: Ord,
84    F: Fn(G::Edge<'a>) -> W,
85{
86    let mut edges: Vec<_> = g.edges().collect();
87    edges.sort_by_key(|&e| weights(e));
88
89    // parent map for finding
90    let mut comps = vec![Component::Root(0); g.num_nodes()];
91    let mut tree = Vec::with_capacity(g.num_nodes() - 1);
92
93    for e in edges {
94        let (u, v) = g.enodes(e);
95        let u = g.node_id(u);
96        let v = g.node_id(v);
97        let (uroot, udepth) = find_root(&comps, u);
98        let (vroot, vdepth) = find_root(&comps, v);
99        if uroot != vroot {
100            tree.push(e);
101            if g.num_nodes() - 1 == tree.len() {
102                break;
103            }
104            if udepth < vdepth {
105                comps[uroot] = Component::Node(vroot);
106            } else {
107                comps[vroot] = Component::Node(uroot);
108                if udepth == vdepth {
109                    comps[uroot] = Component::Root(udepth + 1);
110                }
111            }
112        }
113    }
114
115    tree
116}
117
118/// Union-Find data-structure for Kruskal.
119#[derive(Clone, Copy)]
120enum Component {
121    /// The root element with the tree's depth.
122    Root(usize),
123    /// An inner node with the parent node.
124    Node(usize),
125}
126
127/// Return the root node and the tree's depth of node `u`.
128fn find_root(comps: &[Component], u: usize) -> (usize, usize) {
129    let mut v = u;
130    loop {
131        match comps[v] {
132            Component::Node(parent) => v = parent,
133            Component::Root(depth) => return (v, depth),
134        }
135    }
136}
rs_graph/mst/kruskal.rs

rs_graph/mst/
kruskal.rs
