sinistra 0.1.0-202603071957

A generic graph framework with pluggable storage and topology and streaming graph algorithms.
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

mod bfs;
mod dfs;
mod dijkstra;
mod toposort;

pub use bfs::Event as BfsEvent;
pub use bfs::{bfs, bfs_tree_edges, bfs_vertices};

pub use dfs::Event as DfsEvent;
pub use dfs::dfs;

pub use dijkstra::Dijkstra;
pub use dijkstra::Event as DijkstraEvent;
pub use dijkstra::dijkstra;
pub use dijkstra::dijkstra_distances;

pub use toposort::{bfs_layers, has_path, is_dag, topological_sort};

use std::collections::{BinaryHeap, VecDeque};

use crate::graph::{EdgeHandle, VertexHandle};

#[derive(Debug, Clone, Copy)]
pub enum TraversalEvent {
    Discover {
        vertex: VertexHandle,
    },
    Examine {
        source: VertexHandle,
        target: VertexHandle,
        edge: EdgeHandle,
    },
    Finish {
        vertex: VertexHandle,
    },
}

pub trait Frontier<T> {
    fn push(&mut self, value: T);
    fn pop(&mut self) -> Option<T>;
}

impl<T> Frontier<T> for VecDeque<T> {
    fn push(&mut self, value: T) {
        self.push_back(value);
    }

    fn pop(&mut self) -> Option<T> {
        self.pop_front()
    }
}

impl<T> Frontier<T> for Vec<T> {
    fn push(&mut self, value: T) {
        self.push(value);
    }

    fn pop(&mut self) -> Option<T> {
        self.pop()
    }
}

impl<T: Ord> Frontier<T> for BinaryHeap<T> {
    fn push(&mut self, value: T) {
        BinaryHeap::push(self, value);
    }

    fn pop(&mut self) -> Option<T> {
        BinaryHeap::pop(self)
    }
}

pub trait Policy {
    type Event;
    type Item;

    fn start(&mut self, start: VertexHandle);
    fn pop(&mut self) -> Option<Self::Item>;
    fn process(&mut self, item: Self::Item, pending: &mut VecDeque<Self::Event>);
}

pub struct Traversal<P: Policy> {
    policy: P,
    pending: VecDeque<P::Event>,
}

impl<P: Policy> Traversal<P> {
    pub fn new(mut policy: P, start: VertexHandle) -> Self {
        let pending = VecDeque::new();

        policy.start(start);

        Self { policy, pending }
    }
}

impl<P: Policy> Iterator for Traversal<P> {
    type Item = P::Event;

    fn next(&mut self) -> Option<Self::Item> {
        loop {
            if let Some(event) = self.pending.pop_front() {
                return Some(event);
            }

            let item = self.policy.pop()?;
            self.policy.process(item, &mut self.pending);
        }
    }
}