orbweaver 0.18.2

Crate designed for effortless construction and analysis of graph data structures.
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
156
157

use std::rc::Rc;

use crate::utils::{interner::InternerBuilder, node_map::NodeMap, sym::Sym};
use rayon::prelude::*;

use super::{DirectedAcyclicGraph, DirectedGraph, GraphBuilderError, GraphHasCycle};

#[derive(Clone)]
pub struct DirectedGraphBuilder {
    pub(crate) parents: Vec<Sym>,
    pub(crate) children: Vec<Sym>,
    pub(crate) interner: InternerBuilder,
}

fn find_leaves(parents: &[Sym], children: &[Sym]) -> Vec<Sym> {
    let mut leaves: Vec<_> = children
        .par_iter()
        .filter(|child| parents.binary_search(child).is_err())
        .copied()
        .collect();
    leaves.sort_unstable();
    leaves.dedup();
    leaves
}

fn find_roots(parents: &[Sym], children: &[Sym]) -> Vec<Sym> {
    let mut roots: Vec<_> = parents
        .par_iter()
        .filter(|parent| children.binary_search(parent).is_err())
        .copied()
        .collect();
    roots.sort_unstable();
    roots.dedup();
    roots
}

impl DirectedGraphBuilder {
    pub fn new() -> Self {
        DirectedGraphBuilder {
            interner: InternerBuilder::new(),
            children: Vec::new(),
            parents: Vec::new(),
        }
    }

    #[inline(always)]
    pub(crate) fn get_or_intern(&mut self, val: impl AsRef<str>) -> Sym {
        self.interner.get_or_intern(val)
    }
    pub fn add_edge(&mut self, from: impl AsRef<str>, to: impl AsRef<str>) -> &mut Self {
        let from = self.get_or_intern(&from);
        let to = self.get_or_intern(&to);
        self.parents.push(from);
        self.children.push(to);
        self
    }
    pub fn add_path(
        &mut self,
        path: impl IntoIterator<Item = impl AsRef<str>>,
    ) -> Result<&mut Self, GraphBuilderError> {
        let mut path = path.into_iter().peekable();

        // if it's length 1 (if peek is None) we return an error
        if path.peek().is_none() {
            return Err(GraphBuilderError::LengthOnePath);
        }

        while let (Some(from), Some(to)) = (path.next(), path.peek()) {
            self.add_edge(from.as_ref(), to.as_ref());
        }
        Ok(self)
    }

    pub fn build_directed(self) -> DirectedGraph {
        // When we build we will do some optimizations
        let mut unique_parents = self.parents.clone();
        unique_parents.sort_unstable();
        unique_parents.dedup();
        unique_parents.shrink_to_fit();

        let mut unique_children = self.children.clone();
        unique_children.sort_unstable();
        unique_children.dedup();
        unique_parents.shrink_to_fit();

        let mut nodes = Vec::new();
        nodes.extend_from_slice(&unique_parents);
        nodes.extend_from_slice(&unique_children);
        nodes.sort_unstable();
        nodes.dedup();
        nodes.shrink_to_fit();

        let leaves = find_leaves(&unique_parents, &unique_children);
        let roots = find_roots(&unique_parents, &unique_children);

        let mut n_edges = 0;

        let interner = Rc::new(self.interner.build());

        // Maps parents to their children
        let mut children_map = NodeMap::new(interner.len());

        for i in 0..self.parents.len() {
            let was_added = children_map
                .get_mut(self.parents[i])
                .or_init()
                .insert(self.children[i]);
            if was_added {
                n_edges += 1;
            }
        }

        // Maps children to their parents
        let mut parent_map = NodeMap::new(interner.len());

        for i in 0..self.parents.len() {
            parent_map
                .get_mut(self.children[i])
                .or_init()
                .insert(self.parents[i]);
        }

        // Every parent and child must have been initialized. If it
        // has not that means it's empty.
        for node in &nodes {
            let parent_entry = parent_map.get_mut(*node);
            let child_entry = children_map.get_mut(*node);
            if parent_entry.is_uninitialized() {
                parent_entry.into_empty();
            }
            if child_entry.is_uninitialized() {
                child_entry.into_empty();
            }
        }

        DirectedGraph {
            interner,
            leaves,
            roots,
            nodes,
            children_map,
            parent_map,
            n_edges,
            buf: Default::default(),
        }
    }

    pub fn build_acyclic(self) -> Result<DirectedAcyclicGraph, GraphHasCycle> {
        DirectedAcyclicGraph::build(self.build_directed())
    }
}

impl Default for DirectedGraphBuilder {
    fn default() -> Self {
        Self::new()
    }
}