biconnectivity.h

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

/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   biconnectivity.h
//
//==========================================================================
// $Id: biconnectivity.h,v 1.18 2003/03/26 13:37:14 raitner Exp $

#ifndef GTL_BICONNECTIVITY_H
#define GTL_BICONNECTIVITY_H

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

#include <list>
#include <stack>

__GTL_BEGIN_NAMESPACE

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

    virtual ~biconnectivity () {}

    virtual int check (graph& G);

    virtual void reset ();

    int low_number (const node& n) const 
        {return low_num[n];}

    bool is_biconnected () const 
        {return num_of_components == 1;}

    bool store_components () const
        { return store_comp; }

    void store_components (bool set) 
        { store_comp  = set; if (set) scan_whole_graph (set); }
    
    void make_biconnected (bool set) 
        { add_edges = set; if (set) scan_whole_graph (set); }
    
    bool make_biconnected () const 
        { return add_edges; }
    
    list<edge>::iterator additional_begin ()
        { return additional.begin (); }

    list<edge>::iterator additional_end ()
        { return additional.end (); }
    
    typedef list<node>::iterator cutpoint_iterator;

    cutpoint_iterator cut_points_begin () 
        { return cut_points.begin(); }

    cutpoint_iterator cut_points_end () 
        { return cut_points.end(); }


    typedef list<pair<list<node>, list<edge> > >::iterator component_iterator;

    component_iterator components_begin ()
        { return components.begin(); }


    component_iterator components_end ()
        { return components.end(); }

    int number_of_components () const
        {return num_of_components; }

    //-----------------------------------------------------------------------
    //   Handler used to extend dfs to biconnectivity
    //-----------------------------------------------------------------------
    virtual void init_handler (graph&);

    virtual void entry_handler (graph&, node&, node&);

    virtual void before_recursive_call_handler (graph&, edge&, node&);

    virtual void after_recursive_call_handler (graph&, edge&, node&);

    virtual void old_adj_node_handler (graph&, edge&, node&);

    virtual void new_start_handler (graph&, node&);    

    virtual void leave_handler (graph&, node&, node&);    

    virtual void end_handler (graph&);    


protected:
    list<edge> self_loops;

    node_map<component_iterator> in_component;

    node_map<int> low_num;
    int num_of_components;
    bool store_comp;
    bool add_edges;
    node last;
    stack<node> node_stack;
    stack<edge> edge_stack;
    list<pair<list<node>, list<edge> > > components;
    list<node> cut_points;
    node_map<int> cut_count;
    list<edge> additional;
    node_map<node> first_child;
};

__GTL_END_NAMESPACE

#endif // GTL_BICONNECTIVITY_H

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