icentral_articulation_point/
articulation_point.rs

1crate::ix!();
2
3pub trait FindArticulationPoints {
4
5    fn find_articulation_points(&self, out_vec: &mut Vec<NodeId>);
6
7    fn articulation_point_dfs_visitor<'a>(
8        &self, 
9        u:                      NodeId,
10        ctx:                    &mut ArticulationPointFinderContext<'a>,
11        articulation_point_vec: &mut Vec<NodeId>) 
12    -> Result<(),BetweennessCentralityError>;
13
14    fn articulation_point_dfs_visitor_step_tree_edge<'a>(
15        &self, 
16        v:                      NodeId,
17        u:                      NodeId,
18        ctx:                    &mut ArticulationPointFinderContext<'a>,
19        articulation_point_vec: &mut Vec<NodeId>,
20        tree_edge_cnt:          &mut i32) 
21    -> Result<(),BetweennessCentralityError>;
22}
23
24impl<G> FindArticulationPoints for G 
25
26where G
27: NumNodes
28+ GetNeighborsForNode
29+ Named
30{
31    /**
32      | This function will return a vector of
33      | the articulation points.
34      | 
35      | If an articulation point appears in
36      | more than two biconnected components
37      | it will appear more than once (number
38      | of bcc's it appears in -1)
39      |
40      */
41    fn find_articulation_points(&self, out_vec: &mut Vec<NodeId>)  
42    {
43        debug!("initiated Graph::find_articulation_points");
44        
45        let mut time: f64 = 0.0;
46        let mut u: NodeId = NodeId::zero();
47
48        let num_nodes = self.num_nodes();
49
50        let mut color_vec = ColorMap::new(
51            num_nodes,
52            name![self.name(), "find_articulation_points::color_vec"]
53        );
54
55        let mut pred_vec  = PredecessorMap::new(
56            num_nodes,
57            name![self.name(), "find_articulation_points::pred_vec"]
58        );
59
60        let mut distances = DistanceMap::new(num_nodes, "distances");
61        let mut low_vec   = DistanceMap::new(num_nodes, "low_vec");
62
63        let mut ctx = ArticulationPointFinderContext {
64            color_vec: &mut color_vec, 
65            low_vec:   &mut low_vec, 
66            distances: &mut distances, 
67            pred_vec:  &mut pred_vec, 
68            time:      &mut time, 
69        };
70
71        self.articulation_point_dfs_visitor(
72            u, 
73            &mut ctx,
74            out_vec
75        );
76    }
77
78    fn articulation_point_dfs_visitor<'a>(
79        &self, 
80        u:                      NodeId,
81        ctx:                    &mut ArticulationPointFinderContext<'a>,
82        articulation_point_vec: &mut Vec<NodeId>) 
83    -> Result<(),BetweennessCentralityError>
84    {
85        ctx.color_vec.set_color_for_node_grey(u);
86
87        debug!("stepping time {} by one", *ctx.time);
88
89        *ctx.time += 1.0;
90
91        ctx.distances.set_distance_for_node(u, *ctx.time);
92
93        ctx.low_vec.set_distance_for_node(u, ctx.distances.distance(u));
94
95        let mut tree_edge_cnt: i32 = 0;
96
97        let nbr_vec = self.neighbors(u);
98
99        for &v in nbr_vec.iter() {
100
101            let neighbor_color = ctx.color_vec.color_for_node(v);
102
103            //  (u, v) is a tree edge
104            if neighbor_color == Color::None {
105
106                debug!("processing uncolored neighbor v={} -- supposedly (u={},v={}) is a tree edge", v, u, v);
107
108                self.articulation_point_dfs_visitor_step_tree_edge(
109                    v, 
110                    u, 
111                    ctx,
112                    articulation_point_vec, 
113                    &mut tree_edge_cnt
114                )?;
115
116            } else {
117
118                debug!("processing colored neighbor v={}, of color={} -- supposedly (u={},v={}) is a back edge", v, neighbor_color, u, v);
119
120                ctx.articulation_point_dfs_visitor_step_back_edge(v, u)?;
121            }
122        }
123
124        Ok(())
125    }
126
127    fn articulation_point_dfs_visitor_step_tree_edge<'a>(
128        &self, 
129        v:                      NodeId,
130        u:                      NodeId,
131        ctx:                    &mut ArticulationPointFinderContext<'a>,
132        articulation_point_vec: &mut Vec<NodeId>,
133        tree_edge_cnt:          &mut i32) 
134    -> Result<(),BetweennessCentralityError>
135    {
136        debug!("articulation_point_dfs_visitor_step_tree_edge");
137
138        ctx.pred_vec.set_predecessor_for_node(v, u);
139
140        *tree_edge_cnt += 1;
141
142        debug!("incremented tree_edge_cnt to {}", *tree_edge_cnt);
143
144        self.articulation_point_dfs_visitor(
145            v, 
146            ctx,
147            articulation_point_vec
148        );
149
150        ctx.low_vec.set_distance_for_node(
151            u, 
152            min(
153                FloatOrd(ctx.low_vec.distance(u)),
154                FloatOrd(ctx.low_vec.distance(v))
155            ).0
156        );
157
158        // this is the root of the tree
159        //
160        if ctx.pred_vec.is_tree_root(u) {
161
162            debug!("u={} is the root of the tree", u);
163
164            // if v is u's second child
165            // then u is art vertex
166            //
167            if *tree_edge_cnt > 1 {
168                articulation_point_vec.push(u);
169            }
170
171        } else {
172
173            debug!("u={} is not the root of the tree", u);
174
175            if ctx.low_vec.distance(v) >= ctx.distances.distance(u) {
176
177                debug!("we have found an articulation point! the low_vec distance to v={} is greater than or equal to the low_vec distance to u={}", v, u);
178
179                articulation_point_vec.push(u);
180            }
181        }
182
183        Ok(())
184    }
185}
icentral_articulation_point/articulation_point.rs

icentral_articulation_point/
articulation_point.rs
