1 //! Operators for creating new graphs from existings ones.
2 use super::graph::{Graph, IndexType};
3 use super::EdgeType;
4 use 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 /// ```
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,63 pub 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 }
84