//==========================================================================
//
// st_number.h
//
//==========================================================================
// $Id: st_number.h,v 1.13 2000/01/05 16:32:40 raitner Exp $
#ifndef GTL_ST_NUMBER_H
#define GTL_ST_NUMBER_H
#include <GTL/GTL.h>
#include <GTL/graph.h>
#include <GTL/node_map.h>
#include <GTL/edge_map.h>
#include <GTL/algorithm.h>
#include <list>
#include <utility>
__GTL_BEGIN_NAMESPACE
/**
* @internal
*/
class GTL_EXTERN pathfinder
{
public:
//--------------------------------------------------------- CONSTRUCTOR
pathfinder (const graph& G, edge st, node s);
bool is_valid ()
{ return is_biconn; }
//--------------------------------------------------------- ITERATOR
class const_iterator
{
public:
const_iterator (pathfinder& _pf) : pf (_pf) { }
const_iterator (pathfinder& _pf, node n);
const_iterator& operator++();
const_iterator operator++(int);
const node& operator*() const
{ return curr; }
bool operator== (const const_iterator& it)
{return curr == it.curr; }
bool operator!= (const const_iterator& it)
{return curr != it.curr; }
private:
enum iteration_state {END, UP, DOWN};
iteration_state state;
node curr;
pathfinder& pf;
};
const_iterator path (node n)
{ return const_iterator (*this, n); }
const_iterator end ()
{ return const_iterator (*this); }
private:
//--------------------------------------------------------- FUNCTIONS
void dfs_sub (node&, node&);
//--------------------------------------------------------- MEMBERS
node_map<int> dfs_num;
node_map<int> low_num;
node_map<list<edge> > tree;
node_map<list<edge> > back;
node_map<list<edge> > forward;
node_map<list<edge>::iterator> to_low;
node_map<list<edge>::iterator> to_father;
typedef pair<list<edge>::iterator, list<edge>::iterator> pos_pair;
edge_map<pos_pair > pos;
node_map<int> used;
int act_dfs_num;
int new_nodes;
bool is_biconn;
friend class const_iterator;
};
/**
* @short ST-number algorithm.
*
* Encapsulates the st-number algorithm together with all the data produced by it.
* <p>
* Assigns an integer <code>st[n]</code> to each node <code>n</code> of a undirected,
* biconnected graph, such that each node is connected with at least one node having
* a smaller and with at least one having a larger number than itself. The only
* exception to this rule are the endpoints of edge <code>st</code> connecting nodes
* <code>s</code> (st-number 1) and <code>t</code> (highest st-number)
* <p>
* The following options are supported:
*
* <ul>
* <li> @ref st_number#st_edge sets/retrieves the edge that connects the node
* with the lowest number to that with the highest.
* <li> @ref st_number#s_node sets/retrieves that endpoints of the
* @ref st_number#st_edge, which gets number 1.
* </ul>
*
*/
class GTL_EXTERN st_number : public algorithm
{
public:
/**
* Creates st-number object. Please note that there are no reasonable
* default settings for the parameters, i.e. the edge <code>st</code>
* connecting the lowest with highest numbers node and which of its
* endpoints should get number 1 (= node <code>s</code>) has to be specified
* always.
*/
st_number () : algorithm () { };
/**
* Destructor
*/
virtual ~st_number () { };
/**
* Sets edge <code>st</code> for the next run.
*
* @param <code>e</code> edge <code>st</code>
*/
void st_edge (edge e)
{ st = e; }
/**
* Get edge <code>st</code>.
*
* @return edge <code>st</code>.
*/
edge st_edge () const
{ return st; }
/**
* Sets node <code>s</code> for next run. This must be one of the endpoints
* of edge <code>st</code>. This node will get st-number 1 and thus the other
* endpoint will get the highest st-number.
*
* @param <code>n</code> node <code>s</code>
*/
void s_node (node n)
{ s = n; }
/**
* Get node <code>s</code>
*
* @return node <code>s</code>
*/
node s_node () const
{ return s; }
/**
* Returns st-number of node <code>n</code> as determined in the last run.
*
* @param <code>n</code> node
* @return st-number of <code>n</code>
*/
int& operator[](const node& n)
{ return st_num[n]; }
/**
* @internal
*/
typedef list<node>::iterator iterator;
/**
* @internal
*/
typedef list<node>::reverse_iterator reverse_iterator;
/**
* Iteration through the nodes of graph st-numbered in last
* run in st-number order, i.e. from 1 to highest st-number.
*
* @return start of iteration through nodes in st-number order
*/
iterator begin() {
return st_ord.begin();
}
/**
* Iteration through nodes of graph in st-number order
*
* @return end of iteration through nodes of graph in st-number order
*/
iterator end() {
return st_ord.end();
}
/**
* Iteration through the nodes of graph st-numbered in last
* run in reverse st-number order, i.e. from highest st-number down to 1.
*
* @return start of iteration through nodes in reverse st-number order
*/
reverse_iterator rbegin() {
return st_ord.rbegin();
}
/**
* End of iteration through nodes of graph in reverse st-number order
*
* @return end of iteration through nodes in reverse st-number order
*/
reverse_iterator rend() {
return st_ord.rend();
}
/**
* Checks whether st-number algorithm can be applied to <code>G</code>.
* Besides from the trivial preconditions that edge <code>st</code> and
* node <code>s</code> lie in <code>G</code> and <code>s</code> is really
* an endpoint of <code>st</code> (which isn't checked), <code>G</code>
* must be undirected and biconnected. Note: As for all algorithms in GTL,
* <code>check</code> must be called, because it might do some
* initialization.
*
* @param <code>G</code> graph
* @return <code>GTL_OK</code> iff st-number algorithm may be applied
* @see algorithm#check
*/
int check (graph& G);
/**
* Runs st-number algorithm on graph <code>G</code>. It is assumed that
* <code>check</code> was called previously and returned <code>GTL_OK</code>.
*
* @param <code>G</code> graph
* @return <code>GTL_OK</code> iff <code>G</code> could be correctly st-numbered
* @see algorithm#run
*/
int run (graph& G);
/**
* Resets algorithm in order to be applied to the next graph. This will delete
* most of the information obtained in the last run.
*
* @see algorithm#reset
*/
void reset () {
st_ord.erase (st_ord.begin(), st_ord.end());
}
protected:
/**
* @internal
*/
edge st;
/**
* @internal
*/
node s;
/**
* @internal
*/
pathfinder* pf;
/**
* @internal
*/
list<node> st_ord;
/**
* @internal
*/
node_map<int> st_num;
};
__GTL_END_NAMESPACE
#endif // GTL_ST_NUMBER_H
//--------------------------------------------------------------------------
// end of file
//--------------------------------------------------------------------------
Documentation generated by raitner@hyperion on Tue Mar 7 09:40:04 CET 2000
|
Kdoc |