doc-ogdf/_extract_kuratowskis_8h_source.html

00001 /*
00002  * $Revision: 2299 $
00003  *
00004  * last checkin:
00005  *   $Author: gutwenger $
00006  *   $Date: 2012-05-07 15:57:08 +0200 (Mon, 07 May 2012) $
00007  ***************************************************************/
00008
00044 #ifdef _MSC_VER
00045 #pragma once
00046 #endif
00047
00048 #ifndef OGDF_EXTRACT_KURATOWSKIS_H
00049 #define OGDF_EXTRACT_KURATOWSKIS_H
00050
00051 #include <ogdf/internal/planarity/BoyerMyrvoldPlanar.h>
00052 #include <ogdf/internal/planarity/FindKuratowskis.h>
00053 #include <ogdf/basic/Stack.h>
00054
00055 namespace ogdf {
00056
00057
00059 class OGDF_EXPORT DynamicBacktrack {
00060     public:
00062         DynamicBacktrack(
00063                 const Graph& g,
00064                 const NodeArray<int>& dfi,
00065                 const EdgeArray<int>& flags)
00066                 :   m_flags(flags),
00067                     m_dfi(dfi),
00068                     m_parent(g,NULL) {
00069         };
00070
00072
00076         void init(
00077                 const node start,
00078                 const node end,
00079                 const bool less,
00080                 const int flag,
00081                 const int startFlag,
00082                 const edge startInclude,
00083                 const edge startExlude);
00084
00086
00090         bool addNextPath(SListPure<edge>& list, node& endnode);
00091
00093
00100         bool addNextPathExclude(SListPure<edge>& list,
00101                                 node& endnode,
00102                                 const NodeArray<int>& nodeflags,
00103                                 int exclude,
00104                                 int exceptOnEdge);
00105
00106         // avoid automatic creation of assignment operator
00108         DynamicBacktrack &operator=(const DynamicBacktrack &);
00109
00111         enum enumKuratowskiFlag {
00112             externalPath        = 0x00001, // external paths, e.g. stopX->Ancestor
00113             pertinentPath       = 0x00002, // pertinent paths, e.g. wNode->V
00114             singlePath          = 0x00004, // marker for one single path
00115         };
00116
00117     protected:
00119         const EdgeArray<int>& m_flags;
00121         const NodeArray<int>& m_dfi;
00122
00124         node start;
00126         node end;
00128         bool less;
00130         int flag;
00131
00133         NodeArray<adjEntry> m_parent;
00134
00136         StackPure<adjEntry> stack;
00137 };
00138
00140 class OGDF_EXPORT KuratowskiWrapper {
00141     public:
00143         KuratowskiWrapper() { };
00144
00146         inline bool isK33() { return subdivisionType != E5; }
00148         inline bool isK5() { return subdivisionType == E5; }
00149
00151         enum enumSubdivisionType {
00152             A=0,
00153             AB=1,
00154             AC=2,
00155             AD=3,
00156             AE1=4,
00157             AE2=5,
00158             AE3=6,
00159             AE4=7,
00160             B=8,
00161             C=9,
00162             D=10,
00163             E1=11,
00164             E2=12,
00165             E3=13,
00166             E4=14,
00167             E5=15
00168         };
00170         int subdivisionType;
00171
00173         node V;
00174
00176         SListPure<edge> edgeList;
00177 };
00178
00180
00182 class ExtractKuratowskis {
00183     public:
00185         ExtractKuratowskis(BoyerMyrvoldPlanar& bm);
00187         ~ExtractKuratowskis() { };
00188
00190         void extract(
00191                 const SListPure<KuratowskiStructure>& allKuratowskis,
00192                 SList<KuratowskiWrapper>& output);
00193
00195         void extractBundles(
00196                 const SListPure<KuratowskiStructure>& allKuratowskis,
00197                 SList<KuratowskiWrapper>& output);
00198
00200         enum enumKuratowskiType {
00201             none    = 0, // no kuratowski subdivision exists
00202             K33     = 1, // a K3,3 subdivision exists
00203             K5      = 2  // a K5 subdivision exists
00204         };
00205
00207
00211         static int whichKuratowski(
00212                 const Graph& m_g,
00213                 const NodeArray<int>& m_dfi,
00214                 const SListPure<edge>& list);
00215
00217
00222         static int whichKuratowskiArray(
00223                 const Graph& m_g,
00224                 //const NodeArray<int>& m_dfi,
00225                 EdgeArray<int>& edgenumber);
00226
00228         static bool isANewKuratowski(
00229                 const Graph& g,
00230                 const SListPure<edge>& kuratowski,
00231                 const SList<KuratowskiWrapper>& output);
00233
00235         static bool isANewKuratowski(
00236                 //const Graph& g,
00237                 const EdgeArray<int>& test,
00238                 const SList<KuratowskiWrapper>& output);
00239
00240         // avoid automatic creation of assignment operator
00242         ExtractKuratowskis &operator=(const ExtractKuratowskis &);
00243
00244     protected:
00246         BoyerMyrvoldPlanar& BMP;
00247
00249         const Graph& m_g;
00250
00252         int m_embeddingGrade;
00254         const bool m_avoidE2Minors;
00255
00257
00259         int m_nodeMarker;
00261         NodeArray<int> m_wasHere;
00262
00264         const NodeArray<int>& m_dfi;
00265
00267         const Array<node>& m_nodeFromDFI;
00268
00270         const NodeArray<adjEntry>& m_adjParent;
00271
00273         inline void addExternalFacePath(
00274                             SListPure<edge>& list,
00275                             const SListPure<adjEntry>& externPath) {
00276             SListConstIterator<adjEntry> itExtern;
00277             for (itExtern = externPath.begin(); itExtern.valid(); ++itExtern) {
00278                 list.pushBack((*itExtern)->theEdge());
00279             }
00280         }
00281
00283
00285         inline adjEntry adjToLowestNodeBelow(node high, int low);
00286
00288
00290         inline void addDFSPath(SListPure<edge>& list, node bottom, node top);
00292
00294         inline void addDFSPathReverse(SListPure<edge>& list, node bottom, node top);
00295
00297         inline void truncateEdgelist(SListPure<edge>& list1, const SListPure<edge>& list2);
00298
00300         void extractMinorA(
00301                 SList<KuratowskiWrapper>& output,
00302                 const KuratowskiStructure& k,
00303                 //const WInfo& info,
00304                 const SListPure<edge>& pathX,
00305                 const node endnodeX,
00306                 const SListPure<edge>& pathY,
00307                 const node endnodeY,
00308                 const SListPure<edge>& pathW);
00310         void extractMinorB(
00311                 SList<KuratowskiWrapper>& output,
00312                 //NodeArray<int>& nodeflags,
00313                 //const int nodemarker,
00314                 const KuratowskiStructure& k,
00315                 const WInfo& info,
00316                 const SListPure<edge>& pathX,
00317                 const node endnodeX,
00318                 const SListPure<edge>& pathY,
00319                 const node endnodeY,
00320                 const SListPure<edge>& pathW);
00322         void extractMinorBBundles(
00323                 SList<KuratowskiWrapper>& output,
00324                 NodeArray<int>& nodeflags,
00325                 const int nodemarker,
00326                 const KuratowskiStructure& k,
00327                 EdgeArray<int>& flags,
00328                 const WInfo& info,
00329                 const SListPure<edge>& pathX,
00330                 const node endnodeX,
00331                 const SListPure<edge>& pathY,
00332                 const node endnodeY,
00333                 const SListPure<edge>& pathW);
00335         void extractMinorC(
00336                 SList<KuratowskiWrapper>& output,
00337                 const KuratowskiStructure& k,
00338                 const WInfo& info,
00339                 const SListPure<edge>& pathX,
00340                 const node endnodeX,
00341                 const SListPure<edge>& pathY,
00342                 const node endnodeY,
00343                 const SListPure<edge>& pathW);
00345         void extractMinorD(
00346                 SList<KuratowskiWrapper>& output,
00347                 const KuratowskiStructure& k,
00348                 const WInfo& info,
00349                 const SListPure<edge>& pathX,
00350                 const node endnodeX,
00351                 const SListPure<edge>& pathY,
00352                 const node endnodeY,
00353                 const SListPure<edge>& pathW);
00355         void extractMinorE(
00356                 SList<KuratowskiWrapper>& output,
00357                 bool firstXPath,
00358                 bool firstPath,
00359                 bool firstWPath,
00360                 bool firstWOnHighestXY,
00361                 const KuratowskiStructure& k,
00362                 const WInfo& info,
00363                 const SListPure<edge>& pathX,
00364                 const node endnodeX,
00365                 const SListPure<edge>& pathY,
00366                 const node endnodeY,
00367                 const SListPure<edge>& pathW);
00369         void extractMinorEBundles(
00370                 SList<KuratowskiWrapper>& output,
00371                 bool firstXPath,
00372                 bool firstPath,
00373                 bool firstWPath,
00374                 bool firstWOnHighestXY,
00375                 NodeArray<int>& nodeflags,
00376                 const int nodemarker,
00377                 const KuratowskiStructure& k,
00378                 EdgeArray<int>& flags,
00379                 const WInfo& info,
00380                 const SListPure<edge>& pathX,
00381                 const node endnodeX,
00382                 const SListPure<edge>& pathY,
00383                 const node endnodeY,
00384                 const SListPure<edge>& pathW);
00386         void extractMinorE1(
00387                 SList<KuratowskiWrapper>& output,
00388                 int before,
00389                 //const node z,
00390                 const node px,
00391                 const node py,
00392                 const KuratowskiStructure& k,
00393                 const WInfo& info,
00394                 const SListPure<edge>& pathX,
00395                 const node endnodeX,
00396                 const SListPure<edge>& pathY,
00397                 const node endnodeY,
00398                 const SListPure<edge>& pathW,
00399                 const SListPure<edge>& pathZ,
00400                 const node endnodeZ);
00402         void extractMinorE2(
00403                 SList<KuratowskiWrapper>& output,
00404                 /*int before,
00405                 const node z,
00406                 const node px,
00407                 const node py,*/
00408                 const KuratowskiStructure& k,
00409                 const WInfo& info,
00410                 const SListPure<edge>& pathX,
00411                 const node endnodeX,
00412                 const SListPure<edge>& pathY,
00413                 const node endnodeY,
00414                 //const SListPure<edge>& pathW,
00415                 const SListPure<edge>& pathZ/*,
00416                 const node endnodeZ*/);
00418         void extractMinorE3(
00419                 SList<KuratowskiWrapper>& output,
00420                 int before,
00421                 const node z,
00422                 const node px,
00423                 const node py,
00424                 const KuratowskiStructure& k,
00425                 const WInfo& info,
00426                 const SListPure<edge>& pathX,
00427                 const node endnodeX,
00428                 const SListPure<edge>& pathY,
00429                 const node endnodeY,
00430                 const SListPure<edge>& pathW,
00431                 const SListPure<edge>& pathZ,
00432                 const node endnodeZ);
00434         void extractMinorE4(
00435                 SList<KuratowskiWrapper>& output,
00436                 int before,
00437                 const node z,
00438                 const node px,
00439                 const node py,
00440                 const KuratowskiStructure& k,
00441                 const WInfo& info,
00442                 const SListPure<edge>& pathX,
00443                 const node endnodeX,
00444                 const SListPure<edge>& pathY,
00445                 const node endnodeY,
00446                 const SListPure<edge>& pathW,
00447                 const SListPure<edge>& pathZ,
00448                 const node endnodeZ);
00450         void extractMinorE5(
00451                 SList<KuratowskiWrapper>& output,
00452                 /*int before,
00453                 const node z,
00454                 const node px,
00455                 const node py,*/
00456                 const KuratowskiStructure& k,
00457                 const WInfo& info,
00458                 const SListPure<edge>& pathX,
00459                 const node endnodeX,
00460                 const SListPure<edge>& pathY,
00461                 const node endnodeY,
00462                 const SListPure<edge>& pathW,
00463                 const SListPure<edge>& pathZ,
00464                 const node endnodeZ);
00465 };
00466
00467 }
00468
00469 #endif