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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211

use crate::traversal::{
    BackwardNeighborStrategy, ForwardNeighborStrategy, TraversalNeighborStrategy,
};
use std::marker::PhantomData;
use traitgraph::interface::{GraphBase, NavigableGraph, NodeOrEdge, StaticGraph};

/// An iterator over the univocal extension of a node or edge.
/// The direction is defined by the `NeighborStrategy`.
///
/// Note that this iterator only works for directed graphs, as for undirected graphs it is unclear which node comes after an edge.
pub struct UnivocalIterator<'a, Graph: GraphBase, NeighborStrategy> {
    graph: &'a Graph,
    neighbor_strategy: PhantomData<NeighborStrategy>,
    current_node: Option<Graph::NodeIndex>,
    current_edge: Option<Graph::EdgeIndex>,
}

impl<'a, Graph: NavigableGraph, NeighborStrategy: 'a + TraversalNeighborStrategy<Graph>>
    UnivocalIterator<'a, Graph, NeighborStrategy>
{
    /// Create a new `UnivocalIterator` that iterates over the univocal extension of `start_element` including `start_element`, in the direction specified by `neighbor_strategy`.
    pub fn new(
        graph: &'a Graph,
        start_element: NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>,
    ) -> Self {
        let (current_node, current_edge) = match start_element {
            NodeOrEdge::Node(node) => (Some(node), None),
            NodeOrEdge::Edge(edge) => (None, Some(edge)),
        };
        Self {
            graph,
            neighbor_strategy: Default::default(),
            current_node,
            current_edge,
        }
    }

    /// Create a new `UnivocalIterator` that iterates over the univocal extension of `start_element` excluding `start_element`, in the direction specified by `neighbor_strategy`.
    pub fn new_without_start(
        graph: &'a Graph,
        start_element: NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>,
    ) -> impl 'a + Iterator<Item = NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>> {
        Self::new(graph, start_element).skip(1)
    }
}

impl<'a, Graph: NavigableGraph> UnivocalIterator<'a, Graph, ForwardNeighborStrategy>
where
    ForwardNeighborStrategy: TraversalNeighborStrategy<Graph>,
{
    /// Create a new `UnivocalIterator` that iterates over the forward univocal extension of `start_element` including `start_element`.
    pub fn new_forward(
        graph: &'a Graph,
        start_element: NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>,
    ) -> Self {
        Self::new(graph, start_element)
    }

    /// Create a new `UnivocalIterator` that iterates over the forward univocal extension of `start_element` excluding `start_element`.
    pub fn new_forward_without_start(
        graph: &'a Graph,
        start_element: NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>,
    ) -> impl 'a + Iterator<Item = NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>> {
        Self::new_without_start(graph, start_element)
    }
}

impl<'a, Graph: NavigableGraph> UnivocalIterator<'a, Graph, BackwardNeighborStrategy>
where
    BackwardNeighborStrategy: TraversalNeighborStrategy<Graph>,
{
    /// Create a new `UnivocalIterator` that iterates over the backward univocal extension of `start_element` including `start_element`.
    pub fn new_backward(
        graph: &'a Graph,
        start_element: NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>,
    ) -> Self {
        Self::new(graph, start_element)
    }

    /// Create a new `UnivocalIterator` that iterates over the backward univocal extension of `start_element` excluding `start_element`.
    pub fn new_backward_without_start(
        graph: &'a Graph,
        start_element: NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>,
    ) -> impl 'a + Iterator<Item = NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>> {
        Self::new_without_start(graph, start_element)
    }
}

impl<'a, Graph: NavigableGraph, NeighborStrategy: TraversalNeighborStrategy<Graph>> Iterator
    for UnivocalIterator<'a, Graph, NeighborStrategy>
{
    type Item = NodeOrEdge<Graph::NodeIndex, Graph::EdgeIndex>;

    fn next(&mut self) -> Option<Self::Item> {
        match (self.current_node, self.current_edge) {
            (Some(_), Some(edge)) => {
                self.current_edge = None;
                Some(NodeOrEdge::Edge(edge))
            }
            (Some(node), None) => {
                let mut next_neighbor_iter = NeighborStrategy::neighbor_iterator(self.graph, node);
                if let Some(neighbor) = next_neighbor_iter.next() {
                    let next_node = neighbor.node_id;
                    let next_edge = neighbor.edge_id;

                    if next_neighbor_iter.next().is_none() {
                        self.current_node = Some(next_node);
                        self.current_edge = Some(next_edge);
                    } else {
                        self.current_node = None;
                    }
                } else {
                    self.current_node = None;
                    self.current_edge = None;
                }

                Some(NodeOrEdge::Node(node))
            }
            (None, Some(edge)) => {
                let mut next_node_iter = NeighborStrategy::edge_neighbor_iterator(self.graph, edge);
                let next_node = next_node_iter
                    .next()
                    .expect("Edge does not have a node as successor.");
                debug_assert!(
                    next_node_iter.next().is_none(),
                    "Edge has more than one node as successor."
                );
                self.current_node = Some(next_node);
                self.current_edge = None;
                Some(NodeOrEdge::Edge(edge))
            }
            (None, None) => None,
        }
    }
}

/// Returns true if the given edge is self-bivalent in the given graph, i.e. its univocal extension repeats a node.
pub fn is_edge_self_bivalent<Graph: StaticGraph>(graph: &Graph, edge_id: Graph::EdgeIndex) -> bool {
    let forward_iter =
        UnivocalIterator::new_forward_without_start(graph, NodeOrEdge::Edge(edge_id));
    let mut backward_iter = UnivocalIterator::new_backward(graph, NodeOrEdge::Edge(edge_id));

    let mut last_element = None;
    for element in forward_iter {
        match element {
            NodeOrEdge::Edge(edge) => {
                if edge == edge_id {
                    return true;
                }
                last_element = Some(NodeOrEdge::Edge(edge));
            }
            node => last_element = Some(node),
        }
    }

    let last_element = last_element.expect(
        "Forward univocal extension is empty, but should at least contain the start edge itself",
    );
    backward_iter.any(|e| e == last_element)
}

#[cfg(test)]
mod tests {
    use crate::traversal::univocal_traversal::is_edge_self_bivalent;
    use traitgraph::implementation::petgraph_impl::PetGraph;
    use traitgraph::interface::MutableGraphContainer;

    #[test]
    fn test_is_edge_self_bivalent_simple() {
        let mut graph = PetGraph::new();
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        let n2 = graph.add_node(());
        let n3 = graph.add_node(());
        let n4 = graph.add_node(());
        let e0 = graph.add_edge(n0, n1, ());
        let e1 = graph.add_edge(n0, n2, ());
        let e2 = graph.add_edge(n3, n0, ());
        let e3 = graph.add_edge(n4, n0, ());
        let e4 = graph.add_edge(n1, n3, ());
        let e5 = graph.add_edge(n1, n3, ());
        let e6 = graph.add_edge(n2, n4, ());
        let e7 = graph.add_edge(n2, n4, ());
        let e8 = graph.add_edge(n0, n0, ());

        debug_assert!(!is_edge_self_bivalent(&graph, e0));
        debug_assert!(!is_edge_self_bivalent(&graph, e1));
        debug_assert!(!is_edge_self_bivalent(&graph, e2));
        debug_assert!(!is_edge_self_bivalent(&graph, e3));
        debug_assert!(is_edge_self_bivalent(&graph, e4));
        debug_assert!(is_edge_self_bivalent(&graph, e5));
        debug_assert!(is_edge_self_bivalent(&graph, e6));
        debug_assert!(is_edge_self_bivalent(&graph, e7));
        debug_assert!(is_edge_self_bivalent(&graph, e8));
    }

    #[test]
    fn test_is_edge_self_bivalent_cycle() {
        let mut graph = PetGraph::new();
        let n0 = graph.add_node(());
        let n1 = graph.add_node(());
        let n2 = graph.add_node(());
        let e0 = graph.add_edge(n0, n1, ());
        let e1 = graph.add_edge(n1, n2, ());
        let e2 = graph.add_edge(n2, n0, ());

        debug_assert!(is_edge_self_bivalent(&graph, e0));
        debug_assert!(is_edge_self_bivalent(&graph, e1));
        debug_assert!(is_edge_self_bivalent(&graph, e2));
    }
}