PlanarAugmentation.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_H
#define OGDF_PLANAR_AUGMENTATION_H

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

namespace ogdf {


enum paStopCause {paPlanarity, paCDegree, paBDegree, paRoot};


class PlanarAugmentation;
class labelStruct;


typedef labelStruct* label;

class labelStruct {

friend class OGDF_EXPORT PlanarAugmentation;
friend class OGDF_EXPORT PlanarAugmentationFix;

private:

    node m_parent;
    node m_head;
    List<node> m_pendants;
    paStopCause m_stopCause;

public:
    labelStruct(node parent, node cutvertex, paStopCause sc = paBDegree) {
        m_parent = parent;
        m_head = cutvertex;
        m_stopCause = sc;
    };

    bool isBLabel() {
        return (m_parent != 0);
    };

    bool isCLabel() {
        return (m_parent == 0);
    };

    node getPendant(int nr) {
        return (nr < m_pendants.size()) ? (*(m_pendants.get(nr))) : 0;
    };

    node getFirstPendant() {
        return (m_pendants.size() > 0) ? m_pendants.front() : 0;
    };

    node getLastPendant() {
        return (m_pendants.size() > 0) ? m_pendants.back() : 0;
    };
    
    int size() {
        return m_pendants.size();
    };
    
    void removePendant(node pendant);

    void removePendant(ListIterator<node> it){
        m_pendants.del(it);
    };

    void removeFirstPendant() {
        if (m_pendants.size() > 0){
            m_pendants.popFront();
        }
    };
    
    void addPendant(node pendant) {
        m_pendants.pushBack(pendant);
    };

    void deleteAllPendants() {
        m_pendants.clear();
    };

    node parent() {
        return (m_parent != 0) ? m_parent : m_head;
    };

    node head() {
        return m_head;
    };
    
    void setParent(node newParent){
        m_parent = newParent;
    }
    
    void setHead(node newHead){
        m_head = newHead;
    }
    
    paStopCause stopCause(){
        return m_stopCause; 
    }
    
    void stopCause(paStopCause sc){
        m_stopCause = sc;   
    }

    OGDF_NEW_DELETE
}; // class labelStruct



class OGDF_EXPORT PlanarAugmentation : public AugmentationModule {

public:
    PlanarAugmentation() { }

    ~PlanarAugmentation() { }

protected:
    void doCall(Graph& G, List<edge>& L);

    
private:
    int m_nPlanarityTests;
    
    Graph* m_pGraph;
    DynamicBCTree* m_pBCTree;
    
    List<edge>* m_pResult;
    
    List<label> m_labels;
    List<node> m_pendants;

    List<node> m_pendantsToDel;
    
    NodeArray<label> m_belongsTo;
    NodeArray< ListIterator<label> > m_isLabel;

    NodeArray< SList<adjEntry> > m_adjNonChildren;  


private:

    void augment();
    
    void makeConnectedByPendants();

    void reduceChain(node p, label labelOld = 0);

    paStopCause followPath(node v, node& last);

    bool planarityCheck(node v1, node v2);
    
    node adjToCutvertex(node v, node cutvertex = 0);
    
    node findLastBefore(node pendant, node ancestor);

    void deletePendant(node p, bool removeFromLabel = true);
    void addPendant(node p, label& l);
    
    edge connectPendants(node pendant1, node pendant2);
    void removeAllPendants(label& l);

    void joinPendants(label& l);

    void connectInsideLabel(label& l);

    ListIterator<label> insertLabel(label l);

    void deleteLabel(label& l, bool removePendants = true);

    void connectLabels(label first, label second);

    label newLabel(node cutvertex, node p, paStopCause whyStop);

    bool findMatching(label& first, label& second);
    
    bool connectCondition(label a, label b);

    void updateAdjNonChildren(node newBlock, SList<node>& path);

    void modifyBCRoot(node oldRoot, node newRoot);

    void updateNewEdges(const SList<edge> &newEdges);

    void terminate();
    
};  // class PlanarAugmentation


} // namespace ogdf

#endif