rs_graph/mst/
prim.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
21use std::collections::HashMap;
22use std::hash::Hash;
23
24use crate::adjacencies::Neighbors;
25use crate::collections::BinHeap;
26use crate::num::traits::NumAssign;
27use crate::search::astar::Accumulator;
28use crate::shortestpath::dijkstra;
29
30/// Run Prim's algorithm to solve the *Minimum Spanning Tree*
31/// problem on a graph.
32///
33/// * `g` is the undirected graph `weights` the edge weights
34///
35/// If the graph is not connected, the returned vector only spans one
36/// component. This can easily be verifyed by checking the size of the
37/// returned vector.
38///
39/// # Example
40///
41/// ```
42/// use rs_graph::{Net, traits::*};
43/// use rs_graph::mst::prim;
44/// use rs_graph::string::{Data, from_ascii};
45///
46/// let Data { graph, weights, nodes } = from_ascii::<Net>(r"
47///            ------9-----
48///           /            \
49///       ---a---9--   --2--b
50///      /   |\     \ /     |\
51///     4    5 \     c      4 6
52///    /     |  -7-  |\     |  \
53///   d---1--e-    \ 8 --2--f-3-g
54///    \     | \    \|     /|   |
55///     4    |  -9---h---9- |   |
56///      \   3      / \     9  /
57///       \  | -10--   -8-- | 9
58///        \ |/            \|/
59///         -i------18------j
60///     ").unwrap();
61/// let a = nodes[&'a'];
62/// let b = nodes[&'b'];
63/// let c = nodes[&'c'];
64/// let d = nodes[&'d'];
65/// let e = nodes[&'e'];
66/// let f = nodes[&'f'];
67/// let g = nodes[&'g'];
68/// let h = nodes[&'h'];
69/// let i = nodes[&'i'];
70/// let j = nodes[&'j'];
71///
72/// // run the algorithm
73/// let tree = prim(&graph, |e| weights[graph.edge_id(e)]);
74///
75/// // check the results
76/// let mut sum = 0;
77/// for &e in &tree { sum += weights[graph.edge_id(e)]; }
78/// assert_eq!(sum, 38);
79///
80/// let mut tree = tree.into_iter()
81///      .map(|e| graph.enodes(e))
82///      .map(|(u,v)| (graph.node_id(u), graph.node_id(v)))
83///      .map(|(u,v)| if u > v { (v,u) } else { (u,v) })
84///      .collect::<Vec<_>>();
85/// tree.sort();
86///
87/// assert_eq!(tree, vec![(a,d), (a,h), (b,c), (c,f), (c,h), (d,e), (e,i), (f,g), (h,j)]);
88/// ```
89pub fn prim<'a, G, W, F>(g: &'a G, weights: F) -> Vec<G::Edge<'a>>
90where
91    G: IndexGraph,
92    G::Node<'a>: Hash,
93    W: NumAssign + Ord + Copy + 'a,
94    F: Fn(G::Edge<'a>) -> W,
95{
96    if g.num_nodes() == 0 {
97        return vec![];
98    }
99
100    struct WeightAccumulator;
101    impl<T> Accumulator<T> for WeightAccumulator {
102        fn accum(_dist: T, weight: T) -> T {
103            weight
104        }
105    }
106
107    let mut tree = Vec::with_capacity(g.num_nodes() - 1);
108    for (_, e, _) in dijkstra::start_generic::<_, _, _, _, _, WeightAccumulator>(
109        Neighbors(g),
110        g.id2node(0),
111        weights,
112        (HashMap::new(), BinHeap::<_, _, usize>::default()),
113    ) {
114        tree.push(e);
115    }
116    tree
117}
rs_graph/mst/prim.rs

rs_graph/mst/
prim.rs
