bfs.h

Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file bfs.h

/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   bfs.h
//
//==========================================================================
// $Id: bfs.h,v 1.14 2003/03/24 15:58:54 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

class GTL_EXTERN bfs : public algorithm
{
public:
    
    bfs ();

    virtual ~bfs ();

    int run (graph& G);

    virtual int check (graph& G) { return GTL_OK; }

    virtual void reset ();
    
    //-----------------------------------------------------------------------
    //  Parameters
    //-----------------------------------------------------------------------

    void start_node (const node& n) {start = n;}

    node start_node () const {return start;}

    void scan_whole_graph (bool set) {whole_graph = set;}
    
    bool scan_whole_graph () const {return whole_graph;}

    void calc_level (bool set);
    
    bool calc_level () const {return level_number != 0;}

    void store_non_tree_edges (bool set);

    bool store_non_tree_edges () const {return non_tree != 0;}


    void store_preds (bool set);

    bool store_preds () const {return preds != 0;}

    bool reached (const node& n) const
        {return bfs_number[n] != 0;}

    int bfs_num (const node& n) const 
        {return bfs_number[n];}

    int operator[] (const node& n) const 
        {return bfs_number[n];}

    int level (const node& n) const
        {assert (level_number); return (*level_number)[n];}

    node father (const node& n) const
        {assert (preds); return (*preds)[n];}

    typedef list<edge>::const_iterator tree_edges_iterator;

    tree_edges_iterator tree_edges_begin () const 
        {return tree.begin();}

    tree_edges_iterator tree_edges_end () const
        {return tree.end();}
   
    typedef list<node>::const_iterator bfs_iterator; 

    bfs_iterator begin () const 
        {return bfs_order.begin();}

    bfs_iterator end () const 
        {return bfs_order.end();}

    typedef list<edge>::const_iterator non_tree_edges_iterator;

    non_tree_edges_iterator non_tree_edges_begin () const 
        {assert (non_tree);  return non_tree->begin(); }

    non_tree_edges_iterator non_tree_edges_end () const 
        {assert (non_tree); return non_tree->end(); }
    
    typedef list<bfs_iterator>::const_iterator roots_iterator;

    roots_iterator roots_begin () const 
        {return roots.begin();}

    roots_iterator roots_end () const 
        {return roots.end();}

    int number_of_reached_nodes () const
        {return reached_nodes;}

    //-----------------------------------------------------------------------
    //   Handler
    //-----------------------------------------------------------------------

    virtual void init_handler (graph& G) { };

    virtual void end_handler (graph& G) { };

    virtual void popped_node_handler (graph& G, node& n) { };

    virtual void finished_node_handler (graph& G, node& n) { };

    virtual void unused_node_handler (graph& G, node& n, node& f) { };

    virtual void used_node_handler (graph& G, node& n, node& f) { };

    virtual void new_start_handler (graph& G, node& n) { };

private:

    void bfs_sub (graph&, const node&, edge_map<int>*);

protected:

    //-----------------------------------------------------------------------
    //   Data
    //-----------------------------------------------------------------------
    
    int act_bfs_num;

    deque<node> qu;

    list<node> bfs_order;

    list<edge> tree;

    node_map<int> bfs_number;

    int reached_nodes;
    
    list<bfs_iterator> roots;

    //-----------------------------------------------------------------------
    //   Optional
    //-----------------------------------------------------------------------

    bool whole_graph;

    node start;

    node_map<int>* level_number;

    list<edge>* non_tree;

    node_map<node>* preds;
};

__GTL_END_NAMESPACE

#endif // GTL_BFS_H

//--------------------------------------------------------------------------
//   end of file
//--------------------------------------------------------------------------