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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114

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

pub struct RemovablePairsOfEdges<'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>,
    first_edge: Option<&'a UndirectedEdge>,
    graph: &'a G,
    local_graph: G,
    _colouriser: &'a C,
}

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

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

        while let Some(first_edge) = self.first_edge {
            while let Some(second_edge) = self.second_edge_iterator.next() {
                if first_edge.eq(second_edge) || first_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());

                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());

                if !colourable {
                    return Some((first_edge, second_edge));
                }
            }
            // renew second edge iterator to original value
            self.second_edge_iterator = self.graph.edges();
            self.first_edge = self.first_edge_iterator.next();
        }
        None
    }
}

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

pub struct PairsOfNonAdjacentEdges<'a, G: Graph<E = UndirectedEdge>> {
    first_edge_iterator: Box<dyn Iterator<Item = &'a UndirectedEdge> + 'a>,
    second_edge_iterator: Box<dyn Iterator<Item = &'a UndirectedEdge> + 'a>,
    first_edge_current: Option<&'a UndirectedEdge>,
    graph: &'a G,
}

impl<'a, G: Graph<E = UndirectedEdge>> Iterator for PairsOfNonAdjacentEdges<'a, G> {
    type Item = (&'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();
        }

        while let Some(first_edge) = self.first_edge_current {
            while let Some(second_edge) = self.second_edge_iterator.next() {
                if first_edge.eq(second_edge) {
                    continue;
                }

                if first_edge > second_edge {
                    continue;
                }

                if !first_edge.is_adjacent(second_edge) {
                    return Some((first_edge, second_edge));
                }
            }
            // renew second edge iterator to original value
            self.second_edge_iterator = self.graph.edges();
            self.first_edge_current = self.first_edge_iterator.next();
        }
        None
    }
}

impl<'a, G: Graph<E = UndirectedEdge>> PairsOfNonAdjacentEdges<'a, G> {
    pub fn new(graph: &'a G) -> Self {
        PairsOfNonAdjacentEdges {
            first_edge_iterator: graph.edges(),
            second_edge_iterator: graph.edges(),
            first_edge_current: None,
            graph,
        }
    }
}