petgraph/
operator.rs

1use super::graph::{Graph, IndexType};
2use super::EdgeType;
3use crate::visit::IntoNodeReferences;
4
5/// \[Generic\] complement of the graph
6///
7/// Computes the graph complement of the input Graphand stores it
8/// in the provided empty output Graph.
9///
10/// The function does not create self-loops.
11///
12/// Computes in **O(|V|^2*log(|V|))** time (average).
13///
14/// Returns the complement.
15///
16/// # Example
17/// ```rust
18/// use petgraph::Graph;
19/// use petgraph::operator::complement;
20/// use petgraph::prelude::*;
21///
22/// let mut graph: Graph<(),(),Directed> = Graph::new();
23/// let a = graph.add_node(()); // node with no weight
24/// let b = graph.add_node(());
25/// let c = graph.add_node(());
26/// let d = graph.add_node(());
27///
28/// graph.extend_with_edges(&[
29///     (a, b),
30///     (b, c),
31///     (c, d),
32/// ]);
33/// // a ----> b ----> c ----> d
34///
35/// graph.extend_with_edges(&[(a, b), (b, c), (c, d)]);
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
