saboten 0.1.0

Provides biedged graphs, cactus graphs and trees, and an algorithm for finding ultrabubbles in variation graphs.
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

use fxhash::FxHashSet;

use crate::biedgedgraph::BiedgedGraph;

#[derive(Clone)]
pub struct NetGraph {
    pub graph: BiedgedGraph,
    pub x: u64,
    pub y: u64,
    pub path: Vec<u64>,
}

#[derive(Debug, PartialEq)]
enum Color {
    Black,
    Gray,
}

impl Color {
    fn toggle(&self) -> Self {
        match self {
            Color::Black => Color::Gray,
            Color::Gray => Color::Black,
        }
    }
}

impl NetGraph {
    pub fn is_acyclic(&self) -> bool {
        let graph = &self.graph.graph;

        let mut visited: FxHashSet<u64> = FxHashSet::default();
        let mut in_path: FxHashSet<u64> = FxHashSet::default();
        let mut stack: Vec<(Color, u64)> = Vec::new();

        let mut acyclic = true;

        let x = self.x;

        let start_color = if graph.edges(x).any(|(_, _, w)| w.black > 0) {
            Color::Gray
        } else {
            Color::Black
        };

        stack.push((start_color, x));

        while let Some((last_color, current)) = stack.pop() {
            if !visited.contains(&current) {
                visited.insert(current);
                in_path.insert(current);

                let edges: Vec<_> = graph
                    .edges(current)
                    .filter(|(_, _, w)| match last_color {
                        Color::Black => w.gray > 0,
                        Color::Gray => w.black > 0,
                    })
                    .collect();

                stack.push((last_color.toggle(), current));
                for (_, adj, _) in edges {
                    if in_path.contains(&adj) {
                        acyclic = false;
                    } else {
                        stack.push((last_color.toggle(), adj));
                    }
                }
            } else if in_path.contains(&current) {
                in_path.remove(&current);
            }
        }

        acyclic
    }

    pub fn is_bridgeless(&self) -> bool {
        for node in self.graph.graph.nodes() {
            if node != self.x
                && node != self.y
                && self
                    .graph
                    .graph
                    .edges(node)
                    .find(|(_, _, w)| w.black == 1)
                    .is_none()
            {
                return false;
            }
        }
        true
    }

    pub fn is_ultrabubble(&self) -> bool {
        self.is_bridgeless() & self.is_acyclic()
    }
}