line_graph/
lib.rs

1//! Construct the line graph of an undirected graph
2//!
3//! This crate provides a single function that takes an undirected
4//! [petgraph](https://github.com/petgraph/petgraph) graph and
5//! constructs the corresponding
6//! [line graph](https://en.wikipedia.org/wiki/Line_graph).
7//! Node weights are turned into edge weights and vice versa.
8//!
9//! # Example
10//!
11//! The triangle graph is the same as its line graph.
12//!
13//! ```rust
14//! use line_graph::line_graph;
15//! use petgraph::{
16//!    algo::is_isomorphic,
17//!    graph::UnGraph
18//! };
19//!
20//! let g = UnGraph::<(), ()>::from_edges([(0, 1), (1, 2), (2, 0)]);
21//! let g_line = line_graph(&g);
22//! assert!(is_isomorphic(&g, &g_line));
23//! ```
24//!
25//! # Caveats
26//!
27//! If edges are connected by two vertices, the corresponding vertices
28//! in the line graph will also be connected by two edges.
29//!
30use petgraph::{
31    graph::{DefaultIx, IndexType, UnGraph},
32    visit::{EdgeRef, IntoNodeReferences},
33};
34use std::default::Default;
35
36/// Construct the line graph for `g`
37pub fn line_graph<N, E, Ix>(g: &UnGraph<N, E, Ix>) -> UnGraph<E, N, DefaultIx>
38where
39    N: Clone,
40    E: Clone + Default,
41    Ix: IndexType,
42{
43    let mut line_graph = UnGraph::with_capacity(g.edge_count(), 0);
44    for _ in 0..g.edge_count() {
45        line_graph.add_node(Default::default());
46    }
47    for (nidx, nwt) in g.node_references() {
48        for (s, e1) in g.edges(nidx).enumerate() {
49            for e2 in g.edges(nidx).skip(s + 1) {
50                let (v1, v2) = {
51                    use petgraph::visit::EdgeIndexable;
52                    (g.to_index(e1.id()), g.to_index(e2.id()))
53                };
54                let (v1, v2) = {
55                    use petgraph::visit::NodeIndexable;
56                    (line_graph.from_index(v1), line_graph.from_index(v2))
57                };
58                line_graph.add_edge(v1, v2, nwt.clone());
59            }
60        }
61    }
62
63    for node in g.edge_references() {
64        let id = {
65            use petgraph::visit::EdgeIndexable;
66            g.to_index(node.id())
67        };
68        let id = {
69            use petgraph::visit::NodeIndexable;
70            line_graph.from_index(id)
71        };
72
73        let weight = line_graph.node_weight_mut(id).unwrap();
74        *weight = node.weight().clone();
75    }
76    line_graph
77}
78
79#[cfg(test)]
80mod tests {
81    use super::*;
82    use petgraph::algo::is_isomorphic;
83
84    #[test]
85    fn dipole() {
86        let orig = UnGraph::<(), ()>::from_edges([(0, 1), (0, 1), (0, 1)]);
87        let target = UnGraph::<(), ()>::from_edges([
88            (0, 1),
89            (0, 1),
90            (0, 2),
91            (0, 2),
92            (1, 2),
93            (1, 2),
94        ]);
95        assert!(is_isomorphic(&target, &line_graph(&orig)));
96    }
97
98    // wikipedia example, indices shifted by -1
99    #[test]
100    fn simple() {
101        let orig = UnGraph::<(), ()>::from_edges([
102            (0, 1),
103            (0, 2),
104            (0, 3),
105            (1, 4),
106            (2, 3),
107            (3, 4),
108        ]);
109        let target = UnGraph::<(), ()>::from_edges([
110            (0, 1),
111            (0, 2),
112            (0, 3),
113            (1, 2),
114            (1, 4),
115            (2, 4),
116            (2, 5),
117            (3, 5),
118            (4, 5),
119        ]);
120        assert!(is_isomorphic(&target, &line_graph(&orig)));
121    }
122}
line_graph/lib.rs

line_graph/
lib.rs
