gryf 0.2.1

Graph data structure library with focus on convenience, versatility, correctness and performance.
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

use rustc_hash::{FxBuildHasher, FxHashSet};

use crate::{
    adapt::Transpose,
    algo::Cycle,
    core::{Neighbors, VertexSet, id::UseVertexId, marker::Directed},
    visit::{
        VisitAll, VisitSet, Visitor,
        raw::{RawDfsExtra, RawDfsExtraEvent, RawEvent, RawVisit, RawVisitMulti},
    },
};

use super::Error;

pub fn dfs_visit<'a, G>(graph: &'a G) -> DfsVisit<'a, G>
where
    G: VertexSet + 'a,
{
    DfsVisit {
        raw: RawVisit::new(Some(graph.vertex_count())),
        multi: RawVisitMulti::new(VisitAll::new(graph)),
        closed: FxHashSet::with_capacity_and_hasher(graph.vertex_count(), FxBuildHasher),
        cycle: None,
    }
}

/// A [visitor](Visitor) that visits the vertices in topological order.
///
/// Returned from running the [`TopoSort`](crate::algo::TopoSort) with
/// [DFS](crate::algo::toposort::TopoSortBuilder::dfs) algorithm.
pub struct DfsVisit<'a, G>
where
    G: VertexSet + 'a,
{
    raw: RawVisit<G, UseVertexId, RawDfsExtra>,
    multi: RawVisitMulti<G, UseVertexId, RawDfsExtra, VisitAll<'a, G>>,
    closed: FxHashSet<G::VertexId>,
    cycle: Option<G::EdgeId>,
}

impl<'a, G> Visitor<G> for DfsVisit<'a, G>
where
    G: Neighbors<EdgeType = Directed> + VertexSet,
{
    type Item = Result<G::VertexId, Error<G>>;

    fn visit_next(&mut self, graph: &G) -> Option<Self::Item> {
        if self.cycle.is_some() {
            // We discovered a cycle in the previous iteration, but next vertex
            // was still requested.
            return None;
        }

        // The implementation differs from classic DFS algorithm for topological
        // sorting in order to achieve lazy behavior. The algorithm traverses
        // the graph in reverse DFS order and reports each vertex that is being
        // closed (i.e., when we reached vertex that has no (unreported)
        // predecessors). If a back edge is encountered, the cycle error is
        // reported instead.

        // Reverse the directions of the edges so the traversal actually works
        // in reverse direction.
        let graph = &Transpose::new(graph);

        loop {
            let raw_extra_event = self.multi.next_multi(
                &mut self.raw,
                |raw| {
                    raw.next(graph, |_, raw_event| match raw_event {
                        RawEvent::Skip { vertex, from } if !self.closed.is_visited(&vertex) => {
                            // Vertex not added to the stack, but also
                            // has not been closed. That means that we
                            // encountered a back edge.
                            self.cycle = from.map(|(_, edge)| edge);

                            // Prune to avoid unnecessary work.
                            false
                        }
                        _ => true,
                    })
                },
                |vertex| graph.contains_vertex(vertex),
            )?;

            if let Some(ref cycle) = self.cycle {
                return Some(Err(Error::Cycle(Cycle::new(cycle.clone(), false))));
            }

            if let RawDfsExtraEvent::Close(vertex) = raw_extra_event {
                self.closed.visit(vertex.clone());
                return Some(Ok(vertex));
            }
        }
    }
}