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

// 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 shortestpath::binheap::BinHeap;
use shortestpath::dijkstra;
use {EdgeMap, IndexGraph};

use std::hash::Hash;

use num::traits::NumAssign;

/// Run Prim's algorithm to solve the *Minimum Spanning Tree*
/// problem on a graph.
///
/// * `g` is the undirected graph `weights` the edge weights
///
/// If the graph is not connected, the returned vector only spans one
/// component. This can easily be verifyed by checking the size of the
/// returned vector.
///
/// # Example
///
/// ```
/// use rs_graph::{Net, Builder, EdgeVec};
/// use rs_graph::mst::prim;
///
/// 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)].iter()
/// {
///     g.add_edge(nodes[u], nodes[v]);
///     weights.push(w);
/// }
/// let weights: EdgeVec<_> = weights.into();
///
/// // run the algorithm
/// let tree = prim(&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 prim<'a, G, Ws, W>(g: &'a G, weights: Ws) -> Vec<G::Edge>
where
    G: IndexGraph<'a>,
    G::Node: Hash,
    Ws: EdgeMap<'a, G, W>,
    W: NumAssign + Ord + Copy,
{
    if g.num_nodes() == 0 {
        return vec![];
    }

    dijkstra::generic::<_, _, _, _, _, _, BinHeap<_, usize>>(
        g,
        weights,
        g.id2node(0),
        None,
        |_, w| w,
        |g, u| g.neighs(u),
    ).into_iter()
        .map(|(_, e)| e)
        .collect()
}