st_number.h

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

/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   st_number.h
//
//==========================================================================
// $Id: st_number.h,v 1.17 2002/12/20 08:26:08 chris 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

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;
};

class GTL_EXTERN st_number : public algorithm 
{
public:
    st_number() : algorithm()
    {
    }

    virtual ~st_number()
    {
    }
        
    void st_edge(edge e)
    {
        st = e;
    }

    edge st_edge() const
    {
        return st;
    }

    void s_node(node n) 
    {
        s = n;
    }

    node s_node() const
    {
        return s;
    }

    int& operator[](const node& n)
    {
        return st_num[n];
    }
    
    typedef list<node>::iterator iterator;

    typedef list<node>::reverse_iterator reverse_iterator;
        
    iterator begin()
    {
        return st_ord.begin();
    }   

    iterator end()
    {
        return st_ord.end();
    }
        
    reverse_iterator rbegin()
    {
        return st_ord.rbegin();
    }
        
    reverse_iterator rend()
    {
        return st_ord.rend();
    }
        

    int check(graph& G);


    int run(graph& G);


    void reset()
    {
        st_ord.erase (st_ord.begin(), st_ord.end());
    }
protected:
    edge st;

    node s;

    pathfinder* pf;

    list<node> st_ord;

    node_map<int> st_num;
};

__GTL_END_NAMESPACE

#endif // GTL_ST_NUMBER_H

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