icentral_bcc/
bcc_dfs_visitor.rs

1crate::ix!();
2
3pub trait BccGraphHashInterface
4: NumNodes 
5+ NumEdges 
6+ GetEdges 
7+ InsertEdge 
8+ CreateNamedEmpty
9{ }
10
11impl<T> BccGraphHashInterface for T
12where T: NumNodes + NumEdges + GetEdges + InsertEdge + CreateNamedEmpty {}
13
14pub fn bcc_dfs_visitor<'a,G,GH>(
15    graph:      &G, 
16    u:          NodeId,
17    ctx:        &mut BccDfsVisitorContext<'a>,
18    bcc_vec:    &mut Vec<GH>
19
20) -> Result<(),BetweennessCentralityError> 
21where G: GetNeighborsForNode, GH: BccGraphHashInterface
22{
23    debug!("Graph::initiating bcc_dfs_visitor");
24
25    // 1 means grey
26    ctx.set_color_for_node_grey(u);
27    ctx.step_time_and_update_distances_for_node(u);
28
29    let nbr_vec = graph.neighbors(u);
30
31    let mut tree_edge_cnt: i32 = 0;
32
33    for i in 0..nbr_vec.len() {
34
35        let v: NodeId = nbr_vec[i];
36
37        //  (u, v) is a tree edge
38        if ctx.color_for_node(v) == Color::None {
39
40            bcc_dfs_visitor_step_tree_edge(
41                graph,
42                v,
43                u,
44                ctx,
45                bcc_vec,
46                &mut tree_edge_cnt
47            )?;
48
49        } else {
50
51            ctx.bcc_dfs_visitor_step_colored(
52                v,
53                u,
54            )?;
55        }
56    }
57
58    Ok(())
59}
60
61fn bcc_dfs_visitor_step_tree_edge<'a,G,GH>(
62    graph:         &G, 
63    v:             NodeId,
64    u:             NodeId,
65    ctx:           &mut BccDfsVisitorContext<'a>,
66    bcc_vec:       &mut Vec<GH>,
67    tree_edge_cnt: &mut i32
68
69) -> Result<(),BetweennessCentralityError> 
70where G: GetNeighborsForNode, GH: BccGraphHashInterface
71{
72    ctx.edge_stack.push(Edge::new(u,v));
73
74    ctx.pred_vec.set_predecessor_for_node(v, u);
75
76    *tree_edge_cnt += 1;
77
78    bcc_dfs_visitor(graph, v, ctx, bcc_vec);
79
80    ctx.low_vec.set_distance_for_node(
81        u, 
82        min(
83            FloatOrd(ctx.low_vec.distance(u)),
84            FloatOrd(ctx.low_vec.distance(v))
85        ).0
86    );
87
88    if ctx.low_vec.distance(v) >= ctx.distances.distance(u) {
89
90        //  u is an articulation point, ready to output a bcc
91        let last_edge = Edge::new(u,v);
92
93        let mut bcc = GH::empty("bcc");
94
95        loop {
96
97            let e: Edge = ctx.edge_stack.pop().unwrap();
98
99            bcc.insert_edge(&e);
100
101            if e == last_edge {
102                break;
103            }
104        }
105
106        bcc_vec.push(bcc);
107    }
108
109    Ok(())
110}
icentral_bcc/bcc_dfs_visitor.rs

icentral_bcc/
bcc_dfs_visitor.rs
