traitgraph_algo/traversal/
univocal_traversal.rs

1use crate::traversal::{
2    BackwardNeighborStrategy, ForwardNeighborStrategy, TraversalNeighborStrategy,
3};
4use std::marker::PhantomData;
5use traitgraph::interface::{GraphBase, NavigableGraph, NodeOrEdge, StaticGraph};
6
7/// An iterator over the univocal extension of a node or edge.
8/// The direction is defined by the `NeighborStrategy`.
9///
10/// Note that this iterator only works for directed graphs, as for undirected graphs it is unclear which node comes after an edge.
11pub struct UnivocalIterator<'a, Graph: GraphBase, NeighborStrategy> {
12    graph: &'a Graph,
13    neighbor_strategy: PhantomData<NeighborStrategy>,
14    current_node: Option<Graph::NodeIndex>,
15    current_edge: Option<Graph::EdgeIndex>,
16}
17
18impl<'a, Graph: NavigableGraph, NeighborStrategy: 'a + TraversalNeighborStrategy<Graph>>
19    UnivocalIterator<'a, Graph, NeighborStrategy>
20{
21    /// Create a new `UnivocalIterator` that iterates over the univocal extension of `start_element` including `start_element`, in the direction specified by `neighbor_strategy`.
22    pub fn new(
23        graph: &'a Graph,
24        start_element: NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>,
25    ) -> Self {
26        let (current_node, current_edge) = match start_element {
27            NodeOrEdge::Node(node) => (Some(node), None),
28            NodeOrEdge::Edge(edge) => (None, Some(edge)),
29        };
30        Self {
31            graph,
32            neighbor_strategy: Default::default(),
33            current_node,
34            current_edge,
35        }
36    }
37
38    /// Create a new `UnivocalIterator` that iterates over the univocal extension of `start_element` excluding `start_element`, in the direction specified by `neighbor_strategy`.
39    pub fn new_without_start(
40        graph: &'a Graph,
41        start_element: NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>,
42    ) -> impl 'a + Iterator<Item = NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>> {
43        Self::new(graph, start_element).skip(1)
44    }
45}
46
47impl<'a, Graph: NavigableGraph> UnivocalIterator<'a, Graph, ForwardNeighborStrategy>
48where
49    ForwardNeighborStrategy: TraversalNeighborStrategy<Graph>,
50{
51    /// Create a new `UnivocalIterator` that iterates over the forward univocal extension of `start_element` including `start_element`.
52    pub fn new_forward(
53        graph: &'a Graph,
54        start_element: NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>,
55    ) -> Self {
56        Self::new(graph, start_element)
57    }
58
59    /// Create a new `UnivocalIterator` that iterates over the forward univocal extension of `start_element` excluding `start_element`.
60    pub fn new_forward_without_start(
61        graph: &'a Graph,
62        start_element: NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>,
63    ) -> impl 'a + Iterator<Item = NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>> {
64        Self::new_without_start(graph, start_element)
65    }
66}
67
68impl<'a, Graph: NavigableGraph> UnivocalIterator<'a, Graph, BackwardNeighborStrategy>
69where
70    BackwardNeighborStrategy: TraversalNeighborStrategy<Graph>,
71{
72    /// Create a new `UnivocalIterator` that iterates over the backward univocal extension of `start_element` including `start_element`.
73    pub fn new_backward(
74        graph: &'a Graph,
75        start_element: NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>,
76    ) -> Self {
77        Self::new(graph, start_element)
78    }
79
80    /// Create a new `UnivocalIterator` that iterates over the backward univocal extension of `start_element` excluding `start_element`.
81    pub fn new_backward_without_start(
82        graph: &'a Graph,
83        start_element: NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>,
84    ) -> impl 'a + Iterator<Item = NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>> {
85        Self::new_without_start(graph, start_element)
86    }
87}
88
89impl<Graph: NavigableGraph, NeighborStrategy: TraversalNeighborStrategy<Graph>> Iterator
90    for UnivocalIterator<'_, Graph, NeighborStrategy>
91{
92    type Item = NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>;
93
94    fn next(&mut self) -> Option<Self::Item> {
95        match (self.current_node, self.current_edge) {
96            (Some(_), Some(edge)) => {
97                self.current_edge = None;
98                Some(NodeOrEdge::Edge(edge))
99            }
100            (Some(node), None) => {
101                let mut next_neighbor_iter = NeighborStrategy::neighbor_iterator(self.graph, node);
102                if let Some(neighbor) = next_neighbor_iter.next() {
103                    let next_node = neighbor.node_id;
104                    let next_edge = neighbor.edge_id;
105
106                    if next_neighbor_iter.next().is_none() {
107                        self.current_node = Some(next_node);
108                        self.current_edge = Some(next_edge);
109                    } else {
110                        self.current_node = None;
111                    }
112                } else {
113                    self.current_node = None;
114                    self.current_edge = None;
115                }
116
117                Some(NodeOrEdge::Node(node))
118            }
119            (None, Some(edge)) => {
120                let mut next_node_iter = NeighborStrategy::edge_neighbor_iterator(self.graph, edge);
121                let next_node = next_node_iter
122                    .next()
123                    .expect("Edge does not have a node as successor.");
124                debug_assert!(
125                    next_node_iter.next().is_none(),
126                    "Edge has more than one node as successor."
127                );
128                self.current_node = Some(next_node);
129                self.current_edge = None;
130                Some(NodeOrEdge::Edge(edge))
131            }
132            (None, None) => None,
133        }
134    }
135}
136
137/// Returns true if the given edge is self-bivalent in the given graph, i.e. its univocal extension repeats a node.
138pub fn is_edge_self_bivalent<Graph: StaticGraph>(graph: &Graph, edge_id: Graph::EdgeIndex) -> bool {
139    let forward_iter =
140        UnivocalIterator::new_forward_without_start(graph, NodeOrEdge::Edge(edge_id));
141    let mut backward_iter = UnivocalIterator::new_backward(graph, NodeOrEdge::Edge(edge_id));
142
143    let mut last_element = None;
144    for element in forward_iter {
145        match element {
146            NodeOrEdge::Edge(edge) => {
147                if edge == edge_id {
148                    return true;
149                }
150                last_element = Some(NodeOrEdge::Edge(edge));
151            }
152            node => last_element = Some(node),
153        }
154    }
155
156    let last_element = last_element.expect(
157        "Forward univocal extension is empty, but should at least contain the start edge itself",
158    );
159    backward_iter.any(|e| e == last_element)
160}
161
162#[cfg(test)]
163mod tests {
164    use crate::traversal::univocal_traversal::is_edge_self_bivalent;
165    use traitgraph::implementation::petgraph_impl::PetGraph;
166    use traitgraph::interface::MutableGraphContainer;
167
168    #[test]
169    fn test_is_edge_self_bivalent_simple() {
170        let mut graph = PetGraph::new();
171        let n0 = graph.add_node(());
172        let n1 = graph.add_node(());
173        let n2 = graph.add_node(());
174        let n3 = graph.add_node(());
175        let n4 = graph.add_node(());
176        let e0 = graph.add_edge(n0, n1, ());
177        let e1 = graph.add_edge(n0, n2, ());
178        let e2 = graph.add_edge(n3, n0, ());
179        let e3 = graph.add_edge(n4, n0, ());
180        let e4 = graph.add_edge(n1, n3, ());
181        let e5 = graph.add_edge(n1, n3, ());
182        let e6 = graph.add_edge(n2, n4, ());
183        let e7 = graph.add_edge(n2, n4, ());
184        let e8 = graph.add_edge(n0, n0, ());
185
186        debug_assert!(!is_edge_self_bivalent(&graph, e0));
187        debug_assert!(!is_edge_self_bivalent(&graph, e1));
188        debug_assert!(!is_edge_self_bivalent(&graph, e2));
189        debug_assert!(!is_edge_self_bivalent(&graph, e3));
190        debug_assert!(is_edge_self_bivalent(&graph, e4));
191        debug_assert!(is_edge_self_bivalent(&graph, e5));
192        debug_assert!(is_edge_self_bivalent(&graph, e6));
193        debug_assert!(is_edge_self_bivalent(&graph, e7));
194        debug_assert!(is_edge_self_bivalent(&graph, e8));
195    }
196
197    #[test]
198    fn test_is_edge_self_bivalent_cycle() {
199        let mut graph = PetGraph::new();
200        let n0 = graph.add_node(());
201        let n1 = graph.add_node(());
202        let n2 = graph.add_node(());
203        let e0 = graph.add_edge(n0, n1, ());
204        let e1 = graph.add_edge(n1, n2, ());
205        let e2 = graph.add_edge(n2, n0, ());
206
207        debug_assert!(is_edge_self_bivalent(&graph, e0));
208        debug_assert!(is_edge_self_bivalent(&graph, e1));
209        debug_assert!(is_edge_self_bivalent(&graph, e2));
210    }
211}
traitgraph_algo/traversal/univocal_traversal.rs

traitgraph_algo/traversal/
univocal_traversal.rs
