rs-graph 0.21.0

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

// Copyright (c) 2016-2022 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 crate::traits::IndexGraph;

use std::collections::HashMap;
use std::hash::Hash;

use crate::adjacencies::Neighbors;
use crate::collections::BinHeap;
use crate::num::traits::NumAssign;
use crate::search::astar::Accumulator;
use crate::shortestpath::dijkstra;

/// 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, traits::*};
/// use rs_graph::mst::prim;
/// use rs_graph::string::{Data, from_ascii};
///
/// let Data { graph, weights, nodes } = from_ascii::<Net>(r"
///            ------9-----
///           /            \
///       ---a---9--   --2--b
///      /   |\     \ /     |\
///     4    5 \     c      4 6
///    /     |  -7-  |\     |  \
///   d---1--e-    \ 8 --2--f-3-g
///    \     | \    \|     /|   |
///     4    |  -9---h---9- |   |
///      \   3      / \     9  /
///       \  | -10--   -8-- | 9
///        \ |/            \|/
///         -i------18------j
///     ").unwrap();
/// let a = nodes[&'a'];
/// let b = nodes[&'b'];
/// let c = nodes[&'c'];
/// let d = nodes[&'d'];
/// let e = nodes[&'e'];
/// let f = nodes[&'f'];
/// let g = nodes[&'g'];
/// let h = nodes[&'h'];
/// let i = nodes[&'i'];
/// let j = nodes[&'j'];
///
/// // run the algorithm
/// let tree = prim(&graph, |e| weights[graph.edge_id(e)]);
///
/// // check the results
/// let mut sum = 0;
/// for &e in &tree { sum += weights[graph.edge_id(e)]; }
/// assert_eq!(sum, 38);
///
/// let mut tree = tree.into_iter()
///      .map(|e| graph.enodes(e))
///      .map(|(u,v)| (graph.node_id(u), graph.node_id(v)))
///      .map(|(u,v)| if u > v { (v,u) } else { (u,v) })
///      .collect::<Vec<_>>();
/// tree.sort();
///
/// assert_eq!(tree, vec![(a,d), (a,h), (b,c), (c,f), (c,h), (d,e), (e,i), (f,g), (h,j)]);
/// ```
pub fn prim<'a, G, W, F>(g: &'a G, weights: F) -> Vec<G::Edge<'a>>
where
    G: IndexGraph,
    G::Node<'a>: Hash,
    W: NumAssign + Ord + Copy + 'a,
    F: Fn(G::Edge<'a>) -> W,
{
    if g.num_nodes() == 0 {
        return vec![];
    }

    struct WeightAccumulator;
    impl<T> Accumulator<T> for WeightAccumulator {
        fn accum(_dist: T, weight: T) -> T {
            weight
        }
    }

    let mut tree = Vec::with_capacity(g.num_nodes() - 1);
    for (_, e, _) in dijkstra::start_generic::<_, _, _, _, _, WeightAccumulator>(
        Neighbors(g),
        g.id2node(0),
        weights,
        (HashMap::new(), BinHeap::<_, _, usize>::default()),
    ) {
        tree.push(e);
    }
    tree
}