icentral_bcc/
find_edge_bcc_subgraph.rs

1crate::ix!();
2
3pub trait FindEdgeBccSubgraph {
4
5    fn find_edge_bcc_subgraph<GH: BccGraphHashInterface>(
6        &mut self, 
7        bcc:  &mut GH,
8        edge: &Edge
9    ) -> Result<(),BetweennessCentralityError>;
10}
11
12impl<T> FindEdgeBccSubgraph for T 
13where T: Sized + Named + NumNodes + GetNeighborsForNode
14{
15    /**
16      | the edge (@src, @dst) must be in the graph
17      | the biconnected component subgraph that
18      | contains the passed edge will be returned
19      | in @bcc
20      |
21      | IMP assumption:
22      |
23      | the input graph is connected, and the edge
24      | (src, dst) is inserted, so the edge (src,
25      | dst) is part of a cycle, so both ends
26      | belong to the same bcc
27      |
28      |IMP: (src,dst) must exist!
29      */
30    fn find_edge_bcc_subgraph<GH: BccGraphHashInterface>(
31        &mut self, 
32        bcc:  &mut GH,
33        edge: &Edge
34
35    ) -> Result<(),BetweennessCentralityError> {
36
37        debug!("initiating Graph::find_edge_bcc_subgraph");
38
39        let mut u: NodeId = NodeId::default();
40
41        let num_nodes = self.num_nodes();
42
43        let color_vec_name = name![self.name(), "find_edge_bcc_subgraph::color_vec"];
44        let pred_vec_name  = name![self.name(), "find_edge_bcc_subgraph::pred_vec"];
45        let distances_name = name![self.name(), "find_edge_bcc_subgraph::distances"];
46        let low_vec_name   = name![self.name(), "find_edge_bcc_subgraph::low_vec"];
47
48        let mut color_vec = ColorMap::new(num_nodes, color_vec_name);
49        let mut pred_vec  = PredecessorMap::new(num_nodes, pred_vec_name);
50
51        let mut distances = DistanceMap::new(num_nodes, distances_name);
52        let mut low_vec   = DistanceMap::new(num_nodes, low_vec_name);
53
54        let mut edge_stack: Stack<Edge> = default!();
55
56        let mut time: f64 = 0.0;
57
58        let mut nbrs_vec = self.neighbors(edge.src);
59
60        move_destination_edge_to_front(
61            &mut nbrs_vec, 
62            edge.dst
63        );
64
65        let mut ctx = BccDfsVisitorContext {
66            color_vec:  &mut color_vec, 
67            low_vec:    &mut low_vec, 
68            distances:  &mut distances, 
69            pred_vec:   &mut pred_vec, 
70            edge_stack: &mut edge_stack, 
71            time:       &mut time, 
72        };
73
74        edge_bcc_dfs_visitor(
75            self,
76            edge.src, 
77            &mut ctx,
78        );
79
80        while let Some(e) = edge_stack.pop() {
81            bcc.insert_edge(&e);
82        }
83
84        Ok(())
85    }
86}
icentral_bcc/find_edge_bcc_subgraph.rs

icentral_bcc/
find_edge_bcc_subgraph.rs
