icentral_graph/
find_muc_mcb.rs

1crate::ix!();
2
3impl<GH> FindMucMcb<GH> for Graph<GH> 
4where GH
5: GetEdges
6+ ClearMucs
7+ CreateNamedEmpty
8+ Debug
9+ ExtendWith<GH,Error=BetweennessCentralityError>
10+ FindConnectedComponents<GH,Error=BetweennessCentralityError>
11+ GetConnectedComponentSizes
12+ GetNeighborsForNode
13+ GetNodeIdRange
14+ HasMapForNode
15+ InsertEdge
16+ InsertNode
17+ IsValid
18+ MappedNodes
19+ NewFromCycleVec
20+ NewFromGraphRef<Self>
21+ NumEdges
22+ NumNodes
23+ RemoveBridges
24{
25    fn find_muc_mcb(&mut self) 
26    -> Result<(),BetweennessCentralityError>
27    {
28        self.mcb_find();
29
30        let mcb_cycle_vec_len = self.mcb.num_cycles();
31
32        let visit_markers_name = name![self.name(), "find_muc_mcb::visit_markers"];
33
34        let mut visit_markers = VisitMarkers::new(mcb_cycle_vec_len,visit_markers_name);
35
36        let cycle_graph_name = name![
37            self.name(), 
38            "find_muc_mcb::cycle_graph"
39        ];
40
41        let cycle_graph = GH::new_from_cycle_vec(
42            self.mcb.cycles(), 
43            cycle_graph_name
44        );
45
46        debug!("{:?}", cycle_graph);
47
48        for idx in NodeIdRange::new(0,self.mcb.num_cycles()) {
49
50            if visit_markers.unvisited(idx) {
51
52                self.find_muc_mcb_for_cycle(
53                    idx, 
54                    &cycle_graph, 
55                    &mut visit_markers
56                );
57            }
58        }
59
60        self.create_single_vertex_mucs();
61
62        self.find_conn_verts();
63
64        self.find_all_muc_subgraphs();
65
66        Ok(())
67    }
68
69    fn find_muc_mcb_for_cycle(
70        &mut self, 
71        src:           NodeId, 
72        cycle_graph:   &GH, 
73        visit_markers: &mut VisitMarkers) 
74    -> Result<(),BetweennessCentralityError>
75    {
76        let mut muc = MinimumUnionCycle::<GH>::default();
77
78        muc.set_id(self.mucs.len());
79
80        let cycle = self.mcb.cycle(src).clone();
81
82        self.merge_muc_cycle(
83            &mut muc, 
84            &cycle
85        );
86
87        visit_markers.visit(src);
88
89        let queue_name = name![self.name(),"find_muc_mcb_for_cycle::queue"];
90
91        let mut queue = NodeIdQueue::empty(queue_name);
92
93        queue.enqueue(src);
94
95        while let Some(node) = queue.dequeue() {
96
97            let nbrs = cycle_graph.neighbors(node);
98
99            for nbr in nbrs {
100
101                if visit_markers.unvisited(nbr) {
102
103                    visit_markers.visit(nbr);
104
105                    let cycle = self.mcb.cycle(nbr).clone();
106
107                    self.merge_muc_cycle(
108                        &mut muc, 
109                        &cycle
110                    );
111
112                    queue.enqueue(nbr);
113                }
114            }
115        }
116
117        self.mucs.push(muc);
118
119        Ok(())
120    }
121}
icentral_graph/find_muc_mcb.rs

icentral_graph/
find_muc_mcb.rs
