1 /** \file
2 * \brief Implements Hopcroft/Tarjan algorithm for finding the
3 * triconnected components of a biconnected multi-graph
4 *
5 * \author Carsten Gutwenger
6 *
7 * \par License:
8 * This file is part of the Open Graph Drawing Framework (OGDF).
9 *
10 * \par
11 * Copyright (C)<br>
12 * See README.md in the OGDF root directory for details.
13 *
14 * \par
15 * This program is free software; you can redistribute it and/or
16 * modify it under the terms of the GNU General Public License
17 * Version 2 or 3 as published by the Free Software Foundation;
18 * see the file LICENSE.txt included in the packaging of this file
19 * for details.
20 *
21 * \par
22 * This program is distributed in the hope that it will be useful,
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25 * GNU General Public License for more details.
26 *
27 * \par
28 * You should have received a copy of the GNU General Public
29 * License along with this program; if not, see
30 * http://www.gnu.org/copyleft/gpl.html
31 */
32
33
34 #include <ogdf/graphalg/Triconnectivity.h>
35 #include <ogdf/basic/simple_graph_alg.h>
36 #include <ogdf/basic/NodeSet.h>
37
38 //#define TRIC_COMP_OUTPUT
39
40
41 namespace ogdf {
42
43
~Triconnectivity()44 Triconnectivity::~Triconnectivity()
45 {
46 delete m_pGC;
47 }
48
49
50 // Divides G into triconnected components.
Triconnectivity(const Graph & G)51 Triconnectivity::Triconnectivity (const Graph& G) :
52 m_ESTACK(G.numberOfEdges())
53 {
54 m_pGC = new GraphCopySimple(G);
55 GraphCopySimple &GC = *m_pGC;
56
57 const int n = GC.numberOfNodes();
58 const int m = GC.numberOfEdges();
59
60 #ifdef TRIC_COMP_OUTPUT
61 std::cout << "Dividing G into triconnected components.\n" << std::endl;
62 std::cout << "n = " << n << ", m = " << m << std::endl << std::endl;
63 #endif
64
65 m_component = Array<CompStruct>(3*m-6);
66 m_numComp = 0;
67
68 // special cases
69 OGDF_ASSERT(n >= 2);
70 OGDF_HEAVY_ASSERT(isBiconnected(G));
71
72 if (n <= 2) {
73 OGDF_ASSERT(m >= 3);
74 CompStruct &C = newComp();
75 for (edge e : GC.edges)
76 C << e;
77 C.m_type = CompType::bond;
78 return;
79 }
80
81 m_TYPE.init(GC,EdgeType::unseen);
82 splitMultiEdges();
83
84 // initialize arrays
85 m_NUMBER.init(GC,0); m_LOWPT1.init(GC);
86 m_LOWPT2.init(GC); m_FATHER.init(GC,nullptr);
87 m_ND .init(GC); m_DEGREE.init(GC);
88 m_TREE_ARC.init(GC,nullptr);
89 m_NODEAT = Array<node>(1,n);
90
91 m_numCount = 0;
92 m_start = GC.firstNode();
93 DFS1(GC,m_start,nullptr);
94
95 for (edge e : GC.edges) {
96 bool up = (m_NUMBER[e->target()] - m_NUMBER[e->source()] > 0);
97 if ((up && m_TYPE[e] == EdgeType::frond) || (!up && m_TYPE[e] == EdgeType::tree))
98 GC.reverseEdge(e);
99 }
100
101 #ifdef TRIC_COMP_OUTPUT
102 std::cout << "\nnode\tNUMBER\tFATHER\tLOWPT1\tLOWPT2\tND" << std::endl;
103 for (node v : GC.nodes) {
104 std::cout << GC.original(v) << ": \t" << m_NUMBER[v] << " \t";
105 if (m_FATHER[v] == 0) std::cout << "nil \t";
106 else std::cout << GC.original(m_FATHER[v]) << " \t";
107 std::cout << m_LOWPT1[v] << " \t" << m_LOWPT2[v] << " \t" << m_ND[v] << std::endl;
108 }
109 #endif
110
111 m_A.init(GC);
112 m_IN_ADJ.init(GC,nullptr);
113 buildAcceptableAdjStruct(GC);
114
115 #ifdef TRIC_COMP_OUTPUT
116 std::cout << "\nadjaceny lists:" << std::endl;
117 for (node v : GC.nodes) {
118 std::cout << v << "\t";
119 for(edge ei : m_A[v]) {
120 printOs(ei);
121 }
122 std::cout << std::endl;
123 }
124 #endif
125
126 DFS2(GC);
127
128 #ifdef TRIC_COMP_OUTPUT
129 std::cout << "\nnode\tNEWNUM\tLOWPT1\tLOWPT2\tHIGHPT" << std::endl;
130 for (node v : GC.nodes) {
131 std::cout << GC.original(v) << ": \t" << m_NEWNUM[v] << " \t";
132 std::cout << m_LOWPT1[v] << " \t" << m_LOWPT2[v] << " \t";
133 for(int i : m_HIGHPT[v])
134 std::cout << i << " ";
135 std::cout << std::endl;
136 }
137
138 std::cout << "\nedges starting a path:" << std::endl;
139 for (edge e : GC.edges) {
140 if (m_START[e]) {
141 printOs(e);
142 }
143 }
144 #endif
145
146
147 m_TSTACK_h = new int[2*m+1];
148 m_TSTACK_a = new int[2*m+1];
149 m_TSTACK_b = new int[2*m+1];
150 m_TSTACK_a[m_top = 0] = -1; // start with EOS
151
152 pathSearch(G,m_start);
153
154 // last split component
155 CompStruct &C = newComp();
156 while(!m_ESTACK.empty()) {
157 C << m_ESTACK.popRet();
158 }
159 C.m_type = (C.m_edges.size() > 4) ? CompType::triconnected : CompType::polygon;
160
161 #ifdef TRIC_COMP_OUTPUT
162 printStacks();
163 #endif
164
165 delete[] m_TSTACK_h;
166 delete[] m_TSTACK_a;
167 delete[] m_TSTACK_b;
168
169 // free resources
170 m_NUMBER.init(); m_LOWPT1.init();
171 m_LOWPT2.init(); m_FATHER.init();
172 m_ND .init(); m_TYPE .init();
173 m_A .init(); m_NEWNUM.init();
174 m_HIGHPT.init(); m_START .init();
175 m_DEGREE.init(); m_TREE_ARC.init();
176 m_IN_ADJ.init(); m_IN_HIGH.init();
177 m_NODEAT.init();
178 m_ESTACK.clear();
179
180 assembleTriconnectedComponents();
181
182 // Caution: checkComp() assumes that the graph is simple!
183 #if 0
184 OGDF_ASSERT(checkComp());
185 #endif
186
187 #ifdef TRIC_COMP_OUTPUT
188 std::cout << "\n\nTriconnected components:\n";
189 for (int i = 0; i < m_numComp; i++) {
190 const List<edge> &L = m_component[i].m_edges;
191 if (L.size() == 0) continue;
192 std::cout << "[" << i << "] ";
193 switch(m_component[i].m_type) {
194 case CompType::bond: std::cout << "bond "; break;
195 case CompType::polygon: std::cout << "polygon "; break;
196 case CompType::triconnected: std::cout << "triconnected "; break;
197 }
198
199 for(edge ei : L)
200 printOs(ei);
201 std::cout << "\n";
202 }
203 #endif
204 }
205
206
207 // Tests G for triconnectivity and returns a cut vertex in
208 // s1 or a separation pair in (s1,s2).
Triconnectivity(const Graph & G,bool & isTric,node & s1,node & s2)209 Triconnectivity::Triconnectivity(const Graph &G, bool &isTric, node &s1, node &s2)
210 {
211 m_pGC = new GraphCopySimple(G);
212 GraphCopySimple &GC = *m_pGC;
213
214 const int n = GC.numberOfNodes();
215 const int m = GC.numberOfEdges();
216
217 s1 = s2 = nullptr;
218
219 if (n < 2) {
220 isTric = true;
221 return;
222 } else if (n == 2) {
223 isTric = hasNonSelfLoopEdges(G);
224 return;
225 } else if (m == 0) {
226 isTric = false;
227 return;
228 }
229
230 makeLoopFree(GC);
231 makeParallelFreeUndirected(GC);
232
233 // initialize arrays
234 m_TYPE.init(GC,EdgeType::unseen);
235 m_NUMBER.init(GC,0); m_LOWPT1.init(GC);
236 m_LOWPT2.init(GC); m_FATHER.init(GC,nullptr);
237 m_ND .init(GC); m_DEGREE.init(GC);
238 m_NODEAT.init(1,n);
239
240 m_TREE_ARC.init(GC,nullptr); // probably not required
241
242 m_numCount = 0;
243 m_start = GC.firstNode();
244 DFS1(GC,m_start,nullptr,s1);
245
246 // graph not even connected?
247 if(m_numCount < n) {
248 s1 = nullptr; isTric = false;
249 return;
250 }
251
252 // graph no biconnected?
253 if(s1 != nullptr) {
254 s1 = GC.original(s1);
255 isTric = false; // s1 is a cut vertex
256 return;
257 }
258
259 for (edge e : GC.edges) {
260 bool up = (m_NUMBER[e->target()] - m_NUMBER[e->source()] > 0);
261 if ((up && m_TYPE[e] == EdgeType::frond) || (!up && m_TYPE[e] == EdgeType::tree))
262 GC.reverseEdge(e);
263 }
264
265 m_A.init(GC);
266 m_IN_ADJ.init(GC,nullptr);
267 buildAcceptableAdjStruct(GC);
268
269 DFS2(GC);
270
271 m_TSTACK_h = new int[m];
272 m_TSTACK_a = new int[m];
273 m_TSTACK_b = new int[m];
274 m_TSTACK_a[m_top = 0] = -1; // start with EOS
275
276 isTric = pathSearch(G,m_start,s1,s2);
277 if(s1) {
278 s1 = GC.original(s1);
279 s2 = GC.original(s2);
280 }
281
282 delete[] m_TSTACK_h;
283 delete[] m_TSTACK_a;
284 delete[] m_TSTACK_b;
285
286 // free resources
287 m_NUMBER.init(); m_LOWPT1.init();
288 m_LOWPT2.init(); m_FATHER.init();
289 m_ND .init(); m_TYPE .init();
290 m_A .init(); m_NEWNUM.init();
291 m_HIGHPT.init(); m_START .init();
292 m_DEGREE.init(); m_TREE_ARC.init();
293 m_IN_ADJ.init(); m_IN_HIGH.init();
294 m_NODEAT.init();
295 }
296
297
298 // Splits bundles of multi-edges into bonds and creates
299 // a new virtual edge in GC.
splitMultiEdges()300 void Triconnectivity::splitMultiEdges()
301 {
302 GraphCopySimple &GC = *m_pGC;
303
304 SListPure<edge> edges;
305 EdgeArray<int> minIndex(GC), maxIndex(GC);
306 parallelFreeSortUndirected(GC,edges,minIndex,maxIndex);
307
308 SListIterator<edge> it;
309 for (it = edges.begin(); it.valid(); ) {
310 edge e = *it;
311 int minI = minIndex[e], maxI = maxIndex[e];
312 ++it;
313 if (it.valid() && minI == minIndex[*it] && maxI == maxIndex[*it]) {
314 CompStruct &C = newComp(CompType::bond);
315 C << GC.newEdge(e->source(),e->target()) << e << *it;
316 m_TYPE[e] = m_TYPE[*it] = EdgeType::removed;
317
318 for (++it; it.valid() &&
319 minI == minIndex[*it] && maxI == maxIndex[*it]; ++it)
320 {
321 C << *it;
322 m_TYPE[*it] = EdgeType::removed;
323 }
324 }
325 }
326 }
327
328 // Checks if computed triconnected components are correct.
checkSepPair(edge eVirt)329 bool Triconnectivity::checkSepPair(edge eVirt)
330 {
331 GraphCopySimple G(*m_pGC);
332
333 G.delNode(G.copy(m_pGC->original(eVirt->source())));
334 G.delNode(G.copy(m_pGC->original(eVirt->target())));
335
336 return !isConnected(G);
337 }
338
checkComp()339 bool Triconnectivity::checkComp()
340 {
341 bool ok = true;
342
343 GraphCopySimple &GC = *m_pGC;
344 GraphCopySimple GTest(GC.original());
345
346 if (!isLoopFree(GC)) {
347 ok = false;
348 std::cout << "GC contains loops!" << std::endl;
349 }
350
351 EdgeArray<int> count(GC,0);
352 for (int i = 0; i < m_numComp; i++) {
353 for(edge e : m_component[i].m_edges)
354 count[e]++;
355 }
356
357 for (edge e : GC.edges) {
358 if (GC.original(e) == nullptr) {
359 if (count[e] != 2) {
360 ok = false;
361 std::cout << "virtual edge contained " << count[e];
362 printOs(e); std::cout << std::endl;
363 }
364 if (!checkSepPair(e)) {
365 ok = false;
366 std::cout << "virtual edge"; printOs(e);
367 std::cout << " does not correspond to a sep. pair." << std::endl;
368 }
369
370 } else {
371 if (count[e] != 1) {
372 ok = false;
373 std::cout << "real edge contained " << count[e];
374 printOs(e); std::cout << std::endl;
375 }
376 }
377 }
378
379 NodeSet<> S(GC);
380 NodeArray<node> map(GC);
381
382 for(int i = 0; i < m_numComp; i++) {
383 CompStruct &C = m_component[i];
384 const List<edge> &L = C.m_edges;
385 if (L.size() == 0) continue;
386
387 S.clear();
388
389 for(edge e : L) {
390 S.insert(e->source());
391 S.insert(e->target());
392 }
393
394 const int n = S.size();
395
396 switch(C.m_type) {
397 case CompType::bond:
398 if (n != 2) {
399 ok = false;
400 std::cout << "bond [" << i << "] with " << n << " nodes!" << std::endl;
401 }
402 break;
403
404 case CompType::polygon:
405 if (n < 3) {
406 ok = false;
407 std::cout << "polygon [" << i << "] with " << n << " nodes!" << std::endl;
408 }
409
410 if (L.size() != n) {
411 ok = false;
412 std::cout << "polygon [" << i << "] with " << n << " vertices and " << L.size() << " edges!" << std::endl;
413
414 } else {
415 Graph Gp;
416 for(node v : S.nodes())
417 map[v] = Gp.newNode();
418 for(edge e : L)
419 Gp.newEdge(map[e->source()],map[e->target()]);
420
421 for (node v : Gp.nodes) {
422 if (v->degree() != 2) {
423 ok = false;
424 std::cout << "polygon [" << i << "] contains node with degree " << v->degree() << std::endl;
425 }
426 }
427 if (!isConnected(Gp)) {
428 ok = false;
429 std::cout << "polygon [" << i << "] not connected." << std::endl;
430 }
431 }
432 break;
433
434 case CompType::triconnected:
435 if (n < 4) {
436 ok = false;
437 std::cout << "triconnected component [" << i << "] with " << n << " nodes!" << std::endl;
438 }
439
440 {
441 Graph Gp;
442 for(node v : S.nodes())
443 map[v] = Gp.newNode();
444 for(edge e : L)
445 Gp.newEdge(map[e->source()],map[e->target()]);
446
447 if (!isTriconnectedPrimitive(Gp)) {
448 ok = false;
449 std::cout << "component [" << i << "] not triconnected!" << std::endl;
450 }
451 if (!isSimple(Gp)) {
452 ok = false;
453 std::cout << "triconnected component [" << i << "] not simple!" << std::endl;
454 }
455 }
456 break;
457
458 default:
459 ok = false;
460 std::cout << "component [" << i << "] with undefined type!" << std::endl;
461 }
462 }
463
464 return ok;
465 }
466
467
468 // joins bonds and polygons with common virtual edge in
469 // order to build the triconnected components.
assembleTriconnectedComponents()470 void Triconnectivity::assembleTriconnectedComponents()
471 {
472 GraphCopySimple &GC = *m_pGC;
473
474 EdgeArray<int> comp1(GC), comp2(GC);
475 EdgeArray<ListIterator<edge> > item1(GC,ListIterator<edge>());
476 EdgeArray<ListIterator<edge> > item2(GC);
477
478 bool *visited = new bool[m_numComp];
479
480 int i;
481 for(i = 0; i < m_numComp; i++) {
482 visited[i] = false;
483 List<edge> &L = m_component[i].m_edges;
484
485 ListIterator<edge> it;
486 for(it = L.begin(); it.valid(); ++it) {
487 edge e = *it;
488 if (!item1[e].valid()) {
489 comp1[e] = i; item1[e] = it;
490 } else {
491 comp2[e] = i; item2[e] = it;
492 }
493 }
494 }
495
496 for(i = 0; i < m_numComp; i++) {
497 CompStruct &C1 = m_component[i];
498 List<edge> &L1 = C1.m_edges;
499 visited[i] = true;
500
501 if (L1.size() == 0) continue;
502
503 if (C1.m_type == CompType::polygon || C1.m_type == CompType::bond) {
504 ListIterator<edge> it, itNext;
505 for(it = L1.begin(); it.valid(); it = itNext) {
506 itNext = it.succ();
507 edge e = *it;
508
509 if (GC.original(e) != nullptr) continue;
510
511 int j = comp1[e];
512 ListIterator<edge> it2;
513 if (visited[j]) {
514 j = comp2[e];
515 if (visited[j]) continue;
516 it2 = item2[e];
517 } else
518 it2 = item1[e];
519
520 CompStruct &C2 = m_component[j];
521
522 if (C2.m_type != C1.m_type) continue;
523
524 visited[j] = true;
525 List<edge> &L2 = C2.m_edges;
526
527 L2.del(it2);
528 L1.conc(L2);
529 if (!itNext.valid())
530 itNext = it.succ();
531 L1.del(it);
532
533 GC.delEdge(e);
534 }
535 }
536 }
537
538 delete[] visited;
539 }
540
541
542
543 // The first dfs-search
544 // computes NUMBER[v], FATHER[v], LOWPT1[v], LOWPT2[v],
545 // ND[v], TYPE[e], DEGREE[v]
DFS1(const Graph & G,node v,node u)546 void Triconnectivity::DFS1 (const Graph& G, node v, node u)
547 {
548 m_NUMBER[v] = ++m_numCount;
549 m_FATHER[v] = u;
550 m_DEGREE[v] = v->degree();
551
552 m_LOWPT1[v] = m_LOWPT2[v] = m_NUMBER[v];
553 m_ND[v] = 1;
554
555 for(adjEntry adj : v->adjEntries) {
556 edge e = adj->theEdge();
557
558 if (m_TYPE[e] != EdgeType::unseen)
559 continue;
560
561 node w = e->opposite(v);
562
563 if (m_NUMBER[w] == 0) {
564 m_TYPE[e] = EdgeType::tree;
565
566 m_TREE_ARC[w] = e;
567
568 DFS1(G,w,v);
569
570 if (m_LOWPT1[w] < m_LOWPT1[v]) {
571 m_LOWPT2[v] = min(m_LOWPT1[v],m_LOWPT2[w]);
572 m_LOWPT1[v] = m_LOWPT1[w];
573
574 } else if (m_LOWPT1[w] == m_LOWPT1[v]) {
575 m_LOWPT2[v] = min(m_LOWPT2[v],m_LOWPT2[w]);
576
577 } else {
578 m_LOWPT2[v] = min(m_LOWPT2[v],m_LOWPT1[w]);
579 }
580
581 m_ND[v] += m_ND[w];
582
583 } else {
584
585 m_TYPE[e] = EdgeType::frond;
586
587 if (m_NUMBER[w] < m_LOWPT1[v]) {
588 m_LOWPT2[v] = m_LOWPT1[v];
589 m_LOWPT1[v] = m_NUMBER[w];
590
591 } else if (m_NUMBER[w] > m_LOWPT1[v]) {
592 m_LOWPT2[v] = min(m_LOWPT2[v],m_NUMBER[w]);
593 }
594 }
595 }
596 }
597
DFS1(const Graph & G,node v,node u,node & s1)598 void Triconnectivity::DFS1 (const Graph& G, node v, node u, node &s1)
599 {
600 node firstSon = nullptr;
601
602 m_NUMBER[v] = ++m_numCount;
603 m_FATHER[v] = u;
604 m_DEGREE[v] = v->degree();
605
606 m_LOWPT1[v] = m_LOWPT2[v] = m_NUMBER[v];
607 m_ND[v] = 1;
608
609 for(adjEntry adj : v->adjEntries) {
610 edge e = adj->theEdge();
611
612 if (m_TYPE[e] != EdgeType::unseen)
613 continue;
614
615 node w = e->opposite(v);
616
617 if (m_NUMBER[w] == 0) {
618 m_TYPE[e] = EdgeType::tree;
619 if(firstSon == nullptr) firstSon = w;
620
621 m_TREE_ARC[w] = e;
622
623 DFS1(G,w,v,s1);
624
625 // check for cut vertex
626 if(m_LOWPT1[w] >= m_NUMBER[v] && (w != firstSon || u != nullptr))
627 s1 = v;
628
629 if (m_LOWPT1[w] < m_LOWPT1[v]) {
630 m_LOWPT2[v] = min(m_LOWPT1[v],m_LOWPT2[w]);
631 m_LOWPT1[v] = m_LOWPT1[w];
632
633 } else if (m_LOWPT1[w] == m_LOWPT1[v]) {
634 m_LOWPT2[v] = min(m_LOWPT2[v],m_LOWPT2[w]);
635
636 } else {
637 m_LOWPT2[v] = min(m_LOWPT2[v],m_LOWPT1[w]);
638 }
639
640 m_ND[v] += m_ND[w];
641
642 } else {
643
644 m_TYPE[e] = EdgeType::frond;
645
646 if (m_NUMBER[w] < m_LOWPT1[v]) {
647 m_LOWPT2[v] = m_LOWPT1[v];
648 m_LOWPT1[v] = m_NUMBER[w];
649
650 } else if (m_NUMBER[w] > m_LOWPT1[v]) {
651 m_LOWPT2[v] = min(m_LOWPT2[v],m_NUMBER[w]);
652 }
653 }
654 }
655 }
656
657
658 // Construction of ordered adjaceny lists
buildAcceptableAdjStruct(const Graph & G)659 void Triconnectivity::buildAcceptableAdjStruct(const Graph& G)
660 {
661 int max = 3*G.numberOfNodes()+2;
662 Array<List<edge> > BUCKET(1,max);
663
664 for (edge e : G.edges) {
665 EdgeType t = m_TYPE[e];
666 if (t == EdgeType::removed) continue;
667
668 node w = e->target();
669 int phi = (t == EdgeType::frond) ? 3*m_NUMBER[w]+1 : (
670 (m_LOWPT2[w] < m_NUMBER[e->source()]) ? 3*m_LOWPT1[w] :
671 3*m_LOWPT1[w]+2);
672 BUCKET[phi].pushBack(e);
673 }
674
675 for (int i = 1; i <= max; i++) {
676 for (edge e : BUCKET[i])
677 m_IN_ADJ[e] = m_A[e->source()].pushBack(e);
678 }
679 }
680
681
682 // The second dfs-search
pathFinder(const Graph & G,node v)683 void Triconnectivity::pathFinder(const Graph& G, node v)
684 {
685 m_NEWNUM[v] = m_numCount - m_ND[v] + 1;
686
687 for(edge e : m_A[v]) {
688 node w = e->opposite(v);
689
690 if (m_newPath) {
691 m_newPath = false;
692 m_START[e] = true;
693 }
694
695 if (m_TYPE[e] == EdgeType::tree) {
696 pathFinder(G,w);
697 m_numCount--;
698
699 } else {
700 m_IN_HIGH[e] = m_HIGHPT[w].pushBack(m_NEWNUM[v]);
701 m_newPath = true;
702 }
703 }
704 }
705
DFS2(const Graph & G)706 void Triconnectivity::DFS2 (const Graph& G)
707 {
708 m_NEWNUM .init(G,0);
709 m_HIGHPT .init(G);
710 m_IN_HIGH.init(G,ListIterator<int>());
711 m_START .init(G,false);
712
713 m_numCount = G.numberOfNodes();
714 m_newPath = true;
715
716 pathFinder(G,m_start);
717
718 Array<int> old2new(1,G.numberOfNodes());
719
720 for (node v : G.nodes)
721 old2new[m_NUMBER[v]] = m_NEWNUM[v];
722
723 for (node v : G.nodes) {
724 m_NODEAT[m_NEWNUM[v]] = v;
725 m_LOWPT1[v] = old2new[m_LOWPT1[v]];
726 m_LOWPT2[v] = old2new[m_LOWPT2[v]];
727 }
728 }
729
730
731 // recognition of split components
pathSearch(const Graph & G,node v)732 void Triconnectivity::pathSearch (const Graph& G, node v)
733 {
734 edge e;
735 int y, vnum = m_NEWNUM[v];
736 int a, b;
737
738 List<edge> &Adj = m_A[v];
739 int outv = Adj.size();
740
741 ListIterator<edge> it, itNext;
742 for(it = Adj.begin(); it.valid(); it=itNext)
743 {
744 itNext = it.succ();
745 e = *it;
746 node w = e->target();
747 int wnum = m_NEWNUM[w];
748
749 if (m_TYPE[e] == EdgeType::tree) {
750
751 if (m_START[e]) {
752 y = 0;
753 if (m_TSTACK_a[m_top] > m_LOWPT1[w]) {
754 do {
755 y = max(y,m_TSTACK_h[m_top]);
756 b = m_TSTACK_b[m_top--];
757 } while (m_TSTACK_a[m_top] > m_LOWPT1[w]);
758 TSTACK_push(y,m_LOWPT1[w],b);
759 } else {
760 TSTACK_push(wnum+m_ND[w]-1,m_LOWPT1[w],vnum);
761 }
762 TSTACK_pushEOS();
763 }
764
765 pathSearch(G,w);
766
767 m_ESTACK.push(m_TREE_ARC[w]); // add (v,w) to ESTACK (can differ from e!)
768
769 node x;
770
771 while (vnum != 1 && ((m_TSTACK_a[m_top] == vnum) ||
772 (m_DEGREE[w] == 2 && m_NEWNUM[m_A[w].front()->target()] > wnum)))
773 {
774 a = m_TSTACK_a[m_top];
775 b = m_TSTACK_b[m_top];
776
777 edge eVirt;
778
779 if (a == vnum && m_FATHER[m_NODEAT[b]] == m_NODEAT[a]) {
780 m_top--;
781 }
782
783 else {
784 edge e_ab = nullptr;
785
786 if (m_DEGREE[w] == 2 && m_NEWNUM[m_A[w].front()->target()] > wnum) {
787 #ifdef TRIC_COMP_OUTPUT
788 std::cout << std::endl << "\nfound type-2 separation pair " <<
789 m_pGC->original(v) << ", " <<
790 m_pGC->original(m_A[w].front()->target());
791 #endif
792
793 edge e1 = m_ESTACK.popRet();
794 edge e2 = m_ESTACK.popRet();
795 m_A[w].del(m_IN_ADJ[e2]);
796
797 x = e2->target();
798
799 eVirt = m_pGC->newEdge(v,x);
800 m_DEGREE[x]--; m_DEGREE[v]--;
801
802 OGDF_ASSERT(e2->source() == w);
803 CompStruct &C = newComp(CompType::polygon);
804 C << e1 << e2 << eVirt;
805
806 if (!m_ESTACK.empty()) {
807 e1 = m_ESTACK.top();
808 if (e1->source() == x && e1->target() == v) {
809 e_ab = m_ESTACK.popRet();
810 m_A[x].del(m_IN_ADJ[e_ab]);
811 delHigh(e_ab);
812 }
813 }
814
815 } else {
816 #ifdef TRIC_COMP_OUTPUT
817 std::cout << "\nfound type-2 separation pair " <<
818 m_pGC->original(m_NODEAT[a]) << ", " <<
819 m_pGC->original(m_NODEAT[b]);
820 #endif
821
822 int h = m_TSTACK_h[m_top--];
823
824 CompStruct &C = newComp();
825 while(true) {
826 edge xy = m_ESTACK.top();
827 x = xy->source();
828 node xyTarget = xy->target();
829 if (!(a <= m_NEWNUM[x] && m_NEWNUM[x] <= h &&
830 a <= m_NEWNUM[xyTarget] && m_NEWNUM[xyTarget] <= h)) break;
831
832 if ((m_NEWNUM[x] == a && m_NEWNUM[xyTarget] == b) ||
833 (m_NEWNUM[xyTarget] == a && m_NEWNUM[x] == b))
834 {
835 e_ab = m_ESTACK.popRet();
836 m_A[e_ab->source()].del(m_IN_ADJ[e_ab]);
837 delHigh(e_ab);
838
839 } else {
840 edge eh = m_ESTACK.popRet();
841 if (it != m_IN_ADJ[eh]) {
842 m_A[eh->source()].del(m_IN_ADJ[eh]);
843 delHigh(eh);
844 }
845 C << eh;
846 m_DEGREE[x]--; m_DEGREE[xyTarget]--;
847 }
848 }
849
850 eVirt = m_pGC->newEdge(m_NODEAT[a],m_NODEAT[b]);
851 C.finishTricOrPoly(eVirt);
852 x = m_NODEAT[b];
853 }
854
855 if (e_ab != nullptr) {
856 CompStruct &C = newComp(CompType::bond);
857 C << e_ab << eVirt;
858
859 eVirt = m_pGC->newEdge(v,x);
860 C << eVirt;
861
862 m_DEGREE[x]--; m_DEGREE[v]--;
863 }
864
865 m_ESTACK.push(eVirt);
866 *it = eVirt;
867 m_IN_ADJ[eVirt] = it;
868
869 m_DEGREE[x]++; m_DEGREE[v]++;
870 m_FATHER[x] = v;
871 m_TREE_ARC[x] = eVirt;
872 m_TYPE[eVirt] = EdgeType::tree;
873
874 w = x; wnum = m_NEWNUM[w];
875 }
876 }
877
878 if (m_LOWPT2[w] >= vnum && m_LOWPT1[w] < vnum && (m_FATHER[v] != m_start || outv >= 2))
879 {
880 #ifdef TRIC_COMP_OUTPUT
881 std::cout << "\nfound type-1 separation pair " <<
882 m_pGC->original(m_NODEAT[m_LOWPT1[w]]) << ", " <<
883 m_pGC->original(v);
884 #endif
885
886 CompStruct &C = newComp();
887 int xx;
888 OGDF_ASSERT(!m_ESTACK.empty()); // otherwise undefined behavior since x is not initialized
889 while (!m_ESTACK.empty()) {
890 edge xy = m_ESTACK.top();
891 xx = m_NEWNUM[xy->source()];
892 y = m_NEWNUM[xy->target()];
893
894 if (!((wnum <= xx && xx < wnum+m_ND[w]) || (wnum <= y && y < wnum+m_ND[w])))
895 break;
896
897 C << m_ESTACK.popRet();
898 delHigh(xy);
899 m_DEGREE[m_NODEAT[xx]]--; m_DEGREE[m_NODEAT[y]]--;
900 }
901
902 edge eVirt = m_pGC->newEdge(v,m_NODEAT[m_LOWPT1[w]]);
903 C.finishTricOrPoly(eVirt);
904
905 if ((xx == vnum && y == m_LOWPT1[w]) || (y == vnum && xx == m_LOWPT1[w])) {
906 CompStruct &compBond = newComp(CompType::bond);
907 edge eh = m_ESTACK.popRet();
908 if (m_IN_ADJ[eh] != it) {
909 m_A[eh->source()].del(m_IN_ADJ[eh]);
910 }
911 compBond << eh << eVirt;
912 eVirt = m_pGC->newEdge(v,m_NODEAT[m_LOWPT1[w]]);
913 compBond << eVirt;
914 m_IN_HIGH[eVirt] = m_IN_HIGH[eh];
915 m_DEGREE[v]--;
916 m_DEGREE[m_NODEAT[m_LOWPT1[w]]]--;
917 }
918
919 if (m_NODEAT[m_LOWPT1[w]] != m_FATHER[v]) {
920 m_ESTACK.push(eVirt);
921 *it = eVirt;
922 m_IN_ADJ[eVirt] = it;
923 if (!m_IN_HIGH[eVirt].valid() && high(m_NODEAT[m_LOWPT1[w]]) < vnum)
924 m_IN_HIGH[eVirt] = m_HIGHPT[m_NODEAT[m_LOWPT1[w]]].pushFront(vnum);
925
926 m_DEGREE[v]++;
927 m_DEGREE[m_NODEAT[m_LOWPT1[w]]]++;
928
929 } else {
930 Adj.del(it);
931
932 CompStruct &compBond = newComp(CompType::bond);
933 compBond << eVirt;
934 eVirt = m_pGC->newEdge(m_NODEAT[m_LOWPT1[w]],v);
935 compBond << eVirt;
936
937 edge eh = m_TREE_ARC[v];
938
939 compBond << m_TREE_ARC[v];
940
941 m_TREE_ARC[v] = eVirt;
942 m_TYPE[eVirt] = EdgeType::tree;
943
944 m_IN_ADJ[eVirt] = m_IN_ADJ[eh];
945 *m_IN_ADJ[eh] = eVirt;
946 }
947 }
948
949 if (m_START[e]) {
950 while (TSTACK_notEOS()) {
951 m_top--;
952 }
953 m_top--;
954 }
955
956 while (TSTACK_notEOS() &&
957 m_TSTACK_b[m_top] != vnum && high(v) > m_TSTACK_h[m_top]) {
958 m_top--;
959 }
960
961 outv--;
962
963 } else { // frond arc
964 if (m_START[e]) {
965 y = 0;
966 if (m_TSTACK_a[m_top] > wnum) {
967 do {
968 y = max(y,m_TSTACK_h[m_top]);
969 b = m_TSTACK_b[m_top--];
970 } while (m_TSTACK_a[m_top] > wnum);
971 TSTACK_push(y,wnum,b);
972 } else {
973 TSTACK_push(vnum,wnum,vnum);
974 }
975 }
976
977 m_ESTACK.push(e); // add (v,w) to ESTACK
978 }
979 }
980 }
981
982 // simplified path search for triconnectivity test
pathSearch(const Graph & G,node v,node & s1,node & s2)983 bool Triconnectivity::pathSearch (const Graph &G, node v, node &s1, node &s2)
984 {
985 edge e;
986 int y, vnum = m_NEWNUM[v];
987 int a, b;
988
989 List<edge> &Adj = m_A[v];
990 int outv = Adj.size();
991
992 ListIterator<edge> it, itNext;
993 for(it = Adj.begin(); it.valid(); it=itNext)
994 {
995 itNext = it.succ();
996 e = *it;
997 node w = e->target();
998 int wnum = m_NEWNUM[w];
999
1000 if (m_TYPE[e] == EdgeType::tree) {
1001
1002 if (m_START[e]) {
1003 y = 0;
1004 if (m_TSTACK_a[m_top] > m_LOWPT1[w]) {
1005 do {
1006 y = max(y,m_TSTACK_h[m_top]);
1007 b = m_TSTACK_b[m_top--];
1008 } while (m_TSTACK_a[m_top] > m_LOWPT1[w]);
1009 TSTACK_push(y,m_LOWPT1[w],b);
1010 } else {
1011 TSTACK_push(wnum+m_ND[w]-1,m_LOWPT1[w],vnum);
1012 }
1013 TSTACK_pushEOS();
1014 }
1015
1016 if(!pathSearch(G,w,s1,s2))
1017 return false;
1018
1019 while (vnum != 1 && ((m_TSTACK_a[m_top] == vnum) ||
1020 (m_DEGREE[w] == 2 && m_NEWNUM[m_A[w].front()->target()] > wnum)))
1021 {
1022 a = m_TSTACK_a[m_top];
1023 b = m_TSTACK_b[m_top];
1024
1025 if (a == vnum && m_FATHER[m_NODEAT[b]] == m_NODEAT[a]) {
1026 m_top--;
1027
1028 } else if (m_DEGREE[w] == 2 && m_NEWNUM[m_A[w].front()->target()] > wnum)
1029 {
1030 s1 = v;
1031 s2 = m_A[w].front()->target();
1032 return false;
1033
1034 } else {
1035 s1 = m_NODEAT[a];
1036 s2 = m_NODEAT[b];
1037 return false;
1038 }
1039 }
1040
1041 if (m_LOWPT2[w] >= vnum && m_LOWPT1[w] < vnum && (m_FATHER[v] != m_start || outv >= 2))
1042 {
1043 s1 = m_NODEAT[m_LOWPT1[w]];
1044 s2 = v;
1045 return false;
1046 }
1047
1048 if (m_START[e]) {
1049 while (TSTACK_notEOS()) {
1050 m_top--;
1051 }
1052 m_top--;
1053 }
1054
1055 while (TSTACK_notEOS() &&
1056 m_TSTACK_b[m_top] != vnum && high(v) > m_TSTACK_h[m_top]) {
1057 m_top--;
1058 }
1059
1060 outv--;
1061
1062 } else { // frond arc
1063 if (m_START[e]) {
1064 y = 0;
1065 if (m_TSTACK_a[m_top] > wnum) {
1066 do {
1067 y = max(y,m_TSTACK_h[m_top]);
1068 b = m_TSTACK_b[m_top--];
1069 } while (m_TSTACK_a[m_top] > wnum);
1070 TSTACK_push(y,wnum,b);
1071 } else {
1072 TSTACK_push(vnum,wnum,vnum);
1073 }
1074 }
1075 }
1076 }
1077
1078 return true;
1079 }
1080
1081
1082 // triconnectivity test
isTriconnected(const Graph & G,node & s1,node & s2)1083 bool isTriconnected(const Graph &G, node &s1, node &s2)
1084 {
1085 bool isTric;
1086 Triconnectivity tric2(G,isTric,s1,s2);
1087
1088 return isTric;
1089 }
1090
1091
1092 // debugging stuff
printOs(edge e)1093 void Triconnectivity::printOs(edge e)
1094 {
1095 #ifdef TRIC_COMP_OUTPUT
1096 std::cout << " (" << m_pGC->original(e->source()) << "," <<
1097 m_pGC->original(e->target()) << "," << e->index() << ")";
1098 if (m_pGC->original(e) == 0) std::cout << "v";
1099 #endif
1100 }
1101
printStacks()1102 void Triconnectivity::printStacks()
1103 {
1104 #ifdef TRIC_COMP_OUTPUT
1105 std::cout << "\n\nTSTACK:" << std::endl;
1106
1107 for (int i = m_top; i >= 0; i--)
1108 std::cout << "(" << m_TSTACK_h[i] << "," << m_TSTACK_a[i] << "," << m_TSTACK_b[i] << ")\n";
1109
1110 std::cout << "\nESTACK\n";
1111 while(!m_ESTACK.empty()) {
1112 printOs(m_ESTACK.popRet());
1113 std::cout << std::endl;
1114 }
1115 #endif
1116 }
1117
1118 }
1119