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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144

// Licensed under the Apache License, Version 2.0 (the "License"); you may
// not use this file except in compliance with the License. You may obtain
// a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations
// under the License.

use std::hash::Hash;

use hashbrown::HashMap;
use petgraph::data::Create;
use petgraph::visit::{Data, EdgeCount, EdgeRef, IntoEdges, IntoNodeIdentifiers};

/// Constructs the line graph of an undirected graph.
///
/// The line graph `L(G)` of a graph `G` represents the adjacencies between edges of G.
/// `L(G)` contains a vertex for every edge in `G`, and `L(G)` contains an edge between two
/// vertices if the corresponding edges in `G` have a vertex in common.
///
/// Arguments:
///
/// * `input_graph` - The input graph `G`.
/// * `default_node_weight` - A callable that will return the weight to use
///     for newly created nodes.
/// * `default_edge_weight` - A callable that will return the weight object
///     to use for newly created edges.
///
/// Returns the constructed line graph `L(G)`, and the map from the edges of `L(G)` to
/// the vertices of `G`.
///
/// # Example
/// ```rust
/// use rustworkx_core::line_graph::line_graph;
/// use rustworkx_core::petgraph::visit::EdgeRef;
/// use rustworkx_core::petgraph::Graph;
/// use hashbrown::HashMap;
/// use petgraph::graph::{EdgeIndex, NodeIndex};
/// use petgraph::Undirected;
///
/// let input_graph =
///   Graph::<(), (), Undirected>::from_edges(&[(0, 1), (0, 2), (1, 2), (0, 3)]);
///
/// let (output_graph, output_edge_map): (
///     petgraph::graph::UnGraph<(), ()>,
///     HashMap<petgraph::prelude::EdgeIndex, petgraph::prelude::NodeIndex>,
/// ) = line_graph(&input_graph, || (), || ());
///
/// let output_edge_list = output_graph
///     .edge_references()
///     .map(|edge| (edge.source().index(), edge.target().index()))
///     .collect::<Vec<(usize, usize)>>();
///
/// let expected_edge_list = vec![(3, 1), (3, 0), (1, 0), (2, 0), (2, 1)];
/// let expected_edge_map: HashMap<EdgeIndex, NodeIndex> = [
///     (EdgeIndex::new(0), NodeIndex::new(0)),
///     (EdgeIndex::new(1), NodeIndex::new(1)),
///     (EdgeIndex::new(2), NodeIndex::new(2)),
///     (EdgeIndex::new(3), NodeIndex::new(3)),
/// ]
/// .into_iter()
/// .collect();
///
/// assert_eq!(output_edge_list, expected_edge_list);
/// assert_eq!(output_edge_map, expected_edge_map);
/// ```
pub fn line_graph<K, G, T, F, H, M>(
    input_graph: K,
    mut default_node_weight: F,
    mut default_edge_weight: H,
) -> (G, HashMap<K::EdgeId, G::NodeId>)
where
    K: EdgeCount + IntoNodeIdentifiers + IntoEdges,
    G: Create + Data<NodeWeight = T, EdgeWeight = M>,
    F: FnMut() -> T,
    H: FnMut() -> M,
    K::EdgeId: Hash + Eq,
{
    let num_edges = input_graph.edge_count();
    let mut output_graph = G::with_capacity(num_edges, 0);
    let mut output_edge_map =
        HashMap::<K::EdgeId, G::NodeId>::with_capacity(input_graph.edge_count());

    for edge in input_graph.edge_references() {
        let new_node = output_graph.add_node(default_node_weight());
        output_edge_map.insert(edge.id(), new_node);
    }

    for node in input_graph.node_identifiers() {
        let edges: Vec<K::EdgeRef> = input_graph.edges(node).collect();
        for i in 0..edges.len() {
            for j in i + 1..edges.len() {
                let node0 = output_edge_map.get(&edges[i].id()).unwrap();
                let node1 = output_edge_map.get(&edges[j].id()).unwrap();
                output_graph.add_edge(*node0, *node1, default_edge_weight());
            }
        }
    }
    (output_graph, output_edge_map)
}

#[cfg(test)]

mod test_line_graph {
    use crate::line_graph::line_graph;
    use crate::petgraph::visit::EdgeRef;
    use crate::petgraph::Graph;
    use hashbrown::HashMap;
    use petgraph::graph::{EdgeIndex, NodeIndex};
    use petgraph::Undirected;

    #[test]
    fn test_simple_graph() {
        // Simple graph
        let input_graph = Graph::<(), (), Undirected>::from_edges([(0, 1), (2, 3), (3, 4), (4, 5)]);

        let (output_graph, output_edge_map): (
            petgraph::graph::UnGraph<(), ()>,
            HashMap<petgraph::prelude::EdgeIndex, petgraph::prelude::NodeIndex>,
        ) = line_graph(&input_graph, || (), || ());

        let output_edge_list = output_graph
            .edge_references()
            .map(|edge| (edge.source().index(), edge.target().index()))
            .collect::<Vec<(usize, usize)>>();

        let expected_edge_list = vec![(2, 1), (3, 2)];
        let expected_edge_map: HashMap<EdgeIndex, NodeIndex> = [
            (EdgeIndex::new(0), NodeIndex::new(0)),
            (EdgeIndex::new(1), NodeIndex::new(1)),
            (EdgeIndex::new(2), NodeIndex::new(2)),
            (EdgeIndex::new(3), NodeIndex::new(3)),
        ]
        .into_iter()
        .collect();

        assert_eq!(output_edge_list, expected_edge_list);
        assert_eq!(output_edge_map, expected_edge_map);
    }
}