rustworkx_core/
line_graph.rs

Help
1// Licensed under the Apache License, Version 2.0 (the "License"); you may
2// not use this file except in compliance with the License. You may obtain
3// a copy of the License at
4//
5//     http://www.apache.org/licenses/LICENSE-2.0
6//
7// Unless required by applicable law or agreed to in writing, software
8// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
9// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
10// License for the specific language governing permissions and limitations
11// under the License.
12
13use std::hash::Hash;
14
15use hashbrown::HashMap;
16use petgraph::data::Create;
17use petgraph::visit::{Data, EdgeCount, EdgeRef, IntoEdges, IntoNodeIdentifiers};
18
19/// Constructs the line graph of an undirected graph.
20///
21/// The line graph `L(G)` of a graph `G` represents the adjacencies between edges of G.
22/// `L(G)` contains a vertex for every edge in `G`, and `L(G)` contains an edge between two
23/// vertices if the corresponding edges in `G` have a vertex in common.
24///
25/// Arguments:
26///
27/// * `input_graph` - The input graph `G`.
28/// * `default_node_weight` - A callable that will return the weight to use
29///     for newly created nodes.
30/// * `default_edge_weight` - A callable that will return the weight object
31///     to use for newly created edges.
32///
33/// Returns the constructed line graph `L(G)`, and the map from the edges of `L(G)` to
34/// the vertices of `G`.
35///
36/// # Example
37/// ```rust
38/// use rustworkx_core::line_graph::line_graph;
39/// use rustworkx_core::petgraph::visit::EdgeRef;
40/// use rustworkx_core::petgraph::Graph;
41/// use hashbrown::HashMap;
42/// use petgraph::graph::{EdgeIndex, NodeIndex};
43/// use petgraph::Undirected;
44///
45/// let input_graph =
46///   Graph::<(), (), Undirected>::from_edges(&[(0, 1), (0, 2), (1, 2), (0, 3)]);
47///
48/// let (output_graph, output_edge_map): (
49///     petgraph::graph::UnGraph<(), ()>,
50///     HashMap<petgraph::prelude::EdgeIndex, petgraph::prelude::NodeIndex>,
51/// ) = line_graph(&input_graph, || (), || ());
52///
53/// let output_edge_list = output_graph
54///     .edge_references()
55///     .map(|edge| (edge.source().index(), edge.target().index()))
56///     .collect::<Vec<(usize, usize)>>();
57///
58/// let expected_edge_list = vec![(3, 1), (3, 0), (1, 0), (2, 0), (2, 1)];
59/// let expected_edge_map: HashMap<EdgeIndex, NodeIndex> = [
60///     (EdgeIndex::new(0), NodeIndex::new(0)),
61///     (EdgeIndex::new(1), NodeIndex::new(1)),
62///     (EdgeIndex::new(2), NodeIndex::new(2)),
63///     (EdgeIndex::new(3), NodeIndex::new(3)),
64/// ]
65/// .into_iter()
66/// .collect();
67///
68/// assert_eq!(output_edge_list, expected_edge_list);
69/// assert_eq!(output_edge_map, expected_edge_map);
70/// ```
71pub fn line_graph<K, G, T, F, H, M>(
72    input_graph: K,
73    mut default_node_weight: F,
74    mut default_edge_weight: H,
75) -> (G, HashMap<K::EdgeId, G::NodeId>)
76where
77    K: EdgeCount + IntoNodeIdentifiers + IntoEdges,
78    G: Create + Data<NodeWeight = T, EdgeWeight = M>,
79    F: FnMut() -> T,
80    H: FnMut() -> M,
81    K::EdgeId: Hash + Eq,
82{
83    let num_edges = input_graph.edge_count();
84    let mut output_graph = G::with_capacity(num_edges, 0);
85    let mut output_edge_map =
86        HashMap::<K::EdgeId, G::NodeId>::with_capacity(input_graph.edge_count());
87
88    for edge in input_graph.edge_references() {
89        let new_node = output_graph.add_node(default_node_weight());
90        output_edge_map.insert(edge.id(), new_node);
91    }
92
93    for node in input_graph.node_identifiers() {
94        let edges: Vec<K::EdgeRef> = input_graph.edges(node).collect();
95        for i in 0..edges.len() {
96            for j in i + 1..edges.len() {
97                let node0 = output_edge_map.get(&edges[i].id()).unwrap();
98                let node1 = output_edge_map.get(&edges[j].id()).unwrap();
99                output_graph.add_edge(*node0, *node1, default_edge_weight());
100            }
101        }
102    }
103    (output_graph, output_edge_map)
104}
105
106#[cfg(test)]
107
108mod test_line_graph {
109    use crate::line_graph::line_graph;
110    use crate::petgraph::visit::EdgeRef;
111    use crate::petgraph::Graph;
112    use hashbrown::HashMap;
113    use petgraph::graph::{EdgeIndex, NodeIndex};
114    use petgraph::Undirected;
115
116    #[test]
117    fn test_simple_graph() {
118        // Simple graph
119        let input_graph = Graph::<(), (), Undirected>::from_edges([(0, 1), (2, 3), (3, 4), (4, 5)]);
120
121        let (output_graph, output_edge_map): (
122            petgraph::graph::UnGraph<(), ()>,
123            HashMap<petgraph::prelude::EdgeIndex, petgraph::prelude::NodeIndex>,
124        ) = line_graph(&input_graph, || (), || ());
125
126        let output_edge_list = output_graph
127            .edge_references()
128            .map(|edge| (edge.source().index(), edge.target().index()))
129            .collect::<Vec<(usize, usize)>>();
130
131        let expected_edge_list = vec![(2, 1), (3, 2)];
132        let expected_edge_map: HashMap<EdgeIndex, NodeIndex> = [
133            (EdgeIndex::new(0), NodeIndex::new(0)),
134            (EdgeIndex::new(1), NodeIndex::new(1)),
135            (EdgeIndex::new(2), NodeIndex::new(2)),
136            (EdgeIndex::new(3), NodeIndex::new(3)),
137        ]
138        .into_iter()
139        .collect();
140
141        assert_eq!(output_edge_list, expected_edge_list);
142        assert_eq!(output_edge_map, expected_edge_map);
143    }
144}
rustworkx_core/line_graph.rs

rustworkx_core/
line_graph.rs
