rs-graph 0.14.1

// 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 Worst-Out-Greedy for the Minium-Spanning-Tree problem

use {EdgeMap, IndexGraph};

/// 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, Builder, EdgeVec};
/// use rs_graph::mst::worstout;
///
/// 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 = worstout(&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 worstout<'a, 'b, G, Ws, W>(g: &'a G, weights: Ws) -> Vec<G::Edge>
where
    G: IndexGraph<'a>,
    Ws: EdgeMap<'a, G, W>,
    W: Copy + Ord,
{
    let mut used = idxedgevec![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 = idxnodevec![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()
}