arboreal 0.0.3

Library for building dynamic digraphs with generic data
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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155


use std::collections::HashMap;
use std::fmt::{self, Display};

use crate::graph_base::graph_components::Id;
use super::{Nodal, DirEdge, DiGraph, HistoryDeque};

const DEFAULT_NODE_PREALLOCATION: usize = 20;
const EXPECTED_EDGES_PER_NODE: usize = 3;

impl<N: Nodal, E: DirEdge> DiGraph<N, E> {

    pub(super) fn edge_index(&self, start_id: Id, end_id: Id) -> Option<usize> {
        for (index, edge) in self.edges.iter().enumerate() {
            if edge.terminal_ids() == (start_id, end_id) {
                return Some(index);
            }
        }
        None
    }

    pub(super) fn insert_node_unregistered(&mut self, node: N) {
        let node_id = node.node_id();
        self.nodes.insert(node_id, node);
        self.neighbors_before.insert(node_id, Vec::with_capacity(5));
        self.neighbors_after.insert(node_id, Vec::with_capacity(5));
    }

    pub(super) fn remove_node_unregistered(&mut self, node_id: Id) -> N {
        for id_before in self.neighbors_before.get(&node_id).unwrap().to_owned() {
            let edge_index = self.edge_index(id_before, node_id).unwrap();
            self.remove_edge_unregistered(edge_index);
        }
        for id_after in self.neighbors_after.get(&node_id).unwrap().to_owned() {
            let edge_index = self.edge_index(node_id, id_after).unwrap();
            self.remove_edge_unregistered(edge_index);
        }
        self.nodes
            .remove(&node_id)
            .unwrap()
    }

    pub(super) fn insert_edge_unregistered(&mut self, edge: E) {
        let (start_id, end_id) = edge.terminal_ids();
        self.edges.push(edge);
        // Register end node's id as start node's after-neighbor
        self.neighbors_after
            .get_mut(&start_id)
            .unwrap()
            .push(end_id);
        // Register start node's id as end node's before-neighbor
        self.neighbors_before
            .get_mut(&end_id)
            .unwrap()
            .push(start_id);
    }

    pub(super) fn remove_edge_unregistered(&mut self, edge_index: usize) {
        let dropped_edge = self.edges.swap_remove(edge_index);
        let (start_id, end_id) = dropped_edge.terminal_ids();
        self.neighbors_before
            .get_mut(&end_id)
            .unwrap()
            .retain(|&x| x != start_id);
        self.neighbors_after
            .get_mut(&start_id)
            .unwrap()
            .retain(|&x| x != end_id);
    }

    /// Returns vec of `node_id` for which `in_degree(node_id) == Some(0)`
    pub(super) fn source_node_ids(&self) -> Vec<Id> {
        let mut ids: Vec<Id> = self.nodes
            .keys()
            .cloned()
            .collect();
        ids.retain(|&id| self.in_degree(id) == Some(0));
        ids.shrink_to_fit();
        ids
    }

    /// Returns vec of `node_id` for which `out_degree(node_id) == Some(0)`
    pub(super) fn sink_node_ids(&self) -> Vec<Id> {
        let mut ids: Vec<Id> = self.nodes
            .keys()
            .cloned()
            .collect();
        ids.retain(|&id| self.out_degree(id) == Some(0));
        ids.shrink_to_fit();
        ids
    }

    pub(super) fn path_from_source(&self, id: Id) -> Result<Vec<Id>, &'static str> {
        let source = self.get_source()?;
        todo!()
    }
    pub(super) fn path_to_sink(&self, id: Id) -> Result<Vec<Id>, &'static str> {
        todo!()
    }

    pub(super) fn is_connected(&self) -> bool {
        todo!()
    }
    pub(super) fn is_terminable(&self) -> bool {
        todo!()
    }
    pub(super) fn is_valid(&self) -> bool {
        self.is_connected() && self.is_terminable()
    }
}

impl<N: Nodal, E: DirEdge> Default for DiGraph<N, E> {
    fn default() -> Self {
        let n = DEFAULT_NODE_PREALLOCATION;
        let e = EXPECTED_EDGES_PER_NODE * n;
        let name = None;
        let nodes = HashMap::with_capacity(n);
        let edges = Vec::with_capacity(e);
        let neighbors_before = HashMap::with_capacity(n);
        let neighbors_after = HashMap::with_capacity(n);
        let undo_history = HistoryDeque::default();
        Self { name, nodes, edges, neighbors_before, neighbors_after, undo_history }
    }
}

impl<N: Nodal, E: DirEdge> Display for DiGraph<N, E> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let name = match &self.name {
            Some(name) => format!("DiGraph ('{}')", name),
            None => "DiGraph".to_string()
        };
        let edges_per_line: u8 = 4;
        write!(f, "{name}\n")?;
        write!(f, "\tNode Ids: {:?}\n", self.nodes.keys())?;
        if self.edges.len() > 0 {
            let mut reset_count = 0;
            for edge in self.edges.iter() {
                if reset_count == 0 {
                    write!(f, "\t")?;
                } else {
                    write!(f, ",  ")?;
                }
                write!(f, "{}->{}", edge.start_id(), edge.end_id())?;
                reset_count += 1;
                if reset_count == edges_per_line {
                    reset_count = 0;
                    write!(f, "\n")?;
                }
            }
        } else {
            write!(f, "\t(No edges)")?;
        }
        Ok(())
    }
}