gtl/src/biconnectivity.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   biconnectivity.cpp
0005 //
0006 //==========================================================================
0007 // $Id: biconnectivity.cpp,v 1.20 2002/02/28 15:40:52 raitner Exp $
0008
0009 #include <GTL/biconnectivity.h>
0010
0011 #ifdef __GTL_MSVCC
0012 #   ifdef _DEBUG
0013 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
0014 #   error SEARCH NOT ENABLED
0015 #   endif
0016 #   define new DEBUG_NEW
0017 #   undef THIS_FILE
0018     static char THIS_FILE[] = __FILE__;
0019 #   endif   // _DEBUG
0020 #endif  // __GTL_MSVCC
0021
0022 __GTL_BEGIN_NAMESPACE
0023
0024 biconnectivity::biconnectivity () : dfs ()
0025 {
0026     add_edges = false;
0027     store_preds (true);
0028     store_comp = false;
0029     scan_whole_graph(true);
0030     num_of_components = 0;
0031 }
0032
0033 void biconnectivity::reset ()
0034 {
0035     dfs::reset ();
0036
0037     if (store_comp) {
0038     while (!node_stack.empty()) {
0039         node_stack.pop();
0040     }
0041
0042     while (!edge_stack.empty()) {
0043         edge_stack.pop();
0044     }
0045
0046     components.erase (components.begin(), components.end());
0047     }
0048
0049     if (add_edges) {
0050     additional.erase (additional.begin(), additional.end());
0051     }
0052
0053     cut_points.erase (cut_points.begin(), cut_points.end());
0054     num_of_components = 0;
0055 }
0056
0057 int biconnectivity::check (graph& G)
0058 {
0059     return G.is_undirected() && preds &&
0060     dfs::check (G) == GTL_OK ? GTL_OK : GTL_ERROR;
0061 }
0062
0063
0064 //--------------------------------------------------------------------------
0065 //   Handler
0066 //--------------------------------------------------------------------------
0067
0068
0069 void biconnectivity::init_handler (graph& G)
0070 {
0071     if (add_edges) {
0072     dfs D;
0073     D.scan_whole_graph (true);
0074     D.check (G);
0075     D.run (G);
0076
0077     roots_iterator it, end;
0078     it = D.roots_begin();
0079     end = D.roots_end();
0080     start = *(*it);
0081     ++it;
0082
0083     for (; it != end; ++it) {
0084         additional.push_back (G.new_edge (start, *(*it)));
0085     }
0086
0087     first_child.init (G, node());
0088     }
0089
0090     low_num.init (G);
0091     in_component.init(G);
0092     cut_count.init (G, 0);
0093
0094     //
0095     // Detect self loops and hide them.
0096     //
0097
0098     assert (self_loops.empty());
0099     graph::edge_iterator eit = G.edges_begin(),
0100     eend = G.edges_end();
0101
0102     while (eit != eend) {
0103     edge e = *eit;
0104     eit++;
0105     if (e.target() == e.source()) {
0106         self_loops.push_back(e);
0107         G.hide_edge(e);
0108     }
0109     }
0110 }
0111
0112 void biconnectivity::entry_handler (graph& G, node& curr, node& father)
0113 {
0114     if (add_edges) {
0115     if (father != node()) {
0116         if (first_child[father] == node()) {
0117         first_child[father] = curr;
0118         }
0119     }
0120     }
0121
0122     low_num[curr] = dfs_number[curr];
0123 }
0124
0125 void biconnectivity::new_start_handler (graph& G, node& st)
0126 {
0127     cut_count[st] = -1;
0128
0129     //
0130     // If this node has no adjacent edges, we
0131     // must write down the component right here. This is because
0132     // then the method after_recursive_call_handle is never
0133     // executed.
0134     //
0135     // 28/2/2002 MR
0136     //
0137
0138     if (st.degree() == 0) {
0139     ++num_of_components;
0140
0141     if (store_comp) {
0142         component_iterator li = components.insert (
0143         components.end(),
0144         pair<list<node>,list<edge> > (list<node> (), list<edge> ()));
0145
0146         (*li).first.push_back(st);
0147         in_component[st] = li;
0148     }
0149     }
0150 }
0151
0152 void biconnectivity::before_recursive_call_handler (graph& G, edge& e, node& n)
0153 {
0154     if (store_comp) {
0155     node_stack.push (n);
0156     }
0157 }
0158
0159
0160 void biconnectivity::after_recursive_call_handler (graph& G, edge& e, node& n)
0161 {
0162     node curr = n.opposite (e);
0163
0164     if (low_num[n] < low_num[curr]) {
0165     low_num[curr] = low_num[n];
0166     }
0167
0168     if (low_num[n] >= dfs_num(curr)) {
0169     //
0170     // Component found
0171     //
0172
0173     if (store_comp) {
0174         component_iterator li = components.insert (
0175         components.end(),
0176         pair<list<node>,list<edge> > (list<node> (), list<edge> ()));
0177
0178         list<node>& component = (*li).first;
0179         list<edge>& co_edges = (*li).second;
0180
0181         //
0182         // Nodes of biconnected component
0183         //
0184
0185         node tmp = node_stack.top();
0186
0187         while (dfs_num(tmp) >= dfs_num (n)) {
0188         node_stack.pop();
0189         component.push_back (tmp);
0190         in_component[tmp] = li;
0191         if (node_stack.empty()) break;
0192         else tmp = node_stack.top();
0193         }
0194
0195         component.push_back (curr);
0196
0197         //
0198         // edges of biconnected component
0199         //
0200
0201         edge ed = edge_stack.top();
0202
0203         while ((dfs_num(ed.source()) >= dfs_num (n) &&
0204            dfs_num(ed.target()) >= dfs_num (n)) ||
0205            (dfs_num(ed.source()) == dfs_num (curr) &&
0206            dfs_num(ed.target()) >= dfs_num (n)) ||
0207            (dfs_num(ed.source()) >= dfs_num (n) &&
0208            dfs_num(ed.target()) == dfs_num (curr))) {
0209         edge_stack.pop();
0210         co_edges.push_back (ed);
0211         if (edge_stack.empty()) break;
0212         else ed = edge_stack.top();
0213         }
0214     }
0215
0216
0217     ++num_of_components;
0218
0219     //
0220     // curr is cut point; increase counter
0221     //
0222
0223     ++cut_count[curr];
0224
0225     if (add_edges) {
0226         node father = (*preds)[curr];
0227         node first = first_child[curr];
0228
0229         if (father != node() && n == first) {
0230         additional.push_back (G.new_edge (father, first));
0231         }
0232
0233         if (n != first) {
0234         additional.push_back (G.new_edge (n, first));
0235         }
0236     }
0237
0238     }
0239 }
0240
0241 void biconnectivity::old_adj_node_handler (graph& G, edge& e, node& n)
0242 {
0243     node curr = n.opposite (e);
0244
0245     //
0246     // Store backedges at lower endpoint
0247     //
0248
0249    if (store_comp) {
0250        if (dfs_num (curr) > dfs_num (n)) {
0251        edge_stack.push (e);
0252        }
0253     }
0254
0255     if (dfs_num (n) < low_num[curr]) {
0256     low_num[curr] = dfs_number[n];
0257     }
0258 }
0259
0260 void biconnectivity::leave_handler (graph& G, node& n, node& f)
0261 {
0262     if (cut_count[n] > 0) {
0263     cut_points.push_back (n);
0264     }
0265 }
0266
0267 void biconnectivity::end_handler (graph& G)
0268 {
0269     list<edge>::iterator it = self_loops.begin();
0270     list<edge>::iterator end = self_loops.end();
0271
0272     while (it != end) {
0273     G.restore_edge(*it);
0274     if (store_comp) {
0275         node adj = (*it).target();
0276         component_iterator cit = in_component[adj];
0277         (*cit).second.push_back(*it);
0278     }
0279
0280     it = self_loops.erase(it);
0281     }
0282 }
0283
0284 __GTL_END_NAMESPACE
0285
0286 //--------------------------------------------------------------------------
0287 //   end of file
0288 //--------------------------------------------------------------------------