//==========================================================================
//
// bfs.h
//
//==========================================================================
// $Id: bfs.h,v 1.10 2000/01/05 16:32:33 raitner Exp $
#ifndef GTL_BFS_H
#define GTL_BFS_H
#include <GTL/GTL.h>
#include <GTL/algorithm.h>
#include <GTL/node_map.h>
#include <deque>
__GTL_BEGIN_NAMESPACE
/**
* @short Breadth-First-Search (BFS) algorithm.
*
* Encapsulates the BFS-algorithm together with all data produced
* by it. There are a few parameters, which on the one hand
* influence the behaviour of BFS (e.g. start-node) and on the other
* hand toggle the storing of extra information, such as the
* level-number of each node. In detail these are:
*
* <ul>
* <li> @ref bfs#start_node
* (default: an arbitrary node will be chosen)
* <li> @ref bfs#scan_whole_graph states whether BFS will be
* continued in the unused part of the graph, if not all
* nodes were touched at the end of BFS started at the start-node.
* (default: disabled)
* <li> @ref bfs#calc_level toggle storing of level-numbers for each
* node, i.e. its distance from the start-node.
* (default: disabled)
* <li> @ref bfs#store_preds toggle storing the predecessor of each
* node, i.e. the father in the BFS-tree. (default: disabled)
* <li> @ref bfs#store_non_tree_edges toggle storing of all non_tree_edges
* (tree_edges are always stored) in a list and thus enable or disable
* iteration through all non_tree_edges.
* (default: disabled)
* </ul>
*
* <p>
* Please note that the algorithm always starts with the given
* start-node (if none was given, the first node is chosen and
* stored, thus after BFS the root of the tree is always
* accesible via @ref bfs#start_node) and continues until no more
* unused nodes are reachable from already used ones.
* Thus if the graph isn't connected not all nodes will be reached. If
* @ref bfs#scan_whole_graph isn't set the BFS stops here.
* If it is set, the BFS will be continued with the next unused
* node and so on until all nodes were used.
*
* <p>
* For further customization a few virtual functions, so called handler,
* are called at crucial stages of the algorithm. In this basic
* implementation all of these handler are empty. So if one wants
* to add only a few lines of code (e.g. some new numbering) he is likely
* to take this class as base-class and override the handler
* where neccessary. In detail these are (please look at the
* source code to see where they are called):
*
* <ul>
* <li> @ref bfs#init_handler
* <li> @ref bfs#end_handler
* <li> @ref bfs#popped_node_handler
* <li> @ref bfs#finished_node_handler
* <li> @ref bfs#unused_node_handler
* <li> @ref bfs#used_node_handler
* <li> @ref bfs#new_start_handler
* </ul>
*
* <p>
* <em>Please note:</em> We do <em>not</em> claim that the set of
* handler provided is sufficient in any way. So if you believe
* that some new handler is needed urgently please let us know.
*
* <p>
* There is a lot of information stored during BFS (e.g. nodes in
* bfs-order, list of non-tree edges). Some of it can be obtained directly
* by using the corresponding member-function (e.g. @ref bfs#bfs_num),
* but all information that can be thought of as a list (e.g. nodes in
* bfs-order) can be accessed through iterators. In detail these are (of
* course depending on what options are chosen!):
*
* <ul>
* <li> @ref bfs#bfs_iterator
* <li> @ref bfs#tree_edges_iterator
* <li> @ref bfs#non_tree_edges_iterator
* <li> @ref bfs#roots_iterator
* </ul>
*/
class GTL_EXTERN bfs : public algorithm
{
public:
//-----------------------------------------------------------------------
// algorithm -- Interface
//-----------------------------------------------------------------------
/**
* Default constructor. Options default like described above.
*
* @see algorithm#algorithm
*/
bfs ();
/**
* Destructor.
*
* @see algorithm#~algorithm
*/
virtual ~bfs ();
/**
* Performs BFS.
*
* @param <code>G</code> graph.
* @return <code>algorithm::GTL_OK</code> on success,
* <code>algorithm::GTL_ERROR</code> otherwise.
* @see algorithm#run
*/
int run (graph& G);
/**
* Checks whether the preconditions for BFS are satisfied.
*
* @param <code>G</code> graph.
* @return <code>algorithm::GTL_OK</code> on success,
* <code>algorithm::GTL_ERROR</code> otherwise.
* @see algorithm#check
*/
virtual int check (graph& G) { return GTL_OK; }
/**
* Reset.
*
* @see algorithm#reset
*/
virtual void reset ();
//-----------------------------------------------------------------------
// Parameters
//-----------------------------------------------------------------------
/**
* Sets start-node for BFS. The default start-node is the invalid node
* <code>node()</code>, in this case an arbitrary node is chosen and
* stored when BFS is run.
*
* @param <code>n</code> start-node.
*/
void start_node (const node& n) {start = n;}
/**
* Returns actual start-node for BFS.
*
* @return start-node.
*/
node start_node () const {return start;}
/**
* Enables or disables scanning of the whole graph.
* If enabled and the BFS
* started at the given start-node stops without having touched all nodes,
* it will be continued with the next unused node, and so on until all
* nodes were used. This makes sure that for every node bfs_number is
* defined.
*
* <p>
* On the other hand, if this feature is disabled, one will be able to
* check what nodes can be reached, when starting a BFS at the
* start-node, because for those not reached bfs-number will be 0.
*
* @param <code>set</code> if true enable scanning the whole graph.
* @see bfs#roots_begin
* @see bfs#roots_end
*/
void scan_whole_graph (bool set) {whole_graph = set;}
/**
* Returns true iff the whole graph will be scanned.
*
* @return true iff the whole graph will be scanned.
* @see bfs#roots_begin
* @see bfs#roots_end
*/
bool scan_whole_graph () const {return whole_graph;}
/**
* Enables or disables the calculation of level-numbers for each
* node. If enabled each node gets a level-number meaning its distance
* from the start-node.
*
* @param <code>set</code> if true level-number will be calculated.
* @see bfs#level
*/
void calc_level (bool set);
/**
* Returns true iff level-numbers will be calculated.
*
* @return true iff level-numbers will be calculated.
* @see bfs#level
*/
bool calc_level () const {return level_number != 0;}
/**
* Enables the storing of non-tree-edges. If enabled the list of
* non-tree-edges can be traversed in the order they occured using
* <code>back_edges_iterator</code>
*
* @param <code>set</code> if true back_edges will be stored.
* @see bfs#non_tree_edges_begin
* @see bfs#non_tree_edges_end
*/
void store_non_tree_edges (bool set);
/**
* Returns true iff the storing of non-tree-edges is enabled.
*
* @return true iff the storing of non-tree-edges is enabled.
* @see bfs#non_tree_edges_begin
* @see bfs#non_tree_edges_end
*/
bool store_non_tree_edges () const {return non_tree != 0;}
/**
* Enables or disables the storing of predecessors. If enabled for
* every node the predecessor in BFS will be stored.
*
* @param <code>set</code> if true predecessors will be stored.
* @see bfs#father
*/
void store_preds (bool set);
/**
* Returns true iff the storing of predecessors is enabled.
*
* @return true iff the storing of predecessors is enabled.
* @see bfs#father
*/
bool store_preds () const {return preds != 0;}
//----------------------------------------------------------------------
// Access
//----------------------------------------------------------------------
/**
* Checks whether node <code>n</code> was reached in BFS.
*
* @param <code>n</code> node to be checked.
* @return true iff <code>n</code> was reached.
*/
bool reached (const node& n) const
{return bfs_number[n] != 0;}
/**
* BFS-Number of <code>n</code>. Please note that BFS-Number 0 means
* that this node wasn't reached.
*
* @param <code>n</code> node.
* @return BFS-Number of <code>n</code>.
*/
int bfs_num (const node& n) const
{return bfs_number[n];}
/**
* BFS-Number of <code>n</code>. Please note that BFS-Number 0 means
* that this node wasn't reached.
*
* @param <code>n</code> node.
* @return BFS-Number of <code>n</code>.
*/
int operator[] (const node& n) const
{return bfs_number[n];}
/**
* Returns level-number of node <code>n</code>, if enabled during last
* run.
*
* @param <code>n</code> node.
* @return level-number of <code>n</code>.
* @see bfs#calc_level
*/
int level (const node& n) const
{assert (level_number); return (*level_number)[n];}
/**
* Returns father of node <code>n</code> in BFS-forest. If
*<<code>n</code> is a root
* in the forest or wasn't reached the return
* value is <code>node()</code>.
*
* @param <code>n</code> node.
* @return Father of <code>n</code>.
* @see bfs#store_preds
*/
node father (const node& n) const
{assert (preds); return (*preds)[n];}
/**
* @internal
*/
typedef list<edge>::const_iterator tree_edges_iterator;
/**
* Iterate through all edges picked in last BFS. Please note that this
* edges not always form a tree. In case the graph is not (strongly)
* connected and the whole graph was scanned, they form a forest.
*
* @return start for iteration through all edges followed in BFS.
*/
tree_edges_iterator tree_edges_begin () const
{return tree.begin();}
/**
* End-Iterator for iteration through all edges picked in last BFS.
*
* @return end for iteration through all edges followed in BFS.
*/
tree_edges_iterator tree_edges_end () const
{return tree.end();}
/**
* @internal
*/
typedef list<node>::const_iterator bfs_iterator;
/**
* Iterate through all (reached) nodes in BFS-Order.
*
* @return start for iteration through all nodes in BFS-order.
*/
bfs_iterator begin () const
{return bfs_order.begin();}
/**
* End-Iterator for iteration through all (reached) nodes in BFS-Order.
*
* @return end for iteration through all (reached) nodes
*/
bfs_iterator end () const
{return bfs_order.end();}
/**
* @internal
*/
typedef list<edge>::const_iterator non_tree_edges_iterator;
/**
* Iterate through all non_tree_edges (if enabled).
*
* @return start for iteration through all non-tree-edges.
* @see bfs#store_non_tree_edges
*/
non_tree_edges_iterator non_tree_edges_begin () const
{assert (non_tree); return non_tree->begin(); }
/**
* End-iterator for iteration through all non-tree-edges (if enabled).
*
* @return end for iteration through all non-tree-edges.
* @see bfs#store_non_tree_edges
*/
non_tree_edges_iterator non_tree_edges_end () const
{assert (non_tree); return non_tree->end(); }
/**
* @internal
*/
typedef list<bfs_iterator>::const_iterator roots_iterator;
/**
* Iterator pointing towards the first root in the BFS-forest.
* <em>Please note</em> that intstead of pointing directly towards the node
* (i.e. <code>*it</code> is of type node) the iterator points towards
* a bfs-iterator, which represents the root (i.e. <code>*it</code>
* is of type <code>bfs_iterator</code>).
*
* <p>Using this technique
* makes it possible not only to obtain all the roots in the forest,
* but also the whole trees associated with each one. This can be achieved
* because a <code>root_iterator</code> specifies the exact position of
* the root in the BFS-ordering and by definition of BFS all the descendents of
* the root, i.e. the whole tree below, will come later in BFS, such that by
* incrementing the <code>bfs_iterator</code>, a
* <code>roots_iterator</code> refers to,
* one can traverse the whole tree with this given root.
*
* <p>Of course if the root isn't the last node in the
* BFS-forest all following trees will be traversed, too.
* But since the first node of such
* a tree, that will be discovered, is its root, the successor of the
* <code>roots_iterator</code> can be used as end-iterator.
*
* @return start for iteration through all roots in BFS-forest.
* @see bfs#scan_whole_graph
*/
roots_iterator roots_begin () const
{return roots.begin();}
/**
* Iterator pointing to the end of all roots.
*
* @return end for iteration through all roots in BFS-forest.
* @see bfs#scan_whole_graph
*/
roots_iterator roots_end () const
{return roots.end();}
/**
* Number of nodes reached in last DFS.
*
* @return number of reached nodes.
* @see bfs#scan_whole_graph
*/
int number_of_reached_nodes () const
{return reached_nodes;}
//-----------------------------------------------------------------------
// Handler
//-----------------------------------------------------------------------
/**
* Called at the start of BFS.
*
* @param <code>G</code> graph for which BFS was invoked.
*/
virtual void init_handler (graph& G) { };
/**
* Called right before the end of BFS.
*
* @param <code>G</code> graph for which BFS was invoked.
*/
virtual void end_handler (graph& G) { };
/**
* Called after a node was taken out of the queue.
*
* @param <code>G</code> graph for which BFS was invoked.
* @param <code>n</code> node taken out of the queue.
*/
virtual void popped_node_handler (graph& G, node& n) { };
/**
* Called when finished with the actual node, i.e. after
* looking at all its neighbours.
*
* @param <code>G</code> graph for which BFS was invoked.
* @param <code>n</code> node taken out of the queue.
*/
virtual void finished_node_handler (graph& G, node& n) { };
/**
* Called when an unused node was found.
*
* @param <code>G</code> graph for which BFS was invoked.
* @param <code>n</code> unused node.
* @param <code>f</code> actual node.
*/
virtual void unused_node_handler (graph& G, node& n, node& f) { };
/**
* Called when an used node was found.
*
* @param <code>G</code> graph for which BFS was invoked.
* @param <code>n</code> used node.
* @param <code>f</code> actual node.
*/
virtual void used_node_handler (graph& G, node& n, node& f) { };
/**
* Called when BFS is started with start-node
* <code>n</code>. This is particularly useful when
* BFS was invoked with the <code>scan_whole_graph</code>
* option.
*
* @param <code>G</code> graph for which BFS was invoked.
* @param <code>n</code> start-node.
*/
virtual void new_start_handler (graph& G, node& n) { };
private:
void bfs_sub (graph&, const node&, edge_map<int>*);
protected:
//-----------------------------------------------------------------------
// Data
//-----------------------------------------------------------------------
/**
* @internal
*/
int act_bfs_num;
/**
* @internal
*/
deque<node> qu;
/**
* @internal
*/
list<node> bfs_order;
/**
* @internal
*/
list<edge> tree;
/**
* @internal
*/
node_map<int> bfs_number;
/**
* @internal
*/
int reached_nodes;
/**
* @internal
*/
list<bfs_iterator> roots;
//-----------------------------------------------------------------------
// Optional
//-----------------------------------------------------------------------
/**
* @internal
*/
bool whole_graph;
/**
* @internal
*/
node start;
/**
* @internal
*/
node_map<int>* level_number;
/**
* @internal
*/
list<edge>* non_tree;
/**
* @internal
*/
node_map<node>* preds;
};
__GTL_END_NAMESPACE
#endif // GTL_BFS_H
//--------------------------------------------------------------------------
// end of file
//--------------------------------------------------------------------------
Documentation generated by raitner@hyperion on Tue Mar 7 09:40:04 CET 2000
|
Kdoc |