fera-graph 0.2.0

Graph data structures and algorithms.
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

// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at http://mozilla.org/MPL/2.0/.

#[cfg(feature = "quickcheck")]
#[macro_use]
extern crate quickcheck;
extern crate fera_fun;
extern crate fera_graph;

#[cfg(feature = "quickcheck")]
mod quickchecks {
    use fera_fun::vec;
    use fera_graph::algs::{Kruskal, Prim, Trees};
    use fera_graph::arbitrary::GnConnectedWithEdgeProp;
    use fera_graph::prelude::*;
    use fera_graph::sum_prop;

    quickcheck! {
        fn mst(x: GnConnectedWithEdgeProp<StaticGraph, u32>) -> bool {
            let GnConnectedWithEdgeProp(g, w) = x;
            if g.num_vertices() == 0 || g.num_edges() == 0 {
                return true;
            }
            let prim = vec(g.prim(&w));
            let w_prim: u32 = sum_prop(&w, &prim);
            let kruskal = vec(g.kruskal_mst(&w));
            let w_kruskal: u32 = sum_prop(&w, &kruskal);
            assert!(g.spanning_subgraph(&prim).is_tree());
            assert!(g.spanning_subgraph(&kruskal).is_tree());
            assert_eq!(w_prim, w_kruskal);
            true
        }
    }
}