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

// Copyright (c) 2016, 2017, 2018, 2020 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 Worst-Out-Greedy for the Minium-Spanning-Tree problem

use crate::traits::IndexGraph;
use crate::vec::{EdgeVec, NodeVec};

/// Run Worst-Out-Greedy algorithm to solve the *Minimum Spanning Tree*
/// problem on a graph.
///
/// * `g` is the undirected graph `weights` the edge weights
///
/// The algorithm actually solved a minimum spanning *forest* problem
/// in the graph. This can easily be verified by checking the size of
/// the returned vector.
///
/// # Example
///
/// ```
/// use rs_graph::{Net, traits::*, EdgeVec};
/// use rs_graph::mst::worstout;
/// 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 weights = EdgeVec::new_from_vec(&graph, weights);
/// let tree = worstout(&graph, |e| weights[e]);
///
/// // check the results
/// let mut sum = 0;
/// for &e in &tree { sum += weights[e]; }
/// assert_eq!(sum, 38);
///
/// let mut tree = tree.into_iter()
///      .map(|e| graph.enodes(e))
///      .map(|(u,v)| if graph.node_id(u) > graph.node_id(v) { (v,u) } else { (u,v) })
///      .collect::<Vec<_>>();
/// tree.sort_by_key(|&(u,v)| (graph.node_id(u), graph.node_id(v)));
///
/// assert_eq!(tree, vec![(a,d), (a,h), (b,c), (c,f), (c,h), (d,e), (e,i), (f,g), (h,j)]);
/// ```
pub fn worstout<'a, 'b, G, W, F>(g: &'a G, weights: F) -> Vec<G::Edge>
where
    G: IndexGraph<'a>,
    W: Copy + Ord,
    F: Fn(G::Edge) -> W,
{
    let mut used = EdgeVec::new(g, true);
    let mut edges: Vec<_> = g.edges().collect();
    edges.sort_by_key(|&e| weights(e));

    let mut stack = Vec::with_capacity(g.num_nodes());
    let mut seen = NodeVec::new(g, false);
    for e in edges.into_iter().rev() {
        let (u, v) = g.enodes(e);

        // dfs from u to v
        seen.reset(false);
        seen[u] = true;
        stack.clear();
        stack.push(u);

        // mark this edge as not used, so dfs ignores it
        used[e] = false;
        let mut found = false;
        while let Some(x) = stack.pop() {
            for (_, y) in g.neighs(x).filter(|&(f, _)| used[f]) {
                if !seen[y] {
                    if y == v {
                        found = true;
                        break;
                    }
                    seen[y] = true;
                    stack.push(y);
                }
            }
        }

        // if we have not found another path, keep e
        used[e] = !found;
    }

    g.edges().filter(|&e| used[e]).collect()
}