ext/OGDF/src/planarity/ClusterPlanRep.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 ClusterPlanRep class
  11  *
  12  * \author Karsten Klein
  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/cluster/ClusterPlanRep.h>
  44 #include <ogdf/orthogonal/OrthoRep.h>
  45 #include <ogdf/basic/simple_graph_alg.h>
  46 #include <ogdf/basic/extended_graph_alg.h>
  47 #include <ogdf/basic/Layout.h>
  48 #include <ogdf/basic/GridLayoutMapped.h>
  49 #include <ogdf/basic/tuples.h>
  50
  51 #include <iomanip>
  52
  53
  54 enum edgeDir {undef, in, out};
  55
  56 namespace ogdf {
  57
  58 ClusterPlanRep::ClusterPlanRep(
  59         const ClusterGraphAttributes &acGraph,
  60         const ClusterGraph &clusterGraph)
  61         :
  62         PlanRep(acGraph),
  63         m_pClusterGraph(&clusterGraph)
  64 {
  65         OGDF_ASSERT(&clusterGraph.getGraph() == &acGraph.constGraph())
  66
  67         m_edgeClusterID.init(*this, -1);
  68         m_nodeClusterID.init(*this, -1);
  69
  70         //const Graph &CG = clusterGraph;
  71         //const Graph &G  = acGraph.constGraph();
  72
  73         //if (&acGraph != 0)
  74         //{
  75         //      OGDF_ASSERT(&CG == &G);
  76         //}
  77
  78         m_rootAdj = 0;
  79
  80         //cluster numbers don't need to be consecutive
  81         cluster ci;
  82         forall_clusters(ci, clusterGraph)
  83                 m_clusterOfIndex[ci->index()] = ci; //numbers are unique
  84 }//constructor
  85
  86
  87 void ClusterPlanRep::initCC(int i)
  88 {
  89         PlanRep::initCC(i);
  90
  91         //this means that for every reinitialization IDs are set
  92         //again, but this should not lead to problems
  93         //it cant be done in the constructor because the copies
  94         //in CCs are not yet initialized then
  95         //they are maintained for original nodes and for crossings
  96         //nodes on cluster boundaries
  97         const Graph &CG = *m_pClusterGraph;
  98         node v;
  99         forall_nodes(v, CG)
 100         {
 101                 m_nodeClusterID[copy(v)] = m_pClusterGraph->clusterOf(v)->index();
 102         }//forallnodes
 103
 104         //todo: initialize dummy node ids for different CCs
 105
 106         //initialize all edges totally contained in a single cluster
 107         edge e;
 108         forall_edges(e, *this)
 109         {
 110                 if (ClusterID(e->source()) == ClusterID(e->target()))
 111                         m_edgeClusterID[e] = ClusterID(e->source());
 112         }//foralledges
 113
 114 }//initCC
 115
 116 /**
 117  * Inserts edge eOrig
 118  * This is only an insertion for graphs with already modeled
 119  * boundary edges, otherwise cluster recognition won't work
 120  * */
 121 void ClusterPlanRep::insertEdgePathEmbedded(
 122         edge eOrig,
 123         CombinatorialEmbedding &E,
 124         const SList<adjEntry> &crossedEdges)
 125 {
 126         //inherited insert
 127         PlanRep::insertEdgePathEmbedded(eOrig,E,crossedEdges);
 128
 129         //update node cluster ids for crossing dummies
 130         ListConstIterator<edge> it;
 131         for(it = chain(eOrig).begin(); it.valid(); ++it)
 132         {
 133                 node dummy = (*it)->target();
 134                 if (dummy == copy(eOrig->target())) continue;
 135
 136                 OGDF_ASSERT(dummy->degree() == 4)
 137
 138                 //get the entries on the crossed edge
 139                 adjEntry adjIn = (*it)->adjTarget();
 140                 adjEntry adjC1 = adjIn->cyclicPred();
 141                 adjEntry adjC2 = adjIn->cyclicSucc();
 142
 143                 //insert edge end points have the problem that the next one
 144                 //does not need to have a clusterid yet
 145                 //therefore we use the crossed edges endpoints
 146                 //the two endpoints of the splitted edge
 147                 node v1 = adjC1->twinNode();
 148                 node v2 = adjC2->twinNode();
 149                 OGDF_ASSERT(v1 != dummy)
 150                 OGDF_ASSERT(v2 != dummy)
 151                 node orV1 = original(v1);
 152                 node orV2 = original(v2);
 153                 //inserted edges are never boundaries
 154                 //cases:
 155                 //cross boundary edge
 156                 //cross edge between different boundaries
 157                 //cross edge between boundary and crossing/end
 158                 //cross edge between crossings/ends
 159                 //there are three types of nodes: orig, boundary, crossing
 160                 //!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
 161                 //should only be used with modeled boundaries
 162                 cluster c1, c2;
 163                 if (orV1 && orV2)
 164                 {
 165                         OGDF_ASSERT(m_pClusterGraph->clusterOf(orV1) ==
 166                                                  m_pClusterGraph->clusterOf(orV2));
 167                         OGDF_ASSERT(m_nodeClusterID[v1] != -1)
 168                         m_nodeClusterID[dummy] = m_nodeClusterID[v1];
 169                         continue;
 170                 }//if two originals
 171                 if (orV1 || orV2) //a dummy (crossing/boundary) and an original
 172                 {
 173                         node orV = (orV1 ? orV1 : orV2);
 174                         //node vOr = (orV1 ? v1 : v2);
 175                         node vD  = (orV1 ? v2 : v1);
 176                         cluster orC = m_pClusterGraph->clusterOf(orV);
 177                         cluster dC  = clusterOfDummy(vD);
 178
 179                         OGDF_ASSERT( (orC == dC) ||             //original and crossing
 180                                 (orC == dC->parent()) || //original and boundary
 181                                 (orC->parent() == dC) )
 182
 183                         if (orC == dC) m_nodeClusterID[dummy] = orC->index();
 184                         else if (orC == dC->parent()) m_nodeClusterID[dummy] = orC->index();
 185                                  else OGDF_THROW (AlgorithmFailureException);
 186                         continue;
 187                 }//if one original
 188                 //no originals, only crossings/boundaries
 189                 c1 = clusterOfDummy(v1);
 190                 c2 = clusterOfDummy(v2);
 191                 OGDF_ASSERT( (c1 == c2) ||              //min.one crossing
 192                         (c1 == c2->parent()) || //min. one boundary
 193                         (c1->parent() == c2) ||
 194                         (c1->parent() == c2->parent())
 195                 )
 196
 197                 if (c1 == c2)
 198                         m_nodeClusterID[dummy] = c1->index();
 199                 else if (c1 == c2->parent())
 200                         m_nodeClusterID[dummy] = c1->index();
 201                 else if (c2 == c1->parent())
 202                         m_nodeClusterID[dummy] = c2->index();
 203                 else
 204                         m_nodeClusterID[dummy] = c1->parent()->index();
 205                 continue;
 206
 207
 208         }//for
 209
 210 }//insertEdgePathEmbedded
 211
 212 //use cluster structure to insert edges representing the cluster boundaries
 213 void ClusterPlanRep::ModelBoundaries()
 214 {
 215         //clusters hold their adjacent adjEntries and edges in lists, but after
 216         //insertion of boundaries these lists are outdated due to edge splittings
 217
 218         //is the clusteradjacent edge outgoing?
 219         //2 means undef (only at inner leaf cluster)
 220         AdjEntryArray<int> outEdge(*m_pClusterGraph, 2); //0 in 1 out
 221         //what edge is currently adjacent to cluster (after possible split)
 222         //with original adjEntry in clusteradjlist
 223         AdjEntryArray<edge> currentEdge(*m_pClusterGraph, 0);
 224
 225         List<adjEntry> rootEdges; //edges that can be used to set the outer face
 226
 227         convertClusterGraph(m_pClusterGraph->rootCluster(), currentEdge, outEdge);
 228 }
 229
 230 //recursively insert cluster boundaries for all clusters in cluster tree
 231 void ClusterPlanRep::convertClusterGraph(cluster act,
 232                                                                                  AdjEntryArray<edge>& currentEdge,
 233                                                                                  AdjEntryArray<int>& outEdge)
 234 {
 235
 236         //are we at the first call (no real cluster)
 237         bool isRoot = (act == m_pClusterGraph->rootCluster());
 238
 239         //check if we have to set the external face adj by hand
 240         if (isRoot && !act->cBegin().valid())
 241                 m_rootAdj = firstEdge()->adjSource(); //only root cluster present
 242         //check if leaf cluster in cluster tree (most inner)
 243         bool isLeaf = false;
 244         if ((!act->cBegin().valid()) && (!isRoot)) isLeaf = true;
 245         // Test children first
 246         ListConstIterator<cluster> it;
 247         for (it = act->cBegin(); it.valid();)
 248         {
 249                 ListConstIterator<cluster> succ = it.succ();
 250                 convertClusterGraph((*it), currentEdge, outEdge);
 251
 252                 it = succ;
 253         }
 254         //do not convert root cluster
 255         if (isRoot) return;
 256
 257                 OGDF_ASSERT(this->representsCombEmbedding())
 258
 259         insertBoundary(act, currentEdge, outEdge, isLeaf);
 260
 261         OGDF_ASSERT(this->representsCombEmbedding())
 262
 263
 264 }//convertclustergraph
 265
 266 //inserts Boundary for a single cluster, needs the cluster and updates a
 267 //hashtable linking splitted original edges (used in clusteradjlist) to the
 268 //current (new) edge, if cluster is leafcluster, we check and set the edge
 269 //direction and the adjacent edge corresponding to the adjEntries in the clusters
 270 //adjEntry List
 271 void ClusterPlanRep::insertBoundary(cluster C,
 272                                                                         AdjEntryArray<edge>& currentEdge,
 273                                                                         AdjEntryArray<int>& outEdge,
 274                                                                         bool clusterIsLeaf)
 275 {
 276         //we insert edges to represent the cluster boundary
 277         //by splitting the outgoing edges and connecting the
 278         //split nodes
 279
 280         OGDF_ASSERT(this->representsCombEmbedding())
 281
 282         //retrieve the outgoing edges
 283
 284         //TODO: nichtverbundene Cluster abfangen
 285
 286         SList<adjEntry> outAdj;
 287         //outgoing adjEntries in clockwise order
 288         m_pClusterGraph->adjEntries(C, outAdj);
 289
 290         //now split the edges and save adjEntries
 291         //we maintain two lists of adjentries
 292         List<adjEntry> targetEntries, sourceEntries;
 293         //we need to find out if edge is outgoing
 294         bool isOut = false;
 295         SListIterator<adjEntry> it = outAdj.begin();
 296         //if no outAdj exist, we have a connected component
 297         //and dont need a boundary, change this when unconnected
 298         //graphs are allowed
 299         if (!it.valid()) return;
 300
 301         while (it.valid())
 302         {
 303                 //if clusterIsLeaf, save the corresponding direction and edge
 304                 if (clusterIsLeaf)
 305                 {
 306                         //save the current, unsplitted edge
 307                         //be careful with clusterleaf connecting, layered cl
 308                         if (currentEdge[(*it)] == 0)
 309                                 currentEdge[(*it)] = copy((*it)->theEdge());
 310                         //set twin here?
 311
 312                         //check direction, adjEntry is outgoing, compare with edge
 313                         outEdge[(*it)] = ( ((*it) == (*it)->theEdge()->adjSource()) ? 1 : 0);
 314                 }
 315
 316                 //workaround for nonleaf edges
 317                 if (outEdge[(*it)] == 2)
 318                         outEdge[(*it)] = ( ((*it) == (*it)->theEdge()->adjSource()) ? 1 : 0);
 319
 320                 if (currentEdge[(*it)] == 0)
 321                 {
 322                         //may already be splitted from head
 323                         currentEdge[(*it)] = copy((*it)->theEdge());
 324                 }
 325
 326
 327                 //We need to find the real edge here
 328                 edge splitEdge = currentEdge[(*it)];
 329
 330                 //...outgoing...?
 331                 OGDF_ASSERT(outEdge[(*it)] != 2);
 332                 isOut = outEdge[(*it)] == 1;
 333
 334                 edge newEdge = split(splitEdge);
 335
 336                 //store the adjEntries depending on in/out direction
 337                 if (isOut)
 338                 {
 339                         //splitresults "upper" edge to old target is newEdge!?
 340                         //only update for outgoing edges, ingoing stay actual
 341                         currentEdge[(*it)] = newEdge;
 342                         currentEdge[(*it)->twin()] = newEdge;
 343                         sourceEntries.pushBack(newEdge->adjSource());
 344                         targetEntries.pushBack(splitEdge->adjTarget());
 345
 346                         m_nodeClusterID[newEdge->source()] = C->index();
 347                                 //m_nodeClusterID[splitEdge->source()];
 348                 }//if outgoing
 349                 else
 350                 {
 351                         sourceEntries.pushBack(splitEdge->adjTarget());
 352                         targetEntries.pushBack(newEdge->adjSource());
 353
 354                         m_nodeClusterID[newEdge->source()] = C->index();
 355                 }//else outgoing
 356
 357                 //always set some rootAdj for external face
 358                 if ( (C->parent() == m_pClusterGraph->rootCluster()) && !(it.succ().valid()))
 359                 {
 360                         //save the adjentry corresponding to new splitresult edge
 361                         m_rootAdj = currentEdge[(*it)]->adjSource();
 362                         OGDF_ASSERT(m_rootAdj != 0);
 363                 }//if
 364
 365                 //go on with next edge
 366                 it++;
 367
 368         }//while outedges
 369
 370
 371         //we need pairs of adjEntries
 372         OGDF_ASSERT(targetEntries.size() == sourceEntries.size());
 373         //now flip first target entry to front
 374         //should be nonempty
 375         adjEntry flipper = targetEntries.popFrontRet();
 376         targetEntries.pushBack(flipper);
 377
 378         //connect the new nodes to form the boundary
 379         while (!targetEntries.empty())
 380         {
 381
 382                 edge e = newEdge(sourceEntries.popFrontRet(), targetEntries.popFrontRet());
 383                 //set type of new edges
 384                 setClusterBoundary(e);
 385                 m_edgeClusterID[e] = C->index();
 386
 387                 OGDF_ASSERT(this->representsCombEmbedding())
 388         }
 389
 390         OGDF_ASSERT(this->representsCombEmbedding())
 391
 392 }//insertBoundary
 393
 394
 395
 396 void ClusterPlanRep::expand(bool lowDegreeExpand)
 397 {
 398         PlanRep::expand(lowDegreeExpand);
 399         //update cluster info
 400         node v;
 401         forall_nodes(v, *this)
 402         {
 403                 if (expandedNode(v) != 0)
 404                 {
 405                         OGDF_ASSERT(m_nodeClusterID[expandedNode(v)] != -1)
 406                         m_nodeClusterID[v] = m_nodeClusterID[expandedNode(v)];
 407                 }
 408         }
 409 }//expand
 410
 411 void ClusterPlanRep::expandLowDegreeVertices(OrthoRep &OR)
 412 {
 413         PlanRep::expandLowDegreeVertices(OR);
 414         //update cluster info
 415         node v;
 416         forall_nodes(v, *this)
 417         {
 418                 if (expandedNode(v) != 0)
 419                 {
 420                         OGDF_ASSERT(m_nodeClusterID[expandedNode(v)] != -1)
 421                         m_nodeClusterID[v] = m_nodeClusterID[expandedNode(v)];
 422                 }
 423         }
 424 }//expandlowdegree
 425
 426
 427 //*****************************************************************************
 428 //file output
 429
 430 void ClusterPlanRep::writeGML(const char *fileName, const Layout &drawing)
 431 {
 432         ofstream os(fileName);
 433         writeGML(os,drawing);
 434 }
 435
 436
 437 void ClusterPlanRep::writeGML(const char *fileName)
 438 {
 439         Layout drawing(*this);
 440         ofstream os(fileName);
 441         writeGML(os,drawing);
 442 }
 443
 444
 445 void ClusterPlanRep::writeGML(ostream &os, const Layout &drawing)
 446 {
 447         const Graph &G = *this;
 448
 449         NodeArray<int> id(*this);
 450         int nextId = 0;
 451
 452         os.setf(ios::showpoint);
 453         os.precision(10);
 454
 455         os << "Creator \"ogdf::GraphAttributes::writeGML\"\n";
 456         os << "graph [\n";
 457         os << "  directed 1\n";
 458
 459         node v;
 460         forall_nodes(v,G) {
 461
 462                 node ori = original(v);
 463
 464                 os << "  node [\n";
 465
 466                 os << "    id " << (id[v] = nextId++) << "\n";
 467
 468                 os << "    graphics [\n";
 469                 os << "      x " << drawing.x(v) << "\n";
 470                 os << "      y " << drawing.y(v) << "\n";
 471                 os << "      w " << 10.0 << "\n";
 472                 os << "      h " << 10.0 << "\n";
 473                 os << "      type \"rectangle\"\n";
 474                 os << "      width 1.0\n";
 475                 if (typeOf(v) == Graph::generalizationMerger) {
 476                         os << "      type \"oval\"\n";
 477                         os << "      fill \"#0000A0\"\n";
 478                 }
 479                 else if (typeOf(v) == Graph::generalizationExpander) {
 480                         os << "      type \"oval\"\n";
 481                         os << "      fill \"#00FF00\"\n";
 482                 }
 483                 else if (typeOf(v) == Graph::highDegreeExpander ||
 484                         typeOf(v) == Graph::lowDegreeExpander)
 485                         os << "      fill \"#FFFF00\"\n";
 486                 else if (typeOf(v) == Graph::dummy)
 487                         os << "      type \"oval\"\n";
 488
 489                 else
 490                 if (m_pClusterGraph->clusterOf(ori)->index() != 0) //cluster
 491                 {
 492                         //only < 16
 493                         os << "      fill \"#" << std::hex << std::setw(6) << std::setfill('0')
 494                                 << m_pClusterGraph->clusterOf(ori)->index()*256*256+
 495                                         m_pClusterGraph->clusterOf(ori)->index()*256+
 496                                         m_pClusterGraph->clusterOf(ori)->index()*4 << std::dec << "\"\n";
 497                 }
 498                 else
 499                 {
 500                 if (v->degree() > 4)
 501                         os << "      fill \"#FFFF00\"\n";
 502
 503                 else
 504                         os << "      fill \"#000000\"\n";
 505                 }
 506
 507                 os << "    ]\n"; // graphics
 508
 509                 os << "  ]\n"; // node
 510         }
 511
 512
 513         edge e;
 514         forall_edges(e,G) {
 515                 os << "  edge [\n";
 516
 517                 os << "    source " << id[e->source()] << "\n";
 518                 os << "    target " << id[e->target()] << "\n";
 519
 520                 os << "    generalization " << typeOf(e) << "\n";
 521
 522                 os << "    graphics [\n";
 523
 524                 os << "      type \"line\"\n";
 525
 526                 if (typeOf(e) == Graph::generalization)
 527                 {
 528                         os << "      arrow \"last\"\n";
 529
 530                         os << "      fill \"#FF0000\"\n";
 531                         os << "      width 3.0\n";
 532                 }
 533                 else
 534                 {
 535
 536                         if (typeOf(e->source()) == Graph::generalizationExpander ||
 537                                 typeOf(e->source()) == Graph::generalizationMerger ||
 538                                 typeOf(e->target()) == Graph::generalizationExpander ||
 539                                 typeOf(e->target()) == Graph::generalizationMerger)
 540                         {
 541                                 os << "      arrow \"none\"\n";
 542                                 if (isBrother(e))
 543                                         os << "      fill \"#F0F000\"\n"; //gelb
 544                                 else if (isHalfBrother(e))
 545                                         os << "      fill \"#FF00AF\"\n";
 546                                 else if (isClusterBoundary(e))
 547                                         os << "      fill \"#FF0000\"\n";
 548                                 else
 549                                         os << "      fill \"#FF0000\"\n";
 550                         }
 551                         else
 552                                 os << "      arrow \"none\"\n";
 553                         if (isBrother(e))
 554                                 os << "      fill \"#F0F000\"\n"; //gelb
 555                         else if (isHalfBrother(e))
 556                                 os << "      fill \"#FF00AF\"\n";
 557                         else if (isClusterBoundary(e))
 558                                 os << "      fill \"#FF0000\"\n";
 559                         else
 560                                 os << "      fill \"#00000F\"\n";
 561                         os << "      width 1.0\n";
 562                 }//else generalization
 563                 os << "    ]\n"; // graphics
 564
 565                 os << "  ]\n"; // edge
 566         }
 567
 568         os << "]\n"; // graph
 569 }
 570
 571
 572 }//namespace
 573