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

use crate::graph::edge::Edge;
use crate::graph::vertex::{Vertex, VertexConstructor};
use crate::service::property::max_flow::residual_graph::edge::DirectedFlowEdge;

#[derive(Debug, Hash, Eq, PartialEq, Clone)]
pub struct ResidualVertex {
    index: usize,
    active: bool,
    pub edges: Vec<DirectedFlowEdge>,
}

impl Vertex for ResidualVertex {
    fn index(&self) -> usize {
        self.index
    }
}

impl VertexConstructor for ResidualVertex {
    fn new(index: usize) -> Self {
        ResidualVertex {
            index,
            active: true,
            edges: vec![],
        }
    }
}

impl ResidualVertex {
    pub fn new_non_active(index: usize) -> Self {
        ResidualVertex {
            index,
            active: false,
            edges: vec![],
        }
    }

    pub fn add_edge(&mut self, to: usize) {
        // if self.has_neighbor(to) {
        //     self.increase_edge_capacity(to);
        //     return;
        // }
        self.edges
            .push(DirectedFlowEdge::new_with_capacity(self.index, to, 1));
    }

    pub fn neighbors(&self) -> Vec<usize> {
        let mut neighbors = vec![];
        for edge in self.edges.iter() {
            if edge.capacity() > 0 {
                neighbors.push(edge.to())
            }
        }
        neighbors
    }

    pub fn has_neighbor(&self, neighbor_index: usize) -> bool {
        for neighbor in self.neighbors() {
            if neighbor == neighbor_index {
                return true;
            }
        }
        false
    }

    pub fn active(&self) -> bool {
        self.active
    }

    pub fn set_active(&mut self, active: bool) {
        self.active = active;
    }

    #[allow(dead_code)]
    pub fn edge_capacity(&self, to: usize) -> usize {
        let mut capacity = 0;
        for edge in self.edges.iter() {
            if edge.to() == to {
                capacity += edge.capacity();
            }
        }
        capacity
    }

    pub fn increase_edge_capacity(&mut self, to: usize) {
        for edge in self.edges.iter_mut() {
            if edge.to() == to {
                edge.set_capacity(edge.capacity() + 1);
            }
        }
    }

    ///
    /// decreases edge capacity by 1 if edge is present and capacity is bigger than 0
    /// returns true if edge capacity was decreased, false if vertex does not have edge or its capacity is already 0
    ///
    pub fn decrease_edge_capacity(&mut self, to: usize) -> bool {
        for edge in self.edges.iter_mut() {
            if edge.to() == to {
                if edge.capacity() > 0 {
                    edge.set_capacity(edge.capacity() - 1);
                    return true;
                }
            }
        }
        false
    }
}