icentral_graph/
find_edge_bcc_with_scratch.rs

1crate::ix!();
2
3impl<GH> FindEdgeBccWithScratch<GH> for Graph<GH> 
4
5where GH
6: DebugIterationStep
7+ FindPruningCounts
8+ GetEdges
9+ GetNeighborsForNode
10+ GetNodeIdRange
11+ GetSigmaValueForNode
12+ HasEdge
13+ InitDebugIteration
14+ InsertEdge
15+ MappedNodes
16+ NumEdges
17+ NumNodes
18+ PairDependencyForNode
19+ ParentsForNode
20+ RemoveEdge
21+ BccGraphHashInterface
22{
23    /// a. find the bcc subgraph
24    ///
25    /// b. find the articulation points in bcc
26    ///
27    /// c. find the sizes of the subgraphs
28    /// connected to each art point
29    ///
30    fn find_edge_bcc_with_scratch(&mut self, 
31        bcc:  &mut BiconnectedComponentsScratch<GH>,
32        edge: &Edge)
33    -> Result<(),BetweennessCentralityError>
34    {
35        self.find_edge_bcc_subgraph(bcc.bcc_subgraph_mut(), &edge);
36
37        bcc.bcc_fast_subgraph_reset_with_graphhash();
38
39        let mut art_pt_vec: Vec<NodeId> = vec![];
40
41        self.find_articulation_points(&mut art_pt_vec);
42
43        let mut art_pt_set: HashSet<NodeId> = default!();
44
45        for i in 0..art_pt_vec.len() {
46            art_pt_set.insert(art_pt_vec[i]);
47        }
48
49        for v in bcc.bcc_subgraph_mapped_nodes() {
50
51            if art_pt_set.contains(&v) {
52
53                self.find_edge_bcc_with_scratch_step(v, bcc, edge)?;
54            }
55        }
56
57        let new_delta_articulation_point_map_name = name![
58            self.name(), 
59            "find_edge_bcc_with_scratch::new_delta_articulation_point_map"
60        ];
61
62        // fix articulation_point_map
63        let mut new_delta_articulation_point_map = ArticulationPointMap::empty_mapped(new_delta_articulation_point_map_name);
64
65        for item in bcc.articulation_point_map_iter() {
66
67            let new_v: NodeId = bcc.bcc_fast_subgraph_label_map_outin(*item.0);
68
69            new_delta_articulation_point_map.map_articulation_point(
70                new_v,
71                &item.1.to_vec()
72            );
73        }
74
75        bcc.set_articulation_point_map(new_delta_articulation_point_map);
76
77        Ok(())
78    }
79
80    /// the node is an articulation point and it
81    /// belongs to the bcc of interest, so it must
82    /// be added to the art point of this bcc
83    /// along with the sizes of the subgraphs it
84    /// connects the bcc to
85    ///
86    fn find_edge_bcc_with_scratch_step(&mut self, 
87        v:    NodeId,
88        bcc:  &mut BiconnectedComponentsScratch<GH>,
89        edge: &Edge)
90    -> Result<(),BetweennessCentralityError>
91    {
92        let mut subgraph_sz_vec: Vec<usize>  = vec![];
93
94        let visit_markers_name = name![
95            self.name(), 
96            "find_edge_bcc_With_scratch_step::name"
97        ];
98
99        let mut visit_markers = VisitMarkers::new_with_single_node_visited(
100            self.num_nodes(), 
101            v,
102            visit_markers_name
103        );
104
105        let v_nbr_vec = self.neighbors(v);
106
107        for u in NodeIdRange::new(0,v_nbr_vec.len()) {
108
109            if !bcc.bcc_subgraph_has_edge(&Edge::new(v, u)) && visit_markers.unvisited(u) {
110
111                let cnt = self.connected_component_size_through_v_and_this_edge(
112                    &mut visit_markers, 
113                    u
114                );
115
116                subgraph_sz_vec.push(cnt);
117            }
118        }
119
120        bcc.map_articulation_point(
121            v,
122            &subgraph_sz_vec
123        );
124
125        Ok(())
126    }
127}
icentral_graph/find_edge_bcc_with_scratch.rs

icentral_graph/
find_edge_bcc_with_scratch.rs
