rs_graph/mst/
worstout.rs

1// Copyright (c) 2016, 2017, 2018, 2020, 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 Worst-Out-Greedy for the Minium-Spanning-Tree problem
18
19use crate::traits::IndexGraph;
20
21/// Run Worst-Out-Greedy 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 solved a minimum spanning *forest* problem
27/// in the graph. This can easily be verified by checking the size of
28/// the returned vector.
29///
30/// # Example
31///
32/// ```
33/// use rs_graph::{Net, traits::*};
34/// use rs_graph::mst::worstout;
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 = worstout(&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 worstout<'a, 'b, G, W, F>(g: &'a G, weights: F) -> Vec<G::Edge<'a>>
81where
82    G: IndexGraph,
83    W: Copy + Ord,
84    F: Fn(G::Edge<'a>) -> W,
85{
86    let mut used = vec![true; g.num_edges()];
87    let mut edges: Vec<_> = g.edges().collect();
88    edges.sort_by_key(|&e| weights(e));
89
90    let mut stack = Vec::with_capacity(g.num_nodes());
91    let mut seen = vec![false; g.num_nodes()];
92    for e in edges.into_iter().rev() {
93        let (u, v) = g.enodes(e);
94
95        // dfs from u to v
96        seen.fill(false);
97        seen[g.node_id(u)] = true;
98        stack.clear();
99        stack.push(u);
100
101        // mark this edge as not used, so dfs ignores it
102        used[g.edge_id(e)] = false;
103        let mut found = false;
104        while let Some(x) = stack.pop() {
105            for (_, y) in g.neighs(x).filter(|&(f, _)| used[g.edge_id(f)]) {
106                if !seen[g.node_id(y)] {
107                    if y == v {
108                        found = true;
109                        break;
110                    }
111                    seen[g.node_id(y)] = true;
112                    stack.push(y);
113                }
114            }
115        }
116
117        // if we have not found another path, keep e
118        used[g.edge_id(e)] = !found;
119    }
120
121    g.edges().filter(|&e| used[g.edge_id(e)]).collect()
122}
rs_graph/mst/worstout.rs

rs_graph/mst/
worstout.rs
