?  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 / decomposition / DynamicSPQRForest.cpp
blobdcfb54edf698d39edf4a026edade2a19ba042f35
1 /*
2 * $Revision: 2552 $
3 *
4 * last checkin:
5 * $Author: gutwenger $
6 * $Date: 2012-07-05 16:45:20 +0200 (Do, 05. Jul 2012) $
7 ***************************************************************/
8
9 /** \file
10 * \brief Implementation of class DynamicSPQRForest
11 *
12 * \author Jan Papenfuß
13 *
14 * \par License:
15 * This file is part of the Open Graph Drawing Framework (OGDF).
16 *
17 * \par
18 * Copyright (C)<br>
19 * See README.txt in the root directory of the OGDF installation for details.
20 *
21 * \par
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
26 * for details.
27 *
28 * \par
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
33 *
34 * \par
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
39 *
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
42
43
44 #include <ogdf/decomposition/DynamicSPQRForest.h>
45 #include <ogdf/basic/GraphCopy.h>
46 #include "../decomposition/TricComp.h"
47
48
49 namespace ogdf {
50
51
52 void DynamicSPQRForest::init ()
53 {
54 m_bNode_SPQR.init(m_B,0);
55 m_bNode_numS.init(m_B,0);
56 m_bNode_numP.init(m_B,0);
57 m_bNode_numR.init(m_B,0);
58 m_tNode_type.init(m_T,SComp);
59 m_tNode_owner.init(m_T);
60 m_tNode_hRefEdge.init(m_T);
61 m_tNode_hEdges.init(m_T);
62 m_tNode_isMarked.init(m_T,false);
63 m_hEdge_position.init(m_H);
64 m_hEdge_tNode.init(m_H);
65 m_hEdge_twinEdge.init(m_H,0);
66 m_htogc.init(m_H);
67 }
68
69
70 void DynamicSPQRForest::createSPQR (node vB) const
71 {
72 Graph GC;
73 NodeArray<node> origNode(GC,0);
74 EdgeArray<edge> origEdge(GC,0);
75 SListConstIterator<edge> iH;
76
77 for (iH=m_bNode_hEdges[vB].begin(); iH.valid(); ++iH)
78 m_htogc[(*iH)->source()] = m_htogc[(*iH)->target()] = 0;
79
80 for (iH=m_bNode_hEdges[vB].begin(); iH.valid(); ++iH) {
81 edge eH = *iH;
82 node sH = eH->source();
83 node tH = eH->target();
84 node& sGC = m_htogc[sH];
85 node& tGC = m_htogc[tH];
86 if (!sGC) { sGC = GC.newNode(); origNode[sGC] = sH; }
87 if (!tGC) { tGC = GC.newNode(); origNode[tGC] = tH; }
88 origEdge[GC.newEdge(sGC,tGC)] = eH;
89 }
90
91 TricComp tricComp(GC);
92
93 const GraphCopySimple& GCC = *tricComp.m_pGC;
94
95 EdgeArray<node> partnerNode(GCC,0);
96 EdgeArray<edge> partnerEdge(GCC,0);
97
98 for (int i=0; i<tricComp.m_numComp; ++i) {
99 const TricComp::CompStruct &C = tricComp.m_component[i];
100
101 if (C.m_edges.empty()) continue;
102
103 node vT = m_T.newNode();
104 m_tNode_owner[vT] = vT;
105
106 switch(C.m_type) {
107 case TricComp::bond:
108 m_tNode_type[vT] = PComp;
109 m_bNode_numP[vB]++;
110 break;
111 case TricComp::polygon:
112 m_tNode_type[vT] = SComp;
113 m_bNode_numS[vB]++;
114 break;
115 case TricComp::triconnected:
116 m_tNode_type[vT] = RComp;
117 m_bNode_numR[vB]++;
118 break;
119 }
120
121 for (ListConstIterator<edge> iGCC=C.m_edges.begin(); iGCC.valid(); ++iGCC) {
122 edge eGCC = *iGCC;
123 edge eH = GCC.original(eGCC);
124 if (eH) eH = origEdge[eH];
125 else {
126 node uH = origNode[GCC.original(eGCC->source())];
127 node vH = origNode[GCC.original(eGCC->target())];
128 eH = m_H.newEdge(uH,vH);
129
130 if (!partnerNode[eGCC]) {
131 partnerNode[eGCC] = vT;
132 partnerEdge[eGCC] = eH;
133 }
134 else {
135 m_T.newEdge(partnerNode[eGCC],vT);
136 m_hEdge_twinEdge[eH] = partnerEdge[eGCC];
137 m_hEdge_twinEdge[partnerEdge[eGCC]] = eH;
138 }
139 }
140 m_hEdge_position[eH] = m_tNode_hEdges[vT].pushBack(eH);
141 m_hEdge_tNode[eH] = vT;
142 }
143 }
144
145 m_bNode_SPQR[vB] = m_hEdge_tNode[origEdge[GC.firstEdge()]];
146 m_tNode_hRefEdge[m_bNode_SPQR[vB]] = 0;
147
148 SList<node> lT;
149 lT.pushBack(m_bNode_SPQR[vB]);
150 lT.pushBack(0);
151 while (!lT.empty()) {
152 node vT = lT.popFrontRet();
153 node wT = lT.popFrontRet();
154 for (ListConstIterator<edge> iH=m_tNode_hEdges[vT].begin(); iH.valid(); ++iH) {
155 edge eH = *iH;
156 edge fH = m_hEdge_twinEdge[eH];
157 if (!fH) continue;
158 node uT = m_hEdge_tNode[fH];
159 if (uT==wT) m_tNode_hRefEdge[vT] = eH;
160 else {
161 lT.pushBack(uT);
162 lT.pushBack(vT);
163 }
164 }
165 }
166 }
167
168
169 node DynamicSPQRForest::uniteSPQR (node vB, node sT, node tT)
170 {
171 if (m_tNode_type[tT]==SComp) m_bNode_numS[vB]--;
172 else if (m_tNode_type[tT]==PComp) m_bNode_numP[vB]--;
173 else if (m_tNode_type[tT]==RComp) m_bNode_numR[vB]--;
174 if (!sT) {
175 m_bNode_numR[vB]++;
176 sT = tT;
177 }
178 else {
179 if (m_tNode_hEdges[sT].size()<m_tNode_hEdges[tT].size()) { node uT = sT; sT = tT; tT = uT; }
180 m_tNode_owner[tT] = sT;
181 m_tNode_hEdges[sT].conc(m_tNode_hEdges[tT]);
182 }
183 m_tNode_type[sT] = RComp;
184 return sT;
185 }
186
187
188 node DynamicSPQRForest::findSPQR (node vT) const
189 {
190 if (!vT) return vT;
191 if (m_tNode_owner[vT]==vT) return vT;
192 return m_tNode_owner[vT] = findSPQR(m_tNode_owner[vT]);
193 }
194
195
196 node DynamicSPQRForest::findNCASPQR (node sT, node tT) const
197 {
198 if (m_tNode_isMarked[sT]) return sT;
199 m_tNode_isMarked[sT] = true;
200 node uT = m_tNode_hRefEdge[sT] ? spqrproper(m_hEdge_twinEdge[m_tNode_hRefEdge[sT]]) : 0;
201 if (uT) uT = findNCASPQR(tT,uT);
202 else for (uT=tT; !m_tNode_isMarked[uT]; uT=spqrproper(m_hEdge_twinEdge[m_tNode_hRefEdge[uT]]));
203 m_tNode_isMarked[sT] = false;
204 return uT;
205 }
206
207
208 SList<node>& DynamicSPQRForest::findPathSPQR (node sH, node tH, node& rT) const
209 {
210 SList<node>& pT = *OGDF_NEW SList<node>;
211 node sT = spqrproper(sH->firstAdj()->theEdge());
212 node tT = spqrproper(tH->firstAdj()->theEdge());
213 node nT = findNCASPQR(sT,tT);
214 while (sT!=nT) {
215 edge eH = m_tNode_hRefEdge[sT];
216 node uH = eH->source();
217 node vH = eH->target();
218 if (uH!=sH && vH!=sH) pT.pushBack(sT);
219 if (uH==tH || vH==tH) { rT = sT; return pT; }
220 sT = spqrproper(m_hEdge_twinEdge[eH]);
221 }
222 SListIterator<node> iT = pT.rbegin();
223 while (tT!=nT) {
224 edge eH = m_tNode_hRefEdge[tT];
225 node uH = eH->source();
226 node vH = eH->target();
227 if (uH!=tH && vH!=tH) {
228 if (iT.valid()) pT.insertAfter(tT,iT);
229 else pT.pushFront(tT);
230 }
231 if (uH==sH || vH==sH) { rT = tT; return pT; }
232 tT = spqrproper(m_hEdge_twinEdge[eH]);
233 }
234 if (iT.valid()) pT.insertAfter(nT,iT);
235 else pT.pushFront(nT);
236 rT = nT; return pT;
237 }
238
239
240 SList<node>& DynamicSPQRForest::findPathSPQR (node sH, node tH) const
241 {
242 node vB = bComponent(m_hNode_gNode[sH],m_hNode_gNode[tH]);
243 if (!vB) return *OGDF_NEW SList<node>;
244 if (!m_bNode_SPQR[vB]) {
245 if (m_bNode_hEdges[vB].size()<3) return *OGDF_NEW SList<node>;
246 createSPQR(vB);
247 }
248 node rT;
249 SList<node>& pT = findPathSPQR(sH,tH,rT);
250 if (pT.empty()) if (rT) pT.pushBack(rT);
251 return pT;
252 }
253
254
255 edge DynamicSPQRForest::virtualEdge (node vT, node wT) const
256 {
257 edge eH = m_tNode_hRefEdge[vT];
258 if (eH) {
259 eH = m_hEdge_twinEdge[eH];
260 if (spqrproper(eH)==wT) return eH;
261 }
262 eH = m_tNode_hRefEdge[wT];
263 if (eH) {
264 if (spqrproper(m_hEdge_twinEdge[eH])==vT) return eH;
265 }
266 return 0;
267 }
268
269
270 edge DynamicSPQRForest::updateInsertedEdgeSPQR (node vB, edge eG)
271 {
272 node sG = eG->source();
273 node tG = eG->target();
274 node sH = repVertex(sG,vB);
275 node tH = repVertex(tG,vB);
276 edge eH = m_H.newEdge(sH,tH);
277 m_gEdge_hEdge[eG] = eH;
278 m_hEdge_gEdge[eH] = eG;
279
280 adjEntry aH;
281 forall_adj (aH,sH) {
282 edge fH = aH->theEdge();
283 if (fH==eH) continue;
284 if (fH->opposite(sH)!=tH) continue;
285 node vT = spqrproper(fH);
286 if (m_tNode_type[vT]==PComp) {
287 m_hEdge_position[eH] = m_tNode_hEdges[vT].pushBack(eH);
288 m_hEdge_tNode[eH] = vT;
289 return eG;
290 }
291 edge gH = m_hEdge_twinEdge[fH];
292 if (!gH) {
293 m_bNode_numP[vB]++;
294 node nT = m_T.newNode();
295 m_tNode_type[nT] = PComp;
296 m_tNode_owner[nT] = nT;
297 edge v1 = m_H.newEdge(sH,tH);
298 edge v2 = m_H.newEdge(sH,tH);
299 m_hEdge_position[v1] = m_tNode_hEdges[vT].insertAfter(v1,m_hEdge_position[fH]);
300 m_tNode_hEdges[vT].del(m_hEdge_position[fH]);
301 m_hEdge_position[v2] = m_tNode_hEdges[nT].pushBack(v2);
302 m_hEdge_position[fH] = m_tNode_hEdges[nT].pushBack(fH);
303 m_hEdge_position[eH] = m_tNode_hEdges[nT].pushBack(eH);
304 m_hEdge_tNode[v1] = vT;
305 m_hEdge_twinEdge[v1] = m_tNode_hRefEdge[nT] = v2;
306 m_hEdge_tNode[v2] = m_hEdge_tNode[eH] = m_hEdge_tNode[fH] = nT;
307 m_hEdge_twinEdge[v2] = v1;
308 return eG;
309 }
310 node wT = spqrproper(gH);
311 if (m_tNode_type[wT]==PComp) {
312 m_hEdge_position[eH] = m_tNode_hEdges[vT].pushBack(eH);
313 m_hEdge_tNode[eH] = vT;
314 }
315 else {
316 m_bNode_numP[vB]++;
317 node nT = m_T.newNode();
318 m_tNode_type[nT] = PComp;
319 m_tNode_owner[nT] = nT;
320 edge v1 = m_tNode_hRefEdge[vT];
321 if (!v1) v1 = m_tNode_hRefEdge[wT];
322 else if (spqrproper(m_hEdge_twinEdge[v1])!=wT) v1 = m_tNode_hRefEdge[wT];
323 edge v4 = m_hEdge_twinEdge[v1];
324 edge v2 = m_H.newEdge(v1->source(),v1->target());
325 edge v3 = m_H.newEdge(v4->source(),v4->target());
326 m_hEdge_twinEdge[v1] = v2;
327 m_hEdge_twinEdge[v2] = v1;
328 m_hEdge_twinEdge[v3] = v4;
329 m_hEdge_twinEdge[v4] = v3;
330 m_hEdge_position[v2] = m_tNode_hEdges[nT].pushBack(v2);
331 m_hEdge_position[eH] = m_tNode_hEdges[nT].pushBack(eH);
332 m_hEdge_position[v3] = m_tNode_hEdges[nT].pushBack(v3);
333 m_hEdge_tNode[v2] = m_hEdge_tNode[eH] = m_hEdge_tNode[v3] = nT;
334 m_tNode_hRefEdge[nT] = v3;
335 }
336 return eG;
337 }
338
339 node rT;
340 SList<node>& pT = findPathSPQR(sH,tH,rT);
341 if (pT.size()<2) {
342 if (m_tNode_type[rT]==RComp) {
343 m_hEdge_position[eH] = m_tNode_hEdges[rT].pushBack(eH);
344 m_hEdge_tNode[eH] = rT;
345 }
346 else {
347 List<edge>& aH = m_tNode_hEdges[rT];
348 SList<edge> bH;
349 bool a_is_parent = true;
350 ListIterator<edge> iH = aH.begin();
351 node uH = sH;
352 while (uH!=tH) {
353 node xH = (*iH)->source();
354 node yH = (*iH)->target();
355 if (xH==uH) uH = yH;
356 else if (yH==uH) uH = xH;
357 else { iH = aH.cyclicSucc(iH); continue; }
358 if (*iH==m_tNode_hRefEdge[rT]) a_is_parent = false;
359 bH.pushBack(*iH);
360 ListIterator<edge> jH = iH;
361 iH = aH.cyclicSucc(iH);
362 aH.del(jH);
363 }
364 m_bNode_numS[vB]++;
365 m_bNode_numP[vB]++;
366 node sT = m_T.newNode();
367 node pT = m_T.newNode();
368 m_tNode_type[sT] = SComp;
369 m_tNode_type[pT] = PComp;
370 m_tNode_owner[sT] = sT;
371 m_tNode_owner[pT] = pT;
372 edge v1 = m_H.newEdge(sH,tH);
373 edge v2 = m_H.newEdge(sH,tH);
374 edge v3 = m_H.newEdge(sH,tH);
375 edge v4 = m_H.newEdge(sH,tH);
376 m_hEdge_twinEdge[v1] = v2;
377 m_hEdge_twinEdge[v2] = v1;
378 m_hEdge_twinEdge[v3] = v4;
379 m_hEdge_twinEdge[v4] = v3;
380 m_hEdge_position[v1] = m_tNode_hEdges[sT].pushBack(v1);
381 m_hEdge_position[v2] = m_tNode_hEdges[pT].pushBack(v2);
382 m_hEdge_position[eH] = m_tNode_hEdges[pT].pushBack(eH);
383 m_hEdge_position[v3] = m_tNode_hEdges[pT].pushBack(v3);
384 m_hEdge_position[v4] = m_tNode_hEdges[rT].pushBack(v4);
385 m_hEdge_tNode[v1] = sT;
386 m_hEdge_tNode[v2] = m_hEdge_tNode[eH] = m_hEdge_tNode[v3] = pT;
387 m_hEdge_tNode[v4] = rT;
388 for (SListConstIterator<edge> iH=bH.begin(); iH.valid(); ++iH) {
389 m_hEdge_position[*iH] = m_tNode_hEdges[sT].pushBack(*iH);
390 m_hEdge_tNode[*iH] = sT;
391 }
392 if (a_is_parent) {
393 m_tNode_hRefEdge[sT] = v1;
394 m_tNode_hRefEdge[pT] = v3;
395 }
396 else {
397 m_tNode_hRefEdge[sT] = m_tNode_hRefEdge[rT];
398 m_tNode_hRefEdge[pT] = v2;
399 m_tNode_hRefEdge[rT] = v4;
400 if (!m_tNode_hRefEdge[sT]) m_bNode_SPQR[vB] = sT;
401 }
402 }
403 }
404 else {
405 node xT = 0;
406 SList<edge> absorbedEdges;
407 SList<edge> virtualEdgesInPath;
408 SList<edge> newVirtualEdges;
409
410 edge rH = m_tNode_hRefEdge[rT];
411
412 SListIterator<node> iT = pT.begin();
413 SListIterator<node> jT = iT;
414
415 virtualEdgesInPath.pushBack(0);
416 for (++jT; jT.valid(); ++iT, ++jT) {
417 edge gH,fH = m_tNode_hRefEdge[*iT];
418 if (!fH) {
419 gH = m_tNode_hRefEdge[*jT];
420 fH = m_hEdge_twinEdge[gH];
421 }
422 else {
423 gH = m_hEdge_twinEdge[fH];
424 if (spqrproper(gH)!=*jT) {
425 gH = m_tNode_hRefEdge[*jT];
426 fH = m_hEdge_twinEdge[gH];
427 }
428 }
429 virtualEdgesInPath.pushBack(fH);
430 virtualEdgesInPath.pushBack(gH);
431 }
432 virtualEdgesInPath.pushBack(0);
433
434 for (iT=pT.begin(); iT.valid(); ++iT) {
435 edge fH = virtualEdgesInPath.popFrontRet();
436 edge gH = virtualEdgesInPath.popFrontRet();
437 if (m_tNode_type[*iT]==SComp) {
438 List<edge>& aH = m_tNode_hEdges[*iT];
439 SList<edge> bH;
440 ListIterator<edge> iH,jH;
441 node zH;
442
443 node uH = 0;
444 if (!fH) { fH = gH; uH = sH; }
445 else if (!gH) uH = tH;
446
447 node vH = fH->source();
448 node wH = fH->target();
449
450 if (uH) {
451 iH = jH = m_hEdge_position[fH];
452 for( ; ; ) {
453 iH = aH.cyclicSucc(iH);
454 node xH = (*iH)->source();
455 node yH = (*iH)->target();
456 if (xH==vH) { zH = vH; vH = yH; break; }
457 if (xH==wH) { zH = wH; wH = vH; vH = yH; break; }
458 if (yH==vH) { zH = vH; vH = xH; break; }
459 if (yH==wH) { zH = wH; wH = vH; vH = xH; break; }
460 }
461 m_H.delEdge(*jH);
462 aH.del(jH);
463 jH = iH;
464 iH = aH.cyclicSucc(iH);
465 bH.pushBack(*jH);
466 aH.del(jH);
467 while (vH!=uH) {
468 for( ; ; ) {
469 node xH = (*iH)->source();
470 node yH = (*iH)->target();
471 if (xH==vH) { vH = yH; break; }
472 if (yH==vH) { vH = xH; break; }
473 iH = aH.cyclicSucc(iH);
474 }
475 jH = iH;
476 iH = aH.cyclicSucc(iH);
477 bH.pushBack(*jH);
478 aH.del(jH);
479 }
480 if (bH.size()==1) {
481 edge nH = bH.front();
482 if (nH==rH) rT = 0;
483 absorbedEdges.pushBack(nH);
484 }
485 else {
486 m_bNode_numS[vB]++;
487 node nT = m_T.newNode();
488 m_tNode_type[nT] = SComp;
489 m_tNode_owner[nT] = nT;
490 while (!bH.empty()) {
491 edge nH = bH.popFrontRet();
492 m_hEdge_position[nH] = m_tNode_hEdges[nT].pushBack(nH);
493 m_hEdge_tNode[nH] = nT;
494 if (nH==rH) rT = nT;
495 }
496 edge nH = m_H.newEdge(vH,zH);
497 m_hEdge_position[nH] = m_tNode_hEdges[nT].pushBack(nH);
498 m_hEdge_tNode[nH] = nT;
499 if (nT==rT) {
500 m_tNode_hRefEdge[nT] = rH;
501 if (!rH) m_bNode_SPQR[vB] = nT;
502 rH = nH;
503 }
504 else m_tNode_hRefEdge[nT] = nH;
505 newVirtualEdges.pushBack(nH);
506 }
507 if (m_tNode_hEdges[*iT].size()==1) xT = uniteSPQR(vB,xT,*iT);
508 else {
509 edge nH = m_H.newEdge(wH,vH);
510 m_hEdge_position[nH] = m_tNode_hEdges[*iT].pushBack(nH);
511 m_hEdge_tNode[nH] = *iT;
512 if (*iT==rT) rH = nH;
513 else m_tNode_hRefEdge[*iT] = nH;
514 newVirtualEdges.pushBack(nH);
515 }
516 }
517 else if (aH.size()==3) {
518 aH.del(m_hEdge_position[fH]);
519 aH.del(m_hEdge_position[gH]);
520 m_H.delEdge(fH);
521 m_H.delEdge(gH);
522 xT = uniteSPQR(vB,xT,*iT);
523 }
524 else {
525 node xH = gH->source();
526 node yH = gH->target();
527 edge nH = 0;
528 if (vH==xH) nH = m_H.newEdge(wH,yH);
529 else if (vH==yH) nH = m_H.newEdge(wH,xH);
530 else if (wH==xH) nH = m_H.newEdge(vH,yH);
531 else if (wH==yH) nH = m_H.newEdge(vH,xH);
532 if (nH) {
533 m_hEdge_position[nH] = aH.insertAfter(nH,m_hEdge_position[gH]);
534 m_hEdge_tNode[nH] = *iT;
535 if (*iT==rT) rH = nH;
536 else m_tNode_hRefEdge[*iT] = nH;
537 aH.del(m_hEdge_position[fH]);
538 aH.del(m_hEdge_position[gH]);
539 m_H.delEdge(fH);
540 m_H.delEdge(gH);
541 newVirtualEdges.pushBack(nH);
542 }
543 else {
544 iH = jH = m_hEdge_position[fH];
545 for( ; ; ) {
546 iH = aH.cyclicSucc(iH);
547 node xH = (*iH)->source();
548 node yH = (*iH)->target();
549 if (xH==vH) { zH = vH; vH = yH; break; }
550 if (xH==wH) { zH = wH; wH = vH; vH = yH; break; }
551 if (yH==vH) { zH = vH; vH = xH; break; }
552 if (yH==wH) { zH = wH; wH = vH; vH = xH; break; }
553 }
554 m_H.delEdge(*jH);
555 aH.del(jH);
556 jH = iH;
557 iH = aH.cyclicSucc(iH);
558 bH.pushBack(*jH);
559 aH.del(jH);
560 node pH = gH->source();
561 node qH = gH->target();
562 while (vH!=pH && vH!=qH) {
563 for( ; ; ) {
564 node xH = (*iH)->source();
565 node yH = (*iH)->target();
566 if (xH==vH) { vH = yH; break; }
567 if (yH==vH) { vH = xH; break; }
568 iH = aH.cyclicSucc(iH);
569 }
570 jH = iH;
571 iH = aH.cyclicSucc(iH);
572 bH.pushBack(*jH);
573 aH.del(jH);
574 }
575 aH.del(m_hEdge_position[gH]);
576 m_H.delEdge(gH);
577 if (bH.size()==1) {
578 edge nH = bH.front();
579 if (nH==rH) rT = 0;
580 absorbedEdges.pushBack(nH);
581 }
582 else {
583 m_bNode_numS[vB]++;
584 node nT = m_T.newNode();
585 m_tNode_type[nT] = SComp;
586 m_tNode_owner[nT] = nT;
587 while (!bH.empty()) {
588 edge nH = bH.popFrontRet();
589 m_hEdge_position[nH] = m_tNode_hEdges[nT].pushBack(nH);
590 m_hEdge_tNode[nH] = nT;
591 if (nH==rH) rT = nT;
592 }
593 edge nH = m_H.newEdge(vH,zH);
594 m_hEdge_position[nH] = m_tNode_hEdges[nT].pushBack(nH);
595 m_hEdge_tNode[nH] = nT;
596 if (nT==rT) {
597 m_tNode_hRefEdge[nT] = rH;
598 if (!rH) m_bNode_SPQR[vB] = nT;
599 rH = nH;
600 }
601 else m_tNode_hRefEdge[nT] = nH;
602 newVirtualEdges.pushBack(nH);
603 }
604 if (m_tNode_hEdges[*iT].size()==1) xT = uniteSPQR(vB,xT,*iT);
605 else {
606 edge nH = m_H.newEdge(wH,vH==pH?qH:pH);
607 m_hEdge_position[nH] = m_tNode_hEdges[*iT].pushBack(nH);
608 m_hEdge_tNode[nH] = *iT;
609 if (*iT==rT) rH = nH;
610 else m_tNode_hRefEdge[*iT] = nH;
611 newVirtualEdges.pushBack(nH);
612 }
613 }
614 }
615 }
616 else {
617 if (fH) {
618 m_tNode_hEdges[*iT].del(m_hEdge_position[fH]);
619 m_H.delEdge(fH);
620 }
621 if (gH) {
622 m_tNode_hEdges[*iT].del(m_hEdge_position[gH]);
623 m_H.delEdge(gH);
624 }
625 if (m_tNode_type[*iT]==PComp) {
626 if (m_tNode_hEdges[*iT].size()>1) {
627 edge nH = m_tNode_hEdges[*iT].front();
628 nH = m_H.newEdge(nH->source(),nH->target());
629 m_hEdge_position[nH] = m_tNode_hEdges[*iT].pushBack(nH);
630 m_hEdge_tNode[nH] = *iT;
631 if (*iT==rT) rH = nH;
632 else m_tNode_hRefEdge[*iT] = nH;
633 newVirtualEdges.pushBack(nH);
634 }
635 else xT = uniteSPQR(vB,xT,*iT);
636 }
637 else xT = uniteSPQR(vB,xT,*iT);
638 }
639 }
640 if (!xT) {
641 m_bNode_numR[vB]++;
642 xT = m_T.newNode();
643 m_tNode_type[xT] = RComp;
644 m_tNode_owner[xT] = xT;
645 }
646 while (!newVirtualEdges.empty()) {
647 edge oH = newVirtualEdges.popFrontRet();
648 edge nH = m_H.newEdge(oH->source(),oH->target());
649 m_hEdge_position[nH] = m_tNode_hEdges[xT].pushBack(nH);
650 m_hEdge_tNode[nH] = xT;
651 m_hEdge_twinEdge[nH] = oH;
652 m_hEdge_twinEdge[oH] = nH;
653 }
654 while (!absorbedEdges.empty()) {
655 edge nH = absorbedEdges.popFrontRet();
656 m_hEdge_position[nH] = m_tNode_hEdges[xT].pushBack(nH);
657 m_hEdge_tNode[nH] = xT;
658 }
659 m_hEdge_position[eH] = m_tNode_hEdges[xT].pushBack(eH);
660 m_hEdge_tNode[eH] = xT;
661 if (!rT) m_tNode_hRefEdge[xT] = rH;
662 else if (findSPQR(rT)!=xT) m_tNode_hRefEdge[xT] = m_hEdge_twinEdge[rH];
663 else {
664 m_tNode_hRefEdge[xT] = rH;
665 if (!rH) m_bNode_SPQR[vB] = xT;
666 }
667 }
668 delete &pT;
669 return eG;
670 }
671
672
673 node DynamicSPQRForest::updateInsertedNodeSPQR (node vB, edge eG, edge fG)
674 {
675 node vG = fG->source();
676 node wG = fG->target();
677 node vH = m_H.newNode();
678 node wH = repVertex(wG,vB);
679 m_gNode_hNode[vG] = vH;
680 m_hNode_gNode[vH] = vG;
681 edge fH = m_H.newEdge(vH,wH);
682 m_gEdge_hEdge[fG] = fH;
683 m_hEdge_gEdge[fH] = fG;
684 edge eH = m_gEdge_hEdge[eG];
685 m_H.moveTarget(eH,vH);
686 node vT = spqrproper(eH);
687 if (m_tNode_type[vT]==SComp) {
688 m_hEdge_position[fH] = m_tNode_hEdges[vT].insertAfter(fH,m_hEdge_position[eH]);
689 m_hEdge_tNode[fH] = vT;
690 }
691 else {
692 m_bNode_numS[vB]++;
693 node nT = m_T.newNode();
694 m_tNode_type[nT] = SComp;
695 m_tNode_owner[nT] = nT;
696 node uH = eH->source();
697 node wH = fH->target();
698 edge v1 = m_H.newEdge(uH,wH);
699 edge v2 = m_H.newEdge(uH,wH);
700 m_hEdge_position[v1] = m_tNode_hEdges[vT].insertAfter(v1,m_hEdge_position[eH]);
701 m_tNode_hEdges[vT].del(m_hEdge_position[eH]);
702 m_hEdge_position[v2] = m_tNode_hEdges[nT].pushBack(v2);
703 m_hEdge_position[eH] = m_tNode_hEdges[nT].pushBack(eH);
704 m_hEdge_position[fH] = m_tNode_hEdges[nT].pushBack(fH);
705 m_hEdge_tNode[v1] = vT;
706 m_hEdge_twinEdge[v1] = m_tNode_hRefEdge[nT] = v2;
707 m_hEdge_tNode[v2] = m_hEdge_tNode[eH] = m_hEdge_tNode[fH] = nT;
708 m_hEdge_twinEdge[v2] = v1;
709 }
710 return vG;
711 }
712
713
714 edge DynamicSPQRForest::updateInsertedEdge (edge eG)
715 {
716 node sG = eG->source();
717 node tG = eG->target();
718 node vB = bComponent(sG,tG);
719 if (vB) {
720 if (m_bNode_SPQR[vB]) {
721 edge eH = m_gEdge_hEdge[updateInsertedEdgeSPQR(vB,eG)];
722 m_bNode_hEdges[vB].pushBack(eH);
723 m_hEdge_bNode[eH] = vB;
724 }
725 else DynamicBCTree::updateInsertedEdge(eG);
726 }
727 else {
728 node nT = 0;
729 int numS,numP,numR;
730 SList<node>& pB = findPath(sG,tG);
731 SListIterator<node> jB = pB.begin();
732 SListIterator<node> iB = jB;
733 while (iB.valid()) { if (m_bNode_SPQR[*iB]) break; ++iB; }
734 if (iB.valid()) {
735 nT = m_T.newNode();
736 m_tNode_type[nT] = SComp;
737 m_tNode_owner[nT] = nT;
738 m_tNode_hRefEdge[nT] = 0;
739 numS = 1;
740 numP = 0;
741 numR = 0;
742 node sH = repVertex(sG,*jB);
743 for (iB=jB; iB.valid(); ++iB) {
744 node tH = (++jB).valid() ? cutVertex(*jB,*iB) : repVertex(tG,*iB);
745 node mT;
746 edge mH,nH;
747 switch (numberOfEdges(*iB)) {
748 case 0:
749 break;
750 case 1:
751 nH = m_bNode_hEdges[*iB].front();
752 m_hEdge_position[nH] = m_tNode_hEdges[nT].pushBack(nH);
753 m_hEdge_tNode[nH] = nT;
754 break;
755 case 2:
756 mT = m_T.newNode();
757 m_tNode_type[mT] = PComp;
758 m_tNode_owner[mT] = mT;
759 mH = m_bNode_hEdges[*iB].front();
760 m_hEdge_position[mH] = m_tNode_hEdges[mT].pushBack(mH);
761 m_hEdge_tNode[mH] = mT;
762 mH = m_bNode_hEdges[*iB].back();
763 m_hEdge_position[mH] = m_tNode_hEdges[mT].pushBack(mH);
764 m_hEdge_tNode[mH] = mT;
765 mH = m_H.newEdge(sH,tH);
766 m_hEdge_position[mH] = m_tNode_hEdges[mT].pushBack(mH);
767 m_hEdge_tNode[mH] = mT;
768 nH = m_H.newEdge(sH,tH);
769 m_hEdge_position[nH] = m_tNode_hEdges[nT].pushBack(nH);
770 m_hEdge_tNode[nH] = nT;
771 m_hEdge_twinEdge[mH] = nH;
772 m_hEdge_twinEdge[nH] = mH;
773 m_tNode_hRefEdge[mT] = mH;
774 numP++;
775 break;
776 default:
777 if (!m_bNode_SPQR[*iB]) createSPQR(*iB);
778 edge mG = m_G.newEdge(m_hNode_gNode[sH],m_hNode_gNode[tH]);
779 updateInsertedEdgeSPQR(*iB,mG);
780 mH = m_gEdge_hEdge[mG];
781 mT = spqrproper(mH);
782 m_G.delEdge(mG);
783 m_hEdge_gEdge[mH] = 0;
784 nH = m_H.newEdge(sH,tH);
785 m_hEdge_position[nH] = m_tNode_hEdges[nT].pushBack(nH);
786 m_hEdge_tNode[nH] = nT;
787 m_hEdge_twinEdge[mH] = nH;
788 m_hEdge_twinEdge[nH] = mH;
789 for( ; ; ) {
790 nH = m_tNode_hRefEdge[mT];
791 m_tNode_hRefEdge[mT] = mH;
792 if (!nH) break;
793 mH = m_hEdge_twinEdge[nH];
794 mT = spqrproper(mH);
795 }
796 numS += m_bNode_numS[*iB];
797 numP += m_bNode_numP[*iB];
798 numR += m_bNode_numR[*iB];
799 }
800 if (jB.valid()) sH = cutVertex(*iB,*jB);
801 }
802 }
803 delete &pB;
804 DynamicBCTree::updateInsertedEdge(eG);
805 if (nT) {
806 edge eH = m_gEdge_hEdge[eG];
807 m_hEdge_position[eH] = m_tNode_hEdges[nT].pushBack(eH);
808 m_hEdge_tNode[eH] = nT;
809 node eB = bcproper(eG);
810 m_bNode_SPQR[eB] = nT;
811 m_bNode_numS[eB] = numS;
812 m_bNode_numP[eB] = numP;
813 m_bNode_numR[eB] = numR;
814 }
815 }
816 return eG;
817 }
818
819
820 node DynamicSPQRForest::updateInsertedNode (edge eG, edge fG)
821 {
822 node vB = bcproper(eG);
823 if (m_bNode_SPQR[vB]) {
824 node uG = updateInsertedNodeSPQR(vB,eG,fG);
825 m_gNode_isMarked[uG] = false;
826 edge fH = m_gEdge_hEdge[fG];
827 m_bNode_hEdges[vB].pushBack(fH);
828 m_hEdge_bNode[fH] = vB;
829 m_hNode_bNode[fH->source()] = vB;
830 m_bNode_numNodes[vB]++;
831 return uG;
832 }
833 return DynamicBCTree::updateInsertedNode(eG,fG);
834 }
835
836
837 }
Windows Explorer Extension to Operate Git