DynamicBCTree.h

Go to the documentation of this file.

/*
 * $Revision: 2299 $
 * 
 * last checkin:
 *   $Author: gutwenger $ 
 *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $ 
 ***************************************************************/
 
#ifdef _MSC_VER
#pragma once
#endif

#ifndef OGDF_DYNAMIC_BC_TREE_H
#define OGDF_DYNAMIC_BC_TREE_H

#include <ogdf/decomposition/BCTree.h>

namespace ogdf {

class OGDF_EXPORT DynamicBCTree : public BCTree {

friend class PlanarAugmentation;
friend class PlanarAugmentationFix;

protected:

    mutable NodeArray<node> m_bNode_owner;
    NodeArray<int> m_bNode_degree;

    void init ();

    node unite (node uB, node vB, node wB);
    node find (node vB) const;

    node parent (node vB) const;
    node condensePath (node sG, node tG);

public:

    DynamicBCTree (Graph& G, bool callInitConnected = false) : BCTree(G, callInitConnected) { init(); }
    DynamicBCTree (Graph& G, node vG, bool callInitConnected = false) : BCTree(G,vG, callInitConnected) { init(); }

    node bcproper (node vG) const;
    node bcproper (edge eG) const;

    node repVertex (node uG, node vB) const { return BCTree::repVertex(uG,find(vB)); }
    node cutVertex (node uB, node vB) const { return BCTree::cutVertex(find(uB),find(vB)); }

    virtual edge updateInsertedEdge (edge eG);
    virtual node updateInsertedNode (edge eG, edge fG);

    edge insertEdge (node sG, node tG) { return updateInsertedEdge(m_G.newEdge(sG,tG)); }
    node insertNode (edge eG) { return updateInsertedNode(eG,m_G.split(eG)); }

node bComponent (node uG, node vG) const;

};

}

#endif