petgraph/visit/
undirected_adaptor.rs

Help
1use crate::visit::{
2    Data, GraphBase, GraphProp, GraphRef, IntoEdgeReferences, IntoEdges, IntoEdgesDirected,
3    IntoNeighbors, IntoNeighborsDirected, IntoNodeIdentifiers, IntoNodeReferences,
4    NodeCompactIndexable, NodeCount, NodeIndexable, Visitable,
5};
6use crate::Direction;
7
8/// An edge direction removing graph adaptor.
9#[derive(Copy, Clone, Debug)]
10pub struct UndirectedAdaptor<G>(pub G);
11
12impl<G: GraphRef> GraphRef for UndirectedAdaptor<G> {}
13
14impl<G> IntoNeighbors for UndirectedAdaptor<G>
15where
16    G: IntoNeighborsDirected,
17{
18    type Neighbors = core::iter::Chain<G::NeighborsDirected, G::NeighborsDirected>;
19    fn neighbors(self, n: G::NodeId) -> Self::Neighbors {
20        self.0
21            .neighbors_directed(n, Direction::Incoming)
22            .chain(self.0.neighbors_directed(n, Direction::Outgoing))
23    }
24}
25
26impl<G> IntoEdges for UndirectedAdaptor<G>
27where
28    G: IntoEdgesDirected,
29{
30    type Edges = core::iter::Chain<G::EdgesDirected, G::EdgesDirected>;
31    fn edges(self, a: Self::NodeId) -> Self::Edges {
32        self.0
33            .edges_directed(a, Direction::Incoming)
34            .chain(self.0.edges_directed(a, Direction::Outgoing))
35    }
36}
37
38impl<G> GraphProp for UndirectedAdaptor<G>
39where
40    G: GraphBase,
41{
42    type EdgeType = crate::Undirected;
43
44    fn is_directed(&self) -> bool {
45        false
46    }
47}
48
49macro_rules! access0 {
50    ($e:expr) => {
51        $e.0
52    };
53}
54
55GraphBase! {delegate_impl [[G], G, UndirectedAdaptor<G>, access0]}
56Data! {delegate_impl [[G], G, UndirectedAdaptor<G>, access0]}
57IntoEdgeReferences! {delegate_impl [[G], G, UndirectedAdaptor<G>, access0]}
58Visitable! {delegate_impl [[G], G, UndirectedAdaptor<G>, access0]}
59NodeIndexable! {delegate_impl [[G], G, UndirectedAdaptor<G>, access0]}
60NodeCompactIndexable! {delegate_impl [[G], G, UndirectedAdaptor<G>, access0]}
61IntoNodeIdentifiers! {delegate_impl [[G], G, UndirectedAdaptor<G>, access0]}
62IntoNodeReferences! {delegate_impl [[G], G, UndirectedAdaptor<G>, access0]}
63NodeCount! {delegate_impl [[G], G, UndirectedAdaptor<G>, access0]}
64
65#[cfg(test)]
66mod tests {
67    use alloc::vec::Vec;
68
69    use super::*;
70    use crate::graph::{DiGraph, Graph};
71    use crate::visit::Dfs;
72
73    static LINEAR_EDGES: [(u32, u32); 5] = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)];
74
75    #[test]
76    pub fn test_is_reachable() {
77        // create a linear digraph, choose a node in the centre and check all nodes are visited
78        // by a dfs
79
80        let graph = DiGraph::<(), ()>::from_edges(LINEAR_EDGES);
81
82        let mut nodes = graph.node_identifiers().collect::<Vec<_>>();
83        nodes.sort();
84
85        let graph = UndirectedAdaptor(&graph);
86
87        use crate::visit::Walker;
88        let mut visited_nodes: Vec<_> = Dfs::new(&graph, nodes[2]).iter(&graph).collect();
89        visited_nodes.sort();
90        assert_eq!(visited_nodes, nodes);
91    }
92
93    #[test]
94    pub fn test_neighbors_count() {
95        {
96            let graph = Graph::<(), ()>::from_edges(LINEAR_EDGES);
97            let graph = UndirectedAdaptor(&graph);
98
99            let mut nodes = graph.node_identifiers().collect::<Vec<_>>();
100            nodes.sort();
101            assert_eq!(graph.neighbors(nodes[1]).count(), 2);
102        }
103
104        {
105            let graph = Graph::<(), ()>::from_edges(LINEAR_EDGES);
106            let graph = UndirectedAdaptor(&graph);
107
108            let mut nodes = graph.node_identifiers().collect::<Vec<_>>();
109            nodes.sort();
110            assert_eq!(graph.neighbors(nodes[1]).count(), 2);
111        }
112    }
113}
petgraph/visit/undirected_adaptor.rs

petgraph/visit/
undirected_adaptor.rs
