DynamicBCTree.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/basic.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 override;
 
    node condensePath(node sG, node tG);
 
public:
    explicit DynamicBCTree(Graph& G, bool not_connected = false)
        : DynamicBCTree(G, nullptr, not_connected) { }
 
    explicit DynamicBCTree(Graph& G, node vG, bool not_connected = false)
        : BCTree(G, vG, not_connected) {
        init();
    }
 
 
    node bccomp(node vH) const override;
 
    node bccomp(edge eH) const override;
 
 
    node repVertex(node uG, node vB) const override { return BCTree::repVertex(uG, find(vB)); }
 
    node cutVertex(node uB, node vB) const override {
        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;
 
};
 
}