icentral_graph/
find_edge_bcc_with_component.rs

1crate::ix!();
2
3impl<GH> FindEdgeBccWithComponent<GH> for Graph<GH> 
4where GH
5: HasEdge 
6+ ConnectedComponentSize 
7+ RemoveEdge
8+ CreateNamedEmpty
9+ MappedNodes
10+ NumNodes
11+ Named
12+ GetNeighborsForNode
13+ GetNodeIdRange
14+ GetEdges
15+ BccGraphHashInterface
16{
17    /// the node is an articulation point and it
18    /// belongs to the bcc of interest, so it must
19    /// be added to the art point of this bcc
20    /// along with the sizes of the subgraphs it
21    /// connects the bcc to
22    ///
23    fn find_edge_bcc_with_component_step(
24        &mut self, 
25        gh:        &GH,
26        v:         NodeId,
27        component: &mut Component,
28        e:         &Edge) 
29    -> Result<(),BetweennessCentralityError>
30    {
31        let mut subgraph_sz_vec: Vec<usize>  = vec![];
32
33        let visit_markers_name = name![
34            self.name(), 
35            "find_edge_bcc_with_component_step::visit_markers"
36        ];
37
38        let mut visit_markers = VisitMarkers::new_with_single_node_visited(
39            self.num_nodes(),
40            v,
41            visit_markers_name
42        );
43
44        let v_nbr_vec = self.neighbors(v);
45
46        for &u in v_nbr_vec.iter() {
47
48            if !gh.has_edge(&Edge::new(v, u)) && visit_markers.unvisited(u) {
49
50                let cnt = self.connected_component_size_through_v_and_this_edge(
51                    &mut visit_markers, 
52                    u
53                );
54
55                subgraph_sz_vec.push(cnt);
56
57                // debug!("---{}, {}", v, cnt);
58            }
59        }
60
61        component.map_articulation_point(v,&subgraph_sz_vec);
62
63        Ok(())
64    }
65    
66    /// a. find the bcc subgraph
67    ///
68    /// b. find the articulation points in bcc
69    ///
70    /// c. find the sizes of the subgraphs
71    /// connected to each art point
72    ///
73    /// IMP: assumes @e is not in the graph
74    /// already
75    ///
76    fn find_edge_bcc_with_component(
77        &mut self, 
78        component: &mut Component,
79        e:         &Edge) 
80    -> Result<(),BetweennessCentralityError>
81    {
82        if self.has_edge(e) {
83            return Err(BetweennessCentralityError::DuplicateEdgeInsertion { 
84                edge: e.clone() 
85            });
86        }
87
88        self.insert_edge(e);
89
90        let gh_name = name![self.name(), "find_edge_bcc_with_component::gh"];
91
92        let mut gh: GH = GH::empty(gh_name);
93
94        self.find_edge_bcc_subgraph(&mut gh, e);
95
96        // g.remove_edge(e.src, e.dst); 
97        //
98        // TODO: make sure it's okay! [NO, needed
99        // below]
100        //
101        let mut art_pt_vec: Vec<NodeId> = vec![];
102
103        self.find_articulation_points(&mut art_pt_vec);
104
105        // to make art points unique
106        let mut art_pt_set: HashSet<NodeId> = default!();
107
108        for i in 0..art_pt_vec.len() {
109            art_pt_set.insert(art_pt_vec[i]);
110        }
111
112        for v in gh.mapped_nodes() {
113
114            if art_pt_set.get(&v).is_none() {
115
116                self.find_edge_bcc_with_component_step(
117                    &gh, 
118                    v, 
119                    component, 
120                    e
121                )?;
122            }
123        }
124
125        // fix articulation_point_map
126        gh.remove_edge(e);
127
128        component.reset_subgraph_with(&mut gh);
129
130        component.remap_articulation_point_map();
131
132        self.remove_edge(e);
133
134        Ok(())
135    }
136}
icentral_graph/find_edge_bcc_with_component.rs

icentral_graph/
find_edge_bcc_with_component.rs
