rs-graph 0.14.1

A library for graph algorithms and combinatorial optimization
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

// Copyright (c) 2016, 2017, 2018 Frank Fischer <frank-fischer@shadow-soft.de>
//
// This program is free software: you can redistribute it and/or
// modify it under the terms of the GNU General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see  <http://www.gnu.org/licenses/>
//

//! Implementation of Kruskal's algorithm

use {EdgeMap, IndexGraph, IndexNodeVec};

/// Run Kruskal's algorithm to solve the *Minimum Spanning Tree*
/// problem on a graph.
///
/// * `g` is the undirected graph `weights` the edge weights
///
/// The algorithm actually solves a minimum spanning *forest* problem
/// if the graph is not connected. This can easily be verified by
/// checking the number of returned edges.
///
/// # Example
///
/// ```
/// use rs_graph::{Net, IndexGraph, EdgeVec, Builder};
/// use rs_graph::mst::kruskal;
///
/// let mut g = Net::new();
/// let mut weights: Vec<usize> = vec![];
///
/// let nodes = g.add_nodes(10);
/// for &(u,v,w) in &[(0,1,4), (0,2,1), (0,3,4),
///                   (1,2,5), (1,4,9), (1,5,9), (1,7,7),
///                   (2,3,3), (2,7,9),
///                   (3,7,10), (3,9,18),
///                   (4,5,2), (4,6,4), (4,8,6),
///                   (5,6,2), (5,7,8),
///                   (6,7,9), (6,8,3), (6,9,9),
///                   (7,9,8),
///                   (8,9,9)]
/// {
///     g.add_edge(nodes[u], nodes[v]);
///     weights.push(w);
/// }
///
/// // run the algorithm
/// let weights: EdgeVec<_> = weights.into();
/// let tree = kruskal(&g, &weights);
///
/// // check the results
/// assert_eq!(tree.len(), 9);
/// let mut sum = 0;
/// for e in tree { sum += weights[e]; }
/// assert_eq!(sum, 38);
/// ```
pub fn kruskal<'a, 'b, G, Ws, W>(g: &'a G, weights: Ws) -> Vec<G::Edge>
where
    G: IndexGraph<'a>,
    Ws: EdgeMap<'a, G, W>,
    W: Ord,
{
    let mut edges: Vec<_> = g.edges().collect();
    edges.sort_by_key(|&e| &weights[e]);

    // parent map for finding
    let mut comps = idxnodevec![g; Component::Root(0)];

    let mut tree = Vec::with_capacity(g.num_nodes() - 1);

    for e in edges {
        let (u, v) = g.enodes(e);
        let (uroot, udepth) = comps.find(u);
        let (vroot, vdepth) = comps.find(v);
        if uroot != vroot {
            tree.push(e);
            if g.num_nodes() - 1 == tree.len() {
                break;
            }
            if udepth < vdepth {
                comps[uroot] = Component::Node(vroot);
            } else {
                comps[vroot] = Component::Node(uroot);
                if udepth == vdepth {
                    comps[uroot] = Component::Root(udepth + 1);
                }
            }
        }
    }

    tree
}

/// Union-Find data-structure for Kruskal.
#[derive(Clone, Copy)]
enum Component<N: Copy> {
    /// The root element with the tree's depth.
    Root(usize),
    /// An inner node with the parent node.
    Node(N),
}

impl<'a, G> IndexNodeVec<'a, G, Component<G::Node>>
where
    G: IndexGraph<'a>,
{
    /// Return the root node and the tree's depth of node `u`.
    fn find(&mut self, u: G::Node) -> (G::Node, usize) {
        let mut v = u;
        loop {
            match self[v] {
                Component::Node(parent) => v = parent,
                Component::Root(depth) => return (v, depth),
            }
        }
    }
}