include/GTL/components.h

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   components.h
0005 //
0006 //==========================================================================
0007 // $Id: components.h,v 1.5 2003/04/03 11:44:42 raitner Exp $
0008
0009 #ifndef GTL_COMPONENTS_H
0010 #define GTL_COMPONENTS_H
0011
0012 #include <GTL/GTL.h>
0013 #include <GTL/dfs.h>
0014
0015 #include <list>
0016
0017 __GTL_BEGIN_NAMESPACE
0018 /**
0019  * @brief Connected components algorithm
0020  */
0021 class GTL_EXTERN components : public dfs
0022 {
0023 public:
0024     /**
0025      * @brief Creates connected components algorithm object.
0026      *
0027      * @sa dfs::dfs
0028      */
0029     components ();
0030
0031     /**
0032      * @brief Destroys connected components algorithm object.
0033      *
0034      * @sa dfs::~dfs
0035      */
0036     virtual ~components () {}
0037
0038     /**
0039      * @brief Checks whether the connected components algorithm can be applied
0040      *
0041      * Necessary preconditions:
0042      * - G is undirected.
0043      * - scanning of whole graph is enabled.
0044      * - DFS may be applied
0045      *
0046      * @param G graph.
0047      * @return algorithm::GTL_OK if connected components can be computed for G.
0048      * @sa dfs::scan_whole_graph
0049      */
0050     virtual int check (graph& G);
0051
0052     virtual void reset ();
0053
0054     /**
0055      * @internal
0056      */
0057     typedef list<pair<list<node>, list<edge> > >::iterator component_iterator;
0058
0059     /**
0060      * @brief Start iteration over all components (if enabled during
0061      * last call to run).
0062
0063      * Components are represented as a pair consisting of
0064      * a list of nodes and a list of edges,
0065      * i.e. if @c it is of type @c component_iterator
0066      * then @c *it is of type
0067      * @c pair&lt;list&lt;node&gt;,list&lt;edge&gt;&nbsp;&gt;.
0068      *
0069      * @return iterator to first component
0070      */
0071     component_iterator components_begin ()
0072     { return comp.begin(); }
0073
0074
0075     /**
0076      * @brief End of iteration over all components.
0077      *
0078      * @return end of iteration over biconnected components
0079      * @sa biconnectivity::store_components
0080      */
0081     component_iterator components_end ()
0082     { return comp.end(); }
0083
0084     /**
0085      * @brief Number of components detected during the last run.
0086      *
0087      * @return number of components.
0088      */
0089     int number_of_components () const
0090     {return num_of_components; }
0091
0092     //-----------------------------------------------------------------------
0093     //   Handler used to extend dfs to biconnectivity
0094     //-----------------------------------------------------------------------
0095     /**
0096      * @internal
0097      */
0098     virtual void before_recursive_call_handler (graph&, edge&, node&);
0099
0100     /**
0101      * @internal
0102      */
0103     virtual void old_adj_node_handler (graph&, edge&, node&);
0104
0105     /**
0106      * @internal
0107      */
0108     virtual void new_start_handler (graph&, node&);
0109
0110
0111 protected:
0112
0113     /**
0114      * @internal
0115      */
0116     int num_of_components;
0117     /**
0118      * @internal
0119      */
0120     list<pair<list<node>, list<edge> > > comp;
0121     /**
0122      * @internal
0123      */
0124     component_iterator li;
0125 };
0126
0127 __GTL_END_NAMESPACE
0128
0129 #endif // GTL_BICONNECTIVITY_H
0130
0131 //--------------------------------------------------------------------------
0132 //   end of file
0133 //--------------------------------------------------------------------------