FindKuratowskis.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_FIND_KURATOWSKIS_H
#define OGDF_FIND_KURATOWSKIS_H

#include <ogdf/internal/planarity/BoyerMyrvoldPlanar.h>

#define KURATOWSKI_FILE "../Kuratowski"

namespace ogdf {



struct ExternE {
    node theNode;
    SListPure<int> startnodes;
    SListPure<node> endnodes;
    SListPure<SListPure<edge> > externalPaths;
};


struct WInfo {
    public:
        node w;
        
        enum enumMinorType {
            A=0x0001, // minor A
            B=0x0002, // minor B
            C=0x0004, // minor C
            D=0x0008, // minor D
            E=0x0010  // minor E
        };
        int minorType;
        
        SListPure<adjEntry>* highestXYPath;
        SListPure<adjEntry>* zPath;
        
        bool pxAboveStopX;
        bool pyAboveStopY;
        
        SListPure<SListPure<edge> > pertinentPaths;
        
        SListIterator<ExternE> externEStart;
        SListIterator<ExternE> externEEnd;
        node firstExternEAfterW;
};

class OGDF_EXPORT KuratowskiStructure {
        friend class FindKuratowskis;
        friend class ExtractKuratowskis;
    public:
        KuratowskiStructure() { };
        ~KuratowskiStructure() { };
        
        KuratowskiStructure(const KuratowskiStructure& orig) {
            copy(orig);
        }
        
        KuratowskiStructure& operator=(const KuratowskiStructure& orig) {
            copy(orig);
            return *this;
        }
        
        void clear();
        
        node V;
        int V_DFI;
        
        node R;

        node RReal;
        node stopX;
        node stopY;
        
    protected:

        SListPure<WInfo> wNodes;
        

        ListPure<adjEntry> highestFacePath;
        
        SListPure<SListPure<adjEntry> > highestXYPaths;
        
        SListPure<adjEntry> externalFacePath;
        
        SListPure<edge> externalSubgraph;
        
        SListPure<edge> pertinentSubgraph;
        

        SListPure<SListPure<adjEntry> > zPaths;
        
        SListPure<ExternE> externE;
        
        SListPure<int> stopXStartnodes;
        SListPure<int> stopYStartnodes;
        SListPure<node> stopXEndnodes;
        SListPure<node> stopYEndnodes;
        
        void copy(const KuratowskiStructure& orig);
        void copyPointer(const KuratowskiStructure& orig, SListPure<WInfo>& list);
};


class FindKuratowskis {
    public:
        FindKuratowskis(BoyerMyrvoldPlanar* bm);
        ~FindKuratowskis() { };
        
        void addKuratowskiStructure(
                        const node currentNode,
                        const node root,
                        const node stopx,
                        const node stopy);
        
        inline SListPure<KuratowskiStructure>& getAllKuratowskis() {
            return allKuratowskis;
        }
        
        inline const SListPure<KuratowskiStructure>& getAllKuratowskis() const {
            return allKuratowskis;
        }
        
        // avoid automatic creation of assignment operator
        FindKuratowskis &operator=(const FindKuratowskis &);

    protected:
        BoyerMyrvoldPlanar* pBM;
        
        Graph& m_g;
        
        const int& m_embeddingGrade;
        
        const bool m_bundles;
        
        NodeArray<WInfo*> m_getWInfo;
        
        SListPure<KuratowskiStructure> allKuratowskis;
        
        KuratowskiStructure k;
        

        int m_nodeMarker;
        NodeArray<int> m_wasHere;
        

        const NodeArray<node>& m_realVertex;
        
        const NodeArray<int>& m_dfi;
        
        const Array<node>& m_nodeFromDFI;
        

        const NodeArray<adjEntry>(& m_link)[2];
        
        const NodeArray<adjEntry>& m_adjParent;
        

        const NodeArray<int>& m_leastAncestor;
        

        EdgeArray<int>& m_edgeType;
        
        NodeArray<int>& m_lowPoint;
        
        const NodeArray<int>& m_highestSubtreeDFI;
        

        const NodeArray<ListPure<node> >& m_separatedDFSChildList;
        
        const EdgeArray<node>& m_pointsToRoot;
        

        NodeArray<int>& m_visitedWithBackedge;
        

        NodeArray<SListPure<adjEntry> >& m_backedgeFlags;
        
        NodeArray<SListPure<node> >& m_pertinentRoots;
        
        node findRoot(node stopX);
        
        void extractHighestFacePath(ListPure<adjEntry>& highestFacePath, int marker);
        
        void extractExternalFacePath(
                    SListPure<adjEntry>& externalFacePath,
                    const ListPure<adjEntry>& highestFacePath,
                    int marker,
                    int highMarker);
        
        void splitInMinorTypes(
                const SListPure<adjEntry>& externalFacePath,
                int marker);
        
        void extractExternalSubgraph(
                const node stop,
                int root,
                SListPure<int>& externalStartnodes,
                SListPure<node>& externalEndnodes);
        void extractExternalSubgraphBundles(
                const node stop,
                int root,
                SListPure<edge>& externalSubgraph,
                int nodeMarker);
        
        void extractPertinentSubgraph(
                SListPure<WInfo>& W_All/*,
                const node V*/);
        void extractPertinentSubgraphBundles(
                const SListPure<WInfo>& W_All,
                const node V,
                SListPure<edge>& pertinentSubgraph,
                int nodeMarker);
};

}

#endif