include/GTL/biconnectivity.h

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   biconnectivity.h
0005 //
0006 //==========================================================================
0007 // $Id: biconnectivity.h,v 1.18 2003/03/26 13:37:14 raitner Exp $
0008
0009 #ifndef GTL_BICONNECTIVITY_H
0010 #define GTL_BICONNECTIVITY_H
0011
0012 #include <GTL/GTL.h>
0013 #include <GTL/dfs.h>
0014
0015 #include <list>
0016 #include <stack>
0017
0018 __GTL_BEGIN_NAMESPACE
0019
0020 /**
0021  * $Date: 2003/03/26 13:37:14 $
0022  * $Revision: 1.18 $
0023  *
0024  * @brief Biconnectivity-test and low-numbers.
0025  *
0026  * Obviously there is a close relationship between DFS and the testing of
0027  * biconnectivity. Thus this test takes advantage of the possibility to
0028  * add pieces of code to the DFS-class in order to calculate the
0029  * low-numbers.
0030  *
0031  * As default no biconnected components will be stored and no edges
0032  * will be added to make the graph biconnected. The test will run on the
0033  * whole graph, even if it is not connected.
0034  */
0035
0036 class GTL_EXTERN biconnectivity : public dfs
0037 {
0038 public:
0039     /**
0040      * @brief Creates biconnectivity algorithm object.
0041      *
0042      * @see dfs::dfs
0043      */
0044     biconnectivity ();
0045
0046     /**
0047      * @brief Destroys biconnectivity algorithm object.
0048      *
0049      * @see dfs::~dfs
0050      */
0051     virtual ~biconnectivity () {}
0052
0053     /**
0054      * @brief Checks whether the algorithm can be applied.
0055      *
0056      * Necessary preconditions:
0057      *   - G is undirected.
0058      *   - storing of predecessors is enabled.
0059      *   - DFS may be applied
0060      *
0061      * @param G graph.
0062      * @return algorithm::GTL_OK if binconnectivity-test can
0063      * be applied to @a G.
0064      * @sa dfs::scan_whole_graph, dfs::store_preds
0065      */
0066     virtual int check (graph& G);
0067
0068     virtual void reset ();
0069
0070     /**
0071      * @brief low-number.
0072      *
0073      * @param n node.
0074      * @return low-number of n.
0075      */
0076     int low_number (const node& n) const
0077     {return low_num[n];}
0078
0079     /**
0080      * @brief Biconnectivity-test.
0081      *
0082      * @return true iff graph is biconnected.
0083      */
0084     bool is_biconnected () const
0085     {return num_of_components == 1;}
0086
0087     /**
0088      * @brief Returns whether the storing of components is enabled.
0089      *
0090      * @return true iff storing of components is enabled.
0091      * @sa biconnectivity::components_begin, biconnectivity::components_end
0092      */
0093     bool store_components () const
0094     { return store_comp; }
0095
0096     /**
0097      * @brief Enables or disables the storing of biconnected components.
0098      *
0099      * If this feature is enabled, the whole graph will be scanned
0100      * in order to get all the biconnected components even if the graph
0101      * isn't connected. By default this feature is disabled.
0102      *
0103      * @param set if true each biconnected component will be stored.
0104      * @sa biconnectivity::components_begin, biconnectivity::components_end
0105      */
0106     void store_components (bool set)
0107     { store_comp  = set; if (set) scan_whole_graph (set); }
0108
0109     /**
0110      * @brief If enabled edges will be added to the graph in order to make it
0111      * biconnected, if cutpoints are discovered.
0112      *
0113      * The list of added edges can be accessed via additional_begin and
0114      * additional_end.
0115      *
0116      * @param set if true additional edges will we inserted
0117      *    to make the graph biconnected.
0118      * @sa biconnectivity::additional_begin, biconnectivity::additional_end
0119      */
0120     void make_biconnected (bool set)
0121     { add_edges = set; if (set) scan_whole_graph (set); }
0122
0123     /**
0124      * @brief Returns whether addition of edges neccessary to make graph
0125      * biconnected is enabled.
0126      *
0127      * @return true iff addition edges is enabled.
0128      * @sa biconnectivity::additional_begin, biconnectivity::additional_end
0129      */
0130     bool make_biconnected () const
0131     { return add_edges; }
0132
0133     /**
0134      * @brief Begin of edges added to make graph biconnected.
0135      *
0136      * @return begin of additional edges
0137      * @sa biconnectivity::make_biconnected
0138      */
0139     list<edge>::iterator additional_begin ()
0140     { return additional.begin (); }
0141
0142     /**
0143      * @brief End of edges added to make graph biconnected
0144      *
0145      * @return end of additional edges
0146      * @sa biconnectivity::make_biconnected
0147      */
0148     list<edge>::iterator additional_end ()
0149     { return additional.end (); }
0150
0151     /**
0152      * @internal
0153      */
0154     typedef list<node>::iterator cutpoint_iterator;
0155
0156     /**
0157      * @brief Start iteration over all cutpoints found.
0158      *
0159      * A cutpoints is a node whose removal will disconnect the graph,
0160      * thus a graph with no cutpoints is biconnected and vice versa.
0161      *
0162      * @return iterator to first cutpoint.
0163      * @sa biconnectivity::cut_points_end
0164      */
0165     cutpoint_iterator cut_points_begin ()
0166     { return cut_points.begin(); }
0167
0168     /**
0169      * @brief End of iteration over all cutpoints.
0170      *
0171      * @return one-past-the-end iterator.
0172      * @sa biconnectivity::cut_points_begin
0173      */
0174     cutpoint_iterator cut_points_end ()
0175     { return cut_points.end(); }
0176
0177
0178     /**
0179      * @internal
0180      */
0181     typedef list<pair<list<node>, list<edge> > >::iterator component_iterator;
0182
0183     /**
0184      * @brief Start iteration over all biconnected components (if enabled during
0185      * last call to run).
0186      *
0187      * Components are represented as a pair consisting of
0188      * a list of nodes and a list of edges,
0189      * i.e. if it is of type component_iterator
0190      * then *it is of type
0191      * pair&lt;list&lt;node&gt;,list&lt;edge&gt; &gt;.
0192      *
0193      * @return iterator to first component
0194      * @sa biconnectivity::store_components
0195      */
0196     component_iterator components_begin ()
0197     { return components.begin(); }
0198
0199
0200     /**
0201      * @brief End of iteration over all biconnected components.
0202      *
0203      * @return end of iteration over biconnected components
0204      * @sa biconnectivity::store_components
0205      */
0206     component_iterator components_end ()
0207     { return components.end(); }
0208
0209     /**
0210      * @brief Number von biconnected components detected during the last run.
0211      *
0212      * @return number of biconnected components.
0213      */
0214     int number_of_components () const
0215     {return num_of_components; }
0216
0217     //-----------------------------------------------------------------------
0218     //   Handler used to extend dfs to biconnectivity
0219     //-----------------------------------------------------------------------
0220     /**
0221      * @internal
0222      */
0223     virtual void init_handler (graph&);
0224
0225     /**
0226      * @internal
0227      */
0228     virtual void entry_handler (graph&, node&, node&);
0229
0230     /**
0231      * @internal
0232      */
0233     virtual void before_recursive_call_handler (graph&, edge&, node&);
0234
0235     /**
0236      * @internal
0237      */
0238     virtual void after_recursive_call_handler (graph&, edge&, node&);
0239
0240     /**
0241      * @internal
0242      */
0243     virtual void old_adj_node_handler (graph&, edge&, node&);
0244
0245     /**
0246      * @internal
0247      */
0248     virtual void new_start_handler (graph&, node&);
0249
0250     /**
0251      * @internal
0252      */
0253     virtual void leave_handler (graph&, node&, node&);
0254
0255     /**
0256      * @internal
0257      */
0258     virtual void end_handler (graph&);
0259
0260
0261 protected:
0262     /**
0263      * @internal
0264      */
0265     list<edge> self_loops;
0266
0267     /**
0268      * @internal
0269      */
0270     node_map<component_iterator> in_component;
0271
0272     /**
0273      * @internal
0274      */
0275     node_map<int> low_num;
0276     /**
0277      * @internal
0278      */
0279     int num_of_components;
0280     /**
0281      * @internal
0282      */
0283     bool store_comp;
0284     /**
0285      * @internal
0286      */
0287     bool add_edges;
0288     /**
0289      * @internal
0290      */
0291     node last;
0292     /**
0293      * @internal
0294      */
0295     stack<node> node_stack;
0296     /**
0297      * @internal
0298      */
0299     stack<edge> edge_stack;
0300     /**
0301      * @internal
0302      */
0303     list<pair<list<node>, list<edge> > > components;
0304     /**
0305      * @internal
0306      */
0307     list<node> cut_points;
0308     /**
0309      * @internal
0310      */
0311     node_map<int> cut_count;
0312     /**
0313      * @internal
0314      */
0315     list<edge> additional;
0316     /**
0317      * @internal
0318      */
0319     node_map<node> first_child;
0320 };
0321
0322 __GTL_END_NAMESPACE
0323
0324 #endif // GTL_BICONNECTIVITY_H
0325
0326 //--------------------------------------------------------------------------
0327 //   end of file
0328 //--------------------------------------------------------------------------