ext/OGDF/src/upward/UpwardPlanRep.cpp

   1 /*
   2  * $Revision: 2559 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-06 15:04:28 +0200 (Fr, 06. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of PlanRep base class for planar rep.
  11  *
  12  * \author Hoi-Ming Wong
  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/simple_graph_alg.h>
  44 #include <ogdf/upward/UpwardPlanRep.h>
  45 #include <ogdf/upward/FaceSinkGraph.h>
  46 #include <ogdf/basic/FaceSet.h>
  47 #include <ogdf/basic/tuples.h>
  48
  49
  50
  51 namespace ogdf {
  52
  53
  54 UpwardPlanRep::UpwardPlanRep(const CombinatorialEmbedding &Gamma) :
  55         GraphCopy(Gamma.getGraph()),
  56         isAugmented(false),
  57         t_hat(0),
  58         extFaceHandle(0),
  59         crossings(0)
  60 {
  61         OGDF_ASSERT(Gamma.externalFace() != 0);
  62         OGDF_ASSERT(hasSingleSource(*this));
  63         OGDF_ASSERT(isSimple(*this));
  64
  65         m_isSourceArc.init(*this, false);
  66         m_isSinkArc.init(*this, false);
  67         hasSingleSource(*this, s_hat);
  68         m_Gamma.init(*this);
  69
  70         //compute the ext. face;
  71         adjEntry adj;
  72         node v = this->original(s_hat);
  73         adj = getAdjEntry(Gamma, v, Gamma.externalFace());
  74         adj = this->copy(adj->theEdge())->adjSource();
  75         m_Gamma.setExternalFace(m_Gamma.rightFace(adj));
  76
  77         //outputFaces(Gamma);
  78
  79         computeSinkSwitches();
  80 }
  81
  82
  83 UpwardPlanRep::UpwardPlanRep(const GraphCopy &GC, ogdf::adjEntry adj_ext) :
  84         GraphCopy(GC),
  85         isAugmented(false),
  86         t_hat(0),
  87         extFaceHandle(0),
  88         crossings(0)
  89 {
  90         OGDF_ASSERT(adj_ext != 0);
  91         OGDF_ASSERT(hasSingleSource(*this));
  92
  93         m_isSourceArc.init(*this, false);
  94         m_isSinkArc.init(*this, false);
  95         hasSingleSource(*this, s_hat);
  96         m_Gamma.init(*this);
  97
  98         //compute the ext. face;
  99         node v = copy(GC.original(adj_ext->theNode()));
 100         extFaceHandle = copy(GC.original(adj_ext->theEdge()))->adjSource();
 101         if (extFaceHandle->theNode() != v)
 102                 extFaceHandle = extFaceHandle->twin();
 103         m_Gamma.setExternalFace(m_Gamma.rightFace(extFaceHandle));
 104
 105         adjEntry adj;
 106         forall_adj(adj, s_hat)
 107                 m_isSourceArc[adj->theEdge()] = true;
 108
 109         computeSinkSwitches();
 110 }
 111
 112
 113 //copy constructor
 114 UpwardPlanRep::UpwardPlanRep(const UpwardPlanRep &UPR) :
 115         GraphCopy(),
 116         isAugmented(UPR.isAugmented),
 117         crossings(UPR.crossings)
 118 {
 119         copyMe(UPR);
 120 }
 121
 122
 123 void UpwardPlanRep::copyMe(const UpwardPlanRep &UPR)
 124 {
 125         NodeArray<node> vCopy;
 126         EdgeArray<edge> eCopy;
 127
 128         Graph::construct(UPR,vCopy,eCopy);
 129
 130         // initGC
 131         m_pGraph = UPR.m_pGraph;
 132
 133         m_vOrig.init(*this,0); m_eOrig.init(*this,0);
 134         m_vCopy.init(*m_pGraph,0); m_eCopy.init(*m_pGraph);
 135         m_eIterator.init(*this,0);
 136
 137         node v, w;
 138         forall_nodes(v,UPR)
 139                 m_vOrig[vCopy[v]] = UPR.m_vOrig[v];
 140
 141         edge e;
 142         forall_edges(e,UPR)
 143                 m_eOrig[eCopy[e]] = UPR.m_eOrig[e];
 144
 145         forall_nodes(v,*this)
 146                 if ((w = m_vOrig[v]) != 0) m_vCopy[w] = v;
 147
 148         forall_edges(e,*m_pGraph) {
 149                 ListConstIterator<edge> it;
 150                 for (it = UPR.m_eCopy[e].begin(); it.valid(); ++it)
 151                         m_eIterator[eCopy[*it]] = m_eCopy[e].pushBack(eCopy[*it]);
 152         }
 153
 154         //GraphCopy::initGC(UPR,vCopy,eCopy);
 155         m_Gamma.init(*this);
 156         m_isSinkArc.init(*this, false);
 157         m_isSourceArc.init(*this, false);
 158
 159         if (UPR.numberOfNodes() == 0)
 160                 return;
 161
 162         s_hat = vCopy[UPR.getSuperSource()];
 163         if (UPR.augmented())
 164                 t_hat = vCopy[UPR.getSuperSink()];
 165
 166         OGDF_ASSERT(UPR.extFaceHandle != 0);
 167
 168         e = eCopy[UPR.extFaceHandle->theEdge()];
 169         v = vCopy[UPR.extFaceHandle->theNode()];
 170         if (e->adjSource()->theNode() == v)
 171                 extFaceHandle = e->adjSource();
 172         else
 173                 extFaceHandle = e->adjTarget();
 174
 175         m_Gamma.setExternalFace(m_Gamma.rightFace(extFaceHandle));
 176
 177         forall_edges(e, UPR) {
 178                 edge a = eCopy[e];
 179                 if (UPR.isSinkArc(e))
 180                         m_isSinkArc[a] = true;
 181                 if (UPR.isSourceArc(e))
 182                         m_isSourceArc[a] = true;
 183         }
 184
 185         computeSinkSwitches();
 186 }
 187
 188
 189
 190 UpwardPlanRep & UpwardPlanRep::operator =(const UpwardPlanRep &cp)
 191 {
 192         clear();
 193         createEmpty(cp.original());
 194         isAugmented = cp.isAugmented;
 195         extFaceHandle = 0;
 196         crossings = cp.crossings;
 197         copyMe(cp);
 198         return *this;
 199 }
 200
 201
 202 void UpwardPlanRep::augment()
 203 {
 204         if (isAugmented)
 205                 return;
 206
 207         OGDF_ASSERT(hasSingleSource(*this));
 208
 209         List< Tuple2<adjEntry, adjEntry> > l;
 210         List<adjEntry> switches;
 211
 212         hasSingleSource(*this, s_hat);
 213
 214         adjEntry adj;
 215         forall_adj(adj, s_hat)
 216                 m_isSourceArc[adj->theEdge()] = true;
 217
 218         FaceSinkGraph fsg(m_Gamma, s_hat);
 219         List<adjEntry> dummyList;
 220         FaceArray< List<adjEntry> > sinkSwitches(m_Gamma, dummyList);
 221         fsg.sinkSwitches(sinkSwitches);
 222         m_sinkSwitchOf.init(*this, 0);
 223
 224         face f;
 225         forall_faces(f, m_Gamma) {
 226                 adjEntry adj_top;
 227                 switches = sinkSwitches[f];
 228                 if (switches.empty() || f == m_Gamma.externalFace())
 229                         continue;
 230                 else
 231                         adj_top = switches.popFrontRet(); // first switch in the list is a top sink switch
 232
 233                 while (!switches.empty()) {
 234                         adjEntry adj = switches.popFrontRet();
 235                         Tuple2<adjEntry, adjEntry> pair(adj, adj_top);
 236                         l.pushBack(pair);
 237                 }
 238         }
 239         // construct sink arcs
 240         // for the ext. face
 241         extFaceHandle = getAdjEntry(m_Gamma, s_hat, m_Gamma.externalFace());
 242         node t = this->newNode();
 243         switches = sinkSwitches[m_Gamma.externalFace()];
 244
 245         OGDF_ASSERT(!switches.empty());
 246
 247         while (!switches.empty()) {
 248                 adjEntry adj = switches.popFrontRet();
 249                 edge e_new;
 250                 if (t->degree() == 0) {
 251                         e_new = m_Gamma.splitFace(adj, t);
 252                 }
 253                 else {
 254                         adjEntry adjTgt = getAdjEntry(m_Gamma, t, m_Gamma.rightFace(adj));
 255                         e_new = m_Gamma.splitFace(adj, adjTgt);
 256                 }
 257                 m_isSinkArc[e_new] = true;
 258                 m_Gamma.setExternalFace(m_Gamma.rightFace(extFaceHandle));
 259         }
 260
 261         /*
 262         * set ext. face handle
 263         * we add a additional node t_hat and an addtional edge e=(t, t_hat)
 264         * e will never been crossed. we use e as the ext. face handle
 265         */
 266         t_hat = this->newNode();
 267         adjEntry adjSource = getAdjEntry(m_Gamma, t, m_Gamma.externalFace());
 268         extFaceHandle = m_Gamma.splitFace(adjSource, t_hat)->adjTarget();
 269         m_isSinkArc[extFaceHandle->theEdge()] = true; // not really a sink arc !! TODO??
 270
 271         m_Gamma.setExternalFace(m_Gamma.rightFace(extFaceHandle));
 272
 273         //for int. faces
 274         while (!l.empty()) {
 275                 Tuple2<adjEntry, adjEntry> pair = l.popFrontRet();
 276
 277
 278                 edge e_new;
 279                 if (pair.x2()->theNode()->degree() == 0 ) {
 280                         e_new = m_Gamma.splitFace(pair.x1(), pair.x2()->theNode());
 281                 }
 282                 else {
 283                         adjEntry adjTgt = getAdjEntry(m_Gamma, pair.x2()->theNode(), m_Gamma.rightFace(pair.x1()));
 284                         e_new = m_Gamma.splitFace(pair.x1(), adjTgt);
 285                 }
 286                 m_isSinkArc[e_new] = true;
 287         }
 288
 289         isAugmented = true;
 290
 291         OGDF_ASSERT(isSimple(*this));
 292
 293         computeSinkSwitches();
 294 }
 295
 296
 297 void UpwardPlanRep::removeSinkArcs(SList<adjEntry> &crossedEdges) {
 298
 299         if (crossedEdges.size() == 2)
 300                 return;
 301
 302
 303         SListIterator<adjEntry> itPred = crossedEdges.begin(), itLast = crossedEdges.rbegin(), it;
 304         for(it = itPred.succ(); it != itLast; ++it)     {
 305                 adjEntry adj = *it;
 306                 if (m_isSinkArc[adj->theEdge()]) {
 307                         m_Gamma.joinFaces(adj->theEdge());
 308                         crossedEdges.delSucc(itPred);
 309                         it = itPred;
 310                         continue;
 311                 }
 312                 itPred = it;
 313         }
 314         m_Gamma.setExternalFace(m_Gamma.rightFace(extFaceHandle));
 315 }
 316
 317
 318 void UpwardPlanRep::insertEdgePathEmbedded(edge eOrig, SList<adjEntry> crossedEdges, EdgeArray<int> &costOrig)
 319 {
 320         removeSinkArcs(crossedEdges);
 321
 322         //case the copy v of eOrig->source() is a sink switch
 323         //we muss remove the sink arcs incident to v, since after inserting eOrig, v is not a sink witch
 324         node v =  crossedEdges.front()->theNode();
 325         List<edge> outEdges;
 326         if (v->outdeg() == 1)
 327                 this->outEdges(v, outEdges); // we delete this edges later
 328
 329         m_eCopy[eOrig].clear();
 330
 331         adjEntry adjSrc, adjTgt;
 332         SListConstIterator<adjEntry> it = crossedEdges.begin();
 333         SListConstIterator<adjEntry> itLast = crossedEdges.rbegin();
 334
 335         // iterate over all adjacency entries in crossedEdges except for first
 336         // and last
 337         adjSrc = *it;
 338         List<adjEntry> dirtyList; // left and right face of the element of this list are modified
 339         for(++it; it != itLast; ++it)
 340         {
 341                 adjEntry adj = *it;
 342
 343                 bool isASourceArc = false, isASinkArc = false;
 344                 if (m_isSinkArc[adj->theEdge()])
 345                         isASinkArc = true;
 346                 if (m_isSourceArc[adj->theEdge()])
 347                         isASourceArc = true;
 348
 349                 int c = 0;
 350                 if (original(adj->theEdge()) != 0)
 351                         c = costOrig[original(adj->theEdge())];
 352
 353                 // split edge
 354                 node u = m_Gamma.split(adj->theEdge())->source();
 355                 if (!m_isSinkArc[adj->theEdge()] && !m_isSourceArc[adj->theEdge()])
 356                         crossings = crossings + c; // crossing sink/source arcs cost nothing
 357
 358                 // determine target adjacency entry and source adjacency entry
 359                 // in the next iteration step
 360                 adjTgt = u->firstAdj();
 361                 adjEntry adjSrcNext = adjTgt->succ();
 362
 363                 if (adjTgt != adj->twin())
 364                         swap(adjTgt,adjSrcNext);
 365
 366
 367                 edge e_split = adjTgt->theEdge(); // the new split edge
 368                 if (e_split->source() != u)
 369                         e_split = adjSrcNext->theEdge();
 370
 371                 if (isASinkArc)
 372                         m_isSinkArc[e_split] = true;
 373                 if (isASourceArc)
 374                         m_isSourceArc[e_split] = true;
 375
 376                 // insert a new edge into the face
 377                 edge eNew = m_Gamma.splitFace(adjSrc,adjTgt);
 378                 m_eIterator[eNew] = GraphCopy::m_eCopy[eOrig].pushBack(eNew);
 379                 m_eOrig[eNew] = eOrig;
 380                 dirtyList.pushBack(eNew->adjSource());
 381
 382                 adjSrc = adjSrcNext;
 383         }
 384
 385         // insert last edge
 386         edge eNew = m_Gamma.splitFace(adjSrc,*it);
 387         m_eIterator[eNew] = m_eCopy[eOrig].pushBack(eNew);
 388         m_eOrig[eNew] = eOrig;
 389         dirtyList.pushBack(eNew->adjSource());
 390
 391         // remove the sink arc incident to v
 392         if(!outEdges.empty()) {
 393                 edge e = outEdges.popFrontRet();
 394                 if (m_isSinkArc[e])
 395                         m_Gamma.joinFaces(e);
 396         }
 397
 398         m_Gamma.setExternalFace(m_Gamma.rightFace(extFaceHandle));
 399
 400         //computeSinkSwitches();
 401         FaceSinkGraph fsg(m_Gamma, s_hat);
 402         List<adjEntry> dummyList;
 403         FaceArray< List<adjEntry> > sinkSwitches(m_Gamma, dummyList);
 404         fsg.sinkSwitches(sinkSwitches);
 405
 406         //construct sinkArc for the dirty faces
 407         List< Tuple2<adjEntry, adjEntry> > l;
 408         forall_listiterators(adjEntry, it, dirtyList) {
 409                 face fLeft = m_Gamma.leftFace(*it);
 410                 face fRight = m_Gamma.rightFace(*it);
 411                 List<adjEntry> switches = sinkSwitches[fLeft];
 412
 413                 OGDF_ASSERT(!switches.empty());
 414
 415                 constructSinkArcs(fLeft, switches.front()->theNode());
 416
 417                 OGDF_ASSERT(!switches.empty());
 418
 419                 switches = sinkSwitches[fRight];
 420                 constructSinkArcs(fRight, switches.front()->theNode());
 421         }
 422
 423         m_Gamma.setExternalFace(m_Gamma.rightFace(extFaceHandle));
 424         computeSinkSwitches();
 425 }
 426
 427
 428
 429 void UpwardPlanRep::constructSinkArcs(face f, node t)
 430 {
 431         List<adjEntry> srcList;
 432         adjEntry adjTgt;
 433
 434         if (f != m_Gamma.externalFace()) {
 435                 adjEntry adj;
 436                 forall_face_adj(adj, f) {
 437                         node v = adj->theNode();
 438                         if (v == adj->theEdge()->target() && adj->faceCyclePred()->theEdge()->target() == v) {
 439                                 if (v != t)
 440                                         srcList.pushBack(adj);
 441                                 else
 442                                         adjTgt = adj; // top-sink-switch of f
 443                         }
 444                 }
 445                 // contruct the sink arcs
 446                 while(!srcList.empty()) {
 447                         adjEntry adjSrc = srcList.popFrontRet();
 448                         edge eNew;
 449                         if (t->degree() == 0)
 450                                 eNew = m_Gamma.splitFace(adjSrc, t);
 451                         else {
 452                                 adjEntry adjTgt = getAdjEntry(m_Gamma, t, m_Gamma.rightFace(adjSrc));
 453                                 eNew = m_Gamma.splitFace(adjSrc, adjTgt);
 454                         }
 455                         m_isSinkArc[eNew] = true;
 456                 }
 457         }
 458         else {
 459                 adjEntry adj;
 460                 forall_face_adj(adj, f) {
 461                         node v = adj->theNode();
 462
 463                         OGDF_ASSERT(s_hat != 0);
 464
 465                         if (v->outdeg() == 0 && v != t_hat)
 466                                 srcList.pushBack(adj);
 467                 }
 468
 469                 // contruct the sink arcs
 470                 while(!srcList.empty()) {
 471                         adjEntry adjSrc = srcList.popFrontRet();
 472                         edge eNew;
 473                         if (adjSrc->theNode() == adjSrc->theEdge()->source()) // on the right face part of the ext. face
 474                                 adjTgt = extFaceHandle;
 475                         else
 476                                 adjTgt = extFaceHandle->cyclicPred(); // on the left face part
 477
 478                         eNew = m_Gamma.splitFace(adjSrc, adjTgt);
 479                         m_isSinkArc[eNew] = true;
 480                 }
 481
 482         }
 483 }
 484
 485
 486 void UpwardPlanRep::computeSinkSwitches()
 487 {
 488         OGDF_ASSERT(m_Gamma.externalFace() != 0);
 489
 490         if (s_hat == 0)
 491                 hasSingleSource(*this, s_hat);
 492         FaceSinkGraph fsg(m_Gamma, s_hat);
 493         List<adjEntry> dummyList;
 494         FaceArray< List<adjEntry> > sinkSwitches(m_Gamma, dummyList);
 495         fsg.sinkSwitches(sinkSwitches);
 496         m_sinkSwitchOf.init(*this, 0);
 497
 498         face f;
 499         forall_faces(f, m_Gamma) {
 500                 List<adjEntry> switches = sinkSwitches[f];
 501                 ListIterator<adjEntry> it = switches.begin();
 502                 for (it = it.succ(); it.valid(); it++) {
 503                         m_sinkSwitchOf[(*it)->theNode()] = (*it);
 504                 }
 505         }
 506 }
 507
 508
 509 void UpwardPlanRep::initMe()
 510 {
 511         m_Gamma.init(*this);
 512         isAugmented = false;
 513
 514         FaceSinkGraph fsg(m_Gamma, s_hat);
 515         SList<face> extFaces;
 516         fsg.possibleExternalFaces(extFaces);
 517
 518         OGDF_ASSERT(!extFaces.empty());
 519
 520         face f_ext = 0;
 521         forall_slistiterators(face, it, extFaces) {
 522                 if (f_ext == 0)
 523                         f_ext = *it;
 524                 else {
 525                         if (f_ext->size() < (*it)->size())
 526                                 f_ext = *it;
 527                 }
 528         }
 529         m_Gamma.setExternalFace(f_ext);
 530         adjEntry adj;
 531         forall_adj(adj, s_hat) {
 532                 if (m_Gamma.rightFace(adj) == m_Gamma.externalFace()) {
 533                         extFaceHandle = adj;
 534                         break;
 535                 }
 536         }
 537
 538         computeSinkSwitches();
 539 }
 540
 541
 542 }