?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Don't import ogdf namespace
[TortoiseGit.git] / ext / OGDF / src / planarlayout / BiconnectedShellingOrder.cpp
blobe7eb1db0d293ef4f317ef23fff0044b3a70149ba
1 /*
2 * $Revision: 2599 $
3 *
4 * last checkin:
5 * $Author: chimani $
6 * $Date: 2012-07-15 22:39:24 +0200 (So, 15. Jul 2012) $
7 ***************************************************************/
8
9 /** \file
10 * \brief Implements class BiconnectedShellingOrder which computes
11 * a shelling order for a biconnected planar graph.
12 *
13 * \author Carsten Gutwenger
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 #include <ogdf/planarlayout/BiconnectedShellingOrder.h>
46 #include <ogdf/basic/CombinatorialEmbedding.h>
47 #include <ogdf/basic/FaceArray.h>
48 #include <ogdf/basic/SList.h>
49
50 #include <ogdf/basic/extended_graph_alg.h>
51 #include <ogdf/basic/simple_graph_alg.h>
52
53
54 //#define OUTPUT_BSO
55
56 namespace ogdf {
57
58
59 //---------------------------------------------------------
60 // pair of node v and list itrator it
61 //---------------------------------------------------------
62 struct PairFaceItem;
63
64 struct PairNodeItem
65 {
66 // constructor
67 PairNodeItem() { }
68
69 PairNodeItem(node v, ListIterator<PairFaceItem> it = ListIterator<PairFaceItem>())
70 {
71 m_v = v;
72 m_it = it;
73 }
74
75 node m_v;
76 ListIterator<PairFaceItem> m_it;
77 };
78
79
80 //---------------------------------------------------------
81 // pair of face f and list iterator it
82 //---------------------------------------------------------
83
84 struct PairFaceItem
85 {
86 // constructor
87 PairFaceItem()
88 {
89 m_f = 0;
90 m_it = 0;
91 }
92
93 PairFaceItem(face f)
94 {
95 m_f = f;
96 m_it = 0;
97 }
98
99 PairFaceItem(face f, ListIterator<PairNodeItem> it)
100 {
101 m_f = f;
102 m_it = it;
103 }
104
105 face m_f;
106 ListIterator<PairNodeItem> m_it;
107 };
108
109
110 // defines (as shortcuts)
111 // initialization of a variable
112 #define INIT_VAR(x,var,val) \
113 var[x] = (val); \
114 setUpdate(x);
115
116 // decrement of a variable
117 #define DEC_VAR(x,var) \
118 --var[x]; \
119 setUpdate(x);
120
121 // increment of a variable
122 #define INC_VAR(x,var) \
123 ++var[x]; \
124 setUpdate(x);
125
126
127 //---------------------------------------------------------
128 // class ComputeBicOrder
129 //---------------------------------------------------------
130 class ComputeBicOrder
131 {
132 public:
133 // types of structures to be removed
134 enum CandidateType { typeFace, typeNode, typeEdge };
135
136
137 // constructor
138 ComputeBicOrder (
139 const Graph &G, // biconnected planar graph
140 ConstCombinatorialEmbedding &E, // combinatorial embedding of G
141 face extFace, // external face
142 double baseRatio); // size of base (baseRatio * size(extFace)
143
144 // returns external face
145 face externalFace() { return m_extFace; }
146
147 // returns face left of adj
148 face left(adjEntry adj) { return m_pEmbedding->leftFace(adj); }
149
150 // returns face right of adj
151 face right(adjEntry adj) { return m_pEmbedding->rightFace(adj); }
152
153 // if v = c_i, returns face right of c_i -> c_i+1
154 face right(node v) { return left(m_nextSucc[v]); }
155
156 // if v = c_i, returns face left of c_i -> c_i-1
157 face left(node v) { return right(m_prevPred[v]); }
158
159 // returns number of virtual edges adjacent to v
160 int virte (node v);
161
162 // returns successor of v on contour (if v=c_i returns c_i+1)
163 node next(node v) { return m_next[v]; }
164
165 // returns predecessor of v on contour (if v=c_i returns c_ii1)
166 node prev(node v) { return m_prev[v]; }
167
168 // returns true <=> f contains a virtual edge
169 bool cutv(face f) { return (m_virtSrc[f] != 0); }
170
171 // returns true <=> f is a possible next face, i.e
172 // outv(f) >= 3 and outv(f) = oute(f)+1
173 bool isPossFace(face f) {
174 return (f != externalFace() && m_outv[f] >= 3 && m_outv[f] == m_oute[f]+1);
175 }
176
177 // returns true <=> v is a possible next node, i.e.
178 // cutf(v) <= 1, cutf(v) = virte(v), numsf(v) = 0 and deg(v) >= 3
179 bool isPossNode(node v) { // precond.: v on C_k'
180 return (m_onBase[v] == false && m_cutf[v] <= 1 &&
181 m_cutf[v] == virte(v) && m_numsf[v] == 0 && m_deg[v] >= 3);
182 }
183
184 // returns true <=> v=c_i and c_i -> c_i+1 is a possible next virtual edge, i.e.
185 // c_i -> c_i+1 is a virtual edge and (deg(c_i) = 2 and c_i != vLeft) or
186 // deg(c_i+1) = 2 and c_i+1 != vRight)
187 bool isPossVirt(node v) { // precond.: v on C_k'
188 return m_virtEdge[v] && ((m_deg[v] == 2 && v != m_vLeft) ||
189 (m_deg[next(v)] == 2 && next(v) != m_vRight));
190 }
191
192 // stores the next candidate in m_nextType and m_nextF, m_nextV or
193 // m_nextE (depending on type)
194 // returns true <=> there is a next candidate
195 bool getPossible();
196
197 // returns the type of the next candidate
198 CandidateType nextPoss() { return m_nextType; }
199
200 // puts nodes on base into shelling order set V
201 void setV1(ShellingOrderSet &V);
202
203 // initializes possible nodes and faces
204 void initPossibles();
205
206 // removes next possible face
207 void removeNextFace(ShellingOrderSet &V);
208 // removes next possible node
209 void removeNextNode(ShellingOrderSet &V);
210 // removes next possible virtual edge
211 void removeNextVirt(ShellingOrderSet &V);
212
213 // updates variables of face and nodes contained in m_updateFaces and
214 // m_updateNodes; also updates list of possible nodes, faces and virtual edges
215 void doUpdate();
216
217 // outputs contour and some node and face variables
218 // for debugging only
219 void print();
220
221 private:
222 // if adj = w->v, puts edge (v,w) onto contour
223 void edgeToContour(adjEntry adj);
224 // puts virtual edge (v,w) onto contour and sets m_nextSucc[v] and m_prevPred[w]
225 void virtToContour(node v, node w, adjEntry adjNextSucc, adjEntry adjPrevPred);
226 // puts virtual edge (v,w) onto contour
227 void virtToContour(node v, node w);
228
229 // returns vertex cl of a face to be removed
230 node getFaceCl(face f);
231
232 void setOutv(node v);
233 void setSeqp(node cl, node cr);
234 void delOuterNode(node v);
235 void decSeqp(node v);
236 void putOnOuter(node v, face f);
237 void delOuterRef(face f);
238
239 // returns faces adjacent with v in list L
240 void getAdjFaces(node v, SListPure<face> &L);
241 // returns nodes adjacent with v in list L; nodes are sorted from left
242 // to right
243 void getAdjNodes(node v, SListPure<node> &L);
244
245 // marks face f to be updated
246 void setUpdate(face f);
247 // marks node v to be updated
248 void setUpdate(node v);
249
250 void initVInFStruct(const ConstCombinatorialEmbedding &E);
251 bool vInF(node v, face f);
252 void delVInF(node v, face f);
253
254 int getBaseChain(ConstCombinatorialEmbedding &E,
255 face f,
256 double baseRatio,
257 adjEntry &adjLeft,
258 adjEntry &adjRight);
259
260 adjEntry findMaxBaseChain(ConstCombinatorialEmbedding &E,
261 face f,
262 int &length);
263
264 const Graph *m_pGraph; // the graph
265 ConstCombinatorialEmbedding *m_pEmbedding; // the embedding of the graph
266
267 face m_extFace; // the external face
268
269 adjEntry m_adjLeft; // adjacency entry z_1 -> z_2 (if z_1,...,z_p is base)
270 adjEntry m_adjRight; // adjacency entry z_p-1 -> z_p
271
272 node m_vLeft, m_vRight; // left and right node on base
273 int m_baseLength; // length of base
274
275 // next candidate to be removed
276 CandidateType m_nextType; // type of next candidate
277 face m_nextF; // next face (if m_nextType = typeFace)
278 node m_nextV; // next node (if m_nextType = typeNode)
279 node m_nextE; // next virtual edge (if m_nextType = typeEdge)
280
281 // variables of nodes
282 NodeArray<int> m_deg; // current degree
283 NodeArray<int> m_cutf; // number of adjacent faces f with cutv(f) = true
284 NodeArray<int> m_numsf; // number of adjacent faces f with outv(f) > seqp(f)+1
285 NodeArray<bool> m_onOuter; // true <=> v on contour
286 NodeArray<bool> m_onBase; // true <=> v on base
287
288 // list iterator in m_possNodes containing node (or nil if not contained)
289 NodeArray<ListIterator<node> > m_vLink;
290 // list iterator in m_possVirt containing virtual edge at node (or nil if not contained)
291 NodeArray<ListIterator<node> > m_virtLink;
292 NodeArray<bool> m_vUpdate; // true <=> node marked to be updated
293 NodeArray<ListPure<PairFaceItem> > m_inOutNodes;
294
295 // variables of faces
296 FaceArray<int> m_outv, // number of nodes contained in face on contour
297 m_oute, // number of edges contained in face on contour
298 m_seqp; // number of sequential pairs c_i,c_i+1 of face
299 FaceArray<node> m_virtSrc; // if face contains virtual edge e then source(e), otherwise nil
300 // list iterator in m_possFaces containing face (or nil if not contained)
301 FaceArray<ListIterator<face> > m_fLink;
302 FaceArray<bool> m_fUpdate; // true <=> face marked to be updated
303 FaceArray<bool> m_isSf; // true <=> outv(f) > seqp(f)+1
304 FaceArray<ListPure<PairNodeItem> > m_outerNodes; // list of all nodes of face on contour
305
306 // represantation of the contour
307 NodeArray<node> m_next, m_prev;
308 NodeArray<adjEntry> m_nextSucc, m_prevPred;
309 NodeArray<bool> m_virtEdge; // virt_edge[c_i] = true <=> (c_i,c_i+1) virtuelle Kante
310
311 // lists of possible faces, nodes and edges
312 ListPure<face> m_possFaces; // faces with outv(f) >= 3 und outv(f) = oute(f)+1
313 ListPure<node> m_possNodes; // nodes with cutf(v) <= 1, cutf(v) = virte(v), numsf(v) = 0 and deg(v) >= 3
314 ListPure<node> m_possVirt; // node v denotes virtual edge e = (v,next[v]), that satisfies
315 // (deg(v) = 2 and v != vLeft) or (deg(next(v)) = 2 and next(v) != vRight)
316
317 ListPure <node> m_updateNodes; // list of nodes to be updated
318 SListPure<face> m_updateFaces; // list of faces to be updated
319
320 // deciding "v in F ?" in constant time
321 NodeArray<List<PairFaceItem> > m_facesOf;
322 FaceArray<List<PairNodeItem> > m_nodesOf;
323 };
324
325
326 void ComputeBicOrder::print()
327 {
328 cout << "contour:\n";
329 node v;
330 for(v = m_vLeft; v != 0; v = m_next[v])
331 cout << " " << v << "[" << m_prev[v] << "," << m_prevPred[v] <<
332 " : " << m_next[v] << "," << m_nextSucc[v] <<
333 "; " << m_virtEdge[v] << "]\n";
334
335 cout << "node infos:\n";
336 forall_nodes(v,*m_pGraph)
337 cout << v << ": deg = " << m_deg[v] << ", cutf = " << m_cutf[v] <<
338 ", numsf = " << m_numsf[v] << endl;
339
340 cout << "face infos:\n";
341 face f;
342 forall_faces(f,*m_pEmbedding) {
343 cout << f->index() << ": outv = " << m_outv[f] << ", oute = " <<
344 m_oute[f] << ", seqp = " << m_seqp[f] << ", isSF = " <<
345 m_isSf[f] << ", virtSrc = " << m_virtSrc[f] << endl;
346 }
347 cout << endl;
348 }
349
350
351 ComputeBicOrder::ComputeBicOrder(const Graph &G, // the graph
352 ConstCombinatorialEmbedding &E, // embedding of the graph
353 face extFace, // the external face
354 double baseRatio) // length of the base = baseRatio*size(extface)
355 {
356 m_pGraph = &G;
357 m_pEmbedding = &E;
358
359 #ifdef OUTPUT_BSO
360 cout << "faces:" << endl;
361 face fh;
362 forall_faces(fh,E) {
363 cout << fh->index() << ":";
364 adjEntry adj;
365 forall_face_adj(adj,fh)
366 cout << " " << adj;
367 cout << endl;
368 }
369
370 cout << "adjacency lists:" << endl;
371 node vh;
372 forall_nodes(vh,G) {
373 cout << vh << ":";
374 adjEntry adj;
375 forall_adj(adj,vh)
376 cout << " " << adj;
377 cout << endl;
378 }
379 #endif
380
381 m_vLink .init(G, ListIterator<node>());
382 m_virtLink.init(G, ListIterator<node>());
383
384 m_extFace = extFace;
385
386 #ifdef OUTPUT_BSO
387 cout << "external face = " << extFace->index() << endl;
388 #endif
389
390 m_baseLength = getBaseChain(E, m_extFace, baseRatio, m_adjLeft, m_adjRight);
391 m_vLeft = m_adjLeft->theNode();
392 m_vRight = m_adjRight->twinNode();
393
394 #ifdef OUTPUT_BSO
395 cout << "vLeft = " << m_vLeft << ", " << "vRight = " << m_vRight << endl;
396 #endif
397
398 // initialization of node and face variables
399 m_deg .init (G);
400 m_cutf .init (G, 0);
401 m_numsf .init (G, 0);
402 m_onOuter .init (G, false);
403 m_next .init (G);
404 m_prev .init (G);
405 m_nextSucc .init (G);
406 m_prevPred .init (G);
407 m_virtEdge .init (G, false);
408 m_vUpdate .init (G, false);
409 m_inOutNodes .init (G);
410 m_outv .init (E, 0);
411 m_oute .init (E, 0);
412 m_seqp .init (E, 0);
413 m_virtSrc .init (E, 0);
414 m_fLink .init (E, ListIterator<face>());
415 m_fUpdate .init (E, false);
416 m_isSf .init (E, false);
417 m_outerNodes .init (E);
418 m_onBase .init (G, false);
419
420 initVInFStruct(E);
421
422 // initialization of degree
423 node v, w;
424 forall_nodes(v,G)
425 m_deg[v] = v->degree();
426
427 // initialization of m_onBase[v]
428 adjEntry adj;
429 for(adj = m_adjRight; adj != m_adjLeft; adj = adj->faceCyclePred())
430 m_onBase[adj->theNode()] = true;
431 m_onBase [m_vLeft] = m_onBase [m_vRight] = true;
432
433 adj = m_adjLeft;
434 do {
435 v = adj->theNode();
436 adjEntry adj2;
437 forall_adj(adj2,v)
438 {
439 face f = E.rightFace(adj2);
440 if (f != m_extFace) {
441 m_outv[f] ++;
442 putOnOuter(v,f);
443 }
444 }
445 adj = adj->faceCyclePred();
446 } while(adj != m_adjRight);
447
448 for(adj = m_adjRight->faceCycleSucc(); adj != m_adjLeft; adj = adj->faceCycleSucc())
449 m_oute[E.leftFace(adj)]++;
450
451 m_onOuter [m_vLeft] = true;
452 m_prevPred[m_vLeft] = m_nextSucc[m_vRight] = 0;
453 m_prev[m_vLeft] = m_next[m_vRight] = 0;
454 for (adj = m_adjLeft->faceCyclePred(); adj != m_adjRight; adj = adj->faceCyclePred())
455 {
456 v = adj->twinNode(); w = adj->theNode();
457 m_onOuter[w] = true;
458 edgeToContour(adj);
459
460 adjEntry adj2;
461 forall_adj(adj2,w)
462 {
463 face f = left(adj2);
464 if (vInF(v,f))
465 ++m_seqp[f];
466 }
467 }
468
469 for (v = m_vLeft; v != 0; v = next(v))
470 {
471 forall_adj(adj,v) {
472 face f = left(adj);
473 if ((m_isSf[f] = (m_outv[f] > m_seqp[f]+1)) == true)
474 ++m_numsf[v];
475 }
476 }
477 }
478
479
480 void ComputeBicOrder::setV1(ShellingOrderSet &V)
481 {
482 V = ShellingOrderSet(m_baseLength, 0, 0);
483
484 int i;
485 adjEntry adj;
486 for (i = 1, adj = m_adjLeft; i <= m_baseLength;
487 i++, adj = adj->faceCycleSucc())
488 {
489 V[i] = adj->theNode();
490 }
491 }
492
493
494 void ComputeBicOrder::edgeToContour(adjEntry adj)
495 {
496 node v = adj->twinNode(), w = adj->theNode();
497
498 m_next [v] = w;
499 m_prev [w] = v;
500 m_nextSucc [v] = adj->twin()->cyclicSucc();
501 m_prevPred [w] = adj->cyclicPred();
502 m_virtEdge [v] = false;
503 }
504
505
506 void ComputeBicOrder::virtToContour(
507 node v,
508 node w,
509 adjEntry adjNextSucc,
510 adjEntry adjPrevPred)
511 {
512 m_next [v] = w;
513 m_prev [w] = v;
514 m_nextSucc [v] = adjNextSucc;
515 m_prevPred [w] = adjPrevPred;
516 m_virtEdge [v] = true;
517 }
518
519
520 void ComputeBicOrder::virtToContour(node v, node w)
521 {
522 m_next [v] = w;
523 m_prev [w] = v;
524 m_virtEdge [v] = true;
525 }
526
527
528 void ComputeBicOrder::putOnOuter(node v, face f)
529 {
530 ListIterator<PairNodeItem> it;
531
532 it = m_outerNodes[f].pushBack(PairNodeItem(v));
533 (*it).m_it = m_inOutNodes[v].pushBack(PairFaceItem(f,it));
534 }
535
536
537 void ComputeBicOrder::delOuterRef(face f)
538 {
539 ListPure<PairNodeItem> &L = m_outerNodes[f];
540 PairNodeItem x;
541
542 while (!L.empty()) {
543 x = L.popFrontRet();
544 m_inOutNodes[x.m_v].del(x.m_it);
545 }
546 }
547
548
549 int ComputeBicOrder::virte(node v)
550 {
551 int num = 0;
552
553 if (m_onOuter[v] == true)
554 {
555 if (m_virtEdge[v] == true)
556 num++;
557 if (v != m_vLeft && m_virtEdge[prev(v)] == true)
558 num++;
559 }
560 return num;
561 }
562
563
564 void ComputeBicOrder::initVInFStruct(const ConstCombinatorialEmbedding &E)
565 {
566 const Graph &G = E;
567
568 m_facesOf.init(G);
569 m_nodesOf.init(E);
570
571 face f;
572 forall_faces(f,E)
573 {
574 adjEntry adj;
575 forall_face_adj(adj,f) {
576 node v = adj->theNode();
577
578 ListIterator<PairFaceItem> it = m_facesOf[v].pushBack(PairFaceItem(f));
579 (*it).m_it = m_nodesOf[f].pushBack(PairNodeItem(v,it));
580 }
581 }
582
583 SListPure<node> smallV;
584 node v;
585 forall_nodes(v,G) {
586 if (m_facesOf[v].size() <= 5)
587 smallV.pushBack(v);
588 }
589
590 SListPure<face> smallF;
591 forall_faces(f,E) {
592 if (m_nodesOf[f].size() <= 5)
593 smallF.pushBack(f);
594 }
595
596 for( ; ; )
597 {
598 if (!smallV.empty()) {
599 v = smallV.popFrontRet();
600
601 ListIterator<PairFaceItem> it;
602 for(it = m_facesOf[v].begin(); it.valid(); ++it) {
603 PairFaceItem f_it = *it;
604 m_nodesOf[f_it.m_f].del(f_it.m_it);
605 if (m_nodesOf[f_it.m_f].size() == 5)
606 smallF.pushBack(f_it.m_f);
607 }
608 } else if (!smallF.empty()) {
609 f = smallF.popFrontRet();
610 ListIterator<PairNodeItem> it;
611 for(it = m_nodesOf[f].begin(); it.valid(); ++it) {
612 PairNodeItem v_it = *it;
613 m_facesOf[v_it.m_v].del(v_it.m_it);
614 if (m_facesOf[v_it.m_v].size() == 5)
615 smallV.pushBack(v_it.m_v);
616 }
617 } else
618 break;
619 }
620 }
621
622
623 bool ComputeBicOrder::vInF(node v, face f)
624 {
625 ListIterator<PairNodeItem> itNI;
626 for(itNI = m_nodesOf[f].begin(); itNI.valid(); ++itNI)
627 if ((*itNI).m_v == v) return true;
628
629 ListIterator<PairFaceItem> itFI;
630 for(itFI = m_facesOf[v].begin(); itFI.valid(); ++itFI)
631 if ((*itFI).m_f == f) return true;
632
633 return false;
634 }
635
636
637 void ComputeBicOrder::delVInF(node v, face f)
638 {
639 List<PairNodeItem> &L_f = m_nodesOf[f];
640 List<PairFaceItem> &L_v = m_facesOf[v];
641
642 ListIterator<PairNodeItem> itNI;
643 for(itNI = L_f.begin(); itNI.valid(); ++itNI) {
644 if ((*itNI).m_v == v) {
645 L_f.del(itNI);
646 return;
647 }
648 }
649
650 ListIterator<PairFaceItem> itFI;
651 for(itFI = L_v.begin(); itFI.valid(); ++itFI) {
652 if ((*itFI).m_f == f) {
653 L_v.del(itFI);
654 return;
655 }
656 }
657 }
658
659
660 void ComputeBicOrder::initPossibles()
661 {
662 face f;
663 forall_faces (f, (*m_pEmbedding)) {
664 if (isPossFace(f))
665 m_fLink[f] = m_possFaces.pushBack(f);
666 }
667
668 node v;
669 for (v = next(m_vLeft); v != m_vRight; v = next(v))
670 if (isPossNode(v))
671 m_vLink[v] = m_possNodes.pushBack(v);
672 }
673
674
675 bool ComputeBicOrder::getPossible()
676 {
677 if (!m_possFaces.empty()) {
678 m_nextType = typeFace;
679 m_nextF = m_possFaces.popFrontRet();
680 return true;
681
682 } else if (!m_possNodes.empty()) {
683 m_nextType = typeNode;
684 m_nextV = m_possNodes.popFrontRet();
685 return true;
686
687 } else if (!m_possVirt.empty()) {
688 m_nextType = typeEdge;
689 m_nextE = m_possVirt.popFrontRet();
690 m_virtLink[m_nextE] = ListIterator<node>();
691 return true;
692
693 } else
694 return false;
695 }
696
697
698 node ComputeBicOrder::getFaceCl(face f)
699 {
700 node v;
701
702 if (cutv (f)) {
703 v = m_virtSrc [f];
704
705 } else {
706 adjEntry adj;
707 forall_face_adj(adj, f) {
708 if (m_onOuter[v = adj->theNode()] == true && m_deg[v] == 2)
709 break;
710 }
711 }
712
713 while (v != m_vLeft && m_deg[v] == 2)
714 v = prev(v);
715
716 return v;
717 }
718
719
720 void ComputeBicOrder::getAdjFaces(node v, SListPure<face> &L)
721 {
722 L.clear();
723 if (m_deg[v] <= 1) return;
724
725 adjEntry adjEnd = (v != m_vLeft) ? m_prevPred[v] : m_adjLeft->cyclicPred();
726 adjEntry adjStart = (v != m_vRight) ? m_nextSucc[v] : m_adjRight->twin()->cyclicSucc();
727
728 if (left(adjStart) != m_extFace)
729 L.pushBack(left(adjStart));
730
731 if (m_deg[v] >= 3) {
732 adjEntry adj;
733 for (adj = adjStart; adj != adjEnd; adj = adj->cyclicSucc())
734 L.pushBack(right(adj));
735
736 L.pushBack(right(adjEnd));
737 }
738 }
739
740
741 void ComputeBicOrder::getAdjNodes(node v, SListPure<node> &L)
742 {
743 adjEntry adjEnd = (v != m_vLeft) ? m_prevPred[v] : m_adjLeft->cyclicPred();
744 adjEntry adjStart = (v != m_vRight) ? m_nextSucc[v] : m_adjRight->twin()->cyclicSucc();
745
746 L.clear();
747 L.pushBack((v != m_vLeft) ? prev(v) : m_adjLeft->twinNode());
748
749 if (m_deg[v] >= 3) {
750 adjEntry adj;
751 for (adj = adjEnd; adj != adjStart; adj = adj->cyclicPred())
752 L.pushBack(adj->twinNode());
753 L.pushBack(adjStart->twinNode());
754 }
755 L.pushBack((v != m_vRight) ? next(v) : m_adjRight->theNode());
756 }
757
758
759 void ComputeBicOrder::decSeqp(node v)
760 {
761 node vNext = next(v);
762 node vPrev = prev(v);
763
764 SListPure<face> L;
765 getAdjFaces(v,L);
766
767 SListConstIterator<face> it;
768 for(it = L.begin(); it.valid(); ++it) {
769 face f = *it;
770 if (vInF(vNext,f))
771 m_seqp[f]--;
772 if (vInF(vPrev,f))
773 m_seqp[f]--;
774 }
775 }
776
777
778 void ComputeBicOrder::delOuterNode(node v)
779 {
780 ListIterator<PairFaceItem> it;
781 for(it = m_inOutNodes[v].begin(); it.valid(); ++it)
782 m_outerNodes[(*it).m_f].del((*it).m_it);
783 }
784
785
786 void ComputeBicOrder::setOutv(node v)
787 {
788 SListPure<face> L;
789 getAdjFaces(v,L);
790
791 SListConstIterator<face> it;
792 for(it = L.begin(); it.valid(); ++it) {
793 face f = *it;
794
795 INC_VAR(f,m_outv)
796 putOnOuter(v,f);
797 if (cutv(f) == true) {
798 INC_VAR(v, m_cutf)
799 }
800 if (m_isSf [f]) {
801 INC_VAR(v, m_numsf)
802 }
803 }
804 }
805
806
807 void ComputeBicOrder::setSeqp(node cl, node cr)
808 {
809 SListPure<face> L;
810
811 node v, w;
812 for (v = cl; v != cr; v = w)
813 {
814 w = next(v);
815
816 node wSmall, wBig;
817 if (m_deg[v] < m_deg[w]) {
818 wSmall = v;
819 wBig = w;
820 } else {
821 wSmall = w;
822 wBig = v;
823 }
824
825 getAdjFaces(wSmall, L);
826
827 SListConstIterator<face> it;
828 for(it = L.begin(); it.valid(); ++it) {
829 if (vInF(wBig,*it)) {
830 INC_VAR (*it,m_seqp)
831 }
832 }
833 }
834 }
835
836
837 void ComputeBicOrder::removeNextFace(ShellingOrderSet &V)
838 {
839 #ifdef OUTPUT_BSO
840 cout << "remove next face: " << m_nextF->index() << endl;
841 #endif
842
843 node cl = getFaceCl(m_nextF), cr, v;
844
845 V = ShellingOrderSet(m_outv[m_nextF]-2);
846 V.left(cl);
847
848 int i;
849 for (i = 1, cr = next(cl); cr != m_vRight && m_deg[cr] == 2; i++, cr = next(cr))
850 V [i] = cr ;
851 V.right (cr);
852 V.leftAdj (m_virtEdge[cl] ? 0 : m_nextSucc[cl]->cyclicSucc()->twin());
853 V.rightAdj(m_virtEdge[prev(cr)] ? 0 : m_prevPred[cr]->cyclicPred()->twin());
854
855 if (cutv(m_nextF) && next(m_virtSrc[m_nextF]) == cr)
856 setUpdate(cr);
857
858 if (cutv(m_nextF)) {
859 DEC_VAR(cl,m_cutf)
860 DEC_VAR(cr,m_cutf)
861 v = m_virtSrc[m_nextF];
862 if (v != cr) {
863 m_possVirt.del(m_virtLink[v]);
864 m_virtLink[v] = ListIterator<node>();
865 }
866 }
867
868 adjEntry adj = m_nextSucc[cl]->twin();
869 for( ; ; ) {
870 edgeToContour(adj);
871
872 if (adj->theNode() == cr)
873 break;
874 else {
875 INIT_VAR(adj->theNode(),m_onOuter,true)
876 }
877
878 adj = adj->faceCyclePred();
879 }
880 DEC_VAR (cl,m_deg)
881 DEC_VAR (cr,m_deg)
882
883 for (v = cl; v != cr; v = next(v)) {
884 INC_VAR(right(v),m_oute)
885 if (v != cl)
886 setOutv(v);
887 }
888
889 setSeqp(cl, cr);
890
891 // possibly remove virtual edge
892 if (cutv(m_nextF)) {
893 if (m_virtSrc[m_nextF] == cl) {
894 setUpdate(cl);
895 m_virtEdge[cl] = false;
896 }
897 m_virtSrc[m_nextF] = 0;
898 }
899 delOuterRef(m_nextF);
900 }
901
902
903 void ComputeBicOrder::removeNextNode(ShellingOrderSet &V)
904 {
905 #ifdef OUTPUT_BSO
906 cout << "remove next node: " << m_nextV << endl;
907 #endif
908
909 node cl = prev(m_nextV);
910 node cr = next(m_nextV);
911
912 V = ShellingOrderSet(1);
913 V[1] = m_nextV;
914
915 if (m_virtEdge[prev(m_nextV)] == true) {
916 V.left(m_prevPred[m_nextV]->twinNode());
917 V.leftAdj(m_prevPred[m_nextV]);
918 } else {
919 V.left(prev(m_nextV));
920 V.leftAdj(m_prevPred[m_nextV]->cyclicPred());
921 }
922
923 if (m_virtEdge[m_nextV] == true) {
924 V.right(m_nextSucc[m_nextV]->twinNode());
925 V.rightAdj(m_nextSucc[m_nextV]);
926 } else {
927 V.right(next(m_nextV));
928 V.rightAdj(m_nextSucc[m_nextV]->cyclicSucc());
929 }
930
931 node vVirt = 0;
932 face fVirt = 0;
933 if (m_virtEdge[prev(m_nextV)]) {
934 INIT_VAR(prev(m_nextV), m_virtEdge, false)
935 vVirt = cl;
936 fVirt = left(m_nextV);
937 m_virtSrc [fVirt] = 0;
938 }
939
940 if (m_virtEdge[m_nextV]) {
941 if (m_virtLink[m_nextV].valid()) {
942 m_possVirt.del(m_virtLink[m_nextV]);
943 m_virtLink[m_nextV] = ListIterator<node>();
944 }
945 vVirt = cr;
946 fVirt = right(m_nextV);
947 m_virtSrc[fVirt] = 0;
948 }
949
950 SListPure<face> L;
951 getAdjFaces(m_nextV, L);
952 SListConstIterator<face> itF;
953 for(itF = L.begin(); itF.valid(); ++itF)
954 --m_outv[*itF];
955
956 SListPure<node> L_v;
957 getAdjNodes(m_nextV, L_v);
958
959 delOuterNode(m_nextV);
960 --m_oute[left (m_nextV)];
961 --m_oute[right(m_nextV)];
962 decSeqp(m_nextV);
963
964 SListIterator<node> itV;
965 for(itV = L_v.begin(); itV.valid(); ++itV) {
966 m_onOuter[*itV] = true;
967 DEC_VAR (*itV, m_deg)
968 }
969
970 face potF = 0;
971 node w1 = L_v.popFrontRet();
972 bool firstTime = true;
973 adjEntry adj,adj2;
974 for(itV = L_v.begin(); itV.valid(); ++itV)
975 {
976 node w = *itV;
977
978 if (firstTime == true) {
979 adj2 = m_nextSucc[prev(m_nextV)];
980 adj = m_prevPred[m_nextV];
981 firstTime = false;
982
983 if (prev(m_nextV) != m_vLeft) {
984 face f = left(adj2);
985 if (vInF(prev(prev(m_nextV)),f))
986 potF = f;
987 }
988
989 } else {
990 adj2 = adj->twin()->faceCyclePred()->twin();
991 adj = adj->cyclicPred();
992 }
993
994 for( ; ; )
995 {
996 node v = adj2->twinNode();
997
998 if (v != w && m_onOuter[v] == true)
999 {
1000 face f = left(adj2);
1001
1002 // possibly remove "v in F" relation
1003 if (adj2->theNode() != w1)
1004 {
1005 adjEntry adj1 = adj2->twin()->faceCycleSucc();
1006 do {
1007 delVInF(adj1->twinNode(),f);
1008 adj1 = adj1->faceCycleSucc();
1009 } while (adj1->theNode() != w1);
1010 }
1011 if (f == potF && adj2->theNode() != prev(m_nextV)) {
1012 DEC_VAR(f,m_seqp)
1013 }
1014
1015 // insert new virtual edge
1016 virtToContour(adj2->theNode(), w, adj2, (w == next(m_nextV)) ?
1017 m_prevPred[w] : adj->twin()->cyclicPred());
1018
1019 setUpdate(f);
1020
1021 INC_VAR(adj2->theNode(),m_deg)
1022 INC_VAR(w,m_deg)
1023
1024 if (f != fVirt) {
1025 ListIterator<PairNodeItem> itU;
1026 for(itU = m_outerNodes[f].begin(); itU.valid(); ++itU) {
1027 INC_VAR((*itU).m_v, m_cutf);
1028 }
1029 }
1030 m_virtSrc[f] = adj2->theNode();
1031
1032 break;
1033 }
1034
1035 edgeToContour(adj2->twin());
1036
1037 if (v == w) {
1038 delOuterRef(left(adj2));
1039 break;
1040 }
1041 INIT_VAR(v,m_onOuter,true)
1042 if (adj2->theNode() == cl)
1043 {
1044 ListIterator<PairNodeItem> it, itSucc;
1045 ListPure<PairNodeItem> &L = m_outerNodes[left(adj2)];
1046 for(it = L.begin(); it.valid(); it = itSucc) {
1047 itSucc = it.succ();
1048 if ((*it).m_v == cl) {
1049 m_inOutNodes[cl].del((*it).m_it);
1050 L.del(it);
1051 break;
1052 }
1053 }
1054 m_outv[left(adj2)]--;
1055 }
1056 adj2 = adj2->twin()->faceCyclePred()->twin();
1057 }
1058 w1 = w;
1059 }
1060
1061 for (node v = cl; v != cr; v = next(v)) {
1062 INC_VAR(right(v),m_oute)
1063 if (v != cl)
1064 setOutv(v);
1065 }
1066
1067 setSeqp(cl,cr);
1068
1069 if ((vVirt != 0 && m_virtSrc[fVirt] == 0) ||
1070 (vVirt == cl && m_virtSrc[fVirt] != cl)) {
1071 DEC_VAR(vVirt,m_cutf)
1072 }
1073 }
1074
1075
1076 void ComputeBicOrder::removeNextVirt(ShellingOrderSet &V)
1077 {
1078 #ifdef OUTPUT_BSO
1079 cout << "remove next virt: " << m_nextE << endl;
1080 #endif
1081
1082 node v, cl = m_nextE, cr = next(m_nextE);
1083 int i = 0;
1084
1085 while (m_deg[cl] == 2 && cl != m_vLeft)
1086 { cl = prev(cl); i++; }
1087 while (m_deg[cr] == 2 && cr != m_vRight)
1088 { cr = next(cr); i++; }
1089
1090 V = ShellingOrderSet(i,m_virtEdge[cl] ? 0 : m_prevPred[next(cl)],
1091 m_virtEdge[prev(cr)] ? 0 : m_nextSucc[prev(cr)]);
1092 for (i = 1, v = next(cl); v != cr; v = next(v)) {
1093 V[i++] = v;
1094 delOuterNode(v);
1095 }
1096 V.left (cl);
1097 V.right(cr);
1098
1099 face f = right(cl);
1100 m_virtSrc[f] = cl;
1101
1102 virtToContour(cl, cr);
1103
1104 INIT_VAR(f,m_outv,(m_outv[f] - V.len()))
1105 INIT_VAR(f,m_oute,(m_oute[f] - V.len()))
1106 INIT_VAR(f,m_seqp,(m_seqp[f] - V.len()-1))
1107 setSeqp(cl,cr);
1108 setUpdate(cl);
1109 setUpdate(cr);
1110 }
1111
1112
1113 void ComputeBicOrder::setUpdate(node v)
1114 {
1115 if (m_vUpdate[v] == false) {
1116 m_updateNodes.pushBack(v);
1117 m_vUpdate[v] = true;
1118 }
1119 }
1120
1121
1122 void ComputeBicOrder::setUpdate(face f)
1123 {
1124 if (m_fUpdate[f] == false) {
1125 m_updateFaces.pushBack(f);
1126 m_fUpdate[f] = true;
1127 }
1128 }
1129
1130
1131 void ComputeBicOrder::doUpdate()
1132 {
1133 while (!m_updateFaces.empty())
1134 {
1135 face f = m_updateFaces.popFrontRet();
1136 m_fUpdate[f] = false;
1137 bool isSeperatingFace = (m_outv[f] > m_seqp[f]+1);
1138 if (isSeperatingFace != m_isSf[f])
1139 {
1140 ListIterator<PairNodeItem> it;
1141 for(it = m_outerNodes[f].begin(); it.valid(); ++it)
1142 {
1143 if (isSeperatingFace) {
1144 INC_VAR((*it).m_v,m_numsf)
1145 } else {
1146 DEC_VAR((*it).m_v,m_numsf)
1147 }
1148 }
1149 m_isSf[f] = isSeperatingFace;
1150 }
1151 bool possible = isPossFace(f);
1152 if (possible && !m_fLink[f].valid())
1153 m_fLink[f] = m_possFaces.pushBack(f);
1154 else if (!possible && m_fLink[f].valid()) {
1155 m_possFaces.del(m_fLink[f]);
1156 m_fLink[f] = ListIterator<face>();
1157 }
1158 }
1159
1160 ListIterator<node> it, itPrev;
1161 for (it = m_updateNodes.rbegin(); it.valid(); it = itPrev)
1162 {
1163 itPrev = it.pred();
1164 node v = *it;
1165 if (v != m_vLeft && m_virtEdge[prev(v)] == true)
1166 setUpdate(prev(v));
1167 }
1168
1169 while (!m_updateNodes.empty())
1170 {
1171 node v = m_updateNodes.popFrontRet();
1172 m_vUpdate[v] = false;
1173
1174 bool possible = isPossNode(v);
1175 if (possible && !m_vLink[v].valid())
1176 m_vLink[v] = m_possNodes.pushBack(v);
1177 else if (!possible && m_vLink[v].valid()) {
1178 m_possNodes.del(m_vLink[v]);
1179 m_vLink[v] = ListIterator<node>();
1180 }
1181 possible = isPossVirt(v);
1182 if (possible && !m_virtLink[v].valid())
1183 m_virtLink[v] = m_possVirt.pushBack(v);
1184 else if (!possible && m_virtLink[v].valid()) {
1185 m_possVirt.del(m_virtLink[v]);
1186 m_virtLink[v] = ListIterator<node>();
1187 }
1188 }
1189 }
1190
1191
1192 int ComputeBicOrder::getBaseChain(ConstCombinatorialEmbedding &E,
1193 face f,
1194 double baseRatio,
1195 adjEntry &adjLeft,
1196 adjEntry &adjRight)
1197 {
1198 int len;
1199 adjLeft = findMaxBaseChain(E, f, len);
1200 len = max(2, min(len, (int)(baseRatio*f->size()+0.5)));
1201
1202 adjRight = adjLeft;
1203 for (int i = 2; i < len; i++)
1204 adjRight = adjRight->faceCycleSucc();
1205
1206 return len;
1207 }
1208
1209
1210 struct QType
1211 {
1212 QType (adjEntry adj, int i) {
1213 m_start = adj;
1214 m_limit = i;
1215 }
1216 QType () {
1217 m_start = 0;
1218 m_limit = 0;
1219 }
1220
1221 adjEntry m_start;
1222 int m_limit;
1223 };
1224
1225
1226 adjEntry ComputeBicOrder::findMaxBaseChain(ConstCombinatorialEmbedding &E,
1227 face f,
1228 int &length)
1229 {
1230 const Graph &G = (const Graph &) E;
1231 int p = f->size();
1232
1233 NodeArray<int> num(G,-1);
1234
1235 int i = 0, j, d;
1236
1237 adjEntry adj;
1238 forall_face_adj(adj,f)
1239 num[adj->theNode()] = i++;
1240
1241 Array<SListPure<int> > diag(0,p-1);
1242 forall_face_adj(adj,f)
1243 {
1244 i = num[adj->theNode()];
1245 adjEntry adj2;
1246 for (adj2 = adj->cyclicPred(); adj2 != adj->cyclicSucc();
1247 adj2 = adj2->cyclicPred())
1248 {
1249 j = num[adj2->twinNode()];
1250 if (j != -1)
1251 diag[i].pushBack(j);
1252 }
1253 }
1254
1255 SListPure<QType> Q;
1256 Array<SListIterator<QType> > posInQ (0,p-1,SListIterator<QType>());
1257
1258 length = 0;
1259 bool firstRun = true;
1260 adj = f->firstAdj();
1261 i = num[adj->theNode()];
1262
1263 adjEntry adjStart = 0;
1264 do {
1265 if (posInQ[i].valid()) {
1266 adjEntry adj2 = Q.front().m_start;
1267 d = (i-num[adj2->theNode()]+p) % p +1;
1268 if (d > length || (d == length && adj2->theNode()->index() < adjStart->theNode()->index())) {
1269 length = d;
1270 adjStart = adj2;
1271 }
1272 SListIterator<QType> it, itLimit = posInQ[i];
1273 do {
1274 it = Q.begin();
1275 posInQ[(*it).m_limit] = SListIterator<QType>();
1276 Q.popFront();
1277 } while (it != itLimit);
1278 }
1279
1280 if (diag[i].empty())
1281 j = (i-2+p) % p;
1282 else {
1283 int m = p;
1284 SListConstIterator<int> it;
1285 for(it = diag[i].begin(); it.valid(); ++it) {
1286 int k = *it;
1287 d = (k-i+p)%p;
1288 if (d < m) {
1289 m = d;
1290 j = k;
1291 }
1292 }
1293 j = (j-1+p) % p;
1294 if (!firstRun) {
1295 posInQ[Q.back().m_limit] = 0;
1296 Q.back().m_limit = j;
1297 posInQ[j] = Q.rbegin();
1298 }
1299 }
1300
1301 if (firstRun)
1302 posInQ[j] = Q.pushBack(QType(adj,j));
1303
1304 adj = adj->faceCycleSucc();
1305 i = num[adj->theNode()];
1306 if (i == 0) firstRun = false;
1307 } while (!Q.empty());
1308
1309 return adjStart;
1310 }
1311
1312
1313 //---------------------------------------------------------
1314 // BiconnectedShellingOrder
1315 //---------------------------------------------------------
1316
1317 void BiconnectedShellingOrder::doCall(const Graph &G,
1318 adjEntry adj,
1319 List<ShellingOrderSet> &partition)
1320 {
1321 OGDF_ASSERT(isBiconnected(G) == true);
1322 OGDF_ASSERT(G.representsCombEmbedding() == true);
1323
1324 ConstCombinatorialEmbedding E(G);
1325
1326 face extFace = (adj != 0) ? E.rightFace(adj) : E.maximalFace();
1327 ComputeBicOrder cpo(G,E,extFace,m_baseRatio);
1328
1329 cpo.initPossibles();
1330
1331 #ifdef OUTPUT_BSO
1332 cout << "after initialization:\n";
1333 cpo.print();
1334 #endif
1335
1336 while(cpo.getPossible())
1337 {
1338 switch(cpo.nextPoss())
1339 {
1340 case ComputeBicOrder::typeFace:
1341 partition.pushFront(ShellingOrderSet());
1342 cpo.removeNextFace(partition.front());
1343 break;
1344
1345 case ComputeBicOrder::typeNode:
1346 partition.pushFront(ShellingOrderSet());
1347 cpo.removeNextNode(partition.front());
1348 break;
1349
1350 case ComputeBicOrder::typeEdge:
1351 partition.pushFront(ShellingOrderSet());
1352 cpo.removeNextVirt(partition.front());
1353 break;
1354 }
1355
1356 cpo.doUpdate();
1357
1358 #ifdef OUTPUT_BSO
1359 cout << "after update:\n";
1360 cpo.print();
1361 #endif
1362 }
1363
1364 partition.pushFront(ShellingOrderSet(2));
1365 cpo.setV1(partition.front());
1366 }
1367
1368
1369 } // end namespace ogdf
1370
Windows Explorer Extension to Operate Git