?  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 / basic / Graph.cpp
bloba84745005a508e7174a0e4ba79ccb50fc5e2ad80
1 /*
2 * $Revision: 2523 $
3 *
4 * last checkin:
5 * $Author: gutwenger $
6 * $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
7 ***************************************************************/
8
9 /** \file
10 * \brief Implementation of Graph class
11 *
12 * \author Carsten Gutwenger
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 #include <ogdf/basic/Array.h>
44 #include <ogdf/basic/AdjEntryArray.h>
45 #include <ogdf/fileformats/GmlParser.h>
46 #include <ogdf/basic/simple_graph_alg.h>
47 #include <ogdf/basic/GraphObserver.h>
48
49
50 #define MIN_NODE_TABLE_SIZE (1 << 4)
51 #define MIN_EDGE_TABLE_SIZE (1 << 4)
52
53
54 namespace ogdf {
55
56 Graph::Graph()
57 {
58 m_nNodes = m_nEdges = m_nodeIdCount = m_edgeIdCount = 0;
59 m_nodeArrayTableSize = MIN_NODE_TABLE_SIZE;
60 m_edgeArrayTableSize = MIN_EDGE_TABLE_SIZE;
61 }
62
63
64 Graph::Graph(const Graph &G)
65 {
66 m_nNodes = m_nEdges = m_nodeIdCount = m_edgeIdCount = 0;
67 copy(G);
68 m_nodeArrayTableSize = nextPower2(MIN_NODE_TABLE_SIZE,m_nodeIdCount);
69 m_edgeArrayTableSize = nextPower2(MIN_EDGE_TABLE_SIZE,m_edgeIdCount);
70 }
71
72
73 Graph::~Graph()
74 {
75 ListIterator<NodeArrayBase*> itVNext;
76 for(ListIterator<NodeArrayBase*> itV = m_regNodeArrays.begin();
77 itV.valid(); itV = itVNext)
78 {
79 itVNext = itV.succ();
80 (*itV)->disconnect();
81 }
82
83 ListIterator<EdgeArrayBase*> itENext;
84 for(ListIterator<EdgeArrayBase*> itE = m_regEdgeArrays.begin();
85 itE.valid(); itE = itENext)
86 {
87 itENext = itE.succ();
88 (*itE)->disconnect();
89 }
90
91 ListIterator<AdjEntryArrayBase*> itAdjNext;
92 for(ListIterator<AdjEntryArrayBase*> itAdj = m_regAdjArrays.begin();
93 itAdj.valid(); itAdj = itAdjNext)
94 {
95 itAdjNext = itAdj.succ();
96 (*itAdj)->disconnect();
97 }
98
99 for (node v = m_nodes.begin(); v; v = v->succ()) {
100 v->m_adjEdges.~GraphList<AdjElement>();
101 }
102 }
103
104
105 Graph &Graph::operator=(const Graph &G)
106 {
107 clear(); copy(G);
108 m_nodeArrayTableSize = nextPower2(MIN_NODE_TABLE_SIZE,m_nodeIdCount);
109 m_edgeArrayTableSize = nextPower2(MIN_EDGE_TABLE_SIZE,m_edgeIdCount);
110 reinitArrays();
111
112 OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
113
114 return *this;
115 }
116
117
118 void Graph::assign(const Graph &G, NodeArray<node> &mapNode,
119 EdgeArray<edge> &mapEdge)
120 {
121 clear();
122 copy(G,mapNode,mapEdge);
123 m_nodeArrayTableSize = nextPower2(MIN_NODE_TABLE_SIZE,m_nodeIdCount);
124 m_edgeArrayTableSize = nextPower2(MIN_EDGE_TABLE_SIZE,m_edgeIdCount);
125 reinitArrays();
126 }
127
128
129 void Graph::construct(const Graph &G, NodeArray<node> &mapNode,
130 EdgeArray<edge> &mapEdge)
131 {
132 copy(G,mapNode,mapEdge);
133 m_nodeArrayTableSize = nextPower2(MIN_NODE_TABLE_SIZE,m_nodeIdCount);
134 m_edgeArrayTableSize = nextPower2(MIN_EDGE_TABLE_SIZE,m_edgeIdCount);
135 }
136
137
138 void Graph::copy(const Graph &G, NodeArray<node> &mapNode,
139 EdgeArray<edge> &mapEdge)
140 {
141 if (G.m_nNodes == 0) return;
142
143 mapNode.init(G,0);
144
145 node vG;
146 forall_nodes(vG,G) {
147 node v = mapNode[vG] = pureNewNode();
148 v->m_indeg = vG->m_indeg;
149 v->m_outdeg = vG->m_outdeg;
150 }
151
152 if (G.m_nEdges == 0) return;
153
154 mapEdge.init(G,0);
155
156 edge e, eC;
157 forall_edges(e,G) {
158 m_edges.pushBack(eC = mapEdge[e] =
159 OGDF_NEW EdgeElement(
160 mapNode[e->source()],mapNode[e->target()],m_edgeIdCount));
161
162 eC->m_adjSrc = OGDF_NEW AdjElement(eC,m_edgeIdCount<<1);
163 (eC->m_adjTgt = OGDF_NEW AdjElement(eC,(m_edgeIdCount<<1)|1))
164 ->m_twin = eC->m_adjSrc;
165 eC->m_adjSrc->m_twin = eC->m_adjTgt;
166 m_edgeIdCount++;
167 }
168 m_nEdges = G.m_nEdges;
169
170 EdgeArray<bool> mark(G,false);
171
172 forall_nodes(vG,G) {
173 node v = mapNode[vG];
174 GraphList<AdjElement> &adjEdges = vG->m_adjEdges;
175 for (AdjElement *adjG = adjEdges.begin(); adjG; adjG = adjG->succ()) {
176 int id = adjG->m_edge->index();
177 edge eC = mapEdge[id];
178
179 adjEntry adj;
180 if (eC->isSelfLoop()) {
181 if (mark[id])
182 adj = eC->m_adjTgt;
183 else {
184 adj = eC->m_adjSrc;
185 mark[id] = true;
186 }
187 } else
188 adj = (v == eC->m_src) ? eC->m_adjSrc : eC->m_adjTgt;
189
190 v->m_adjEdges.pushBack(adj);
191 adj->m_node = v;
192 }
193 }
194 }
195
196
197 void Graph::copy(const Graph &G)
198 {
199 NodeArray<node> mapNode;
200 EdgeArray<edge> mapEdge;
201 copy(G,mapNode,mapEdge);
202
203 OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
204 }
205
206
207 void Graph::constructInitByNodes(
208 const Graph &G,
209 const List<node> &nodes,
210 NodeArray<node> &mapNode,
211 EdgeArray<edge> &mapEdge)
212 {
213 // clear
214 for (node v = m_nodes.begin(); v; v = v->succ()) {
215 v->m_adjEdges.~GraphList<AdjElement>();
216 }
217
218 m_nodes.clear();
219 m_edges.clear();
220
221 m_nNodes = m_nEdges = m_nodeIdCount = m_edgeIdCount = 0;
222 m_nodeArrayTableSize = MIN_NODE_TABLE_SIZE;
223
224
225 // list of edges adjacent to nodes in nodes
226 SListPure<edge> edges;
227
228 // create nodes and assemble list of edges
229 ListConstIterator<node> itG;
230 for(itG = nodes.begin(); itG.valid(); ++itG) {
231 node vG = *itG;
232 node v = mapNode[vG] = pureNewNode();
233
234 v->m_indeg = vG->m_indeg;
235 v->m_outdeg = vG->m_outdeg;
236
237 adjEntry adjG;
238 forall_adj(adjG,vG) {
239 // corresponding adjacency entries differ by index modulo 2
240 // the following conditions makes sure that each edge is
241 // added only once to edges
242 if ((adjG->m_id & 1) == 0)
243 edges.pushBack(adjG->m_edge);
244 }
245 }
246
247 // create edges
248 SListConstIterator<edge> it;
249 for(it = edges.begin(); it.valid(); ++it)
250 {
251 edge eG = *it;
252 node v = mapNode[eG->source()];
253 node w = mapNode[eG->target()];
254
255 edge eC = mapEdge[eG] = OGDF_NEW EdgeElement(v, w, m_edgeIdCount);
256 m_edges.pushBack(eC);
257
258 eC->m_adjSrc = OGDF_NEW AdjElement(eC, m_edgeIdCount<<1);
259 (eC->m_adjTgt = OGDF_NEW AdjElement(eC, (m_edgeIdCount<<1)|1))
260 ->m_twin = eC->m_adjSrc;
261 eC->m_adjSrc->m_twin = eC->m_adjTgt;
262 ++m_edgeIdCount;
263 ++m_nEdges;
264 }
265
266 EdgeArray<bool> mark(G,false);
267 for(itG = nodes.begin(); itG.valid(); ++itG) {
268 node vG = *itG;
269 node v = mapNode[vG];
270
271 GraphList<AdjElement> &adjEdges = vG->m_adjEdges;
272 for (AdjElement *adjG = adjEdges.begin(); adjG; adjG = adjG->succ()) {
273 int id = adjG->m_edge->index();
274 edge eC = mapEdge[id];
275
276 adjEntry adj;
277 if (eC->isSelfLoop()) {
278 if (mark[id])
279 adj = eC->m_adjTgt;
280 else {
281 adj = eC->m_adjSrc;
282 mark[id] = true;
283 }
284 } else
285 adj = (v == eC->m_src) ? eC->m_adjSrc : eC->m_adjTgt;
286
287 v->m_adjEdges.pushBack(adj);
288 adj->m_node = v;
289 }
290 }
291
292 /*
293 AdjElement *adjSrc = OGDF_NEW AdjElement(v);
294
295 v->m_adjEdges.pushBack(adjSrc);
296 //v->m_outdeg++;
297
298 AdjElement *adjTgt = OGDF_NEW AdjElement(w);
299
300 w->m_adjEdges.pushBack(adjTgt);
301 //w->m_indeg++;
302
303 adjSrc->m_twin = adjTgt;
304 adjTgt->m_twin = adjSrc;
305
306 adjTgt->m_id = (adjSrc->m_id = m_edgeIdCount << 1) | 1;
307 edge e = OGDF_NEW EdgeElement(v,w,adjSrc,adjTgt,m_edgeIdCount++);
308
309 ++m_nEdges;
310 m_edges.pushBack(e);
311
312 mapEdge[eG] = adjSrc->m_edge = adjTgt->m_edge = e;
313 }*/
314
315 // set size of associated arrays and reinitialize all (we have now a
316 // completely new graph)
317 m_nodeArrayTableSize = nextPower2(MIN_NODE_TABLE_SIZE,m_nodeIdCount);
318 m_edgeArrayTableSize = nextPower2(MIN_EDGE_TABLE_SIZE,m_edgeIdCount);
319 reinitArrays();
320
321 OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
322 }
323
324
325 //------------------
326 //mainly a copy of the above code, remerge this again
327 void Graph::constructInitByActiveNodes(
328 const List<node> &nodes,
329 const NodeArray<bool> &activeNodes,
330 NodeArray<node> &mapNode,
331 EdgeArray<edge> &mapEdge)
332 {
333 // clear
334 for (node v = m_nodes.begin(); v; v = v->succ()) {
335 v->m_adjEdges.~GraphList<AdjElement>();
336 }
337
338 m_nodes.clear();
339 m_edges.clear();
340
341 m_nNodes = m_nEdges = m_nodeIdCount = m_edgeIdCount = 0;
342 m_nodeArrayTableSize = MIN_NODE_TABLE_SIZE;
343
344
345 // list of edges adjacent to nodes in nodes
346 SListPure<edge> edges;
347
348 // create nodes and assemble list of edges
349 //NOTE: nodes is a list of ACTIVE nodes
350 ListConstIterator<node> itG;
351 for(itG = nodes.begin(); itG.valid(); ++itG) {
352 node vG = *itG;
353 node v = mapNode[vG] = pureNewNode();
354
355 //we cannot assign the original degree, as there
356 //may be edges to non-active nodes
357 //v->m_indeg = vG->m_indeg;
358 //v->m_outdeg = vG->m_outdeg;
359
360 int inCount = 0;
361 int outCount = 0;
362 adjEntry adjG;
363 forall_adj(adjG,vG)
364 {
365 // coresponding adjacency entries differ by index modulo 2
366 // the following conditions makes sure that each edge is
367 // added only once to edges
368 if (activeNodes[adjG->m_edge->opposite(vG)])
369 {
370 if ((adjG->m_id & 1) == 0)
371 {
372 edges.pushBack(adjG->m_edge);
373 }//if one time
374 if (adjG->m_edge->source() == vG) outCount++;
375 else inCount++;
376 }//if opposite active
377 }//foralladj
378 v->m_indeg = inCount;
379 v->m_outdeg = outCount;
380 }//for nodes
381
382 // create edges
383 SListConstIterator<edge> it;
384 for(it = edges.begin(); it.valid(); ++it)
385 {
386 edge eG = *it;
387 node v = mapNode[eG->source()];
388 node w = mapNode[eG->target()];
389
390 AdjElement *adjSrc = OGDF_NEW AdjElement(v);
391
392 v->m_adjEdges.pushBack(adjSrc);
393 //v->m_outdeg++;
394
395 AdjElement *adjTgt = OGDF_NEW AdjElement(w);
396
397 w->m_adjEdges.pushBack(adjTgt);
398 //w->m_indeg++;
399
400 adjSrc->m_twin = adjTgt;
401 adjTgt->m_twin = adjSrc;
402
403 adjTgt->m_id = (adjSrc->m_id = m_edgeIdCount << 1) | 1;
404 edge e = OGDF_NEW EdgeElement(v,w,adjSrc,adjTgt,m_edgeIdCount++);
405
406 ++m_nEdges;
407 m_edges.pushBack(e);
408
409 mapEdge[eG] = adjSrc->m_edge = adjTgt->m_edge = e;
410 }
411
412 // set size of associated arrays and reinitialize all (we have now a
413 // completely new graph)
414 m_nodeArrayTableSize = nextPower2(MIN_NODE_TABLE_SIZE,m_nodeIdCount);
415 m_edgeArrayTableSize = nextPower2(MIN_EDGE_TABLE_SIZE,m_edgeIdCount);
416 reinitArrays();
417
418 OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
419 }//constructinitbyactivenodes
420
421 //------------------
422
423
424
425 node Graph::newNode()
426 {
427 ++m_nNodes;
428 if (m_nodeIdCount == m_nodeArrayTableSize) {
429 m_nodeArrayTableSize <<= 1;
430 for(ListIterator<NodeArrayBase*> it = m_regNodeArrays.begin();
431 it.valid(); ++it)
432 {
433 (*it)->enlargeTable(m_nodeArrayTableSize);
434 }
435 }
436
437 #ifdef OGDF_DEBUG
438 node v = OGDF_NEW NodeElement(this,m_nodeIdCount++);
439 #else
440 node v = OGDF_NEW NodeElement(m_nodeIdCount++);
441 #endif
442
443 m_nodes.pushBack(v);
444 // notify all registered observers
445 for(ListIterator<GraphObserver*> it = m_regStructures.begin();
446 it.valid(); ++it) (*it)->nodeAdded(v);
447
448 return v;
449 }
450
451
452 //what about negative index numbers?
453 node Graph::newNode(int index)
454 {
455 ++m_nNodes;
456
457 if(index >= m_nodeIdCount) {
458 m_nodeIdCount = index+1;
459
460 if(index >= m_nodeArrayTableSize) {
461 m_nodeArrayTableSize = nextPower2(m_nodeArrayTableSize,index);
462 for(ListIterator<NodeArrayBase*> it = m_regNodeArrays.begin();
463 it.valid(); ++it)
464 {
465 (*it)->enlargeTable(m_nodeArrayTableSize);
466 }
467 }
468 }
469
470 #ifdef OGDF_DEBUG
471 node v = OGDF_NEW NodeElement(this,index);
472 #else
473 node v = OGDF_NEW NodeElement(index);
474 #endif
475
476 m_nodes.pushBack(v);
477 // notify all registered observers
478 for(ListIterator<GraphObserver*> it = m_regStructures.begin();
479 it.valid(); ++it) (*it)->nodeAdded(v);
480 return v;
481 }
482
483
484 node Graph::pureNewNode()
485 {
486 ++m_nNodes;
487
488 #ifdef OGDF_DEBUG
489 node v = OGDF_NEW NodeElement(this,m_nodeIdCount++);
490 #else
491 node v = OGDF_NEW NodeElement(m_nodeIdCount++);
492 #endif
493
494 m_nodes.pushBack(v);
495 // notify all registered observers
496 for(ListIterator<GraphObserver*> it = m_regStructures.begin();
497 it.valid(); ++it) (*it)->nodeAdded(v);
498 return v;
499 }
500
501
502 // IMPORTANT:
503 // The indices of the two adjacency entries pointing to an edge differ
504 // only in the last bit (adjSrc/2 == adjTgt/2)
505 //
506 // This can be useful sometimes in order to avoid visiting an edge twice.
507 edge Graph::createEdgeElement(node v, node w, adjEntry adjSrc, adjEntry adjTgt)
508 {
509 if (m_edgeIdCount == m_edgeArrayTableSize) {
510 m_edgeArrayTableSize <<= 1;
511
512 for(ListIterator<EdgeArrayBase*> it = m_regEdgeArrays.begin();
513 it.valid(); ++it)
514 {
515 (*it)->enlargeTable(m_edgeArrayTableSize);
516 }
517
518 for(ListIterator<AdjEntryArrayBase*> itAdj = m_regAdjArrays.begin();
519 itAdj.valid(); ++itAdj)
520 {
521 (*itAdj)->enlargeTable(m_edgeArrayTableSize << 1);
522 }
523 }
524
525 adjTgt->m_id = (adjSrc->m_id = m_edgeIdCount << 1) | 1;
526 edge e = OGDF_NEW EdgeElement(v,w,adjSrc,adjTgt,m_edgeIdCount++);
527 m_edges.pushBack(e);
528 // notify all registered observers
529 for(ListIterator<GraphObserver*> it = m_regStructures.begin();
530 it.valid(); ++it) (*it)->edgeAdded(e);
531 return e;
532 }
533
534
535 edge Graph::newEdge(node v, node w, int index)
536 {
537 OGDF_ASSERT(v != 0 && w != 0);
538 OGDF_ASSERT(v->graphOf() == this && w->graphOf() == this);
539
540 ++m_nEdges;
541
542 AdjElement *adjSrc = OGDF_NEW AdjElement(v);
543
544 v->m_adjEdges.pushBack(adjSrc);
545 v->m_outdeg++;
546
547 AdjElement *adjTgt = OGDF_NEW AdjElement(w);
548
549 w->m_adjEdges.pushBack(adjTgt);
550 w->m_indeg++;
551
552 adjSrc->m_twin = adjTgt;
553 adjTgt->m_twin = adjSrc;
554
555 if(index >= m_edgeIdCount) {
556 m_edgeIdCount = index+1;
557
558 if(index >= m_edgeArrayTableSize) {
559 m_edgeArrayTableSize = nextPower2(m_edgeArrayTableSize,index);
560
561 for(ListIterator<EdgeArrayBase*> it = m_regEdgeArrays.begin();
562 it.valid(); ++it)
563 {
564 (*it)->enlargeTable(m_edgeArrayTableSize);
565 }
566
567 for(ListIterator<AdjEntryArrayBase*> itAdj = m_regAdjArrays.begin();
568 itAdj.valid(); ++itAdj)
569 {
570 (*itAdj)->enlargeTable(m_edgeArrayTableSize << 1);
571 }
572 }
573 }
574
575 adjTgt->m_id = (adjSrc->m_id = index/*m_edgeIdCount*/ << 1) | 1;
576 edge e = OGDF_NEW EdgeElement(v,w,adjSrc,adjTgt,index);
577 m_edges.pushBack(e);
578 // notify all registered observers
579 for(ListIterator<GraphObserver*> it = m_regStructures.begin();
580 it.valid(); ++it) (*it)->edgeAdded(e);
581 return adjSrc->m_edge = adjTgt->m_edge = e;
582 }
583
584
585 edge Graph::newEdge(node v, node w)
586 {
587 OGDF_ASSERT(v != 0 && w != 0);
588 OGDF_ASSERT(v->graphOf() == this && w->graphOf() == this);
589
590 ++m_nEdges;
591
592 AdjElement *adjSrc = OGDF_NEW AdjElement(v);
593
594 v->m_adjEdges.pushBack(adjSrc);
595 v->m_outdeg++;
596
597 AdjElement *adjTgt = OGDF_NEW AdjElement(w);
598
599 w->m_adjEdges.pushBack(adjTgt);
600 w->m_indeg++;
601
602 adjSrc->m_twin = adjTgt;
603 adjTgt->m_twin = adjSrc;
604
605 edge e = createEdgeElement(v,w,adjSrc,adjTgt);
606
607 return adjSrc->m_edge = adjTgt->m_edge = e;
608 }
609
610
611 edge Graph::newEdge(adjEntry adjStart, adjEntry adjEnd, Direction dir)
612 {
613 OGDF_ASSERT(adjStart != 0 && adjEnd != 0)
614 OGDF_ASSERT(adjStart->graphOf() == this && adjEnd->graphOf() == this);
615
616 ++m_nEdges;
617
618 node v = adjStart->theNode(), w = adjEnd->theNode();
619
620 AdjElement *adjTgt = OGDF_NEW AdjElement(w);
621 AdjElement *adjSrc = OGDF_NEW AdjElement(v);
622
623 if(dir == ogdf::after) {
624 w->m_adjEdges.insertAfter(adjTgt,adjEnd);
625 v->m_adjEdges.insertAfter(adjSrc,adjStart);
626 } else {
627 w->m_adjEdges.insertBefore(adjTgt,adjEnd);
628 v->m_adjEdges.insertBefore(adjSrc,adjStart);
629 }
630
631 w->m_indeg++;
632 v->m_outdeg++;
633
634 adjSrc->m_twin = adjTgt;
635 adjTgt->m_twin = adjSrc;
636
637 edge e = createEdgeElement(v,w,adjSrc,adjTgt);
638
639 return adjSrc->m_edge = adjTgt->m_edge = e;
640 }
641
642 edge Graph::newEdge(node v, adjEntry adjEnd)
643 {
644 OGDF_ASSERT(v != 0 && adjEnd != 0)
645 OGDF_ASSERT(v->graphOf() == this && adjEnd->graphOf() == this);
646
647 ++m_nEdges;
648
649 node w = adjEnd->theNode();
650
651 AdjElement *adjTgt = OGDF_NEW AdjElement(w);
652
653 w->m_adjEdges.insertAfter(adjTgt,adjEnd);
654 w->m_indeg++;
655
656 AdjElement *adjSrc = OGDF_NEW AdjElement(v);
657
658 v->m_adjEdges.pushBack(adjSrc);
659 v->m_outdeg++;
660
661 adjSrc->m_twin = adjTgt;
662 adjTgt->m_twin = adjSrc;
663
664 edge e = createEdgeElement(v,w,adjSrc,adjTgt);
665
666 return adjSrc->m_edge = adjTgt->m_edge = e;
667 }//newedge
668 //copy of above function with edge ending at v
669 edge Graph::newEdge(adjEntry adjStart, node v)
670 {
671 OGDF_ASSERT(v != 0 && adjStart != 0)
672 OGDF_ASSERT(v->graphOf() == this && adjStart->graphOf() == this);
673
674 ++m_nEdges;
675
676 node w = adjStart->theNode();
677
678 AdjElement *adjSrc = OGDF_NEW AdjElement(w);
679
680 w->m_adjEdges.insertAfter(adjSrc, adjStart);
681 w->m_outdeg++;
682
683 AdjElement *adjTgt = OGDF_NEW AdjElement(v);
684
685 v->m_adjEdges.pushBack(adjTgt);
686 v->m_indeg++;
687
688 adjSrc->m_twin = adjTgt;
689 adjTgt->m_twin = adjSrc;
690
691 edge e = createEdgeElement(w,v,adjSrc,adjTgt);
692
693 return adjSrc->m_edge = adjTgt->m_edge = e;
694 }//newedge
695
696
697 void Graph::move(edge e,
698 adjEntry adjSrc,
699 Direction dirSrc,
700 adjEntry adjTgt,
701 Direction dirTgt)
702 {
703 OGDF_ASSERT(e->graphOf() == this);
704 OGDF_ASSERT(adjSrc->graphOf() == this && adjTgt->graphOf() == this);
705 OGDF_ASSERT(adjSrc != e->m_adjSrc && adjSrc != e->m_adjTgt);
706 OGDF_ASSERT(adjTgt != e->m_adjSrc && adjTgt != e->m_adjTgt);
707
708 node v = adjSrc->m_node, w = adjTgt->m_node;
709 adjEntry adj1 = e->m_adjSrc, adj2 = e->m_adjTgt;
710 e->m_src->m_adjEdges.move(adj1,v->m_adjEdges,adjSrc,dirSrc);
711 e->m_tgt->m_adjEdges.move(adj2,w->m_adjEdges,adjTgt,dirTgt);
712
713 e->m_src->m_outdeg--;
714 e->m_tgt->m_indeg--;
715
716 adj1->m_node = e->m_src = v;
717 adj2->m_node = e->m_tgt = w;
718
719 v->m_outdeg++;
720 w->m_indeg++;
721 }
722
723
724 void Graph::moveTarget(edge e, node v)
725 {
726 OGDF_ASSERT(e->graphOf() == this);
727 OGDF_ASSERT(v->graphOf() == this);
728
729 adjEntry adj = e->m_adjTgt;
730 e->m_tgt->m_adjEdges.move(adj,v->m_adjEdges);
731
732 e->m_tgt->m_indeg--;
733 adj->m_node = e->m_tgt = v;
734 v->m_indeg++;
735 }
736
737 void Graph::moveTarget(edge e, adjEntry adjTgt, Direction dir)
738 {
739 node v = adjTgt->theNode();
740
741 OGDF_ASSERT(e->graphOf() == this);
742 OGDF_ASSERT(v->graphOf() == this);
743
744 adjEntry adj = e->m_adjTgt;
745 e->m_tgt->m_adjEdges.move(adj,v->m_adjEdges, adjTgt, dir);
746
747 e->m_tgt->m_indeg--;
748 adj->m_node = e->m_tgt = v;
749 v->m_indeg++;
750 }
751
752 // By Leipert
753 void Graph::moveSource(edge e, node v)
754 {
755 OGDF_ASSERT(e->graphOf() == this);
756 OGDF_ASSERT(v->graphOf() == this);
757
758 adjEntry adj = e->m_adjSrc;
759 e->m_src->m_adjEdges.move(adj,v->m_adjEdges);
760
761 e->m_src->m_outdeg--;
762 adj->m_node = e->m_src = v;
763 v->m_outdeg++;
764 }
765
766 void Graph::moveSource(edge e, adjEntry adjSrc, Direction dir)
767 {
768 node v = adjSrc->theNode();
769
770 OGDF_ASSERT(e->graphOf() == this);
771 OGDF_ASSERT(v->graphOf() == this);
772
773 adjEntry adj = e->m_adjSrc;
774 e->m_src->m_adjEdges.move(adj,v->m_adjEdges, adjSrc, dir);
775
776 e->m_src->m_outdeg--;
777 adj->m_node = e->m_src = v;
778 v->m_outdeg++;
779 }
780
781 edge Graph::split(edge e)
782 {
783 OGDF_ASSERT(e != 0 && e->graphOf() == this);
784
785 ++m_nEdges;
786
787 node u = newNode();
788 u->m_indeg = u->m_outdeg = 1;
789
790 adjEntry adjTgt = OGDF_NEW AdjElement(u);
791 adjTgt->m_edge = e;
792 adjTgt->m_twin = e->m_adjSrc;
793 e->m_adjSrc->m_twin = adjTgt;
794
795 // adapt adjacency entry index to hold invariant
796 adjTgt->m_id = e->m_adjTgt->m_id;
797
798 u->m_adjEdges.pushBack(adjTgt);
799
800 adjEntry adjSrc = OGDF_NEW AdjElement(u);
801 adjSrc->m_twin = e->m_adjTgt;
802 u->m_adjEdges.pushBack(adjSrc);
803
804 int oldId = e->m_adjTgt->m_id;
805 edge e2 = createEdgeElement(u,e->m_tgt,adjSrc,e->m_adjTgt);
806 resetAdjEntryIndex(e->m_adjTgt->m_id,oldId);
807
808 e2->m_adjTgt->m_twin = adjSrc;
809 e->m_adjTgt->m_edge = adjSrc->m_edge = e2;
810
811 e->m_tgt = u;
812 e->m_adjTgt = adjTgt;
813 return e2;
814 }
815
816
817 void Graph::unsplit(node u)
818 {
819 edge eIn = u->firstAdj()->theEdge();
820 edge eOut = u->lastAdj()->theEdge();
821
822 if (eIn->target() != u)
823 swap(eIn,eOut);
824
825 unsplit(eIn,eOut);
826 }
827
828
829
830 void Graph::unsplit(edge eIn, edge eOut)
831 {
832 node u = eIn->target();
833
834 // u must be a node with exactly one incoming edge eIn and one outgoing
835 // edge eOut
836 OGDF_ASSERT(u->graphOf() == this && u->indeg() == 1 &&
837 u->outdeg() == 1 && eOut->source() == u);
838
839 // none of them is a self-loop!
840 OGDF_ASSERT(eIn->isSelfLoop() == false && eOut->isSelfLoop() == false);
841
842 // we reuse these adjacency entries
843 adjEntry adjSrc = eIn ->m_adjSrc;
844 adjEntry adjTgt = eOut->m_adjTgt;
845
846 eIn->m_tgt = eOut->m_tgt;
847
848 // adapt adjacency entry index to hold invariant
849 resetAdjEntryIndex(eIn->m_adjTgt->m_id,adjTgt->m_id);
850 adjTgt->m_id = eIn->m_adjTgt->m_id; // correct id of adjacency entry!
851
852 eIn->m_adjTgt = adjTgt;
853
854 adjSrc->m_twin = adjTgt;
855 adjTgt->m_twin = adjSrc;
856
857 adjTgt->m_edge = eIn;
858
859 // notify all registered observers
860 for(ListIterator<GraphObserver*> it = m_regStructures.begin();
861 it.valid(); ++it) (*it)->edgeDeleted(eOut);
862 // notify all registered observers
863 for(ListIterator<GraphObserver*> it = m_regStructures.begin();
864 it.valid(); ++it) (*it)->nodeDeleted(u);
865 // remove structures that are no longer used
866 m_edges.del(eOut);
867 m_nodes.del(u);
868 --m_nNodes;
869 --m_nEdges;
870
871 }
872
873
874 void Graph::delNode(node v)
875 {
876 OGDF_ASSERT(v != 0 && v->graphOf() == this)
877
878 for(ListIterator<GraphObserver*> it = m_regStructures.begin();
879 it.valid(); ++it) (*it)->nodeDeleted(v);
880
881 --m_nNodes;
882
883 GraphList<AdjElement> &adjEdges = v->m_adjEdges;
884 AdjElement *adj;
885 while((adj = adjEdges.begin()) != 0)
886 delEdge(adj->m_edge);
887
888 m_nodes.del(v);
889 }
890
891
892 void Graph::delEdge(edge e)
893 {
894 OGDF_ASSERT(e != 0 && e->graphOf() == this)
895
896 // notify all registered observers
897 for(ListIterator<GraphObserver*> it = m_regStructures.begin();
898 it.valid(); ++it) (*it)->edgeDeleted(e);
899
900 --m_nEdges;
901
902 node src = e->m_src, tgt = e->m_tgt;
903
904 src->m_adjEdges.del(e->m_adjSrc);
905 src->m_outdeg--;
906 tgt->m_adjEdges.del(e->m_adjTgt);
907 tgt->m_indeg--;
908
909 m_edges.del(e);
910 }
911
912
913 void Graph::clear()
914 {
915 //tell all structures to clear their graph-initialized data
916 for(ListIterator<GraphObserver*> it = m_regStructures.begin();
917 it.valid(); ++it)
918 {
919 (*it)->cleared();
920 }//for
921 for (node v = m_nodes.begin(); v; v = v->succ()) {
922 v->m_adjEdges.~GraphList<AdjElement>();
923 }
924
925 m_nodes.clear();
926 m_edges.clear();
927
928 m_nNodes = m_nEdges = m_nodeIdCount = m_edgeIdCount = 0;
929 m_nodeArrayTableSize = MIN_NODE_TABLE_SIZE;
930 reinitArrays();
931
932 OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
933 }
934
935
936 void Graph::reverseEdge(edge e)
937 {
938 OGDF_ASSERT(e != 0 && e->graphOf() == this)
939 node &src = e->m_src, &tgt = e->m_tgt;
940
941 swap(src,tgt);
942 swap(e->m_adjSrc,e->m_adjTgt);
943 src->m_outdeg++; src->m_indeg--;
944 tgt->m_outdeg--; tgt->m_indeg++;
945 }
946
947
948 void Graph::reverseAllEdges()
949 {
950 for (edge e = m_edges.begin(); e; e = e->succ())
951 reverseEdge(e);
952
953 OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
954 }
955
956
957 void Graph::reverseAdjEdges()
958 {
959 node v;
960 forall_nodes(v,*this)
961 reverseAdjEdges(v);
962 }
963
964
965 node Graph::chooseNode() const
966 {
967 if (m_nNodes == 0) return 0;
968 int k = ogdf::randomNumber(0,m_nNodes-1);
969 node v = firstNode();
970 while(k--) v = v->succ();
971 return v;
972 }
973
974
975 edge Graph::chooseEdge() const
976 {
977 if (m_nEdges == 0) return 0;
978 int k = ogdf::randomNumber(0,m_nEdges-1);
979 edge e = firstEdge();
980 while(k--) e = e->succ();
981 return e;
982 }
983
984
985 edge Graph::searchEdge(node v, node w) const
986 {
987 OGDF_ASSERT(v != 0 && v->graphOf() == this)
988 OGDF_ASSERT(w != 0 && w->graphOf() == this)
989 adjEntry adj;
990 forall_adj(adj,v) {
991 if(adj->twinNode() == w) return adj->twin()->theEdge();
992 }
993 return 0;
994 }
995
996
997 void Graph::hideEdge(edge e)
998 {
999 OGDF_ASSERT(e != 0 && e->graphOf() == this)
1000 --m_nEdges;
1001
1002 node src = e->m_src, tgt = e->m_tgt;
1003
1004 src->m_adjEdges.delPure(e->m_adjSrc);
1005 src->m_outdeg--;
1006 tgt->m_adjEdges.delPure(e->m_adjTgt);
1007 tgt->m_indeg--;
1008
1009 m_edges.move(e, m_hiddenEdges);
1010 }
1011
1012
1013 void Graph::restoreEdge(edge e)
1014 {
1015 ++m_nEdges;
1016
1017 node v = e->m_src;
1018 v->m_adjEdges.pushBack(e->m_adjSrc);
1019 ++v->m_outdeg;
1020
1021 node w = e->m_tgt;
1022 w->m_adjEdges.pushBack(e->m_adjTgt);
1023 ++w->m_indeg;
1024
1025 m_hiddenEdges.move(e, m_edges);
1026 }
1027
1028
1029 void Graph::restoreAllEdges()
1030 {
1031 edge e, ePrev;
1032 for(e = m_hiddenEdges.rbegin(); e != 0; e = ePrev) {
1033 ePrev = e->pred();
1034 restoreEdge(e);
1035 }
1036 }
1037
1038
1039 int Graph::genus() const
1040 {
1041 if (m_nNodes == 0) return 0;
1042
1043 int nIsolated = 0;
1044 node v;
1045 forall_nodes(v,*this)
1046 if (v->degree() == 0) ++nIsolated;
1047
1048 NodeArray<int> component(*this);
1049 int nCC = connectedComponents(*this,component);
1050
1051 AdjEntryArray<bool> visited(*this,false);
1052 int nFaceCycles = 0;
1053
1054 forall_nodes(v,*this) {
1055 adjEntry adj1;
1056 forall_adj(adj1,v) {
1057 if (visited[adj1]) continue;
1058
1059 adjEntry adj = adj1;
1060 do {
1061 visited[adj] = true;
1062 adj = adj->faceCycleSucc();
1063 } while (adj != adj1);
1064
1065 ++nFaceCycles;
1066 }
1067 }
1068
1069 return (m_nEdges - m_nNodes - nIsolated - nFaceCycles + 2*nCC) / 2;
1070 }
1071
1072
1073 ListIterator<NodeArrayBase*> Graph::registerArray(
1074 NodeArrayBase *pNodeArray) const
1075 {
1076 return m_regNodeArrays.pushBack(pNodeArray);
1077 }
1078
1079
1080 ListIterator<EdgeArrayBase*> Graph::registerArray(
1081 EdgeArrayBase *pEdgeArray) const
1082 {
1083 return m_regEdgeArrays.pushBack(pEdgeArray);
1084 }
1085
1086
1087 ListIterator<AdjEntryArrayBase*> Graph::registerArray(
1088 AdjEntryArrayBase *pAdjArray) const
1089 {
1090 return m_regAdjArrays.pushBack(pAdjArray);
1091 }
1092
1093 ListIterator<GraphObserver*> Graph::registerStructure(
1094 GraphObserver *pStructure) const
1095 {
1096 return m_regStructures.pushBack(pStructure);
1097 }//registerstructure
1098
1099
1100 void Graph::unregisterArray(ListIterator<NodeArrayBase*> it) const
1101 {
1102 m_regNodeArrays.del(it);
1103 }
1104
1105
1106 void Graph::unregisterArray(ListIterator<EdgeArrayBase*> it) const
1107 {
1108 m_regEdgeArrays.del(it);
1109 }
1110
1111
1112 void Graph::unregisterArray(ListIterator<AdjEntryArrayBase*> it) const
1113 {
1114 m_regAdjArrays.del(it);
1115 }
1116
1117 void Graph::unregisterStructure(ListIterator<GraphObserver*> it) const
1118 {
1119 m_regStructures.del(it);
1120 }
1121
1122 void Graph::reinitArrays()
1123 {
1124 ListIterator<NodeArrayBase*> itNode = m_regNodeArrays.begin();
1125 for(; itNode.valid(); ++itNode)
1126 (*itNode)->reinit(m_nodeArrayTableSize);
1127
1128 ListIterator<EdgeArrayBase*> itEdge = m_regEdgeArrays.begin();
1129 for(; itEdge.valid(); ++itEdge)
1130 (*itEdge)->reinit(m_edgeArrayTableSize);
1131
1132 ListIterator<AdjEntryArrayBase*> itAdj = m_regAdjArrays.begin();
1133 for(; itAdj.valid(); ++itAdj)
1134 (*itAdj)->reinit(m_edgeArrayTableSize << 1);
1135 }
1136
1137 void Graph::reinitStructures()
1138 {
1139 //is there a challenge?
1140 ListIterator<GraphObserver*> itGS = m_regStructures.begin();
1141 for (;itGS.valid(); ++itGS)
1142 (*itGS)->reInit();
1143 }
1144
1145
1146 void Graph::resetAdjEntryIndex(int newIndex, int oldIndex)
1147 {
1148 ListIterator<AdjEntryArrayBase*> itAdj = m_regAdjArrays.begin();
1149 for(; itAdj.valid(); ++itAdj)
1150 (*itAdj)->resetIndex(newIndex,oldIndex);
1151 }
1152
1153
1154 int Graph::nextPower2(int start, int idCount)
1155 {
1156 while (start <= idCount)
1157 start <<= 1;
1158
1159 return start;
1160 }
1161
1162
1163 bool Graph::readGML(const char *fileName)
1164 {
1165 ifstream is(fileName);
1166 return readGML(is);
1167 }
1168
1169
1170 bool Graph::readGML(istream &is)
1171 {
1172 GmlParser gml(is);
1173 if (gml.error()) return false;
1174 bool result = gml.read(*this);
1175
1176 OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
1177
1178 return result;
1179 }
1180
1181
1182 void Graph::writeGML(const char *fileName) const
1183 {
1184 ofstream os(fileName);
1185 writeGML(os);
1186 }
1187
1188
1189 void Graph::writeGML(ostream &os) const
1190 {
1191 NodeArray<int> id(*this);
1192 int nextId = 0;
1193
1194 os << "Creator \"ogdf::Graph::writeGML\"\n";
1195 os << "graph [\n";
1196 os << " directed 1\n";
1197
1198 node v;
1199 forall_nodes(v,*this) {
1200 os << " node [\n";
1201 os << " id " << (id[v] = nextId++) << "\n";
1202 os << " ]\n"; // node
1203 }
1204
1205 edge e;
1206 forall_edges(e,*this) {
1207 os << " edge [\n";
1208 os << " source " << id[e->source()] << "\n";
1209 os << " target " << id[e->target()] << "\n";
1210 os << " ]\n"; // edge
1211 }
1212
1213 os << "]\n"; // graph
1214 }
1215
1216
1217 // read graph in LEDA format from file fileName
1218 bool Graph::readLEDAGraph(const char *fileName)
1219 {
1220 ifstream is(fileName);
1221 return readLEDAGraph(is);
1222 }
1223
1224
1225 bool Graph::readToEndOfLine(istream &is)
1226 {
1227 int c;
1228 do {
1229 if (is.eof()) return false;
1230 c = is.get();
1231 } while(c != '\n');
1232 return true;
1233 }
1234
1235
1236 // read graph in LEDA format from input stream is
1237 bool Graph::readLEDAGraph(istream &is)
1238 {
1239 clear();
1240
1241 // the first three strings in the LEDA format describe the type of the
1242 // format, of nodes and of edges. We simply ignore the additional node/
1243 // edge attributes
1244 String formatType, nodeType, edgeType;
1245
1246 is >> formatType;
1247 is >> nodeType;
1248 is >> edgeType;
1249
1250 if (formatType != "LEDA.GRAPH")
1251 return false;
1252
1253
1254 // number of nodes
1255 int n;
1256 is >> n >> std::ws;
1257
1258 // create n nodes and ignore n lines
1259 Array<node> nodes(1,n);
1260 int i;
1261 for(i = 1; i <= n; ++i) {
1262 if (readToEndOfLine(is) == false)
1263 return false;
1264 nodes[i] = newNode();
1265 }
1266
1267 // number of edges
1268 int m;
1269 is >> m;
1270
1271 for(i = 1; i <= m; ++i) {
1272 // read index of source and target node
1273 int src, tgt;
1274 is >> src >> tgt;
1275
1276 // indices valid?
1277 if (src < 1 || n < src || tgt < 1 || n < tgt)
1278 return false;
1279
1280 newEdge(nodes[src],nodes[tgt]);
1281
1282 // ignore rest of line
1283 if (readToEndOfLine(is) == false)
1284 return false;
1285 }
1286
1287 OGDF_ASSERT_IF(dlConsistencyChecks, consistencyCheck());
1288
1289 return true;
1290 }
1291
1292
1293 bool Graph::consistencyCheck() const
1294 {
1295 int n = 0;
1296 node v;
1297 forall_nodes(v,*this) {
1298 #ifdef OGDF_DEBUG
1299 if (v->graphOf() != this)
1300 return false;
1301 #endif
1302
1303 n++;
1304 int in = 0, out = 0;
1305
1306 adjEntry adj;
1307 forall_adj(adj,v) {
1308 edge e = adj->m_edge;
1309 if (adj->m_twin->m_edge != e)
1310 return false;
1311
1312 if (e->m_adjSrc == adj)
1313 out++;
1314 else if (e->m_adjTgt == adj)
1315 in++;
1316 else
1317 return false;
1318
1319 if (adj->m_node != v)
1320 return false;
1321
1322 #ifdef OGDF_DEBUG
1323 if (adj->graphOf() != this)
1324 return false;
1325 #endif
1326 }
1327
1328 if (v->m_indeg != in)
1329 return false;
1330
1331 if (v->m_outdeg != out)
1332 return false;
1333 }
1334
1335 if (n != m_nNodes)
1336 return false;
1337
1338 int m = 0;
1339 edge e;
1340 forall_edges(e,*this) {
1341 #ifdef OGDF_DEBUG
1342 if (e->graphOf() != this)
1343 return false;
1344 #endif
1345
1346 m++;
1347 if (e->m_adjSrc == e->m_adjTgt)
1348 return false;
1349
1350 if (e->m_adjSrc->m_edge != e)
1351 return false;
1352
1353 if (e->m_adjTgt->m_edge != e)
1354 return false;
1355
1356 if (e->m_adjSrc->m_node != e->m_src)
1357 return false;
1358
1359 if (e->m_adjTgt->m_node != e->m_tgt)
1360 return false;
1361 }
1362
1363 if (m != m_nEdges)
1364 return false;
1365
1366 return true;
1367 }
1368
1369
1370 void Graph::resetEdgeIdCount(int maxId)
1371 {
1372 m_edgeIdCount = maxId+1;
1373
1374 #ifdef OGDF_DEBUG
1375 if (ogdf::debugLevel >= int(ogdf::dlConsistencyChecks)) {
1376 edge e;
1377 forall_edges(e,*this)
1378 {
1379 // if there is an edge with higer index than maxId, we cannot
1380 // set the edge id count to maxId+1
1381 if (e->index() > maxId)
1382 OGDF_ASSERT(false);
1383 }
1384 }
1385 #endif
1386 }
1387
1388
1389 node Graph::splitNode(adjEntry adjStartLeft, adjEntry adjStartRight)
1390 {
1391 OGDF_ASSERT(adjStartLeft != 0 && adjStartRight != 0);
1392 OGDF_ASSERT(adjStartLeft->graphOf() == this && adjStartRight->graphOf() == this);
1393 OGDF_ASSERT(adjStartLeft->theNode() == adjStartRight->theNode());
1394
1395 node w = newNode();
1396
1397 adjEntry adj, adjSucc;
1398 for(adj = adjStartRight; adj != adjStartLeft; adj = adjSucc) {
1399 adjSucc = adj->cyclicSucc();
1400 moveAdj(adj,w);
1401 }
1402
1403 newEdge(adjStartLeft, adjStartRight, ogdf::before);
1404
1405 return w;
1406 }
1407
1408
1409 node Graph::contract(edge e)
1410 {
1411 adjEntry adjSrc = e->adjSource();
1412 adjEntry adjTgt = e->adjTarget();
1413 node v = e->source();
1414 node w = e->target();
1415
1416 adjEntry adjNext;
1417 for(adjEntry adj = adjTgt->cyclicSucc(); adj != adjTgt; adj = adjNext)
1418 {
1419 adjNext = adj->cyclicSucc();
1420
1421 edge eAdj = adj->theEdge();
1422 if(w == eAdj->source())
1423 moveSource(eAdj, adjSrc, before);
1424 else
1425 moveTarget(eAdj, adjSrc, before);
1426 }
1427
1428 delNode(adjTgt->theNode());
1429
1430 return v;
1431 }
1432
1433
1434 void Graph::moveAdj(adjEntry adj, node w)
1435 {
1436 node v = adj->m_node;
1437
1438 v->m_adjEdges.move(adj,w->m_adjEdges);
1439 adj->m_node = w;
1440
1441 edge e = adj->m_edge;
1442 if(v == e->m_src) {
1443 --v->m_outdeg;
1444 e->m_src = w;
1445 ++w->m_outdeg;
1446 } else {
1447 --v->m_indeg;
1448 e->m_tgt = w;
1449 ++w->m_indeg;
1450 }
1451 }
1452
1453
1454 ostream &operator<<(ostream &os, ogdf::node v)
1455 {
1456 if (v) os << v->index(); else os << "nil";
1457 return os;
1458 }
1459
1460 ostream &operator<<(ostream &os, ogdf::edge e)
1461 {
1462 if (e) os << "(" << e->source() << "," << e->target() << ")";
1463 else os << "nil";
1464 return os;
1465 }
1466
1467 ostream &operator<<(ostream &os, ogdf::adjEntry adj)
1468 {
1469 if (adj) {
1470 ogdf::edge e = adj->theEdge();
1471 if (adj == e->adjSource())
1472 os << e->source() << "->" << e->target();
1473 else
1474 os << e->target() << "->" << e->source();
1475 } else os << "nil";
1476 return os;
1477 }
1478
1479
1480 } // end namespace ogdf
1481
Windows Explorer Extension to Operate Git