dfs.h

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

/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   dfs.h
//
//==========================================================================
// $Id: dfs.h,v 1.25 2003/03/24 15:58:54 raitner Exp $

#ifndef GTL_DFS_H
#define GTL_DFS_H

#include <GTL/GTL.h>
#include <GTL/algorithm.h>

__GTL_BEGIN_NAMESPACE

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


    virtual ~dfs ();
    
    int run (graph& G);

    virtual int check (graph& G);

    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_comp_num (bool set);

    bool calc_comp_num () const {return comp_number != 0;}


    void store_preds (bool set);

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

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

    //---------------------------------------------------------------------
    //   Access 
    //----------------------------------------------------------------------

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

    int dfs_num (const node& n) const 
        {return dfs_number[n];}

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

    int comp_num (const node& n) const
        {assert (comp_number); return (*comp_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 dfs_iterator; 

    dfs_iterator begin () const 
        {return dfs_order.begin();}

    dfs_iterator end () const 
        {return dfs_order.end();}

    typedef list<edge>::const_iterator non_tree_edges_iterator;

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

    non_tree_edges_iterator non_tree_edges_end () const 
        {assert (back_edges); return back_edges->end(); }

    typedef list<dfs_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 - for customization purposes
    //-----------------------------------------------------------------------

    virtual void init_handler (graph& G) {}
    
    virtual void end_handler (graph& G) {}

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

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

    virtual void before_recursive_call_handler (graph& G, edge& e, node& n) {}
    
    virtual void after_recursive_call_handler (graph& G, edge& e, node& n) {}
    
    virtual void old_adj_node_handler (graph& G, edge& e, node& n) {}

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

private:

    void dfs_sub (graph&, node&, node&);

protected:    

    //----------------------------------------------------------------------
    //   Data
    //----------------------------------------------------------------------

    int act_dfs_num;
    int act_comp_num;
    list<edge> tree;
    list<node> dfs_order;
    node_map<int> dfs_number;
    int reached_nodes;
    edge_map<int>* used;
    list<dfs_iterator> roots;
    

    //-----------------------------------------------------------------------
    // Optional 
    //-----------------------------------------------------------------------
    
    node_map<int>* comp_number;
    node_map<node>* preds;
    list<edge>* back_edges;
    node start;
    bool whole_graph;
};

__GTL_END_NAMESPACE

#endif // GTL_DFS_H

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