mapgraph 0.12.0

A directed graph that can also be used as an arbitrary map.
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

//! Provides implementation of the DFS algorithm.

use crate::{
    graph::{iter::Walker, Edge, Node},
    map::{IntKeyMap, KeySet, Map},
    FrozenGraph,
};
use core::fmt::Debug;

fn dfs_visit_mut_impl<G, N, E, NI, EI, NM, EM, VS, F>(
    graph: &mut G,
    node_index: NI,
    f: &mut F,
    visited: &mut VS,
) where
    G: AsMut<FrozenGraph<N, E, NI, EI, NM, EM>>,
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
    VS: KeySet<NI>,
    F: FnMut(&mut G, NI),
{
    f(graph, node_index);
    visited.insert(node_index);

    let mut walker = graph.as_mut().walk_successors(node_index);
    while let Some(succ_index) = walker.walk_next(graph.as_mut()) {
        if !visited.contains(succ_index) {
            dfs_visit_mut_impl(graph, succ_index, f, visited);
        }
    }
}

/// Calls a closure for each node in the graph in the DFS order starting at a specified index.
pub fn dfs_visit_mut<G, N, E, NI, EI, NM, EM, VS, F>(
    graph: &mut G,
    idx: NI,
    mut f: F,
    visited: &mut VS,
) where
    G: AsMut<FrozenGraph<N, E, NI, EI, NM, EM>>,
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
    VS: KeySet<NI>,
    F: FnMut(&mut G, NI),
{
    dfs_visit_mut_impl(graph, idx, &mut f, visited)
}

fn reverse_dfs_visit_mut_impl<G, N, E, NI, EI, NM, EM, VS, F>(
    graph: &mut G,
    node_index: NI,
    f: &mut F,
    visited: &mut VS,
) where
    G: AsMut<FrozenGraph<N, E, NI, EI, NM, EM>>,
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
    VS: KeySet<NI>,
    F: FnMut(&mut G, NI),
{
    visited.insert(node_index);

    let mut walker = graph.as_mut().walk_successors(node_index);
    while let Some(succ_index) = walker.walk_next(graph.as_mut()) {
        if !visited.contains(succ_index) {
            reverse_dfs_visit_mut_impl(graph, succ_index, f, visited);
        }
    }

    f(graph, node_index);
}

/// Calls a closure for each node in the graph the reverse DFS order starting at a specified index.
pub fn reverse_dfs_visit_mut<G, N, E, NI, EI, NM, EM, VS, F>(
    graph: &mut G,
    idx: NI,
    mut f: F,
    visited: &mut VS,
) where
    G: AsMut<FrozenGraph<N, E, NI, EI, NM, EM>>,
    NI: Copy + Eq + Debug + 'static,
    EI: Copy + Eq + Debug + 'static,
    NM: Map<Node<N, EI>, Key = NI>,
    EM: IntKeyMap<Edge<E, NI, EI>, Key = EI>,
    VS: KeySet<NI>,
    F: FnMut(&mut G, NI),
{
    reverse_dfs_visit_mut_impl(graph, idx, &mut f, visited)
}