arboreal 0.0.4

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


use std::collections::HashMap;

use crate::graph_base::graph_components::*;

type NodeMap<N> = HashMap<Id, N>;

fn edge_index<E: DirEdge>(edges: &Vec<E>, id_in: Id, id_out: Id) -> Option<usize> {
    for (index, edge) in edges.iter().enumerate() {
        if edge.start_id() == id_in && edge.end_id() == id_out {
            return Some(index);
        }
    }
    None
}

fn node_id_present<N: Nodal>(nodes: &NodeMap<N>, id: Id) -> bool {
    nodes.get(&id).is_some()
}

pub fn check_add_node<N: Nodal, E: DirEdge>(nodes: &NodeMap<N>, new_node: N) -> GraphChange<N, E> {
    if node_id_present(nodes, new_node.node_id()) {
        return GraphChange::Failure("Node with this id already exists.");
    }
    GraphChange::AddNode(new_node)
}

/// Determines in- and out-degree of `id` in `edges`.
/// If no edge is found with a terminal at this `id`, `(0, 0)` is returned.
pub fn check_node_degrees<N: Nodal, E: DirEdge>(edges: &Vec<E>, id: Id) -> (usize, usize) {
    let mut degs = (0, 0);
    for edge in edges.iter() {
        if edge.start_id() == id {
            degs.0 += 1;
        }
        if edge.end_id() == id {
            degs.1 += 1;
        }
    }
    degs
}

pub fn check_remove_node<N: Nodal, E: DirEdge>(nodes: &NodeMap<N>, edges: &Vec<E>, id: Id) -> GraphChange<N, E> {
    if !node_id_present(nodes, id) {
        return GraphChange::Failure("Node with this id not found.");
    }
    let node_to_discard = nodes.get(&id)
        .unwrap()
        .clone();
    let mut edges_to_drop = Vec::with_capacity(nodes.len());
    let keep_rule = |e: &E| !(e.start_id() == id || e.end_id() == id);
    for edge in edges.iter() {
        if !keep_rule(edge) {
            edges_to_drop.push(edge.clone());
        }
    }
    GraphChange::RemoveNode(node_to_discard, edges_to_drop)
}

pub fn check_add_edge<N: Nodal, E: DirEdge>(nodes: &NodeMap<N>, edges: &Vec<E>, new_edge: E) -> GraphChange<N, E> {
    let (id_in, id_out) = new_edge.terminal_ids();
    if let Some(_index) = edge_index(edges, id_in, id_out) {
        return GraphChange::Failure("Edge with these terminals already exists.");
    }
    if node_id_present(nodes, id_in) && node_id_present(nodes, id_out)
    {
        return GraphChange::AddEdge(new_edge)
    }
    GraphChange::Failure("Terminals not found in graph.")
}

pub fn check_add_edge_with_nodes<N: Nodal, E: DirEdge>(nodes: &NodeMap<N>, edges: &Vec<E>, id_in: Id, id_out: Id) -> GraphChange<N, E> {
    if let Some(_index) = edge_index(edges, id_in, id_out) {
        return GraphChange::Failure("Edge with these terminals already exists.");
    }
    let new_in = match node_id_present(nodes, id_in) {
        true => None,
        false => Some(id_in)
    };
    let new_out = match node_id_present(nodes, id_out) {
        true => None, 
        false => Some(id_out)
    };
    let proposed_edge = E::bare(id_in, id_out);
    GraphChange::AddEdgeWith(proposed_edge, new_in, new_out)
}

pub fn check_remove_edge<N: Nodal, E: DirEdge>(edges: &Vec<E>, id_in: Id, id_out: Id) -> GraphChange<N, E> {
    if let Some(index) = edge_index(edges, id_in, id_out) {
        let edge_to_drop = edges[index].clone();
        return GraphChange::RemoveEdge(edge_to_drop);
    }
    GraphChange::Failure("Edge not found in graph.")
}

pub fn collect_reachable_neighbors(census: &mut Vec<Id>, starting_point: Id, after_neighbor_map: &HashMap<Id, Vec<Id>>) {
        if census.contains(&starting_point) {
            return
        }
        census.push(starting_point);
        if let Some(cul_da_sac) = after_neighbor_map.get(&starting_point) {
            for neighbor in cul_da_sac.iter() {
                collect_reachable_neighbors(census, *neighbor, after_neighbor_map);
            }
        }
    }