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

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

///
/// I-extension will extend graph by two vertices
/// if graph is snark and first_edge and second_edge are non adjacent and removable
/// -> output graph will be snark as well
///
pub fn i_extension<G: Graph + Clone, E: Edge>(graph: &G, first_edge: &E, second_edge: &E) -> G {
    let mut result_graph = (*graph).clone();
    result_graph.remove_edge(first_edge.from(), first_edge.to());
    result_graph.remove_edge(second_edge.from(), second_edge.to());

    let first_new_vertex = graph.size();
    let second_new_vertex = graph.size() + 1;
    result_graph.add_edge(first_edge.from(), first_new_vertex);
    result_graph.add_edge(first_edge.to(), first_new_vertex);
    result_graph.add_edge(second_edge.from(), second_new_vertex);
    result_graph.add_edge(second_edge.to(), second_new_vertex);
    result_graph.add_edge(first_new_vertex, second_new_vertex);
    result_graph
}

///
/// Iterator over possible I-extensions of given graph
///
/// Be aware that graph isomorphism for result dot products is not checked and so result graph
/// could be the same as previous or next one
///
pub struct IExtensions<'a, G: Graph + Clone, C: Colouriser> {
    graph: &'a G,
    _colouriser: &'a C,
    removable_edge_pairs: RemovablePairsOfEdges<'a, G, C>,
}

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

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(pair) = self.removable_edge_pairs.next() {
            let graph = i_extension(self.graph, pair.0, pair.1);
            return Some(graph);
        }
        None
    }
}

impl<'a, G: Graph<E = UndirectedEdge> + Clone, C: Colouriser> IExtensions<'a, G, C> {
    pub fn new(graph: &'a G, colouriser: &'a C) -> Self {
        IExtensions {
            graph,
            _colouriser: colouriser,
            removable_edge_pairs: RemovablePairsOfEdges::new(&graph, &colouriser),
        }
    }
}