snark-tool 0.4.0

snark-tool library contains structures and algorithm for (mainly) cubic graph analysis
Documentation 
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

use crate::graph::edge::Edge;
use crate::graph::graph::Graph;
use crate::graph::undirected::edge::UndirectedEdge;
use crate::service::colour::colouriser::Colouriser;

pub struct RemovableTripletsOfEdges<'a, G: Graph + Clone, C: Colouriser> {
    first_edge_iterator: Box<dyn Iterator<Item = &'a UndirectedEdge> + 'a>,
    second_edge_iterator: Box<dyn Iterator<Item = &'a UndirectedEdge> + 'a>,
    third_edge_iterator: Box<dyn Iterator<Item = &'a UndirectedEdge> + 'a>,
    first_edge_current: Option<&'a UndirectedEdge>,
    second_edge_current: Option<&'a UndirectedEdge>,
    graph: &'a G,
    local_graph: G,
    _colouriser: &'a C,
}

impl<'a, G: Graph<E = UndirectedEdge> + Clone, C: Colouriser> Iterator
    for RemovableTripletsOfEdges<'a, G, C>
{
    type Item = (&'a UndirectedEdge, &'a UndirectedEdge, &'a UndirectedEdge);

    fn next(&mut self) -> Option<Self::Item> {
        if self.first_edge_current.is_none() {
            self.first_edge_current = self.first_edge_iterator.next();
        }
        if self.second_edge_current.is_none() {
            self.second_edge_current = self.second_edge_iterator.next();
        }

        while let Some(first_edge) = self.first_edge_current {
            while let Some(second_edge) = self.second_edge_current {
                if first_edge.eq(second_edge) || second_edge < first_edge {
                    self.second_edge_current = self.second_edge_iterator.next();
                    continue;
                }
                while let Some(third_edge) = self.third_edge_iterator.next() {
                    if second_edge.eq(third_edge)
                        || first_edge.eq(third_edge)
                        || third_edge < second_edge
                    {
                        continue;
                    }
                    self.local_graph
                        .remove_edge(first_edge.from(), first_edge.to());
                    self.local_graph
                        .remove_edge(second_edge.from(), second_edge.to());
                    self.local_graph
                        .remove_edge(third_edge.from(), third_edge.to());

                    let colourable = C::is_colorable(&self.local_graph);

                    self.local_graph
                        .add_edge(first_edge.from(), first_edge.to());
                    self.local_graph
                        .add_edge(second_edge.from(), second_edge.to());
                    self.local_graph
                        .add_edge(third_edge.from(), third_edge.to());

                    if !colourable {
                        return Some((first_edge, second_edge, third_edge));
                    }
                }
                // renew third edge iterator to original value
                self.third_edge_iterator = self.graph.edges();
                // shift second edge to next
                self.second_edge_current = self.second_edge_iterator.next();
            }
            // renew second edge iterator to original value and take first next
            self.second_edge_iterator = self.graph.edges();
            self.second_edge_current = self.second_edge_iterator.next();
            // shift first edge to next
            self.first_edge_current = self.first_edge_iterator.next();
        }
        None
    }
}

impl<'a, G: Graph<E = UndirectedEdge> + Clone, C: Colouriser> RemovableTripletsOfEdges<'a, G, C> {
    pub fn new(graph: &'a G, colouriser: &'a C) -> Self {
        RemovableTripletsOfEdges {
            first_edge_iterator: graph.edges(),
            second_edge_iterator: graph.edges(),
            third_edge_iterator: graph.edges(),
            first_edge_current: None,
            second_edge_current: None,
            graph,
            local_graph: graph.clone(),
            _colouriser: colouriser,
        }
    }
}