bitdag 0.1.2

A crate to deconstruct the hierrachie of a DAG into a Bitmatrix for fast child-parent-queries.
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

use crate::edge::Edge;
use crate::error::BitDagError;
use crate::traits::ToEdges;
use fastobo::ast::{EntityFrame, OboDoc, TermClause};
use std::collections::{HashMap, HashSet, VecDeque};

impl ToEdges for OboDoc {
    fn edges(&self, root_node: &str) -> Result<Vec<Edge>, BitDagError> {
        let mut parent_to_children: HashMap<String, Vec<String>> = HashMap::new();

        for entity in self.entities() {
            if let EntityFrame::Term(term) = entity {
                let child_id = term.id().to_string();

                for clause in term.clauses() {
                    if let TermClause::IsA(parent_ident) = clause.as_inner() {
                        parent_to_children
                            .entry(parent_ident.to_string())
                            .or_default()
                            .push(child_id.clone());
                    }
                }
            }
        }

        let mut edges = Vec::new();
        let mut queue: VecDeque<String> = VecDeque::new();
        let mut visited: HashSet<String> = HashSet::new();

        queue.push_back(root_node.to_string());
        visited.insert(root_node.to_string());

        while let Some(parent) = queue.pop_front() {
            if let Some(children) = parent_to_children.get(&parent) {
                for child in children {
                    edges.push((parent.clone(), child.clone()).into());

                    if visited.insert(child.clone()) {
                        queue.push_back(child.clone());
                    }
                }
            }
        }

        Ok(edges)
    }
}