petgraph/
operator.rs

1//! Operators for creating new graphs from existings ones.
2use super::graph::{Graph, IndexType};
3use super::EdgeType;
4use crate::visit::IntoNodeReferences;
5
6/// \[Generic\] complement of the graph
7///
8/// Computes the graph complement of the input Graph and stores it
9/// in the provided empty output Graph.
10///
11/// The function does not create self-loops.
12///
13/// Computes in **O(|V|^2*log(|V|))** time (average).
14///
15/// Returns the complement.
16///
17/// # Example
18/// ```rust
19/// use petgraph::Graph;
20/// use petgraph::operator::complement;
21/// use petgraph::prelude::*;
22///
23/// let mut graph: Graph<(),(),Directed> = Graph::new();
24/// let a = graph.add_node(()); // node with no weight
25/// let b = graph.add_node(());
26/// let c = graph.add_node(());
27/// let d = graph.add_node(());
28///
29/// graph.extend_with_edges(&[
30///     (a, b),
31///     (b, c),
32///     (c, d),
33/// ]);
34/// // a ----> b ----> c ----> d
35///
36/// let mut output: Graph<(), (), Directed> = Graph::new();
37///
38/// complement(&graph, &mut output, ());
39///
40/// let mut expected_res: Graph<(), (), Directed> = Graph::new();
41/// let a = expected_res.add_node(());
42/// let b = expected_res.add_node(());
43/// let c = expected_res.add_node(());
44/// let d = expected_res.add_node(());
45/// expected_res.extend_with_edges(&[
46///     (a, c),
47///     (a, d),
48///     (b, a),
49///     (b, d),
50///     (c, a),
51///     (c, b),
52///     (d, a),
53///     (d, b),
54///     (d, c),
55/// ]);
56///
57/// for x in graph.node_indices() {
58///     for y in graph.node_indices() {
59///         assert_eq!(output.contains_edge(x, y), expected_res.contains_edge(x, y));
60///     }
61/// }
62/// ```
63pub fn complement<N, E, Ty, Ix>(
64    input: &Graph<N, E, Ty, Ix>,
65    output: &mut Graph<N, E, Ty, Ix>,
66    weight: E,
67) where
68    Ty: EdgeType,
69    Ix: IndexType,
70    E: Clone,
71    N: Clone,
72{
73    for (_node, weight) in input.node_references() {
74        output.add_node(weight.clone());
75    }
76    for x in input.node_indices() {
77        for y in input.node_indices() {
78            if x != y && !input.contains_edge(x, y) {
79                output.add_edge(x, y, weight.clone());
80            }
81        }
82    }
83}
petgraph/operator.rs

petgraph/
operator.rs
