BCTree.h

Go to the documentation of this file.

/*
 * $Revision: 2027 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2010-09-01 11:55:17 +0200 (Wed, 01 Sep 2010) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_BC_TREE_H
#define OGDF_BC_TREE_H

#include <ogdf/basic/BoundedStack.h>
#include <ogdf/basic/EdgeArray.h>
#include <ogdf/basic/NodeArray.h>
#include <ogdf/basic/SList.h>

namespace ogdf {

class OGDF_EXPORT BCTree {

public:

    enum GNodeType { Normal, CutVertex };
    enum BNodeType { BComp, CComp };

protected:

    Graph& m_G;
    Graph m_B;
    mutable Graph m_H;

    int m_numB;
    int m_numC;

    NodeArray<bool> m_gNode_isMarked;
    NodeArray<node> m_gNode_hNode;
    EdgeArray<edge> m_gEdge_hEdge;

    NodeArray<BNodeType> m_bNode_type;
    mutable NodeArray<bool> m_bNode_isMarked;
    NodeArray<node> m_bNode_hRefNode;
    NodeArray<node> m_bNode_hParNode;
    NodeArray<SList<edge> > m_bNode_hEdges;
    NodeArray<int> m_bNode_numNodes;

    mutable NodeArray<node> m_hNode_bNode;
    mutable EdgeArray<node> m_hEdge_bNode;
    NodeArray<node> m_hNode_gNode;
    EdgeArray<edge> m_hEdge_gEdge;

    int m_count;
    NodeArray<int> m_number;
    NodeArray<int> m_lowpt;
    BoundedStack<adjEntry> m_eStack;
    NodeArray<node> m_gtoh;
    SList<node> m_nodes;

    void init (node vG);
    
    void initNotConnected (node vG);
    void biComp (adjEntry adjuG, node vG);

    virtual node parent (node vB) const;
    node findNCA (node uB, node vB) const;

public:

    BCTree (Graph& G, bool callInitConnected = false) : m_G(G), m_eStack(G.numberOfEdges()) { 
        if (!callInitConnected) 
            init(G.firstNode()); 
        else initNotConnected(G.firstNode());
    }
    
    BCTree (Graph& G, node vG, bool callInitConnected = false) : m_G(G), m_eStack(G.numberOfEdges()) { 
        if (!callInitConnected) 
            init(vG); 
        else initNotConnected(vG);
    }
    
    virtual ~BCTree () { }

    const Graph& originalGraph () const { return m_G; }
    const Graph& bcTree () const { return m_B; }
    const Graph& auxiliaryGraph () const { return m_H; }

    int numberOfBComps () const { return m_numB; }
    int numberOfCComps () const { return m_numC; }

    GNodeType typeOfGNode (node vG) const { return m_bNode_type[m_hNode_bNode[m_gNode_hNode[vG]]]==BComp ? Normal : CutVertex; }
    virtual node bcproper (node vG) const { return m_hNode_bNode[m_gNode_hNode[vG]]; }
    virtual node bcproper (edge eG) const { return m_hEdge_bNode[m_gEdge_hEdge[eG]]; }
    node rep (node vG) const { return m_gNode_hNode[vG]; }
    edge rep (edge eG) const { return m_gEdge_hEdge[eG]; }

    node original (node vH) { return m_hNode_gNode[vH]; }
    edge original (edge eH) const { return m_hEdge_gEdge[eH]; }

    BNodeType typeOfBNode (node vB) const { return m_bNode_type[vB]; }
    const SList<edge>& hEdges (node vB) const { return m_bNode_hEdges[vB]; }
    int numberOfEdges (node vB) const { return m_bNode_hEdges[vB].size(); }
    int numberOfNodes (node vB) const { return m_bNode_numNodes[vB]; }

    node bComponent (node uG, node vG) const;
    
    SList<node>& findPath (node sG, node tG) const;
    
    SList<node>* findPathBCTree (node sB, node tB) const;

    virtual node repVertex (node uG, node vB) const;
    virtual node cutVertex (node uB, node vB) const;

private:
    // avoid automatic creation of assignment operator

    BCTree(const BCTree &);

    BCTree &operator=(const BCTree &);
};

}

#endif