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
use super::graph::{Graph, IndexType};
use super::EdgeType;
use crate::visit::IntoNodeReferences;
/// \[Generic\] complement of the graph
///
/// Computes the graph complement of the input Graphand stores it
/// in the provided empty output Graph.
///
/// The function does not create self-loops.
///
/// Computes in **O(|V|^2*log(|V|))** time (average).
///
/// Returns the complement.
///
/// # Example
/// ```rust
/// use petgraph::Graph;
/// use petgraph::operator::complement;
/// use petgraph::prelude::*;
///
/// let mut graph: Graph<(),(),Directed> = Graph::new();
/// let a = graph.add_node(()); // node with no weight
/// let b = graph.add_node(());
/// let c = graph.add_node(());
/// let d = graph.add_node(());
///
/// graph.extend_with_edges(&[
/// (a, b),
/// (b, c),
/// (c, d),
/// ]);
/// // a ----> b ----> c ----> d
///
/// graph.extend_with_edges(&[(a, b), (b, c), (c, d)]);
/// let mut output: Graph<(), (), Directed> = Graph::new();
///
/// complement(&graph, &mut output, ());
///
/// let mut expected_res: Graph<(), (), Directed> = Graph::new();
/// let a = expected_res.add_node(());
/// let b = expected_res.add_node(());
/// let c = expected_res.add_node(());
/// let d = expected_res.add_node(());
/// expected_res.extend_with_edges(&[
/// (a, c),
/// (a, d),
/// (b, a),
/// (b, d),
/// (c, a),
/// (c, b),
/// (d, a),
/// (d, b),
/// (d, c),
/// ]);
///
/// for x in graph.node_indices() {
/// for y in graph.node_indices() {
/// assert_eq!(output.contains_edge(x, y), expected_res.contains_edge(x, y));
/// }
/// }
/// ```
pub fn complement<N, E, Ty, Ix>(
input: &Graph<N, E, Ty, Ix>,
output: &mut Graph<N, E, Ty, Ix>,
weight: E,
) where
Ty: EdgeType,
Ix: IndexType,
E: Clone,
N: Clone,
{
for (_node, weight) in input.node_references() {
output.add_node(weight.clone());
}
for x in input.node_indices() {
for y in input.node_indices() {
if x != y && !input.contains_edge(x, y) {
output.add_edge(x, y, weight.clone());
}
}
}
}