planarity.h

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

/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   planarity.h
//
//==========================================================================
// $Id: planarity.h,v 1.22 2008/02/03 18:17:08 chris Exp $

#ifndef PLANARITY_H
#define PLANARITY_H

#include <GTL/GTL.h>
#include <GTL/graph.h>
#include <GTL/algorithm.h>
#include <GTL/st_number.h>
#include <GTL/embedding.h>
#include <GTL/biconnectivity.h>
#include <GTL/pq_node.h>

__GTL_BEGIN_NAMESPACE

class GTL_EXTERN planarity : public algorithm 
{
public:
    planarity();
    
    ~planarity();

    int check(graph& G);
    
    int run(graph& G);
    
    void reset();
    
    void calc_embedding(bool p)
    {
        emp = p;
        if (!emp) kup = false;
    }

    bool calc_embedding () const
        { return emp; }

    void calc_obstruction(bool p)
    {
        kup = p;
        if (kup) emp = true;
    }

    bool calc_obstruction() const
    {
        return kup;
    }

    void make_biconnected(bool p) 
    {
        bip = p;
    }
    
    bool make_biconnected() const 
    {
        return bip;
    }

    bool is_planar() const
    {
        return planar;
    }
    
    planar_embedding& get_embedding()
    {
        return embedding;
    }

    list<edge>& get_obstruction_edges()
    {
        return ob_edges;
    }

    list<node>& get_obstruction_nodes()
    {
        return ob_nodes;
    }
private:
    bool run_on_biconnected(graph& G, planar_embedding& em);

    void add_to_embedding(graph& G, planar_embedding& em);

    void correct_embedding(planar_embedding& em,
                           st_number& st,
                           node_map<list<direction_indicator> >& dirs);

    void extend_embedding(
        node n,
        planar_embedding& em,
        node_map<int>& mark,
        node_map<symlist<edge>::iterator >& upward_begin);
        
    void switch_to_component(graph& G,
                             biconnectivity::component_iterator it);
 
    void examine_obstruction(graph& G,
                             st_number& st,
                             node act,
                             pq_node* fail,
                             bool failed_at_root,
                             planar_embedding& em,
                             node_map<list<direction_indicator> >& dirs,
                             pq_tree* PQ); 

    void dfs_bushform(node act,
                      node_map<int>& mark,
                      st_number& st,
                      int stop,
                      node_map<edge>& to_father);

    
    void attachment_cycle (node n, planar_embedding& em);

    void mark_all_neighbors_of_leaves (pq_node* act, node_map<int>& mark);
    
    pq_leaf* run_through_partial(q_node* partial,
                                 node_map<int>& mark,
                                 node_map<edge>& to_father,
                                 node v);

    node up_until_marked(node act,
                         node_map<int>& mark,
                         node_map<edge>& to_father);

    node up_until_marked(node act,
                         node_map<int>& mark,
                         st_number& st);

    pq_leaf* search_full_leaf (pq_node* n);
        
    pq_leaf* search_empty_leaf(pq_node* n);

    void case_A(p_node* p_fail,
                node act,
                st_number& _st,
                node_map<edge> to_father,
                graph& G);

    void case_B(p_node* p_fail,
                node act,
                st_number& _st,
                node_map<edge> to_father,
                graph& G);

    void case_C(node* nodes,
                pq_leaf** leaves,
                st_number& _st,
                node_map<edge> to_father,
                graph& G,
                q_node* q_fail);

    void case_D(node* nodes,
                pq_leaf** leaves,
                st_number& _st,
                node_map<edge> to_father,
                graph& G,
                q_node* q_fail);

    void case_E(node* nodes,
                pq_leaf** leaves,
                st_number& _st,
                node_map<edge> to_father,
                graph& G,
                q_node* q_fail);

#ifdef _DEBUG

    void write_bushform(graph& G, st_number& _st, int k, const char* name,
                        const node_map<int>& mark, const node_map<edge>& to_father);

    void write_node(ostream& os, int id, int label, int mark);
#endif
    
    list<edge> ob_edges;
    
    list<node> ob_nodes;
    
    planar_embedding embedding;
    
    bool planar;
    
    bool emp;
    
    bool kup;
    
    bool bip;
};

__GTL_END_NAMESPACE

#endif // PLANARITY_H

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