libpitust 0.1.0

libpitust implements random utility functions I tend to use a lot
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

//! Module `scc` computes the strongly connected components of the graph.
//!
//! See https://cp-algorithms.com/graph/strongly-connected-components.html

use crate::{
    graph::{GraphPred, GraphSucc, indexgraph::IndexGraph, node_map::NodeMap},
    index::vec::IndexVec,
    index_type,
};

fn scc_dfs<G: GraphSucc>(
    graph: G,
    vis: &mut NodeMap<G, bool>,
    items: &mut Vec<G::Node>,
    node: G::Node,
) {
    debug_assert!(!vis[node]);
    vis[node] = true;
    for node in graph.succ_of(node) {
        if !vis[node] {
            scc_dfs(graph, vis, items, node);
        }
    }
    items.push(node);
}
fn scc_dfs_rev<G: GraphPred>(
    graph: G,
    vis: &mut NodeMap<G, bool>,
    items: &mut Vec<G::Node>,
    node: G::Node,
) {
    debug_assert!(!vis[node]);
    vis[node] = true;
    for node in graph.pred_of(node) {
        if !vis[node] {
            scc_dfs_rev(graph, vis, items, node);
        }
    }
    items.push(node);
}

index_type!(pub CondensedNode<Id>);

pub fn scc<G: GraphPred + GraphSucc>(
    graph: G,
) -> (NodeMap<G, CondensedNode<G>>, IndexGraph<CondensedNode<G>>) {
    // first pass
    let mut order = vec![];
    let mut dfs_vis = NodeMap::new_with(graph, |_| false);
    for node in graph.nodes() {
        if !dfs_vis[node] {
            scc_dfs(graph, &mut dfs_vis, &mut order, node);
        }
    }
    order.reverse();

    // second pass
    dfs_vis.clear(graph);
    let mut condensed_lut = NodeMap::new_with(graph, |_| CondensedNode::ZERO);
    let mut components = vec![];
    let mut index_graph = IndexVec::new();
    for &node in &order {
        if dfs_vis[node] {
            continue;
        }

        scc_dfs_rev(graph, &mut dfs_vis, &mut components, node);
        let con_node = index_graph.push(vec![]);
        for c in components.drain(..) {
            condensed_lut[c] = con_node;
        }
    }

    // build condensation graph
    for &node in &order {
        let src = condensed_lut[node];
        for succ in graph.succ_of(node) {
            let dst = condensed_lut[succ];
            if src != dst {
                index_graph[src].push(dst);
            }
        }
    }
    for (_, set) in &mut index_graph {
        set.sort_unstable();
        set.dedup();
    }

    (condensed_lut, index_graph.into())
}