graphannis 0.10.1

This is a prototype for a new backend implementation of the ANNIS linguistic search and visualization system.
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

use annis::db::graphstorage::EdgeContainer;
use annis::types::NodeID;
use rustc_hash::FxHashSet;

pub struct CycleSafeDFS<'a> {
    min_distance: usize,
    max_distance: usize,
    inverse: bool,
    container: &'a EdgeContainer,

    stack: Vec<(NodeID, usize)>,
    path: Vec<NodeID>,
    nodes_in_path: FxHashSet<NodeID>,
    last_distance: usize,
    cycle_detected: bool,
}

pub struct DFSStep {
    pub node: NodeID,
    pub distance: usize,
}

impl<'a> CycleSafeDFS<'a> {
    pub fn new(
        container: &'a EdgeContainer,
        node: &NodeID,
        min_distance: usize,
        max_distance: usize,
    ) -> CycleSafeDFS<'a> {
        let mut stack = vec![];
        stack.push((node.clone(), 0));

        let path = vec![];
        let nodes_in_path = FxHashSet::default();

        CycleSafeDFS {
            min_distance,
            max_distance,
            inverse: false,
            container,
            stack,
            path,
            nodes_in_path,
            last_distance: 0,
            cycle_detected: false,
        }
    }

    pub fn new_inverse(
        container: &'a EdgeContainer,
        node: &NodeID,
        min_distance: usize,
        max_distance: usize,
    ) -> CycleSafeDFS<'a> {
        let mut stack = vec![];
        stack.push((node.clone(), 0));

        let path = vec![];
        let nodes_in_path = FxHashSet::default();

        CycleSafeDFS {
            min_distance,
            max_distance,
            inverse: true,
            container,
            stack,
            path,
            nodes_in_path,
            last_distance: 0,
            cycle_detected: true,
        }
    }

    pub fn is_cyclic(&self) -> bool {
        self.cycle_detected
    }

    fn enter_node(&mut self, entry: (NodeID, usize)) -> bool {
        let node = entry.0;
        let dist = entry.1;

        trace!("enter node {}", node);
        // test if subgraph was completed
        if self.last_distance >= dist {
            // remove all entries below the parent node from the path
            for i in dist..self.path.len() {
                trace!("truncating {} from path", &self.path[i]);
                self.nodes_in_path.remove(&self.path[i]);
            }
            self.path.truncate(dist);
        }
        // test for cycle
        if self.nodes_in_path.contains(&node) {
            trace!("cycle detected for node {} with distance {}", &node, dist);
            self.last_distance = dist;
            self.cycle_detected = true;
            return false;
        } else {
            self.path.push(node.clone());
            self.nodes_in_path.insert(node);
            self.last_distance = dist;
            trace!("removing from stack");
            self.stack.pop();

            // check if distance is in valid range
            let found = dist >= self.min_distance && dist <= self.max_distance;

            if dist < self.max_distance {
                if self.inverse {
                    // add all parent nodes to the stack
                    for o in self.container.get_ingoing_edges(&node) {
                        self.stack.push((o, dist + 1));
                        trace!("adding {} to stack with new size {}", o, self.stack.len());
                    }
                } else {
                    // add all child nodes to the stack
                    for o in self.container.get_outgoing_edges(&node) {
                        self.stack.push((o, dist + 1));
                        trace!("adding {} to stack with new size {}", o, self.stack.len());
                    }
                }
            }
            trace!(
                "enter_node finished with result {} for node {}",
                found,
                node
            );
            return found;
        }
    }
}

impl<'a> Iterator for CycleSafeDFS<'a> {
    type Item = DFSStep;

    fn next(&mut self) -> Option<Self::Item> {
        let mut result: Option<DFSStep> = None;
        while result.is_none() && !self.stack.is_empty() {
            let top = self.stack.last().unwrap().clone();
            if self.enter_node(top) {
                result = Some(DFSStep {
                    node: top.0,
                    distance: top.1,
                });
            }
        }

        return result;
    }
}