1 /*
2 Copyright (c) 1997-2021, John M. Boyer
3 All rights reserved.
4 See the LICENSE.TXT file for licensing information.
5 */
6
7 #define GRAPHTEST_C
8
9 #include "graph.h"
10 #include "stack.h"
11
12 extern void _ClearVertexVisitedFlags(graphP theGraph, int);
13
14 /* Private function declarations */
15
16 int _TestPath(graphP theGraph, int U, int V);
17 int _TryPath(graphP theGraph, int e, int V);
18 void _MarkPath(graphP theGraph, int e);
19 int _TestSubgraph(graphP theSubgraph, graphP theGraph);
20
21 int _CheckEmbeddingIntegrity(graphP theGraph, graphP origGraph);
22 int _CheckEmbeddingFacialIntegrity(graphP theGraph);
23 int _CheckObstructionIntegrity(graphP theGraph, graphP origGraph);
24
25 int _CheckKuratowskiSubgraphIntegrity(graphP theGraph);
26 int _CheckOuterplanarObstructionIntegrity(graphP theGraph);
27
28 int _CheckAllVerticesOnExternalFace(graphP theGraph);
29 void _MarkExternalFaceVertices(graphP theGraph, int startVertex);
30
31 /********************************************************************
32 gp_TestEmbedResultIntegrity()
33
34 This function tests the integrity of the graph result returned
35 from gp_Embed().
36
37 The caller of gp_Embed() does not have to save the original graph
38 because, for efficiency, gp_Embed() operates on the input graph.
39 However, to test the integrity of the result relative to the input,
40 a copy of the input graph is required.
41
42 Modules that extend/alter the behavior of gp_Embed() beyond the
43 core planarity embedder and planarity obstruction isolator should
44 also provide overriding integrity test routines appropriate to the
45 extension algorithm.
46
47 The main method first calls gp_SortVertices on theGraph, if the
48 origGraph is not in DFI order (the common case). Therefore,
49 extension integrity tests can count on a consistent numbering
50 between theGraph and the origGraph, either DFI order or pre-DFS
51 order if that is the state of the origGraph.
52
53 After all tests, the main method ensures theGraph is restored to
54 DFI order by invoking gp_SortVertices if needed, thus ensuring
55 that theGraph has the documented post-condition of gp_Embed().
56
57 For an embedResult of OK, fpCheckEmbeddingIntegrity is invoked.
58 The core planarity implementation does a face walk of all faces
59 of the embedding. It ensures that all edges were used in the face
60 walk and that the right number of faces exist for the number of
61 vertices and edges. Also, we ensure that all adjacencies expressed
62 in the original graph still exist in the result graph.
63
64 For an embedResult of NONEMBEDDABLE, fpCheckObstructionIntegrity
65 is invoked. The core planarity algorithm checks that the result
66 graph is homeomorphic to K5 or K3,3 and that it is in fact a
67 subgraph of the input graph. Other algorithms use overloads to
68 make appropriate checks.
69
70 Returns NOTOK on integrity check failure or embedResult of NOTOK
71 OK for successful integrity check of OK embedResult
72 NONEMBEDDABLE for successful integrity check of an
73 embedResult of NONEMBEDDABLE
74 ********************************************************************/
75
gp_TestEmbedResultIntegrity(graphP theGraph,graphP origGraph,int embedResult)76 int gp_TestEmbedResultIntegrity(graphP theGraph, graphP origGraph, int embedResult)
77 {
78 int RetVal = embedResult;
79
80 if (theGraph == NULL || origGraph == NULL)
81 return NOTOK;
82
83 if (embedResult == OK)
84 {
85 RetVal = theGraph->functions.fpCheckEmbeddingIntegrity(theGraph, origGraph);
86 }
87 else if (embedResult == NONEMBEDDABLE)
88 {
89 RetVal = theGraph->functions.fpCheckObstructionIntegrity(theGraph, origGraph);
90 }
91
92 if (RetVal == OK)
93 RetVal = embedResult;
94
95 return RetVal;
96 }
97
98 /********************************************************************
99 _CheckEmbeddingIntegrity()
100
101 The core planarity implementation does a face walk of all faces
102 of the embedding. It ensures that all edges were used in the face
103 walk and that the right number of faces exist for the number of
104 vertices and edges. Also, we ensure that all adjacencies expressed
105 in the original graph still exist in the result graph, accounting
106 for the fact that the result graph is sorted by DFI, but the input
107 may or may not be sorted by DFI.
108
109 returns OK if all integrity tests passed, NOTOK otherwise
110 ********************************************************************/
111
_CheckEmbeddingIntegrity(graphP theGraph,graphP origGraph)112 int _CheckEmbeddingIntegrity(graphP theGraph, graphP origGraph)
113 {
114 if (theGraph == NULL || origGraph == NULL)
115 return NOTOK;
116
117 if (_TestSubgraph(theGraph, origGraph) != TRUE)
118 return NOTOK;
119
120 if (_TestSubgraph(origGraph, theGraph) != TRUE)
121 return NOTOK;
122
123 if (_CheckEmbeddingFacialIntegrity(theGraph) != OK)
124 return NOTOK;
125
126 if (theGraph->embedFlags == EMBEDFLAGS_OUTERPLANAR)
127 {
128 if (_CheckAllVerticesOnExternalFace(theGraph) != OK)
129 return NOTOK;
130 }
131
132 return OK;
133 }
134
135 /********************************************************************
136 _CheckEmbeddingFacialIntegrity()
137
138 This function traverses all faces of a graph structure containing
139 the planar embedding that results from gp_Embed(). The algorithm
140 begins by placing all of the graph's arcs onto a stack and marking
141 all of them as unvisited. For each arc popped, if it is visited,
142 it is immediately discarded and the next arc is popped. Popping an
143 unvisited arc e begins a face traversal. We move to the true twin
144 arc of e, and obtain its successor arc. This amounts to always
145 going clockwise or counterclockwise (depending on how the graph is
146 drawn on the plane, or alternately whether one is above or below
147 the plane). This traversal continues until we make it back to the
148 original arc e. Each arc along the way is marked as visited. Further,
149 if the successor arc has been visited, then there is an error since
150 an arc can only appear in one face (the twin arc appears in a separate
151 face, which is traversed in the opposing direction).
152 If this algorithm succeeds without double visiting any arcs, and it
153 produces the correct face count according to Euler's formula, then
154 the embedding has all vertices oriented the same way.
155 NOTE: In disconnected graphs, the face reader counts the external
156 face of each connected component. So, we adjust the face
157 count by subtracting one for each component, then we add one
158 to count the external face shared by all components.
159 ********************************************************************/
160
_CheckEmbeddingFacialIntegrity(graphP theGraph)161 int _CheckEmbeddingFacialIntegrity(graphP theGraph)
162 {
163 stackP theStack = theGraph->theStack;
164 int EsizeOccupied, v, e, eTwin, eStart, eNext, NumFaces, connectedComponents;
165
166 if (theGraph == NULL)
167 return NOTOK;
168
169 /* The stack need only contain 2M entries, one for each edge record. With
170 max M at 3N, this amounts to 6N integers of space. The embedding
171 structure already contains this stack, so we just make sure it
172 starts out empty. */
173
174 sp_ClearStack(theStack);
175
176 /* Push all arcs and set them to unvisited */
177
178 EsizeOccupied = gp_EdgeInUseIndexBound(theGraph);
179 for (e = gp_GetFirstEdge(theGraph); e < EsizeOccupied; e+=2)
180 {
181 // Except skip edge holes
182 if (gp_EdgeInUse(theGraph, e))
183 {
184 sp_Push(theStack, e);
185 gp_ClearEdgeVisited(theGraph, e);
186 eTwin = gp_GetTwinArc(theGraph, e);
187 sp_Push(theStack, eTwin);
188 gp_ClearEdgeVisited(theGraph, eTwin);
189 }
190 }
191
192 // There are M edges, so we better have pushed 2M arcs just now
193 // i.e. testing that the continue above skipped only edge holes
194 if (sp_GetCurrentSize(theStack) != 2*theGraph->M)
195 return NOTOK;
196
197
198 /* Read faces until every arc is used */
199
200 NumFaces = 0;
201 while (sp_NonEmpty(theStack))
202 {
203 /* Get an arc; if it has already been used by a face, then
204 don't use it to traverse a new face */
205 sp_Pop(theStack, eStart);
206 if (gp_GetEdgeVisited(theGraph, eStart)) continue;
207
208 e = eStart;
209 do {
210 eNext = gp_GetNextArcCircular(theGraph, gp_GetTwinArc(theGraph, e));
211 if (gp_GetEdgeVisited(theGraph, eNext))
212 return NOTOK;
213 gp_SetEdgeVisited(theGraph, eNext);
214 e = eNext;
215 } while (e != eStart);
216 NumFaces++;
217 }
218
219 /* Count the external face once rather than once per connected component;
220 each connected component is detected by the fact that it has no
221 DFS parent, except in the case of isolated vertices, no face was counted
222 so we do not subtract one. */
223
224 connectedComponents = 0;
225 for (v = gp_GetFirstVertex(theGraph); gp_VertexInRange(theGraph, v); v++)
226 {
227 if (gp_IsDFSTreeRoot(theGraph, v))
228 {
229 if (gp_GetVertexDegree(theGraph, v) > 0)
230 NumFaces--;
231 connectedComponents++;
232 }
233 }
234
235 NumFaces++;
236
237 /* Test number of faces using the extended Euler's formula.
238 For connected components, Euler's formula is f=m-n+2, but
239 for disconnected graphs it is extended to f=m-n+1+c where
240 c is the number of connected components.*/
241
242 return NumFaces == theGraph->M - theGraph->N + 1 + connectedComponents
243 ? OK : NOTOK;
244 }
245
246 /********************************************************************
247 _CheckAllVerticesOnExternalFace()
248
249 Determines whether or not any vertices have been embedded within
250 the bounding cycle of the external face.
251 The input graph may be disconnected, so this routine walks the
252 external face starting at each vertex with no DFSParent.
253
254 return OK if all vertices visited on external face walks, NOTOK otherwise
255 ********************************************************************/
256
_CheckAllVerticesOnExternalFace(graphP theGraph)257 int _CheckAllVerticesOnExternalFace(graphP theGraph)
258 {
259 int v;
260
261 // Mark all vertices unvisited
262 _ClearVertexVisitedFlags(theGraph, FALSE);
263
264 // For each connected component, walk its external face and
265 // mark the vertices as visited
266 for (v = gp_GetFirstVertex(theGraph); gp_VertexInRange(theGraph, v); v++)
267 {
268 if (gp_IsDFSTreeRoot(theGraph, v))
269 _MarkExternalFaceVertices(theGraph, v);
270 }
271
272 // If any vertex is unvisited, then the embedding is not an outerplanar
273 // embedding, so we return NOTOK
274 for (v = gp_GetFirstVertex(theGraph); gp_VertexInRange(theGraph, v); v++)
275 if (!gp_GetVertexVisited(theGraph, v))
276 return NOTOK;
277
278 // All vertices were found on external faces of the connected components
279 // so the embedding is an outerplanar embedding and we return OK
280 return OK;
281 }
282
283 /********************************************************************
284 _MarkExternalFaceVertices()
285
286 Walks the external face of the connected component containing the
287 start vertex, and marks the visited flag of all vertices found.
288 The start vertex is assumed to be on the external face.
289 This method assumed the embedding integrity has already been
290 verified to be correct.
291 This method correctly handles components that have cut vertices,
292 i.e. it does not assume that the outer face is a simple cycle;
293 it only assumes that all vertices are reachable by walking a
294 single face that starts with startVertex.
295 ********************************************************************/
296
_MarkExternalFaceVertices(graphP theGraph,int startVertex)297 void _MarkExternalFaceVertices(graphP theGraph, int startVertex)
298 {
299 int nextVertex = startVertex;
300 int e = gp_GetFirstArc(theGraph, nextVertex);
301 int eTwin;
302
303 // Handle the case of an isolated vertex
304 if (gp_IsNotArc(e))
305 {
306 gp_SetVertexVisited(theGraph, startVertex);
307 return;
308 }
309
310 // Process a non-trivial connected component
311 do {
312 gp_SetVertexVisited(theGraph, nextVertex);
313
314 // The arc out of the vertex just visited points to the next vertex
315 nextVertex = gp_GetNeighbor(theGraph, e);
316
317 // Arc used to enter the next vertex is needed so we can get the
318 // next edge in rotation order.
319 // Note: for bicomps, first and last arcs of all external face vertices
320 // indicate the edges that hold them to the external face
321 // But _JoinBicomps() has already occurred, so cut vertices
322 // will have external face edges other than the first and last arcs
323 // Hence we need this more sophisticated traversal method
324 eTwin = gp_GetTwinArc(theGraph, e);
325
326 // Now we get the next arc in rotation order as the new arc out to the
327 // vertex after nextVertex. This sets us up for the next iteration.
328 // Note: We cannot simply follow the chain of nextVertex first arcs
329 // as we started out doing at the top of this method. This is
330 // because we are no longer dealing with bicomps only.
331 // Since _JoinBicomps() has already been invoked, there may now
332 // be cut vertices on the external face whose adjacency lists
333 // contain external face arcs in positions other than the first and
334 // and last arcs. We will visit those vertices multiple times,
335 // which is OK (just that we have to explain why we're calculating
336 // jout in this way).
337 e = gp_GetNextArcCircular(theGraph, eTwin);
338
339 // Now things get really interesting. The DFS root (startVertex) may
340 // itself be a cut vertex to which multiple bicomps have been joined.
341 // So we cannot simply stop when the external face walk gets back to
342 // startVertex. We must actually get back to startVertex using its
343 // last arc. This ensures that we've looped down into all the DFS
344 // subtrees rooted at startVertex and walked their external faces.
345
346 // Since we started the whole external face walk with the first arc
347 // of startVertex, we need to proceed until we reenter startVertex
348 // using its last arc.
349
350 } while (eTwin != gp_GetLastArc(theGraph, startVertex));
351 }
352
353
354 /********************************************************************
355 _CheckObstructionIntegrity()
356
357 Returns OK if theGraph is a subgraph of origGraph and it contains
358 an allowed homeomorph, and NOTOK otherwise.
359
360 For core planarity, the allowed homeomorphs are K_5 or K_{3,3}
361
362 Extension modules may overload this method to implement different
363 tests. For example, K_{3,3} search allows only K_{3,3} and
364 outerplanarity allows only K_4 or K_{2,3}.
365 ********************************************************************/
366
_CheckObstructionIntegrity(graphP theGraph,graphP origGraph)367 int _CheckObstructionIntegrity(graphP theGraph, graphP origGraph)
368 {
369 if (theGraph == NULL || origGraph == NULL)
370 return NOTOK;
371
372 if (_TestSubgraph(theGraph, origGraph) != TRUE)
373 {
374 return NOTOK;
375 }
376
377 if (theGraph->embedFlags == EMBEDFLAGS_PLANAR)
378 return _CheckKuratowskiSubgraphIntegrity(theGraph);
379
380 else if (theGraph->embedFlags == EMBEDFLAGS_OUTERPLANAR)
381 return _CheckOuterplanarObstructionIntegrity(theGraph);
382
383 return NOTOK;
384 }
385
386 /********************************************************************
387 _getImageVertices()
388
389 Count the number of vertices of each degree and find the locations of
390 the image vertices (also sometimes called the corners of the obstruction).
391 An image vertex is a vertex of degree three or higher because degree
392 2 vertices are generally internal to the paths between the image
393 vertices.
394
395 The notable exception is K_{2,3}, an obstruction to outerplanarity.
396 This routine does not know the obstruction it is looking for, so the
397 caller must decide whether there are any degree 2 vertices that should
398 be added to imageVerts.
399
400 Return NOTOK if any vertex of degree 1 or higher than the max is found
401 NOTOK if more than the max number of image vertices is found.
402 Return OK otherwise.
403 ********************************************************************/
404
_getImageVertices(graphP theGraph,int * degrees,int maxDegree,int * imageVerts,int maxNumImageVerts)405 int _getImageVertices(graphP theGraph, int *degrees, int maxDegree,
406 int *imageVerts, int maxNumImageVerts)
407 {
408 int K, v, imageVertPos, degree;
409
410 for (degree = 0; degree <= maxDegree; degree++)
411 degrees[degree] = 0;
412
413 for (K = 0; K < maxNumImageVerts; K++)
414 imageVerts[K] = NIL;
415
416 imageVertPos = 0;
417
418 for (v = gp_GetFirstVertex(theGraph); gp_VertexInRange(theGraph, v); v++)
419 {
420 degree = gp_GetVertexDegree(theGraph, v);
421 if (degree == 1)
422 return NOTOK;
423 if (degree > maxDegree)
424 return NOTOK;
425
426 degrees[degree]++;
427
428 if (imageVertPos < maxNumImageVerts && degree > 2)
429 imageVerts[imageVertPos++] = v;
430 else if (degree > 2)
431 return NOTOK;
432 }
433
434 return OK;
435 }
436
437 /********************************************************************
438 _TestForCompleteGraphObstruction()
439
440 theGraph - the graph to test
441 numVerts - the number of image vertices (corners) of the complete
442 graph homeomorph being tested for (e.g. 5 for a K5)
443 degrees - array of counts of the number of vertices of each degree
444 given by the array index. Only valid up to numVerts-1
445 imageVerts - the vertices of degree numVerts-1
446
447 This routine tests whether theGraph is a K_{numVerts} homeomorph for
448 numVerts >= 4.
449
450 returns FALSE if numVerts < 4,
451 if theGraph has other than numVerts image vertices
452 if theGraph contains other than degree 2 vertices plus
453 the image vertices
454 if any pair of image vertices lacks a connecting path
455 if any degree two vertices are not in the connecting paths
456 TRUE otherwise
457 ********************************************************************/
458
_TestForCompleteGraphObstruction(graphP theGraph,int numVerts,int * degrees,int * imageVerts)459 int _TestForCompleteGraphObstruction(graphP theGraph, int numVerts,
460 int *degrees, int *imageVerts)
461 {
462 int v, w;
463
464 // We need to make sure we have numVerts vertices of degree numVerts-1
465 // For example, if numVerts==5, then we're looking for a K5, so we
466 // need to have degrees[4] == 5 (5 vertices of degree 4)
467 if (degrees[numVerts-1] != numVerts)
468 return FALSE;
469
470 // All vertices need to be degree 0, degree 2 or degree numVerts-1
471 if (degrees[0]+degrees[2]+degrees[numVerts-1] != theGraph->N)
472 return FALSE;
473
474 // We clear all the vertex visited flags
475 _ClearVertexVisitedFlags(theGraph, FALSE);
476
477 // For each pair of image vertices, we test that there is a path
478 // between the two vertices. If so, the visited flags of the
479 // internal vertices along the path are marked
480 //
481 for (v = 0; v < numVerts; v++)
482 for (w = 0; w < numVerts; w++)
483 if (v != w)
484 if (_TestPath(theGraph, imageVerts[v],
485 imageVerts[w]) != TRUE)
486 return FALSE;
487
488 // The visited flags should have marked only degree two vertices,
489 // so for every marked vertex, we subtract one from the count of
490 // the degree two vertices.
491 for (v = gp_GetFirstVertex(theGraph); gp_VertexInRange(theGraph, v); v++)
492 if (gp_GetVertexVisited(theGraph, v))
493 degrees[2]--;
494
495 /* If every degree 2 vertex is used in a path between image
496 vertices, then there are no extra pieces of the graph
497 in theGraph. Specifically, the prior tests identify
498 a K_5 and ensure that nothing else could exist in the
499 graph except extra degree 2 vertices, which must be
500 joined in a cycle so that all are degree 2. */
501
502 return degrees[2] == 0 ? TRUE : FALSE;
503 }
504
505 /********************************************************************
506 _TestForK33GraphObstruction()
507
508 theGraph - the graph to test
509 degrees - array of counts of the number of vertices of each degree
510 given by the array index. Only valid up to numVerts-1
511 imageVerts - the degree 3 vertices of the K3,3 homeomorph
512
513 This routine tests whether theGraph is a K_{3,3} homeomorph.
514
515 returns TRUE if so, FALSE if not
516 ********************************************************************/
517
_TestForK33GraphObstruction(graphP theGraph,int * degrees,int * imageVerts)518 int _TestForK33GraphObstruction(graphP theGraph, int *degrees, int *imageVerts)
519 {
520 int v, K, imageVertPos, temp, success;
521
522 if (degrees[4] != 0)
523 return FALSE;
524
525 if (degrees[3] != 6)
526 return FALSE;
527
528 /* Partition the six image vertices into two sets of 3
529 (or report failure) */
530
531 for (imageVertPos = 3; imageVertPos < 6; imageVertPos++)
532 {
533 K = 0;
534 success = FALSE;
535 do {
536 if (_TestPath(theGraph, imageVerts[imageVertPos], imageVerts[0]) == TRUE)
537 {
538 success = TRUE;
539 break;
540 }
541
542 K++;
543 temp = imageVerts[K];
544 imageVerts[K] = imageVerts[imageVertPos];
545 imageVerts[imageVertPos] = temp;
546 } while (K < 3);
547
548 if (!success)
549 return FALSE;
550 }
551
552 /* Now test the paths between each of the first three vertices and
553 each of the last three vertices */
554
555 _ClearVertexVisitedFlags(theGraph, FALSE);
556
557 for (imageVertPos=0; imageVertPos<3; imageVertPos++)
558 for (K=3; K<6; K++)
559 if (_TestPath(theGraph, imageVerts[imageVertPos],
560 imageVerts[K]) != TRUE)
561 return FALSE;
562
563 for (v = gp_GetFirstVertex(theGraph); gp_VertexInRange(theGraph, v); v++)
564 if (gp_GetVertexVisited(theGraph, v))
565 degrees[2]--;
566
567 /* If every degree 2 vertex is used in a path between image
568 vertices, then there are no extra pieces of the graph
569 in theGraph. Specifically, the prior tests identify
570 a K_{3,3} and ensure that nothing else could exist in the
571 graph except extra degree 2 vertices, which must be
572 joined in a cycle so that all are degree 2. */
573
574 return degrees[2] == 0 ? TRUE : FALSE;
575 }
576
577 /********************************************************************
578 _CheckKuratowskiSubgraphIntegrity()
579
580 This function checks whether theGraph received as input contains
581 either a K_5 or K_{3,3} homeomorph.
582
583 RETURNS: OK if theGraph contains a K_5 or K_{3,3} homeomorph,
584 NOTOK otherwise
585
586 To be a K_5 homeomorph, there must be exactly 5 vertices of degree 4,
587 which are called 'image' vertices, and all other vertices must be
588 either degree 2 or degree 0. Furthermore, each of the image vertices
589 must be able to reach all of the other image vertices by a single edge
590 or a path of degree two vertices.
591
592 To be a K_{3,3} homeomorph, there must be exactly 6 vertices of degree 3,
593 which are called 'image' vertices, and all other vertices must be either
594 degree 2 or degree 0. Furthermore, the image vertices must be connected
595 by edges or paths of degree two vertices in the manner suggested by
596 a K_{3,3}. To test this, we select an image vertex U, and determine
597 three image vertices X, Y and Z reachable from U by single edges or
598 paths of degree 2 vertices. Then, we check that the two remaining image
599 vertices, V and W, can also reach X, Y and Z by single edges or paths of
600 degree 2 vertices.
601
602 It is not necessary to check that the paths between the image vertices
603 are distinct since if the paths had a common vertex, then the common
604 vertex would not be degree 2.
605 ********************************************************************/
606
_CheckKuratowskiSubgraphIntegrity(graphP theGraph)607 int _CheckKuratowskiSubgraphIntegrity(graphP theGraph)
608 {
609 int degrees[5], imageVerts[6];
610
611 if (_getImageVertices(theGraph, degrees, 4, imageVerts, 6) != OK)
612 return NOTOK;
613
614 if (_TestForCompleteGraphObstruction(theGraph, 5, degrees, imageVerts) == TRUE)
615 {
616 return OK;
617 }
618
619 if (_TestForK33GraphObstruction(theGraph, degrees, imageVerts) == TRUE)
620 {
621 return OK;
622 }
623
624 return NOTOK;
625 }
626
627 /********************************************************************
628 _TestForK23GraphObstruction()
629
630 theGraph - the graph to test
631 degrees - array of counts of the number of vertices of each degree
632 given by the array index. Only valid up to numVerts-1
633 imageVerts - the degree 3 vertices of the K2,3 homeomorph
634
635 This routine tests whether theGraph is a K_{2,3} homeomorph.
636 This routine operates over the results of _getImageVertices()
637
638 returns TRUE if so, FALSE if not
639 ********************************************************************/
640
_TestForK23GraphObstruction(graphP theGraph,int * degrees,int * imageVerts)641 int _TestForK23GraphObstruction(graphP theGraph, int *degrees, int *imageVerts)
642 {
643 int v, e, imageVertPos;
644
645 // This function operates over the imageVerts results produced by
646 // getImageVertices, which only finds vertices of degree 3 or higher.
647 // So, for a K2,3, there must be exactly two degree 3 vertices and
648 // no degree 4 vertices.
649 if (degrees[3] != 2)
650 return FALSE;
651
652 // For K_{2,3}, the three vertices of degree 2 were not
653 // detected as image vertices because degree 2 vertices
654 // are indistinguishable from the internal path vertices
655 // between the image vertices. So, here we acknowledge
656 // that more image vertices need to be selected.
657 imageVertPos = 2;
658
659 // Assign the remaining three image vertices to be the
660 // neighbors of the first degree 3 image vertex.
661 // Ensure that each is distinct from the second
662 // degree 3 image vertex. This must be the case because
663 // the two degree 3 image vertices are in the same partition
664 // and hence must not be adjacent.
665
666 e = gp_GetFirstArc(theGraph, imageVerts[0]);
667 while (gp_IsArc(e))
668 {
669 imageVerts[imageVertPos] = gp_GetNeighbor(theGraph, e);
670 if (imageVerts[imageVertPos] == imageVerts[1])
671 return FALSE;
672 imageVertPos++;
673 e = gp_GetNextArc(theGraph, e);
674 }
675
676 /* The paths from imageVerts[0] to each of the new degree 2
677 image vertices are the edges we just traversed.
678 Now test the paths between each of the degree 2 image
679 vertices and imageVerts[1]. */
680
681 _ClearVertexVisitedFlags(theGraph, FALSE);
682
683 for (imageVertPos=2; imageVertPos<5; imageVertPos++)
684 {
685 if (_TestPath(theGraph, imageVerts[imageVertPos],
686 imageVerts[1]) != TRUE)
687 return FALSE;
688
689 gp_SetVertexVisited(theGraph, imageVerts[imageVertPos]);
690 }
691
692 for (v = gp_GetFirstVertex(theGraph); gp_VertexInRange(theGraph, v); v++)
693 if (gp_GetVertexVisited(theGraph, v))
694 degrees[2]--;
695
696 /* If every degree 2 vertex is used in a path between the
697 two degree 3 image vertices, then there are no extra
698 pieces of the graph in theGraph. Specifically, the
699 prior tests identify a K_{2,3} and ensure that nothing
700 else could exist in the graph... except extra degree 2
701 vertices joined in a cycle. We return NOTOK in that case. */
702
703 return degrees[2] == 0 ? TRUE : FALSE;
704 }
705
706 /********************************************************************
707 _CheckOuterplanarObstructionIntegrity()
708
709 This function checks whether theGraph received as input contains
710 either a K_4 or K_{2,3} homeomorph.
711
712 RETURNS: OK if theGraph contains a K_4 or K_{2,3} homeomorph,
713 NOTOK otherwise
714
715 To be a K_4 homeomorph, there must be exactly 4 vertices of degree 3,
716 which are called 'image' vertices, and all other vertices must be
717 either degree 2 or degree 0. Furthermore, each of the image vertices
718 must be able to reach all of the other image vertices by a single edge
719 or a path of degree two vertices.
720
721 To be a K_{2,3} homeomorph, there must be exactly 2 vertices of degree 3.
722 All other vertices must be degree 2. Furthermore, the two degree 3
723 vertices must have three internally disjoint paths connecting them,
724 and each path must contain at least two edges (i.e. at least one internal
725 vertex). The two degree 3 vertices are image vertices, and an internal
726 vertex from each of the three paths contributes the remaining three
727 image vertices.
728
729 It is not necessary to check that the paths between the degree three
730 vertices are distinct since if the paths had a common vertex, then the
731 common vertex would not be degree 2.
732 ********************************************************************/
733
_CheckOuterplanarObstructionIntegrity(graphP theGraph)734 int _CheckOuterplanarObstructionIntegrity(graphP theGraph)
735 {
736 int degrees[4], imageVerts[5];
737
738 if (_getImageVertices(theGraph, degrees, 3, imageVerts, 5) != OK)
739 return NOTOK;
740
741 if (_TestForCompleteGraphObstruction(theGraph, 4, degrees, imageVerts) == TRUE)
742 {
743 return OK;
744 }
745
746 if (_TestForK23GraphObstruction(theGraph, degrees, imageVerts) == TRUE)
747 {
748 return OK;
749 }
750
751 /* We get here only if we failed to recognize an outerplanarity
752 obstruction, so we return failure */
753
754 return NOTOK;
755 }
756
757 /********************************************************************
758 _TestPath()
759
760 This function determines whether there exists a path of degree two
761 vertices between two given vertices. The function marks each
762 degree two vertex as visited. It returns TRUE if it finds the
763 path and FALSE otherwise.
764 ********************************************************************/
765
_TestPath(graphP theGraph,int U,int V)766 int _TestPath(graphP theGraph, int U, int V)
767 {
768 int e = gp_GetFirstArc(theGraph, U);
769
770 while (gp_IsArc(e))
771 {
772 if (_TryPath(theGraph, e, V) == OK)
773 {
774 _MarkPath(theGraph, e);
775 return TRUE;
776 }
777
778 e = gp_GetNextArc(theGraph, e);
779 }
780
781 return FALSE;
782 }
783
784 /********************************************************************
785 _TryPath()
786
787 This function seeks a given path to a vertex V starting with a
788 given edge out of a starting vertex U. The path is allowed to
789 contain zero or more degree two vertices, but we stop as soon as
790 a vertex of degree higher than two is encountered.
791 The function returns boolean true if that vertex is V, and
792 boolean false otherwise.
793 ********************************************************************/
794
_TryPath(graphP theGraph,int e,int V)795 int _TryPath(graphP theGraph, int e, int V)
796 {
797 int eTwin, nextVertex;
798
799 nextVertex = gp_GetNeighbor(theGraph, e);
800
801 // while nextVertex is strictly degree 2
802 while (gp_IsArc(gp_GetFirstArc(theGraph, nextVertex)) &&
803 gp_IsArc(gp_GetLastArc(theGraph, nextVertex)) &&
804 gp_GetNextArc(theGraph, gp_GetFirstArc(theGraph, nextVertex)) == gp_GetLastArc(theGraph, nextVertex))
805 {
806 eTwin = gp_GetTwinArc(theGraph, e);
807 e = gp_GetFirstArc(theGraph, nextVertex);
808 if (e == eTwin)
809 e = gp_GetLastArc(theGraph, nextVertex);
810
811 nextVertex = gp_GetNeighbor(theGraph, e);
812 }
813
814 return nextVertex == V ? TRUE : FALSE;
815 }
816
817 /********************************************************************
818 _MarkPath()
819
820 This function sets the visitation flag on all degree two vertices
821 along a path to a vertex V that starts with a given edge out of
822 a starting vertex U.
823 ********************************************************************/
824
_MarkPath(graphP theGraph,int e)825 void _MarkPath(graphP theGraph, int e)
826 {
827 int eTwin, nextVertex;
828
829 nextVertex = gp_GetNeighbor(theGraph, e);
830 // while nextVertex is strictly degree 2
831 while (gp_IsArc(gp_GetFirstArc(theGraph, nextVertex)) &&
832 gp_IsArc(gp_GetLastArc(theGraph, nextVertex)) &&
833 gp_GetNextArc(theGraph, gp_GetFirstArc(theGraph, nextVertex)) == gp_GetLastArc(theGraph, nextVertex))
834 {
835 gp_SetVertexVisited(theGraph, nextVertex);
836
837 eTwin = gp_GetTwinArc(theGraph, e);
838 e = gp_GetFirstArc(theGraph, nextVertex);
839 if (e == eTwin)
840 e = gp_GetLastArc(theGraph, nextVertex);
841
842 nextVertex = gp_GetNeighbor(theGraph, e);
843 }
844 }
845
846 /********************************************************************
847 _TestSubgraph()
848 Checks whether theSubgraph is in fact a subgraph of theGraph.
849 For each vertex v in graph G and subgraph H, we iterate the adjacency
850 list of H(v) and, for each neighbor w, we mark G(w). Then, we
851 iterate the adjacency list of G(v) and unmark each neighbor. Then,
852 we iterate the adjacency list of H(v) again to ensure that every
853 neighbor w was unmarked. If there exists a marked neighbor, then
854 H(v) contains an incident edge that is not incident to G(v).
855
856 Returns TRUE if theSubgraph contains only edges from theGraph,
857 FALSE otherwise
858 ********************************************************************/
859
_TestSubgraph(graphP theSubgraph,graphP theGraph)860 int _TestSubgraph(graphP theSubgraph, graphP theGraph)
861 {
862 int v, e, degreeCount;
863 int Result = TRUE;
864 int invokeSortOnGraph = FALSE;
865 int invokeSortOnSubgraph = FALSE;
866
867 // If the graph is not sorted by DFI, but the alleged subgraph is,
868 // then "unsort" the alleged subgraph so both have the same vertex order
869 if (!(theGraph->internalFlags & FLAGS_SORTEDBYDFI) &&
870 (theSubgraph->internalFlags & FLAGS_SORTEDBYDFI))
871 {
872 invokeSortOnSubgraph = TRUE;
873 gp_SortVertices(theSubgraph);
874 }
875
876 // If the graph is not sorted by DFI, but the alleged subgraph is,
877 // then "unsort" the alleged subgraph so both have the same vertex order
878 if (!(theSubgraph->internalFlags & FLAGS_SORTEDBYDFI) &&
879 (theGraph->internalFlags & FLAGS_SORTEDBYDFI))
880 {
881 invokeSortOnGraph = TRUE;
882 gp_SortVertices(theGraph);
883 }
884
885 /* We clear all visitation flags */
886
887 _ClearVertexVisitedFlags(theGraph, FALSE);
888
889 /* For each vertex... */
890 for (v = gp_GetFirstVertex(theSubgraph), degreeCount = 0; gp_VertexInRange(theSubgraph, v); v++)
891 {
892 /* For each neighbor w in the adjacency list of vertex v in the
893 subgraph, set the visited flag in w in the graph */
894
895 e = gp_GetFirstArc(theSubgraph, v);
896 while (gp_IsArc(e))
897 {
898 if (gp_IsNotVertex(gp_GetNeighbor(theSubgraph, e)))
899 {
900 Result = FALSE;
901 break;
902 }
903 degreeCount++;
904 gp_SetVertexVisited(theGraph, gp_GetNeighbor(theSubgraph, e));
905 e = gp_GetNextArc(theSubgraph, e);
906 }
907
908 if (Result != TRUE)
909 break;
910
911 /* For each neighbor w in the adjacency list of vertex v in the graph,
912 clear the visited flag in w in the graph */
913
914 e = gp_GetFirstArc(theGraph, v);
915 while (gp_IsArc(e))
916 {
917 if (gp_IsNotVertex(gp_GetNeighbor(theGraph, e)))
918 {
919 Result = FALSE;
920 break;
921 }
922 gp_ClearVertexVisited(theGraph, gp_GetNeighbor(theGraph, e));
923 e = gp_GetNextArc(theGraph, e);
924 }
925
926 if (Result != TRUE)
927 break;
928
929 /* For each neighbor w in the adjacency list of vertex v in the subgraph,
930 ensure that the visited flag in w was cleared (otherwise, the "subgraph"
931 would incorrectly contain an adjacency not contained in the ("super") graph) */
932
933 e = gp_GetFirstArc(theSubgraph, v);
934 while (gp_IsArc(e))
935 {
936 if (gp_GetVertexVisited(theGraph, gp_GetNeighbor(theSubgraph, e)))
937 {
938 Result = FALSE;
939 break;
940 }
941 e = gp_GetNextArc(theSubgraph, e);
942 }
943
944 if (Result != TRUE)
945 break;
946 }
947
948 // Restore the DFI sort order of either graph if it had to be reordered at the start
949 if (invokeSortOnSubgraph)
950 gp_SortVertices(theSubgraph);
951 if (invokeSortOnGraph)
952 gp_SortVertices(theGraph);
953
954 // Assuming theSubgraph is a subgraph, we also do an extra integrity check to ensure
955 // proper edge array utilization
956 if (Result == TRUE)
957 {
958 // If the edge count is wrong, we fail the subgraph test in a way that invokes
959 // the name NOTOK so that in debug mode there is more trace on the failure.
960 if (degreeCount != 2*theSubgraph->M)
961 Result = NOTOK == FALSE ? NOTOK : FALSE;
962 }
963
964 return Result;
965 }
966