//==========================================================================
//
// components.h
//
//==========================================================================
// $Id: components.h,v 1.3 2000/03/06 15:16:52 raitner Exp $
#ifndef GTL_COMPONENTS_H
#define GTL_COMPONENTS_H
#include <GTL/GTL.h>
#include <GTL/dfs.h>
#include <list>
__GTL_BEGIN_NAMESPACE
/**
* @short Connected components
*/
class GTL_EXTERN components : public dfs
{
public:
/**
* Creates connected components algorithm object.
*
* @see dfs#dfs
*/
components ();
/**
* Destroys connected components algorithm object.
*
* @see dfs#~dfs
*/
virtual ~components () {}
/**
* Necessary preconditions:
* <ul>
* <li> <code>G</code> is undirected.
* <li> scanning of whole graph is enabled.
* <li> DFS may be applied
* </ul>
*
* @param <code>G</code> graph.
* @return <code>algorithm::GTL_OK</code> if connected components can
* be computed for <code>G</code>.
* @see dfs#scan_whole_graph
*/
virtual int check (graph& G);
/**
* Reset
*/
virtual void reset ();
/**
* @internal
*/
typedef list<pair<list<node>, list<edge> > >::iterator component_iterator;
/**
* Start iteration over all components (if enabled during
* last call to run). Components are represented as a pair consisting of
* a list of nodes and a list of edges,
* i.e. if <code>it</code> is of type <code>component_iterator</code>
* then <code>*it</code> is of type
* <code>pair<list<node>,list<edge> ></code>.
*
* @return iterator to first component
*/
component_iterator components_begin ()
{ return comp.begin(); }
/**
* End of iteration over all components.
*
* @return end of iteration over biconnected components
* @see biconnectivity#store_components
*/
component_iterator components_end ()
{ return comp.end(); }
/**
* Number of components detected during the last run.
*
* @return number of components.
*/
int number_of_components () const
{return num_of_components; }
//-----------------------------------------------------------------------
// Handler used to extend dfs to biconnectivity
//-----------------------------------------------------------------------
/**
* @internal
*/
virtual void before_recursive_call_handler (graph&, edge&, node&);
/**
* @internal
*/
virtual void old_adj_node_handler (graph&, edge&, node&);
/**
* @internal
*/
virtual void new_start_handler (graph&, node&);
protected:
/**
* @internal
*/
int num_of_components;
/**
* @internal
*/
list<pair<list<node>, list<edge> > > comp;
/**
* @internal
*/
component_iterator li;
};
__GTL_END_NAMESPACE
#endif // GTL_BICONNECTIVITY_H
//--------------------------------------------------------------------------
// end of file
//--------------------------------------------------------------------------
Documentation generated by raitner@hyperion on Tue Mar 7 09:40:04 CET 2000
|
Kdoc |