icentral_graph/
find_edge_bcc_with_delta.rs

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

icentral_graph/
find_edge_bcc_with_delta.rs
