PlanarAugmentationFix.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_PLANAR_AUGMENTATION_FIX_H
#define OGDF_PLANAR_AUGMENTATION_FIX_H

#include <ogdf/module/AugmentationModule.h>
#include <ogdf/basic/List.h>
#include <ogdf/decomposition/DynamicBCTree.h>
#include <ogdf/basic/CombinatorialEmbedding.h>
#include <ogdf/basic/FaceArray.h>
#include <ogdf/basic/GraphCopy.h>

#include <ogdf/augmentation/PlanarAugmentation.h>


namespace ogdf {



class OGDF_EXPORT PlanarAugmentationFix : public AugmentationModule {

public:
    PlanarAugmentationFix() { }

    ~PlanarAugmentationFix() { }


protected:

    void doCall(Graph& g, List<edge>& L);
    
private:    
    CombinatorialEmbedding* m_pEmbedding;
    
    CombinatorialEmbedding* m_pActEmbedding;
    
    Graph* m_pGraph;

    List<edge>* m_pResult;
    
    DynamicBCTree* m_pBCTree;
    
    GraphCopy m_graphCopy;
    
    EdgeArray<edge> m_eCopy;

    List<label> m_labels;
    
    NodeArray< ListIterator<label> > m_isLabel;
    
    NodeArray<label> m_belongsTo;
    
    NodeArray< ListIterator<node> > m_belongsToIt;

    node m_actBCRoot;

private:

    void augment(adjEntry adjOuterFace);
    
    void modifyBCRoot(node oldRoot, node newRoot);
    
    void changeBCRoot(node oldRoot, node newRoot);

    void reduceChain(node pendant);

    paStopCause followPath(node v, node& last);
    
    bool findMatching(node& pendant1, node& pendant2, adjEntry& v1, adjEntry& v2);
    
    void findMatchingRev(node& pendant1, node& pendant2, adjEntry& v1, adjEntry& v2);

    label newLabel(node cutvertex, node parent, node pendant, paStopCause whyStop);

    void addPendant(node p, label& l);

    ListIterator<label> insertLabel(label l);

    void connectPendants(node pendant1, node pendant2, adjEntry adjV1, adjEntry adjV2);

    void connectSingleLabel();

    void deletePendant(node pendant);

    void deleteLabel(label& l, bool removePendants = true);
    
    void removeLabel(label& l);
    
};  // class PlanarAugmentationFix


} // namespace ogdf

#endif