?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Don't import ogdf namespace
[TortoiseGit.git] / ext / OGDF / ogdf / planarity / ExtractKuratowskis.h
blob18f8a9e44bde66fb0b671009abb655a9f0a5b6f6
1 /*
2 * $Revision: 2583 $
3 *
4 * last checkin:
5 * $Author: gutwenger $
6 * $Date: 2012-07-12 01:02:21 +0200 (Do, 12. Jul 2012) $
7 ***************************************************************/
8
9 /** \file
10 * \brief Declaration of the class ExtractKuratowskis
11 *
12 * \author Jens Schmidt
13 *
14 *
15 * \par License:
16 * This file is part of the Open Graph Drawing Framework (OGDF).
17 *
18 * \par
19 * Copyright (C)<br>
20 * See README.txt in the root directory of the OGDF installation for details.
21 *
22 * \par
23 * This program is free software; you can redistribute it and/or
24 * modify it under the terms of the GNU General Public License
25 * Version 2 or 3 as published by the Free Software Foundation;
26 * see the file LICENSE.txt included in the packaging of this file
27 * for details.
28 *
29 * \par
30 * This program is distributed in the hope that it will be useful,
31 * but WITHOUT ANY WARRANTY; without even the implied warranty of
32 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
33 * GNU General Public License for more details.
34 *
35 * \par
36 * You should have received a copy of the GNU General Public
37 * License along with this program; if not, write to the Free
38 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
39 * Boston, MA 02110-1301, USA.
40 *
41 * \see http://www.gnu.org/copyleft/gpl.html
42 ***************************************************************/
43
44
45 #ifdef _MSC_VER
46 #pragma once
47 #endif
48
49 #ifndef OGDF_EXTRACT_KURATOWSKIS_H
50 #define OGDF_EXTRACT_KURATOWSKIS_H
51
52 #include <ogdf/internal/planarity/BoyerMyrvoldPlanar.h>
53 #include <ogdf/internal/planarity/FindKuratowskis.h>
54 #include <ogdf/basic/Stack.h>
55
56 namespace ogdf {
57
58
59 //! Extracts all possible paths with backtracking using given edges and special constraints
60 class OGDF_EXPORT DynamicBacktrack {
61 public:
62 //! Constructor
63 DynamicBacktrack(
64 const Graph& g,
65 const NodeArray<int>& dfi,
66 const EdgeArray<int>& flags)
67 : m_flags(flags),
68 m_dfi(dfi),
69 m_parent(g,NULL) {
70 }
71
72 //! Reinitializes backtracking with new constraints. All paths will be traversed again.
73 /** Startedges are either only \a startInclude or not \a startExclude, all startedges
74 * have to contain the flag \a startFlag, if \a startFlag != 0. The \a start- and \a endnode
75 * of extracted paths is given, too.
76 */
77 void init(
78 const node start,
79 const node end,
80 const bool less,
81 const int flag,
82 const int startFlag,
83 const edge startInclude,
84 const edge startExlude);
85
86 //! Returns next possible path from \a start- to \a endnode, if exists.
87 /** The path is returned to \a list. After that a process image is made,
88 * allowing to pause backtracking and extracting further paths later.
89 * \a Endnode returns the last traversed node.
90 */
91 bool addNextPath(SListPure<edge>& list, node& endnode);
92
93 //! Returns next possible path under constraints from \a start- to \a endnode, if exists.
94 /** All paths avoid \a exclude-edges, except if on an edge with flag \a exceptOnEdge.
95 * The NodeArray \a nodeflags is used to mark visited nodes. Only that part of the path,
96 * which doesn't contain \a exclude-edges is finally added.
97 * The path is returned to \a list. After that a process image is made,
98 * allowing to pause backtracking and extracting further paths later.
99 * \a Endnode returns the last traversed node.
100 */
101 bool addNextPathExclude(SListPure<edge>& list,
102 node& endnode,
103 const NodeArray<int>& nodeflags,
104 int exclude,
105 int exceptOnEdge);
106
107 // avoid automatic creation of assignment operator
108 //! Assignment is not defined!
109 DynamicBacktrack &operator=(const DynamicBacktrack &);
110
111 //! Marks an edge with three Flags: externalPath, pertinentPath and/or singlePath
112 enum enumKuratowskiFlag {
113 externalPath = 0x00001, // external paths, e.g. stopX->Ancestor
114 pertinentPath = 0x00002, // pertinent paths, e.g. wNode->V
115 singlePath = 0x00004, // marker for one single path
116 };
117
118 protected:
119 //! Flags, that partition the edges into pertinent and external subgraphs
120 const EdgeArray<int>& m_flags;
121 //! The one and only DFI-NodeArray
122 const NodeArray<int>& m_dfi;
123
124 //! Start node of backtracking
125 node start;
126 //! Identifies endnodes
127 node end;
128 //! Iff true, DFI of endnodes has to be < \a DFI[end], otherwise the only valid endnode is \a end
129 bool less;
130 //! Every traversed edge has to be signed with this flag
131 int flag;
132
133 //! Saves the parent edge for each node in path
134 NodeArray<adjEntry> m_parent;
135
136 //! Backtracking stack. A NULL-element indicates a return from a child node
137 StackPure<adjEntry> stack;
138 };
139
140 //! Wrapper-class for Kuratowski Subdivisions containing the minortype and edgelist
141 class OGDF_EXPORT KuratowskiWrapper {
142 public:
143 //! Constructor
144 KuratowskiWrapper() { }
145
146 //! Returns true, iff subdivision is a K3,3-minor
147 inline bool isK33() const { return subdivisionType != E5; }
148 //! Returns true, iff subdivision is a K5-minor
149 inline bool isK5() const { return subdivisionType == E5; }
150
151 //! Possible minortypes of a Kuratowski Subdivision
152 enum enumSubdivisionType {
153 A=0,
154 AB=1,
155 AC=2,
156 AD=3,
157 AE1=4,
158 AE2=5,
159 AE3=6,
160 AE4=7,
161 B=8,
162 C=9,
163 D=10,
164 E1=11,
165 E2=12,
166 E3=13,
167 E4=14,
168 E5=15
169 };
170 //! Minortype of the Kuratowski Subdivision
171 int subdivisionType;
172
173 //! The node which was embedded while the Kuratowski Subdivision was found
174 node V;
175
176 //! Contains the edges of the Kuratowski Subdivision
177 SListPure<edge> edgeList;
178 };
179
180 //! Extracts multiple Kuratowski Subdivisions
181 /** \pre Graph has to be simple.
182 */
183 class ExtractKuratowskis {
184 public:
185 //! Constructor
186 ExtractKuratowskis(BoyerMyrvoldPlanar& bm);
187 //! Destructor
188 ~ExtractKuratowskis() { }
189
190 //! Extracts all Kuratowski Subdivisions and adds them to \a output (without bundles)
191 void extract(
192 const SListPure<KuratowskiStructure>& allKuratowskis,
193 SList<KuratowskiWrapper>& output);
194
195 //! Extracts all Kuratowski Subdivisions and adds them to \a output (with bundles)
196 void extractBundles(
197 const SListPure<KuratowskiStructure>& allKuratowskis,
198 SList<KuratowskiWrapper>& output);
199
200 //! Enumeration over Kuratowski Type none, K33, K5
201 enum enumKuratowskiType {
202 none = 0, //!< no kuratowski subdivision exists
203 K33 = 1, //!< a K3,3 subdivision exists
204 K5 = 2 //!< a K5 subdivision exists
205 };
206
207 //! Checks, if \a list forms a valid Kuratowski Subdivision and returns the type
208 /**
209 * @return Returns the following value:
210 * - none = no Kuratowski
211 * - K33 = the K3,3
212 * - K5 = the K5
213 */
214 static int whichKuratowski(
215 const Graph& m_g,
216 const NodeArray<int>& dfi,
217 const SListPure<edge>& list);
218
219 //! Checks, if edges in Array \a edgenumber form a valid Kuratowski Subdivision and returns the type
220 /**
221 * \pre The numer of edges has to be 1 for used edges, otherwise 0.
222 * @return Returns the following value:
223 * - none = no Kuratowski
224 * - K33 = the K3,3
225 * - K5 = the K5
226 */
227 static int whichKuratowskiArray(
228 const Graph& g,
229 //const NodeArray<int>& m_dfi,
230 EdgeArray<int>& edgenumber);
231
232 //! Returns true, iff the Kuratowski is not already contained in output
233 static bool isANewKuratowski(
234 const Graph& g,
235 const SListPure<edge>& kuratowski,
236 const SList<KuratowskiWrapper>& output);
237 //! Returns true, iff the Kuratowski is not already contained in output
238 /** \pre Kuratowski Edges are all edges != 0 in the Array.
239 */
240 static bool isANewKuratowski(
241 //const Graph& g,
242 const EdgeArray<int>& test,
243 const SList<KuratowskiWrapper>& output);
244
245 // avoid automatic creation of assignment operator
246 //! Assignment operator is undefined!
247 ExtractKuratowskis &operator=(const ExtractKuratowskis &);
248
249 protected:
250 //! Link to class BoyerMyrvoldPlanar
251 BoyerMyrvoldPlanar& BMP;
252
253 //! Input graph
254 const Graph& m_g;
255
256 //! Some parameters, see BoyerMyrvold for further instructions
257 int m_embeddingGrade;
258 //! Some parameters, see BoyerMyrvold for further instructions
259 const bool m_avoidE2Minors;
260
261 //! Value used as marker for visited nodes etc.
262 /** Used during Backtracking and the extraction of some specific minortypes
263 */
264 int m_nodeMarker;
265 //! Array maintaining visited bits on each node
266 NodeArray<int> m_wasHere;
267
268 //! The one and only DFI-NodeArray
269 const NodeArray<int>& m_dfi;
270
271 //! Returns appropriate node from given DFI
272 const Array<node>& m_nodeFromDFI;
273
274 //! The adjEntry which goes from DFS-parent to current vertex
275 const NodeArray<adjEntry>& m_adjParent;
276
277 //! Adds external face edges to \a list
278 inline void addExternalFacePath(
279 SListPure<edge>& list,
280 const SListPure<adjEntry>& externPath) {
281 SListConstIterator<adjEntry> itExtern;
282 for (itExtern = externPath.begin(); itExtern.valid(); ++itExtern) {
283 list.pushBack((*itExtern)->theEdge());
284 }
285 }
286
287 //! Returns \a adjEntry of the edge between node \a high and a special node
288 /** The special node is that node with the lowest DFI not less than the DFI of \a low.
289 */
290 inline adjEntry adjToLowestNodeBelow(node high, int low);
291
292 //! Adds DFS-path from node \a bottom to node \a top to \a list
293 /** \pre Each virtual node has to be merged.
294 */
295 inline void addDFSPath(SListPure<edge>& list, node bottom, node top);
296 //! Adds DFS-path from node \a top to node \a bottom to \a list
297 /** \pre Each virtual node has to be merged.
298 */
299 inline void addDFSPathReverse(SListPure<edge>& list, node bottom, node top);
300
301 //! Separates \a list1 from edges already contained in \a list2
302 inline void truncateEdgelist(SListPure<edge>& list1, const SListPure<edge>& list2);
303
304 //! Extracts minortype A and adds it to list \a output
305 void extractMinorA(
306 SList<KuratowskiWrapper>& output,
307 const KuratowskiStructure& k,
308 //const WInfo& info,
309 const SListPure<edge>& pathX,
310 const node endnodeX,
311 const SListPure<edge>& pathY,
312 const node endnodeY,
313 const SListPure<edge>& pathW);
314 //! Extracts minortype B and adds it to list \a output (no bundles)
315 void extractMinorB(
316 SList<KuratowskiWrapper>& output,
317 //NodeArray<int>& nodeflags,
318 //const int nodemarker,
319 const KuratowskiStructure& k,
320 const WInfo& info,
321 const SListPure<edge>& pathX,
322 const node endnodeX,
323 const SListPure<edge>& pathY,
324 const node endnodeY,
325 const SListPure<edge>& pathW);
326 //! Extracts minortype B and adds it to list \a output (with bundles)
327 void extractMinorBBundles(
328 SList<KuratowskiWrapper>& output,
329 NodeArray<int>& nodeflags,
330 const int nodemarker,
331 const KuratowskiStructure& k,
332 EdgeArray<int>& flags,
333 const WInfo& info,
334 const SListPure<edge>& pathX,
335 const node endnodeX,
336 const SListPure<edge>& pathY,
337 const node endnodeY,
338 const SListPure<edge>& pathW);
339 //! Extracts minortype C and adds it to list \a output
340 void extractMinorC(
341 SList<KuratowskiWrapper>& output,
342 const KuratowskiStructure& k,
343 const WInfo& info,
344 const SListPure<edge>& pathX,
345 const node endnodeX,
346 const SListPure<edge>& pathY,
347 const node endnodeY,
348 const SListPure<edge>& pathW);
349 //! Extracts minortype D and adds it to list \a output
350 void extractMinorD(
351 SList<KuratowskiWrapper>& output,
352 const KuratowskiStructure& k,
353 const WInfo& info,
354 const SListPure<edge>& pathX,
355 const node endnodeX,
356 const SListPure<edge>& pathY,
357 const node endnodeY,
358 const SListPure<edge>& pathW);
359 //! Extracts minortype E and adds it to list \a output (no bundles)
360 void extractMinorE(
361 SList<KuratowskiWrapper>& output,
362 bool firstXPath,
363 bool firstPath,
364 bool firstWPath,
365 bool firstWOnHighestXY,
366 const KuratowskiStructure& k,
367 const WInfo& info,
368 const SListPure<edge>& pathX,
369 const node endnodeX,
370 const SListPure<edge>& pathY,
371 const node endnodeY,
372 const SListPure<edge>& pathW);
373 //! Extracts minortype E and adds it to list \a output (bundles)
374 void extractMinorEBundles(
375 SList<KuratowskiWrapper>& output,
376 bool firstXPath,
377 bool firstPath,
378 bool firstWPath,
379 bool firstWOnHighestXY,
380 NodeArray<int>& nodeflags,
381 const int nodemarker,
382 const KuratowskiStructure& k,
383 EdgeArray<int>& flags,
384 const WInfo& info,
385 const SListPure<edge>& pathX,
386 const node endnodeX,
387 const SListPure<edge>& pathY,
388 const node endnodeY,
389 const SListPure<edge>& pathW);
390 //! Extracts minorsubtype E1 and adds it to list \a output
391 void extractMinorE1(
392 SList<KuratowskiWrapper>& output,
393 int before,
394 //const node z,
395 const node px,
396 const node py,
397 const KuratowskiStructure& k,
398 const WInfo& info,
399 const SListPure<edge>& pathX,
400 const node endnodeX,
401 const SListPure<edge>& pathY,
402 const node endnodeY,
403 const SListPure<edge>& pathW,
404 const SListPure<edge>& pathZ,
405 const node endnodeZ);
406 //! Extracts minorsubtype E2 and adds it to list \a output
407 void extractMinorE2(
408 SList<KuratowskiWrapper>& output,
409 /*int before,
410 const node z,
411 const node px,
412 const node py,*/
413 const KuratowskiStructure& k,
414 const WInfo& info,
415 const SListPure<edge>& pathX,
416 const node endnodeX,
417 const SListPure<edge>& pathY,
418 const node endnodeY,
419 //const SListPure<edge>& pathW,
420 const SListPure<edge>& pathZ/*,
421 const node endnodeZ*/);
422 //! Extracts minorsubtype E3 and adds it to list \a output
423 void extractMinorE3(
424 SList<KuratowskiWrapper>& output,
425 int before,
426 const node z,
427 const node px,
428 const node py,
429 const KuratowskiStructure& k,
430 const WInfo& info,
431 const SListPure<edge>& pathX,
432 const node endnodeX,
433 const SListPure<edge>& pathY,
434 const node endnodeY,
435 const SListPure<edge>& pathW,
436 const SListPure<edge>& pathZ,
437 const node endnodeZ);
438 //! Extracts minorsubtype E4 and adds it to list \a output
439 void extractMinorE4(
440 SList<KuratowskiWrapper>& output,
441 int before,
442 const node z,
443 const node px,
444 const node py,
445 const KuratowskiStructure& k,
446 const WInfo& info,
447 const SListPure<edge>& pathX,
448 const node endnodeX,
449 const SListPure<edge>& pathY,
450 const node endnodeY,
451 const SListPure<edge>& pathW,
452 const SListPure<edge>& pathZ,
453 const node endnodeZ);
454 //! Extracts minorsubtype E5 and adds it to list \a output
455 void extractMinorE5(
456 SList<KuratowskiWrapper>& output,
457 /*int before,
458 const node z,
459 const node px,
460 const node py,*/
461 const KuratowskiStructure& k,
462 const WInfo& info,
463 const SListPure<edge>& pathX,
464 const node endnodeX,
465 const SListPure<edge>& pathY,
466 const node endnodeY,
467 const SListPure<edge>& pathW,
468 const SListPure<edge>& pathZ,
469 const node endnodeZ);
470 };
471
472 }
473
474 #endif
Windows Explorer Extension to Operate Git