ext/OGDF/src/cluster/CconnectClusterPlanar.cpp

   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 Implementation of cluster planarity tests and cluster
  11  * planar embedding for c-connected clustered graphs. Based on
  12  * the algorithm by Cohen, Feng and Eades which uses PQ-trees.
  13  *
  14  * \author Sebastian Leipert
  15  *
  16  * \par License:
  17  * This file is part of the Open Graph Drawing Framework (OGDF).
  18  *
  19  * \par
  20  * Copyright (C)<br>
  21  * See README.txt in the root directory of the OGDF installation for details.
  22  *
  23  * \par
  24  * This program is free software; you can redistribute it and/or
  25  * modify it under the terms of the GNU General Public License
  26  * Version 2 or 3 as published by the Free Software Foundation;
  27  * see the file LICENSE.txt included in the packaging of this file
  28  * for details.
  29  *
  30  * \par
  31  * This program is distributed in the hope that it will be useful,
  32  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  33  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  34  * GNU General Public License for more details.
  35  *
  36  * \par
  37  * You should have received a copy of the GNU General Public
  38  * License along with this program; if not, write to the Free
  39  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  40  * Boston, MA 02110-1301, USA.
  41  *
  42  * \see  http://www.gnu.org/copyleft/gpl.html
  43  ***************************************************************/
  44
  45
  46 #include <ogdf/cluster/CconnectClusterPlanar.h>
  47 #include <ogdf/basic/simple_graph_alg.h>
  48 #include <ogdf/basic/extended_graph_alg.h>
  49
  50 namespace ogdf {
  51
  52 // Constructor
  53 CconnectClusterPlanar::CconnectClusterPlanar()
  54 {
  55         ogdf::strcpy(errorCode,124,"\0");
  56         m_errorCode = none;
  57 }
  58
  59 // Destructor
  60 CconnectClusterPlanar::~CconnectClusterPlanar()
  61 {
  62 }
  63
  64 // Tests if a ClusterGraph is C-planar
  65 // Specifies reason for non planarity
  66 bool CconnectClusterPlanar::call(ClusterGraph &C, char (&code)[124])
  67 {
  68         bool cPlanar =  call(C);
  69         strcpy(code,124,errorCode);
  70         return cPlanar;
  71 }
  72
  73 // Tests if a ClusterGraph is C-planar
  74 bool CconnectClusterPlanar::call(ClusterGraph &C)
  75 {
  76         Graph G;
  77         ClusterGraph Cp(C,G);
  78         OGDF_ASSERT(Cp.consistencyCheck());
  79
  80
  81         m_clusterPQTree.init(Cp,0);
  82
  83         bool cPlanar = preProcess(Cp,G);
  84
  85         m_parallelEdges.init();
  86         m_isParallel.init();
  87         m_clusterPQTree.init();
  88
  89         return cPlanar;
  90 }
  91
  92
  93
  94 // Tests if a ClusterGraph is C-planar
  95 bool CconnectClusterPlanar::call(const ClusterGraph &C)
  96 {
  97         Graph G;
  98         ClusterGraph Cp(C,G);
  99         OGDF_ASSERT(Cp.consistencyCheck());
 100         OGDF_ASSERT(&G == &(Graph&) Cp);
 101
 102         m_clusterPQTree.init(Cp,0);
 103
 104
 105         bool cPlanar = preProcess(Cp,G);
 106
 107         m_parallelEdges.init();
 108         m_isParallel.init();
 109         m_clusterPQTree.init();
 110
 111         return cPlanar;
 112 }
 113
 114
 115
 116 //
 117 //      CallTree:
 118 //
 119 //  call(ClusterGraph &C)
 120 //
 121 //              preProcess(ClusterGraph &C,Graph &G)
 122 //
 123 //                      planarityTest(ClusterGraph &C,cluster &act,Graph &G)
 124 //
 125 //                              foreach ChildCluster
 126 //                                      planarityTest(ClusterGraph &C,cluster &act,Graph &G)
 127 //
 128 //                              preparation(Graph  &G,cluster &cl)
 129 //
 130 //                                      foreach biconnected Component
 131 //                                              doTest(Graph &G,NodeArray<int> &numbering,cluster &cl)
 132 //
 133
 134
 135
 136
 137
 138
 139 bool CconnectClusterPlanar::preProcess(ClusterGraph &C,Graph &G)
 140 {
 141         if (!isCConnected(C))
 142         {
 143                 ogdf::sprintf(errorCode,124,"Graph is not C-connected \n");
 144                 m_errorCode = nonCConnected;
 145                 return false;
 146         }
 147
 148         if (!isPlanar(C))
 149         {
 150                 ogdf::sprintf(errorCode,124,"Graph is not planar\n");
 151                 m_errorCode = nonPlanar;
 152                 return false;
 153         }
 154
 155         cluster c;
 156
 157         SListPure<node> selfLoops;
 158         makeLoopFree(G,selfLoops);
 159
 160         c = C.rootCluster();
 161
 162         bool cPlanar = planarityTest(C,c,G);
 163
 164         return cPlanar;
 165 }
 166
 167
 168
 169 // Recursive call for testing c-planarity of the clustered graph
 170 // that is induced by cluster act
 171 bool CconnectClusterPlanar::planarityTest(
 172         ClusterGraph &C,
 173         cluster &act,
 174         Graph &G)
 175 {
 176         // Test children first
 177         ListConstIterator<cluster> it;
 178         for (it = act->cBegin(); it.valid();)
 179         {
 180                 ListConstIterator<cluster> succ = it.succ();
 181                 cluster next = (*it);
 182                 if (!planarityTest(C,next,G))
 183                         return false;
 184                 it = succ;
 185         }
 186
 187         // Get induced subgraph of cluster act and test it for planarity
 188
 189         List<node> subGraphNodes;
 190         ListIterator<node> its;
 191         for (its = act->nBegin(); its.valid(); its++)
 192                 subGraphNodes.pushBack(*its);
 193
 194         Graph subGraph;
 195         NodeArray<node> table;
 196         inducedSubGraph(G,subGraphNodes.begin(),subGraph,table);
 197
 198
 199         // Introduce super sink and add edges corresponding
 200         // to outgoing edges of the cluster
 201
 202         node superSink = subGraph.newNode();
 203         EdgeArray<node> outgoingTable(subGraph,0);
 204
 205
 206
 207         for (its = act->nBegin(); its.valid(); its++)
 208         {
 209                 node w = (*its);
 210                 adjEntry adj = w->firstAdj();
 211                 forall_adj(adj,w)
 212                 {
 213                         edge e = adj->theEdge();
 214                         edge cor = 0;
 215                         if (table[e->source()] == 0) // edge is connected to a node outside the cluster
 216                         {
 217                                 cor = subGraph.newEdge(table[e->target()],superSink);
 218                                 outgoingTable[cor] = e->source();
 219                         }
 220                         else if (table[e->target()] == 0) // dito
 221                         {
 222                                 cor = subGraph.newEdge(table[e->source()],superSink);
 223                                 outgoingTable[cor] = e->target();
 224                         }
 225
 226                         // else edge connects two nodes of the cluster
 227                 }
 228         }
 229         if (superSink->degree() == 0) // root cluster is not connected to outside clusters
 230         {
 231                 subGraph.delNode(superSink);
 232                 superSink = 0;
 233         }
 234
 235
 236         bool cPlanar = preparation(subGraph,act,superSink);
 237
 238
 239         if (cPlanar && act != C.rootCluster())
 240         {
 241                 // Remove induced subgraph and the cluster act.
 242                 // Replace it by a wheel graph
 243                 while (!subGraphNodes.empty())
 244                 {
 245                         node w = subGraphNodes.popFrontRet();
 246 //                      C.unassignNode(w);
 247                         G.delNode(w);
 248                 }
 249
 250                 cluster parent = act->parent();
 251
 252                 if (superSink && m_clusterPQTree[act])
 253                         constructWheelGraph(C,G,parent,m_clusterPQTree[act],outgoingTable);
 254
 255                 C.delCluster(act);
 256                 if (m_clusterPQTree[act] != 0) // if query necessary for clusters with just one child
 257                 {
 258                         m_clusterPQTree[act]->emptyAllPertinentNodes();
 259                         delete m_clusterPQTree[act];
 260                 }
 261
 262         }
 263         else if (!cPlanar)
 264                 {
 265                         ogdf::sprintf(errorCode,124,"Graph is not planar at cluster %d.\n",act->index());
 266                         m_errorCode = nonCPlanar;
 267                 }//if not cplanar
 268
 269         return cPlanar;
 270
 271 }
 272
 273
 274
 275
 276 void CconnectClusterPlanar::constructWheelGraph(ClusterGraph &C,
 277                                                                                                 Graph &G,
 278                                                                                                 cluster &parent,
 279                                                                                                 PlanarPQTree* T,
 280                                                                                                 EdgeArray<node> &outgoingTable)
 281 {
 282
 283         const PQNode<edge,IndInfo*,bool>* root = T->root();
 284         const PQNode<edge,IndInfo*,bool>*  checkNode = 0;
 285
 286         Queue<const PQNode<edge,IndInfo*,bool>*> treeNodes;
 287         treeNodes.append(root);
 288
 289         node correspond = G.newNode(); // Corresponds to the root node.
 290                                                                    // root node is either a leaf or a P-node
 291         C.reassignNode(correspond,parent);
 292
 293         Queue<node> graphNodes;
 294         graphNodes.append(correspond);
 295
 296         node hub;
 297         node next = 0;
 298         node pre;
 299         node newNode; // corresponds to anchor of a hub or a cut node
 300
 301
 302
 303         while (!treeNodes.empty())
 304         {
 305                 checkNode = treeNodes.pop();
 306                 correspond = graphNodes.pop();
 307
 308                 PQNode<edge,IndInfo*,bool>*  firstSon  = 0;
 309                 PQNode<edge,IndInfo*,bool>*  nextSon   = 0;
 310                 PQNode<edge,IndInfo*,bool>*  oldSib    = 0;
 311                 PQNode<edge,IndInfo*,bool>*  holdSib   = 0;
 312
 313
 314                 if (checkNode->type() == PQNodeRoot::PNode)
 315                 {
 316                         // correspond is a cut node
 317
 318                         OGDF_ASSERT(checkNode->referenceChild())
 319                         firstSon = checkNode->referenceChild();
 320
 321                         if (firstSon->type() != PQNodeRoot::leaf)
 322                         {
 323                                 treeNodes.append(firstSon);
 324                                 newNode = G.newNode();
 325                                 C.reassignNode(newNode,parent);
 326                                 graphNodes.append(newNode);
 327                                 G.newEdge(correspond,newNode);
 328                         }
 329                         else
 330                         {
 331                                 // insert Edge to the outside
 332                                 PQLeaf<edge,IndInfo*,bool>* leaf =
 333                                         (PQLeaf<edge,IndInfo*,bool>*) firstSon;
 334                                 edge f = leaf->getKey()->m_userStructKey;
 335                                 //node x = outgoingTable[f];
 336                                 G.newEdge(correspond,outgoingTable[f]);
 337                                 delete leaf->getKey();
 338                         }
 339
 340                         nextSon = firstSon->getNextSib(oldSib);
 341                         oldSib = firstSon;
 342                         pre = next;
 343                         while (nextSon && nextSon != firstSon)
 344                         {
 345                                 if (nextSon->type() != PQNodeRoot::leaf)
 346                                 {
 347                                         treeNodes.append(nextSon);
 348                                         newNode = G.newNode();  // new node corresponding to anchor
 349                                                                                         // or cutnode
 350                                         C.reassignNode(newNode,parent);
 351                                         graphNodes.append(newNode);
 352                                         G.newEdge(correspond,newNode);
 353                                 }
 354                                 else
 355                                 {
 356                                         // insert Edge to the outside
 357                                         PQLeaf<edge,IndInfo*,bool>* leaf =
 358                                                 (PQLeaf<edge,IndInfo*,bool>*) nextSon;
 359                                         edge f = leaf->getKey()->m_userStructKey;
 360                                         //node x = outgoingTable[f];
 361                                         G.newEdge(correspond,outgoingTable[f]);
 362                                         delete leaf->getKey();
 363                                 }
 364                                 holdSib = nextSon->getNextSib(oldSib);
 365                                 oldSib = nextSon;
 366                                 nextSon = holdSib;
 367                         }
 368
 369                 }
 370                 else if (checkNode->type() == PQNodeRoot::QNode)
 371                 {
 372                         // correspond is the anchor of a hub
 373                         OGDF_ASSERT(checkNode->getEndmost(PQNodeRoot::LEFT))
 374                         firstSon = checkNode->getEndmost(PQNodeRoot::LEFT);
 375
 376                         hub = G.newNode();
 377                         C.reassignNode(hub,parent);
 378                         G.newEdge(hub,correspond); // link anchor and hub
 379                         next = G.newNode();   // for first son
 380                         C.reassignNode(next,parent);
 381                         G.newEdge(hub,next);
 382                         G.newEdge(correspond,next);
 383
 384                         if (firstSon->type() != PQNodeRoot::leaf)
 385                         {
 386                                 treeNodes.append(firstSon);
 387                                 newNode = G.newNode();
 388                                 C.reassignNode(newNode,parent);
 389                                 graphNodes.append(newNode);
 390                                 G.newEdge(next,newNode);
 391                         }
 392                         else
 393                         {
 394                                 // insert Edge to the outside
 395                                 PQLeaf<edge,IndInfo*,bool>* leaf =
 396                                         (PQLeaf<edge,IndInfo*,bool>*) firstSon;
 397                                 edge f = leaf->getKey()->m_userStructKey;
 398                                 //node x = outgoingTable[f];
 399                                 G.newEdge(next,outgoingTable[f]);
 400                                 delete leaf->getKey();
 401                         }
 402
 403                         nextSon = firstSon->getNextSib(oldSib);
 404                         oldSib = firstSon;
 405                         pre = next;
 406                         while (nextSon)
 407                         {
 408                                 next = G.newNode();
 409                                 C.reassignNode(next,parent);
 410                                 G.newEdge(hub,next);
 411                                 G.newEdge(pre,next);
 412                                 if (nextSon->type() != PQNodeRoot::leaf)
 413                                 {
 414                                         treeNodes.append(nextSon);
 415                                         newNode = G.newNode();  // new node corresponding to anchor
 416                                                                                         // or cutnode
 417                                         C.reassignNode(newNode,parent);
 418                                         graphNodes.append(newNode);
 419
 420                                         G.newEdge(next,newNode);
 421                                 }
 422                                 else
 423                                 {
 424                                         // insert Edge to the outside
 425                                         PQLeaf<edge,IndInfo*,bool>* leaf =
 426                                                 (PQLeaf<edge,IndInfo*,bool>*) nextSon;
 427                                         edge f = leaf->getKey()->m_userStructKey;
 428                                         G.newEdge(next,outgoingTable[f]);
 429                                         delete leaf->getKey();
 430                                 }
 431                                 holdSib = nextSon->getNextSib(oldSib);
 432                                 oldSib = nextSon;
 433                                 nextSon = holdSib;
 434                                 pre = next;
 435
 436                         }
 437                         G.newEdge(next,correspond);
 438                 }
 439         }
 440
 441         OGDF_ASSERT(C.consistencyCheck());
 442 }
 443
 444
 445
 446
 447
 448 //
 449 // Prepare planarity test for one cluster
 450 //
 451 bool CconnectClusterPlanar::preparation(Graph  &G,
 452                                                                                 cluster &cl,
 453                                                                                 node superSink)
 454 {
 455
 456         node v;
 457         edge e;
 458         int  bcIdSuperSink = -1; // ID of biconnected component that contains superSink
 459                                                          // Initialization with -1 necessary for assertion
 460         bool cPlanar = true;
 461
 462
 463         NodeArray<node> tableNodes(G,0);
 464         EdgeArray<edge> tableEdges(G,0);
 465         NodeArray<bool> mark(G,0);
 466
 467         EdgeArray<int> componentID(G);
 468
 469
 470         // Determine Biconnected Components
 471         int bcCount = biconnectedComponents(G,componentID);
 472
 473         // Determine edges per biconnected component
 474         Array<SList<edge> > blockEdges(0,bcCount-1);
 475         forall_edges(e,G)
 476         {
 477                 blockEdges[componentID[e]].pushFront(e);
 478         }
 479
 480         // Determine nodes per biconnected component.
 481         Array<SList<node> > blockNodes(0,bcCount-1);
 482         for (int i = 0; i < bcCount; i++)
 483         {
 484                 SListIterator<edge> it;
 485                 for (it = blockEdges[i].begin(); it.valid(); ++it)
 486                 {
 487                         e = *it;
 488                         if (!mark[e->source()])
 489                         {
 490                                 blockNodes[i].pushBack(e->source());
 491                                 mark[e->source()] = true;
 492                         }
 493                         if (!mark[e->target()])
 494                         {
 495                                 blockNodes[i].pushBack(e->target());
 496                                 mark[e->target()] = true;
 497                         }
 498                 }
 499                 if (superSink && mark[superSink])
 500                 {
 501                         OGDF_ASSERT(bcIdSuperSink == -1);
 502                         bcIdSuperSink = i;
 503                 }
 504                 SListIterator<node> itn;
 505                 for (itn = blockNodes[i].begin(); itn.valid(); ++itn)
 506                 {
 507                         v = *itn;
 508                         if (mark[v])
 509                                 mark[v] = false;
 510                         else
 511                         {
 512                                 OGDF_ASSERT(mark[v]); // v has been placed two times on the list.
 513                         }
 514                 }
 515
 516         }
 517
 518
 519         // Perform planarity test for every biconnected component
 520
 521         if (bcCount == 1)
 522         {
 523                 // Compute st-numbering
 524                 NodeArray<int> numbering(G,0);
 525                 int n;
 526                 if (superSink)
 527                         n = stNumber(G,numbering,0,superSink);
 528                 else
 529                         n = stNumber(G,numbering);
 530                 OGDF_ASSERT_IF(dlConsistencyChecks,testSTnumber(G,numbering,n))
 531
 532
 533                 EdgeArray<edge> backTableEdges(G,0);
 534                 forall_edges(e,G)
 535                         backTableEdges[e] = e;
 536
 537                 cPlanar = doTest(G,numbering,cl,superSink,backTableEdges);
 538         }
 539         else
 540         {
 541                 for (int i = 0; i < bcCount; i++)
 542                 {
 543                         #ifdef OGDF_DEBUG
 544                         if(int(ogdf::debugLevel)>=int(dlHeavyChecks)){
 545                                 cout<<endl<<endl<<"-----------------------------------";
 546                                 cout<<endl<<endl<<"Component "<<i<<endl;}
 547                         #endif
 548
 549                         Graph C;
 550
 551                         SListIterator<node> itn;
 552                         for (itn = blockNodes[i].begin(); itn.valid(); ++ itn)
 553                         {
 554                                 v = *itn;
 555                                 node w = C.newNode();
 556                                 tableNodes[v] = w;
 557
 558                                 #ifdef OGDF_DEBUG
 559                                 if(int(ogdf::debugLevel)>=int(dlHeavyChecks)){
 560                                         cout <<"Original: " << v << " New: " << w<< endl;}
 561                                 #endif
 562
 563                         }
 564
 565                         NodeArray<node> backTableNodes(C,0);
 566
 567                         SListIterator<edge> it;
 568                         for (it = blockEdges[i].begin(); it.valid(); ++it)
 569                         {
 570                                 e = *it;
 571                                 edge f = C.newEdge(tableNodes[e->source()],tableNodes[e->target()]);
 572                                 tableEdges[e] = f;
 573                         }
 574
 575                         EdgeArray<edge> backTableEdges(C,0);
 576                         for (it = blockEdges[i].begin(); it.valid(); ++it)
 577                                 backTableEdges[tableEdges[*it]] = *it;
 578
 579                         // Compute st-numbering
 580                         NodeArray<int> numbering(C,0);
 581                         int n;
 582                         if (bcIdSuperSink == i)
 583                         {
 584                                 n = stNumber(C,numbering,0,tableNodes[superSink]);
 585                                 OGDF_ASSERT_IF(dlConsistencyChecks,testSTnumber(C,numbering,n))
 586                                 cPlanar = doTest(C,numbering,cl,tableNodes[superSink],backTableEdges);
 587                         }
 588                         else
 589                         {
 590                                 n = stNumber(C,numbering);
 591                                 OGDF_ASSERT_IF(dlConsistencyChecks,testSTnumber(C,numbering,n))
 592                                 cPlanar = doTest(C,numbering,cl,0,backTableEdges);
 593                         }
 594
 595                         if (!cPlanar)
 596                                 break;
 597
 598
 599
 600                 }
 601
 602         }
 603
 604         return cPlanar;
 605 }
 606
 607
 608 // Performs a planarity test on a biconnected component
 609 // of G. numbering contains an st-numbering of the component.
 610 bool CconnectClusterPlanar::doTest(
 611         Graph &G,
 612         NodeArray<int> &numbering,
 613         cluster &cl,
 614         node superSink,
 615         EdgeArray<edge> &edgeTable)
 616 {
 617         node v;
 618         bool cPlanar = true;
 619
 620         NodeArray<SListPure<PlanarLeafKey<IndInfo*>* > > inLeaves(G);
 621         NodeArray<SListPure<PlanarLeafKey<IndInfo*>* > > outLeaves(G);
 622         Array<node> table(G.numberOfNodes()+1);
 623
 624         forall_nodes(v,G)
 625         {
 626                 edge e;
 627                 forall_adj_edges(e,v)
 628                 {
 629                         if (numbering[e->opposite(v)] > numbering[v])
 630                                 //sideeffect: loops are ignored
 631                         {
 632                                 PlanarLeafKey<IndInfo*>* L = OGDF_NEW PlanarLeafKey<IndInfo*>(e);
 633                                 inLeaves[v].pushFront(L);
 634                         }
 635                 }
 636                 table[numbering[v]] = v;
 637         }
 638
 639         forall_nodes(v,G)
 640         {
 641                 SListIterator<PlanarLeafKey<IndInfo*>* > it;
 642                 for (it = inLeaves[v].begin(); it.valid(); ++it)
 643                 {
 644                         PlanarLeafKey<IndInfo*>* L = *it;
 645                         outLeaves[L->userStructKey()->opposite(v)].pushFront(L);
 646                 }
 647         }
 648
 649         PlanarPQTree* T = new PlanarPQTree();
 650
 651         T->Initialize(inLeaves[table[1]]);
 652         for (int i = 2; i < G.numberOfNodes(); i++)
 653         {
 654                 if (T->Reduction(outLeaves[table[i]]))
 655                 {
 656                         T->ReplaceRoot(inLeaves[table[i]]);
 657                         T->emptyAllPertinentNodes();
 658
 659                 }
 660                 else
 661                 {
 662                         cPlanar = false;
 663                         break;
 664                 }
 665         }
 666         if (cPlanar && cl && superSink)
 667         {
 668                 // Keep the PQTree to construct a wheelgraph
 669                 // Replace the edge stored in the keys of T
 670                 // by the original edges.
 671                 // Necessary, since the edges currently in T
 672                 // correspond to a graph that mirrors a biconnected
 673                 // component and thus is deallocated
 674
 675                 SListIterator<PlanarLeafKey<IndInfo*>* >  it;
 676                 int n = G.numberOfNodes();
 677
 678                 for (it = outLeaves[table[n]].begin(); it.valid(); ++it)
 679                 {
 680                         PQLeafKey<edge,IndInfo*,bool>* key = (PQLeafKey<edge,IndInfo*,bool>*) *it;
 681                         key->m_userStructKey = edgeTable[key->m_userStructKey];
 682                 }
 683
 684                 m_clusterPQTree[cl] = T;
 685
 686         }
 687         else //if (cPlanar)
 688                 delete T;
 689
 690         // Cleanup
 691         forall_nodes(v,G)
 692         {
 693                 if (v != superSink || !cPlanar)
 694                 {
 695                         while (!outLeaves[v].empty())
 696                         {
 697                                 PlanarLeafKey<IndInfo*>* L = outLeaves[v].popFrontRet();
 698                                 delete L;
 699                         }
 700                 }
 701         }
 702
 703         return cPlanar;
 704 }
 705
 706
 707
 708 void CconnectClusterPlanar::prepareParallelEdges(Graph &G)
 709 {
 710
 711         edge e;
 712
 713         // Stores for one reference edge all parallel edges.
 714         m_parallelEdges.init(G);
 715         // Is true for any multiedge, except for the reference edge.
 716         m_isParallel.init(G,false);
 717         getParallelFreeUndirected(G,m_parallelEdges);
 718         m_parallelCount = 0;
 719         forall_edges(e,G)
 720         {
 721                 if (!m_parallelEdges[e].empty())
 722                 {
 723                         ListIterator<edge> it;
 724                         for (it = m_parallelEdges[e].begin(); it.valid(); it++)
 725                         {
 726                                 m_isParallel[*it] = true;
 727                                 m_parallelCount++;
 728                         }
 729                 }
 730         }
 731 }
 732
 733
 734
 735
 736 } // end namespace ogdf
 737