graphalgs 0.2.0

Graph algorithms based on the Rust 'petgraph' library.
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
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

use std::collections::HashSet;
use std::hash::Hash;

use crate::traits::EdgeCount;
use petgraph::visit::{EdgeRef, IntoEdgeReferences, IntoNodeIdentifiers, NodeCount, NodeIndexable};

/// Graph`s complement.
///
/// Returns the complement of the input directed graph as a set of edges in the format `(usize, usize)`,
/// where each number is the index of the corresponding vertex.
///
/// # Examples
///
/// ```
/// use petgraph::Graph;
/// use graphalgs::generate::complement;
/// use std::collections::HashSet;
///
/// // Create the following graph:
/// //  0 -- 1
/// //  |    |
/// //  3 -- 2
///
/// let graph = Graph::<(), ()>::from_edges(&[
///     (0, 1, ()), (1, 2, ()), (2, 3, ()), (3, 0, ()),
///     (1, 0, ()), (2, 1, ()), (3, 2, ()), (0, 3, ()),
/// ]);
///
/// // It's complement consists of two pairs of vertices:
/// // 0 -- 2
/// // 1 -- 3
///
/// let mut compl = HashSet::<(usize, usize)>::new();
/// compl.insert((0, 2)); compl.insert((2, 0));
/// compl.insert((1, 3)); compl.insert((3, 1));
///
/// assert_eq!(complement(&graph), compl);
/// ```
pub fn complement<G>(graph: G) -> HashSet<(usize, usize)>
where
    G: IntoEdgeReferences + NodeCount + EdgeCount + IntoNodeIdentifiers + NodeIndexable,
    G::NodeId: Eq + Hash,
{
    let mut edges: HashSet<(G::NodeId, G::NodeId)> =
        HashSet::with_capacity(graph.number_of_edges());

    for edge in graph.edge_references() {
        edges.insert((edge.source(), edge.target()));
    }

    let n = graph.node_count();
    let edge_count = n * (n - 1) - graph.number_of_edges();
    let mut compl: HashSet<(usize, usize)> = HashSet::with_capacity(edge_count);

    for i in graph.node_identifiers() {
        for j in graph.node_identifiers() {
            if i != j && !edges.contains(&(i, j)) {
                compl.insert((graph.to_index(i), graph.to_index(j)));
            }
        }
    }

    compl
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::generate::random_digraph;
    use petgraph::algo::is_isomorphic;
    use petgraph::graph::Graph;
    use petgraph::Directed;

    fn graph1() -> Graph<(), ()> {
        let mut graph = Graph::<(), ()>::new();
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        let n2 = graph.add_node(());
        let n3 = graph.add_node(());

        graph.add_edge(n0, n1, ());
        graph.add_edge(n1, n0, ());
        graph.add_edge(n1, n2, ());
        graph.add_edge(n2, n1, ());
        graph.add_edge(n1, n3, ());
        graph.add_edge(n3, n1, ());

        graph
    }

    #[test]
    fn test_complement() {
        let expected = vec![(0, 2), (2, 0), (0, 3), (3, 0), (2, 3), (3, 2)]
            .into_iter()
            .collect::<HashSet<(usize, usize)>>();

        assert_eq!(complement(&graph1()), expected);

        for _ in 0..10 {
            let graph =
                Graph::<(), (), Directed, usize>::from_edges(random_digraph(20, 150).unwrap());
            let compl = Graph::<(), (), Directed, usize>::from_edges(complement(&graph));
            let compl_compl = Graph::<(), (), Directed, usize>::from_edges(complement(&compl));
            assert!(is_isomorphic(&graph, &compl_compl));
        }
    }
}