ext/OGDF/src/basic/GraphAttributes.cpp

   1 /*
   2  * $Revision: 2571 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-10 17:25:20 +0200 (Di, 10. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of class GraphAttributes.
  11  *
  12  * Class GraphAttributes extends a graph by graphical attributes like
  13  * node position, color, etc.
  14  *
  15  * \author Carsten Gutwenger
  16  *
  17  * \par License:
  18  * This file is part of the Open Graph Drawing Framework (OGDF).
  19  *
  20  * \par
  21  * Copyright (C)<br>
  22  * See README.txt in the root directory of the OGDF installation for details.
  23  *
  24  * \par
  25  * This program is free software; you can redistribute it and/or
  26  * modify it under the terms of the GNU General Public License
  27  * Version 2 or 3 as published by the Free Software Foundation;
  28  * see the file LICENSE.txt included in the packaging of this file
  29  * for details.
  30  *
  31  * \par
  32  * This program is distributed in the hope that it will be useful,
  33  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  34  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  35  * GNU General Public License for more details.
  36  *
  37  * \par
  38  * You should have received a copy of the GNU General Public
  39  * License along with this program; if not, write to the Free
  40  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  41  * Boston, MA 02110-1301, USA.
  42  *
  43  * \see  http://www.gnu.org/copyleft/gpl.html
  44  ***************************************************************/
  45
  46
  47 #include <ogdf/basic/GraphAttributes.h>
  48 #include <ogdf/fileformats/GmlParser.h>
  49 #include <ogdf/fileformats/XmlParser.h>
  50
  51
  52 namespace ogdf {
  53
  54 //---------------------------------------------------------
  55 // GraphAttributes
  56 // graph topology + graphical attributes
  57 //---------------------------------------------------------
  58
  59 GraphAttributes::GraphAttributes() : m_pGraph(0), m_directed(true) { }
  60
  61
  62
  63 GraphAttributes::GraphAttributes(const Graph &G, long initAttr) :
  64         m_pGraph(&G), m_directed(true), m_attributes(0)
  65 {
  66         initAttributes(m_attributes = initAttr);
  67 }
  68
  69
  70
  71 void GraphAttributes::initAttributes(long attr)
  72 {
  73         m_attributes |= attr;
  74
  75         //no color without graphics
  76         OGDF_ASSERT( (m_attributes & nodeGraphics) != 0 || (m_attributes & nodeColor) == 0);
  77         //no fill and linewithout graphics
  78         OGDF_ASSERT( (m_attributes & nodeGraphics) != 0 || (attr & nodeStyle) == 0);
  79         //no color without graphics
  80         OGDF_ASSERT( (m_attributes & edgeGraphics) != 0 || (attr & edgeColor) == 0);
  81
  82         if (attr & nodeGraphics) {
  83                 m_x     .init(*m_pGraph,0.0);
  84                 m_y     .init(*m_pGraph,0.0);
  85                 m_width .init(*m_pGraph,0.0);
  86                 m_height.init(*m_pGraph,0.0);
  87                 m_nodeShape.init(*m_pGraph,rectangle);
  88         }
  89
  90         if (attr & nodeColor)
  91         {
  92                 m_nodeColor.init(*m_pGraph, "");
  93                 m_nodeLine.init(*m_pGraph, "");
  94         }
  95
  96         if (attr & nodeStyle)
  97         {
  98                 m_nodePattern.init(*m_pGraph, bpNone);
  99                 m_nodeStyle.init(*m_pGraph, esSolid);
 100                 m_nodeLineWidth.init(*m_pGraph, 1);
 101                 //images should not be added here as nodestyle, purely experimental
 102                 //such that it fits PG code
 103                 //images:
 104                 m_imageUri.init(*m_pGraph, "");
 105                 m_imageStyle.init(*m_pGraph, GraphAttributes::FreeScale);
 106                 m_imageAlign.init(*m_pGraph, GraphAttributes::Center);
 107                 m_imageDrawLine.init(*m_pGraph, false);
 108                 m_imageWidth.init(*m_pGraph, 0);
 109                 m_imageHeight.init(*m_pGraph, 0);
 110         }
 111
 112         if (attr & edgeGraphics) {
 113                 m_bends.init(*m_pGraph,DPolyline());
 114         }
 115
 116         if (attr & edgeColor)
 117                 m_edgeColor.init(*m_pGraph);
 118
 119         if (attr & edgeStyle)
 120         {
 121                 m_edgeStyle.init(*m_pGraph, esSolid);
 122                 m_edgeWidth.init(*m_pGraph, 1.0);
 123         }
 124
 125         if (attr & nodeLevel) {
 126                 m_level.init(*m_pGraph,0);
 127         }
 128         if (attr & nodeWeight) {
 129                 m_nodeIntWeight.init(*m_pGraph,0);
 130         }
 131         if (attr & edgeIntWeight) {
 132                 m_intWeight.init(*m_pGraph,1);
 133         }
 134         if (attr & edgeDoubleWeight) {
 135                 m_doubleWeight.init(*m_pGraph,1.0);
 136         }
 137         if (attr & nodeLabel) {
 138                 m_nodeLabel.init(*m_pGraph);
 139         }
 140         if (attr & edgeLabel) {
 141                 m_edgeLabel.init(*m_pGraph);
 142         }
 143         if (attr & edgeType) {
 144                 m_eType.init(*m_pGraph,Graph::association);//should be Graph::standard end explicitly set
 145         }
 146         if (attr & nodeType) {
 147                 m_vType.init(*m_pGraph,Graph::vertex);
 148         }
 149         if (attr & nodeId) {
 150                 m_nodeId.init(*m_pGraph, -1);
 151         }
 152         if (attr & edgeArrow) {
 153                 m_edgeArrow.init(*m_pGraph, undefined);
 154         }
 155         if (attr & nodeTemplate) {
 156                 m_nodeTemplate.init(*m_pGraph);
 157         }
 158         if (attr & edgeSubGraph) {
 159                 m_subGraph.init(*m_pGraph,0);
 160         }
 161 }
 162
 163 void GraphAttributes::destroyAttributes(long attr)
 164 {
 165         m_attributes &= ~attr;
 166
 167         if (attr & nodeGraphics) {
 168                 m_x     .init();
 169                 m_y     .init();
 170                 m_width .init();
 171                 m_height.init();
 172                 m_nodeShape.init();
 173                 if (attr & nodeColor)
 174                         m_nodeColor.init();
 175                 if (attr & nodeStyle)
 176                 {
 177                         m_nodePattern.init();
 178                         m_nodeLine.init();
 179                         m_nodeLineWidth.init();
 180                         //should have its own trigger attribute
 181                         //images
 182                         m_imageUri.init();
 183                         m_imageStyle.init();
 184                         m_imageAlign.init();
 185                         m_imageDrawLine.init();
 186                         m_imageWidth.init();
 187                         m_imageHeight.init();
 188                 }
 189         }
 190
 191         if (attr & edgeGraphics) {
 192                 m_bends.init();
 193         }
 194         if (attr & edgeColor)
 195         {
 196                 m_edgeColor.init();
 197         }
 198         if (attr & edgeStyle)
 199         {
 200                 m_edgeStyle.init();
 201                 m_edgeWidth.init();
 202         }
 203
 204         if (attr & nodeLevel) {
 205                 m_level.init();
 206         }
 207         if (attr & nodeWeight) {
 208                 m_nodeIntWeight.init();
 209         }
 210         if (attr & edgeIntWeight) {
 211                 m_intWeight.init();
 212         }
 213         if (attr & edgeDoubleWeight) {
 214                 m_doubleWeight.init();
 215         }
 216         if (attr & nodeLabel) {
 217                 m_nodeLabel.init();
 218         }
 219         if (attr & edgeLabel) {
 220                 m_edgeLabel.init();
 221         }
 222         if (attr & nodeId) {
 223                 m_nodeId.init();
 224         }
 225         if (attr & edgeArrow) {
 226                 m_edgeArrow.init();
 227         }
 228         if (attr & nodeTemplate) {
 229                 m_nodeTemplate.init();
 230         }
 231         if (attr & edgeSubGraph) {
 232                 m_subGraph.init();
 233         }
 234 }
 235
 236
 237 void GraphAttributes::init(const Graph &G, long initAttr)
 238 {
 239         m_pGraph = &G;
 240         destroyAttributes(m_attributes);
 241         m_attributes = 0;
 242         initAttributes(m_attributes = initAttr);
 243 }
 244
 245 void GraphAttributes::setAllWidth(double w)
 246 {
 247         node v;
 248         forall_nodes(v,*m_pGraph)
 249                 m_width[v] = w;
 250 }
 251
 252
 253 void GraphAttributes::setAllHeight(double h)
 254 {
 255         node v;
 256         forall_nodes(v,*m_pGraph)
 257                 m_height[v] = h;
 258 }
 259
 260
 261 void GraphAttributes::clearAllBends()
 262 {
 263         edge e;
 264         forall_edges(e,*m_pGraph)
 265                 m_bends[e].clear();
 266 }
 267
 268
 269 bool GraphAttributes::readGML(Graph &G, const String &fileName)
 270 {
 271         ifstream is(fileName.cstr());
 272         if (!is)
 273                 return false; // couldn't open file
 274
 275         return readGML(G,is);
 276 }
 277
 278
 279 bool GraphAttributes::readGML(Graph &G, istream &is)
 280 {
 281         GmlParser gml(is);
 282         if (gml.error())
 283                 return false;
 284
 285         return gml.read(G,*this);
 286 }
 287
 288
 289 bool GraphAttributes::readRudy(Graph &G, const String &fileName)
 290 {
 291         ifstream is(fileName.cstr());
 292         if (!is)
 293                 return false;
 294         return readRudy(G,is);
 295 }
 296
 297
 298 bool GraphAttributes::readRudy(Graph &G, istream &is)
 299 {
 300         if (!is)
 301                 return false;
 302         int i;
 303         int n, m;
 304         int src, tgt;
 305         double weight;
 306         edge e;
 307
 308         is >> n >> m;
 309
 310         G.clear();
 311         Array<node> mapToNode(0,n-1,0);
 312
 313         if (attributes() & edgeDoubleWeight){
 314                 for(i=0; i<m; i++) {
 315                         is >> src >> tgt >> weight;
 316                         src--;
 317                         tgt--;
 318                         if(mapToNode[src] == 0) mapToNode[src] = G.newNode(src);
 319                         if(mapToNode[tgt] == 0) mapToNode[tgt] = G.newNode(tgt);
 320                         e = G.newEdge(mapToNode[src],mapToNode[tgt]);
 321                         this->doubleWeight(e)=weight;
 322                 }
 323         }
 324         return true;
 325 }
 326
 327
 328 void GraphAttributes::writeRudy(const String &fileName) const
 329 {
 330         ofstream os(fileName.cstr());
 331         writeRudy(os);
 332 }
 333
 334
 335 void GraphAttributes::writeRudy(ostream &os) const
 336 {
 337         const Graph &G = this->constGraph();
 338         os << G.numberOfNodes() << " " << G.numberOfEdges() << endl;
 339
 340         edge e;
 341         if (attributes() & edgeDoubleWeight){
 342                 forall_edges(e,G) {
 343                         os << (e->source()->index())+1 << " " << (e->target()->index())+1;
 344                         os << " " << this->doubleWeight(e) << endl;
 345                 }
 346         }
 347         else forall_edges(e,G) os << (e->source()->index())+1 << " " << (e->target()->index())+1 << endl;
 348 }
 349
 350
 351 const int c_maxLengthPerLine = 200;
 352
 353 void GraphAttributes::writeLongString(ostream &os, const String &str) const
 354 {
 355         os << "\"";
 356
 357         int num = 1;
 358         const char *p = str.cstr();
 359         while(*p != 0)
 360         {
 361                 switch(*p) {
 362                 case '\\':
 363                         os << "\\\\";
 364                         num += 2;
 365                         break;
 366                 case '\"':
 367                         os << "\\\"";
 368                         num += 2;
 369                         break;
 370
 371                 // ignored white space
 372                 case '\r':
 373                 case '\n':
 374                 case '\t':
 375                         break;
 376
 377                 default:
 378                         os << *p;
 379                         ++num;
 380                 }
 381
 382                 if(num >= c_maxLengthPerLine) {
 383                         os << "\\\n";
 384                         num = 0;
 385                 }
 386
 387                 ++p;
 388         }
 389
 390         os << "\"";
 391 }
 392
 393
 394 void GraphAttributes::writeGML(const String &fileName) const
 395 {
 396         ofstream os(fileName.cstr());
 397         writeGML(os);
 398 }
 399
 400
 401 void GraphAttributes::writeGML(ostream &os) const
 402 {
 403         NodeArray<int> id(*m_pGraph);
 404         int nextId = 0;
 405
 406         os.setf(ios::showpoint);
 407         os.precision(10);
 408
 409         os << "Creator \"ogdf::GraphAttributes::writeGML\"\n";
 410
 411         os << "graph [\n";
 412
 413         os << (m_directed ? "  directed 1\n" : "  directed 0\n");
 414
 415         node v;
 416         forall_nodes(v,*m_pGraph) {
 417                 os << "  node [\n";
 418
 419                 os << "    id " << (id[v] = nextId++) << "\n";
 420
 421                 if (attributes() & nodeTemplate) {
 422                         os << "    template ";
 423                         writeLongString(os, templateNode(v));
 424                         os << "\n";
 425                 }
 426
 427                 if (attributes() & nodeLabel) {
 428                         //os << "label \"" << labelNode(v) << "\"\n";
 429                         os << "    label ";
 430                         writeLongString(os, labelNode(v));
 431                         os << "\n";
 432                 }
 433
 434                 if (m_attributes & nodeGraphics) {
 435                         os << "    graphics [\n";
 436                         os << "      x " << m_x[v] << "\n";
 437                         os << "      y " << m_y[v] << "\n";
 438                         os << "      w " << m_width[v] << "\n";
 439                         os << "      h " << m_height[v] << "\n";
 440                         if (m_attributes & nodeColor)
 441                         {
 442                                 os << "      fill \"" << m_nodeColor[v] << "\"\n";
 443                                 os << "      line \"" << m_nodeLine[v] << "\"\n";
 444                         }//color
 445                         if (m_attributes & nodeStyle)
 446                         {
 447                                 os << "      pattern \"" << m_nodePattern[v] << "\"\n";
 448                                 os << "      stipple " << styleNode(v) << "\n";
 449                                 os << "      lineWidth " << lineWidthNode(v) << "\n";
 450                         }
 451                         switch (m_nodeShape[v])
 452                         {
 453                                 case rectangle: os << "      type \"rectangle\"\n"; break;
 454                                 case oval: os << "      type \"oval\"\n"; break;
 455                         }
 456                         os << "      width 1.0\n";
 457                         os << "    ]\n"; // graphics
 458                 }
 459
 460                 os << "  ]\n"; // node
 461         }
 462
 463         edge e;
 464         forall_edges(e,*m_pGraph) {
 465                 os << "  edge [\n";
 466
 467                 os << "    source " << id[e->source()] << "\n";
 468                 os << "    target " << id[e->target()] << "\n";
 469
 470                 if (attributes() & edgeLabel){
 471                         os << "    label ";
 472                         writeLongString(os, labelEdge(e));
 473                         os << "\n";
 474                 }
 475                 if (attributes() & edgeType)
 476                         os << "    generalization " << type(e) << "\n";
 477
 478                 if (attributes() & edgeSubGraph)
 479                         os << "    subgraph " << subGraphBits(e) << "\n";
 480
 481                 if (m_attributes & edgeGraphics) {
 482                         os << "    graphics [\n";
 483
 484                         os << "      type \"line\"\n";
 485
 486                         if (attributes() & GraphAttributes::edgeType) {
 487                                 if (attributes() & GraphAttributes::edgeArrow) {
 488                                         switch(arrowEdge(e)) {
 489                                                 case GraphAttributes::none:
 490                                                         os << "      arrow \"none\"\n";
 491                                                         break;
 492
 493                                                 case GraphAttributes::last:
 494                                                         os << "      arrow \"last\"\n";
 495                                                         break;
 496
 497                                                 case GraphAttributes::first:
 498                                                         os << "      arrow \"first\"\n";
 499                                                         break;
 500
 501                                                 case GraphAttributes::both:
 502                                                         os << "      arrow \"both\"\n";
 503                                                         break;
 504
 505                                                 case GraphAttributes::undefined:
 506                                                         // do nothing
 507                                                         break;
 508
 509                                                 default:
 510                                                         // do nothing
 511                                                         break;
 512                                         }
 513                                 } else {
 514                                         if (type(e) == Graph::generalization)
 515                                                 os << "      arrow \"last\"\n";
 516                                         else
 517                                                 os << "      arrow \"none\"\n";
 518                                 }
 519
 520                         } else { // GraphAttributes::edgeType not used
 521                                 if (m_directed) {
 522                                         os << "      arrow \"last\"\n";
 523                                 } else {
 524                                         os << "      arrow \"none\"\n";
 525                                 }
 526                         }
 527
 528                         if (attributes() & GraphAttributes::edgeStyle)
 529                         {
 530                                 os << "      stipple " << styleEdge(e) << "\n";
 531                                 os << "      lineWidth " << edgeWidth(e) << "\n";
 532                         }//edgestyle is gml graphlet extension!!!
 533                         if (attributes() & edgeDoubleWeight)
 534                         {
 535                                 os << "      weight " << doubleWeight(e) << "\n";
 536                         }
 537                         //hier noch Unterscheidung Knotentypen, damit die Berechnung
 538                         //fuer Ellipsen immer bis zum echten Rand rechnet
 539                         const DPolyline &dpl = m_bends[e];
 540                         if (!dpl.empty()) {
 541                                 os << "      Line [\n";
 542
 543                                 node v = e->source();
 544                                 if(dpl.front().m_x < m_x[v] - m_width[v]/2 ||
 545                                         dpl.front().m_x > m_x[v] + m_width[v]/2 ||
 546                                         dpl.front().m_y < m_y[v] - m_height[v]/2 ||
 547                                         dpl.front().m_y > m_y[v] + m_height[v]/2)
 548                                 {
 549                                         os << "        point [ x " << m_x[e->source()] << " y " <<
 550                                                 m_y[e->source()] << " ]\n";
 551                                 }
 552
 553                                 ListConstIterator<DPoint> it;
 554                                 for(it = dpl.begin(); it.valid(); ++it)
 555                                         os << "        point [ x " << (*it).m_x << " y " << (*it).m_y << " ]\n";
 556
 557                                 v = e->target();
 558                                 if(dpl.back().m_x < m_x[v] - m_width[v]/2 ||
 559                                         dpl.back().m_x > m_x[v] + m_width[v]/2 ||
 560                                         dpl.back().m_y < m_y[v] - m_height[v]/2 ||
 561                                         dpl.back().m_y > m_y[v] + m_height[v]/2)
 562                                 {
 563                                         os << "        point [ x " << m_x[e->target()] << " y " <<
 564                                                 m_y[e->target()] << " ]\n";
 565                                 }
 566
 567                                 os << "      ]\n"; // Line
 568                         }//bends
 569
 570                         //output width and color
 571                         if ((m_attributes & edgeColor) &&
 572                                 (m_edgeColor[e].length() != 0))
 573                                 os << "      fill \"" << m_edgeColor[e] << "\"\n";
 574
 575                         os << "    ]\n"; // graphics
 576                 }
 577
 578                 os << "  ]\n"; // edge
 579         }
 580
 581         os << "]\n"; // graph
 582 }
 583
 584
 585 bool GraphAttributes::readXML(Graph &G, const String &fileName)
 586 {
 587         ifstream is(fileName.cstr());
 588         return readXML(G,is);
 589 }
 590
 591
 592 bool GraphAttributes::readXML(Graph &G, istream &is)
 593 {
 594         // need at least these attributes
 595         initAttributes(~m_attributes &
 596                 (nodeGraphics | edgeGraphics | nodeLabel | edgeLabel));
 597
 598         XmlParser xml(is);
 599         if (xml.error()) return false;
 600
 601         return xml.read(G,*this);
 602 }
 603
 604
 605
 606 //
 607 // calculates the bounding box of the graph
 608 const DRect GraphAttributes::boundingBox() const
 609 {
 610         double minx, maxx, miny, maxy;
 611         const Graph           &G  = constGraph();
 612         const GraphAttributes &AG = *this;
 613         node v = G.firstNode();
 614
 615         if (v == 0) {
 616                 minx = maxx = miny = maxy = 0.0;
 617         }
 618         else {
 619                 minx = AG.x(v) - AG.width(v)/2;
 620                 maxx = AG.x(v) + AG.width(v)/2;
 621                 miny = AG.y(v) - AG.height(v)/2;
 622                 maxy = AG.y(v) + AG.height(v)/2;
 623
 624                 forall_nodes(v, G) {
 625                         double x1 = AG.x(v) - AG.width(v)/2;
 626                         double x2 = AG.x(v) + AG.width(v)/2;
 627                         double y1 = AG.y(v) - AG.height(v)/2;
 628                         double y2 = AG.y(v) + AG.height(v)/2;
 629
 630                         if (x1 < minx) minx = x1;
 631                         if (x2 > maxx) maxx = x2;
 632                         if (y1 < miny) miny = y1;
 633                         if (y2 > maxy) maxy = y2;
 634                 }
 635         }
 636
 637         edge e;
 638         forall_edges(e, G) {
 639                 const DPolyline &dpl = AG.bends(e);
 640                 ListConstIterator<DPoint> iter;
 641                 for (iter = dpl.begin(); iter.valid(); ++iter) {
 642                         if ((*iter).m_x < minx) minx = (*iter).m_x;
 643                         if ((*iter).m_x > maxx) maxx = (*iter).m_x;
 644                         if ((*iter).m_y < miny) miny = (*iter).m_y;
 645                         if ((*iter).m_y > maxy) maxy = (*iter).m_y;
 646                 }
 647         }
 648
 649         return DRect(minx, miny, maxx, maxy);
 650 }
 651
 652
 653 //
 654 // returns a list of all hierachies in the graph (a hierachy consists of a set of nodes)
 655 // at least one list is returned, which is the list of all nodes not belonging to any hierachy
 656 // this is always the first list
 657 // the return-value of this function is the number of hierachies
 658 int GraphAttributes::hierarchyList(List<List<node>* > &list) const
 659 {
 660         // list must be empty during startup
 661         OGDF_ASSERT(list.empty());
 662
 663         const Graph &G = constGraph();
 664         Array<bool> processed(0, G.maxNodeIndex(), false);
 665         node v;
 666         edge e;
 667
 668         // initialize the first list of all single nodes
 669         List<node> *firstList = OGDF_NEW List<node>;
 670         list.pushBack(firstList);
 671
 672         forall_nodes(v, G) { // scan all nodes
 673
 674                 // skip, if already processed
 675                 if (processed[v->index()])
 676                         continue;
 677
 678                 List<node> nodeSet;                    // set of nodes in this hierachy,
 679                 // whose neighbours have to be processed
 680                 List<node> *hierachy = OGDF_NEW List<node>; // holds all nodes in this hierachy
 681
 682                 nodeSet.pushBack(v);           // push the unprocessed node to the list
 683                 processed[v->index()] = true;  // and mark it as processed
 684
 685                 do { // scan all neighbours of nodes in 'nodeSet'
 686                         node v = nodeSet.popFrontRet();
 687                         hierachy->pushBack(v); // push v to the list of nodes in this hierachy
 688
 689                         // process all the neighbours of v, e.g. push them into 'nodeSet'
 690                         forall_adj_edges(e, v) {
 691                                 if (type(e) == Graph::generalization) {
 692                                         node w = e->source() == v ? e->target() : e->source();
 693                                         if (!processed[w->index()]) {
 694                                                 nodeSet.pushBack(w);
 695                                                 processed[w->index()] = true;
 696                                         }
 697                                 }
 698                         }
 699                 } while (!nodeSet.empty());
 700
 701                 // skip adding 'hierachy', if it contains only one node
 702                 if (hierachy->size() == 1) {
 703                         firstList->conc(*hierachy);
 704                         delete hierachy;
 705                 }
 706                 else
 707                         list.pushBack(hierachy);
 708         }
 709
 710         return list.size() - 1 + (*list.begin())->size();
 711 }
 712
 713
 714 //
 715 // returns a list of all hierarchies in the graph (in this case, a hierarchy consists of a set of edges)
 716 // list may be empty, if no generalizations are used
 717 // the return-value of this function is the number of hierarchies with generalizations
 718 int GraphAttributes::hierarchyList(List<List<edge>* > &list) const
 719 {
 720         // list must be empty during startup
 721         OGDF_ASSERT(list.empty());
 722
 723         const Graph &G = constGraph();
 724         Array<bool> processed(0, G.maxNodeIndex(), false);
 725         node v;
 726         edge e;
 727
 728         forall_nodes(v, G) { // scan all nodes
 729
 730                 // skip, if already processed
 731                 if (processed[v->index()])
 732                         continue;
 733
 734                 List<node> nodeSet;                    // set of nodes in this hierarchy,
 735                 // whose neighbours have to be processed
 736                 List<edge> *hierarchy = OGDF_NEW List<edge>; // holds all edges in this hierarchy
 737
 738                 nodeSet.pushBack(v);           // push the unprocessed node to the list
 739                 processed[v->index()] = true;  // and mark it as processed
 740
 741                 do { // scan all neighbours of nodes in 'nodeSet'
 742                         node v = nodeSet.popFrontRet();
 743
 744                         // process all the neighbours of v, e.g. push them into 'nodeSet'
 745                         forall_adj_edges(e, v) {
 746                                 if (type(e) == Graph::generalization) {
 747                                         node w = e->source() == v ? e->target() : e->source();
 748                                         if (!processed[w->index()]) {
 749                                                 nodeSet.pushBack(w);
 750                                                 processed[w->index()] = true;
 751                                                 hierarchy->pushBack(e); // push e to the list of edges in this hierarchy
 752                                         }
 753                                 }
 754                         }
 755                 } while (!nodeSet.empty());
 756
 757                 // skip adding 'hierarchy', if it contains only one node
 758                 if (hierarchy->empty())
 759                         delete hierarchy;
 760                 else
 761                         list.pushBack(hierarchy);
 762         }
 763
 764         return list.size();
 765 }
 766
 767
 768
 769 void GraphAttributes::removeUnnecessaryBendsHV()
 770 {
 771         edge e;
 772         forall_edges(e,*m_pGraph)
 773         {
 774                 DPolyline &dpl = m_bends[e];
 775
 776                 if(dpl.size() < 3)
 777                         continue;
 778
 779                 ListIterator<DPoint> it1, it2, it3;
 780
 781                 it1 = dpl.begin();
 782                 it2 = it1.succ();
 783                 it3 = it2.succ();
 784
 785                 do {
 786                         if(((*it1).m_x == (*it2).m_x && (*it2).m_x == (*it3).m_x) ||
 787                                 ((*it1).m_y == (*it2).m_y && (*it2).m_y == (*it3).m_y))
 788                         {
 789                                 dpl.del(it2);
 790                                 it2 = it3;
 791                         } else {
 792                                 it1 = it2;
 793                                 it2 = it3;
 794                         }
 795
 796                         it3 = it2.succ();
 797                 } while(it3.valid());
 798         }
 799 }
 800
 801
 802 void GraphAttributes::writeXML(
 803         const String &fileName,
 804         const char* delimiter,
 805         const char* offset) const
 806 {
 807         ofstream os(fileName.cstr());
 808         writeXML(os,delimiter,offset);
 809 }
 810
 811
 812 void GraphAttributes::writeXML(
 813         ostream &os,
 814         const char* delimiter,
 815         const char* offset) const
 816 {
 817         NodeArray<int> id(*m_pGraph);
 818
 819         int nextId = 0;
 820
 821         os.setf(ios::showpoint);
 822         os.precision(10);
 823
 824         os << "<GRAPH TYPE=\"SSJ\">" << delimiter;
 825
 826         node v;
 827         forall_nodes(v,*m_pGraph) {
 828                 if (m_attributes & nodeLabel)
 829                 {
 830                         os << "<NODE NAME=\"" << m_nodeLabel[v] << "\">" << delimiter;
 831                 }
 832                 id[v] = nextId++;
 833
 834                 if (m_attributes & nodeGraphics) {
 835                         os << offset << "<POSITION X=\"" << m_x[v] << "\" ";
 836                         os << "Y=\"" << m_y[v] << "\" /> " << delimiter;
 837                         os << offset << "<SIZE WIDTH=\"" << m_width[v] << "\" ";
 838                         os << "HEIGHT=\"" << m_height[v] << "\" />"  << delimiter;
 839
 840                 }
 841                 os << "</NODE>" << delimiter;
 842         }
 843
 844         edge e;
 845         forall_edges(e,*m_pGraph) {
 846                 if (m_attributes & edgeLabel)
 847                 {
 848                         os << "<EDGE NAME=\"" << m_edgeLabel[e] << "\" ";
 849                 }
 850                 if (m_attributes & nodeLabel)
 851                 {
 852                         os << "SOURCE=\"" << m_nodeLabel[e->source()] << "\" ";
 853                         os << "TARGET=\"" << m_nodeLabel[e->target()] << "\" ";
 854                         os << "GENERALIZATION=\"" << (m_eType[e]==Graph::generalization?1:0) << "\">" << delimiter;
 855                 }
 856
 857                 if (m_attributes & edgeGraphics) {
 858
 859                         const DPolyline &dpl = m_bends[e];
 860                         if (!dpl.empty()) {
 861                                 os << offset << "<PATH TYPE=\"polyline\">" << delimiter;
 862 /*                              if (m_backward[e])
 863                                 {
 864                                         os << (*dpl.rbegin()).m_x  << " " <<  (*dpl.rbegin()).m_y << " ";
 865                                         if (dpl.size() > 1)
 866                                                 os << (*dpl.begin()).m_x << " " << (*dpl.begin()).m_y << " ";
 867                                 }
 868                                 else
 869                                 {
 870 */
 871                                 ListConstIterator<DPoint> iter;
 872                                 for (iter = dpl.begin(); iter.valid(); ++iter)
 873                                         os << offset << offset << "<POSITION X=\"" << (*iter).m_x << "\" "
 874                                                 << "Y=\"" << (*iter).m_y << "\" />" << delimiter;
 875 //                                      if (dpl.size() > 1)
 876 //                                              os << "<POSITION X=\"" << (*dpl.rbegin()).m_x << "\" "
 877 //                                                 << "Y=\"" << (*dpl.rbegin()).m_y << "\" />";
 878 //                              }
 879                                 os << offset << "</PATH>" << delimiter;
 880                         }
 881
 882                 }
 883
 884                 os << "</EDGE>" << delimiter; // edge
 885         }
 886
 887         os << "</GRAPH>";
 888 }
 889
 890 void GraphAttributes::addNodeCenter2Bends(int mode)
 891 {
 892         edge e;
 893         forall_edges(e, *m_pGraph) {
 894                 node v = e->source();
 895                 node w = e->target();
 896                 DPolyline &bendpoints = bends(e);
 897                 switch (mode) {
 898                 case 0 : // push center to the bends and return
 899                         bendpoints.pushFront(DPoint(x(v), y(v)));
 900                         bendpoints.pushBack (DPoint(x(w), y(w)));
 901                         break;
 902                 case 1 : // determine intersection with node and [center, last-bend-point]
 903                         bendpoints.pushFront(DPoint(x(v), y(v)));
 904                         bendpoints.pushBack (DPoint(x(w), y(w)));
 905                 case 2 : // determine intersection between node and last bend-segment
 906                         {
 907                                 DPoint sp1(x(v) - width(v)/2, y(v) - height(v)/2);
 908                                 DPoint sp2(x(v) - width(v)/2, y(v) + height(v)/2);
 909                                 DPoint sp3(x(v) + width(v)/2, y(v) + height(v)/2);
 910                                 DPoint sp4(x(v) + width(v)/2, y(v) - height(v)/2);
 911                                 DLine sourceRect[4] = {
 912                                         DLine(sp1, sp2),
 913                                         DLine(sp2, sp3),
 914                                         DLine(sp3, sp4),
 915                                         DLine(sp4, sp1)
 916                                 };
 917
 918                                 DPoint tp1(x(w) - width(w)/2, y(w) - height(w)/2);
 919                                 DPoint tp2(x(w) - width(w)/2, y(w) + height(w)/2);
 920                                 DPoint tp3(x(w) + width(w)/2, y(w) + height(w)/2);
 921                                 DPoint tp4(x(w) + width(w)/2, y(w) - height(w)/2);
 922                                 DLine targetRect[4] = {
 923                                         DLine(tp1, tp2),
 924                                         DLine(tp2, tp3),
 925                                         DLine(tp3, tp4),
 926                                         DLine(tp4, tp1)
 927                                 };
 928
 929                                 DRect source(sp1, sp3);
 930                                 DRect target(tp1, tp3);
 931
 932                                 DPoint c1 = bendpoints.popFrontRet();
 933                                 DPoint c2 = bendpoints.popBackRet();
 934
 935                                 while (!bendpoints.empty() && source.contains(bendpoints.front()))
 936                                         c1 = bendpoints.popFrontRet();
 937                                 while (!bendpoints.empty() && target.contains(bendpoints.back()))
 938                                         c2 = bendpoints.popBackRet();
 939
 940                                 DPoint a1, a2;
 941                                 int i;
 942                                 if (bendpoints.size() == 0) {
 943                                         DLine cross(c1, c2);
 944                                         for (i = 0; i < 4; i++)
 945                                                 if (cross.intersection(sourceRect[i], a1)) break;
 946                                         for (i = 0; i < 4; i++)
 947                                                 if (cross.intersection(targetRect[i], a2)) break;
 948                                 }
 949                                 else {
 950                                         DLine cross1(c1, bendpoints.front());
 951                                         for (i = 0; i < 4; i++)
 952                                                 if (cross1.intersection(sourceRect[i], a1)) break;
 953                                         DLine cross2(bendpoints.back(), c2);
 954                                         for (i = 0; i < 4; i++)
 955                                                 if (cross2.intersection(targetRect[i], a2)) break;
 956                                 }
 957                                 bendpoints.pushFront(a1);
 958                                 bendpoints.pushBack(a2);
 959                                 break;
 960                         }
 961                         OGDF_NODEFAULT
 962                 }
 963                 bendpoints.normalize();
 964         }
 965 }
 966
 967 /* Methods for OGML serialization */
 968
 969 // static helper method for mapping edge styles to ogml
 970 const char * GraphAttributes::edgeStyleToOGML(const GraphAttributes::EdgeStyle & edgeStyle)
 971 {
 972         switch (edgeStyle)  {
 973         case GraphAttributes::esNoPen:
 974                 return "esNoPen";
 975         case GraphAttributes::esSolid:
 976                 return "esSolid";
 977         case GraphAttributes::esDash:
 978                 return "esDash";
 979         case GraphAttributes::esDot:
 980                 return "esDot";
 981         case GraphAttributes::esDashdot:
 982                 return "esDashdot";
 983         case GraphAttributes::esDashdotdot:
 984                 return "esDashdotdot";
 985         default:
 986                 return "esSolid";
 987         }//switch
 988 }
 989
 990 // static helper method for mapping image alignments to ogml
 991 const char * GraphAttributes::imageAlignmentToOGML(const GraphAttributes::ImageAlignment &imgAlign)
 992 {
 993         switch (imgAlign)   {
 994         case GraphAttributes::TopLeft:
 995                 return "topLeft";
 996         case GraphAttributes::TopCenter:
 997                 return "topCenter";
 998         case GraphAttributes::TopRight:
 999                 return "topRight";
1000         case GraphAttributes::CenterLeft:
1001                 return "centerLeft";
1002         case GraphAttributes::Center:
1003                 return "center";
1004         case GraphAttributes::CenterRight:
1005                 return "centerRight";
1006         case GraphAttributes::BottomLeft:
1007                 return "bottomLeft";
1008         case GraphAttributes::BottomCenter:
1009                 return "bottomCenter";
1010         case GraphAttributes::BottomRight:
1011                 return "bottomRight";
1012         default:
1013                 return "center";
1014         }//switch
1015 }
1016
1017
1018 // static helper method for mapping image style to ogml
1019 const char * GraphAttributes::imageStyleToOGML(const GraphAttributes::ImageStyle &imgStyle)
1020 {
1021         switch (imgStyle)   {
1022         case GraphAttributes::FreeScale: return "freeScale";
1023         case GraphAttributes::FixScale:  return "fixScale";
1024         default: return "freeScale";
1025         }//switch
1026 }
1027
1028
1029 // static helper method for mapping brush patterns styles to ogml
1030 const char * GraphAttributes::brushPatternToOGML(const GraphAttributes::BrushPattern & brushPattern)
1031 {
1032         switch (brushPattern) {
1033         case GraphAttributes::bpNone:
1034                 return "bpNone";
1035         case GraphAttributes::bpSolid:
1036                 return "bpSolid";
1037         case GraphAttributes::bpDense1:
1038                 return "bpDense1";
1039         case GraphAttributes::bpDense2:
1040                 return "bpDense2";
1041         case GraphAttributes::bpDense3:
1042                 return "bpDense3";
1043         case GraphAttributes::bpDense4:
1044                 return "bpDense4";
1045         case GraphAttributes::bpDense5:
1046                 return "bpDense5";
1047         case GraphAttributes::bpDense6:
1048                 return "bpDense6";
1049         case GraphAttributes::bpDense7:
1050                 return "bpDense7";
1051         case GraphAttributes::bpHorizontal:
1052                 return "bpHorizontal";
1053         case GraphAttributes::bpVertical:
1054                 return "bpVertical";
1055         case GraphAttributes::bpCross:
1056                 return "bpCross";
1057         case GraphAttributes::BackwardDiagonal:
1058                 return "BackwardDiagonal";
1059         case GraphAttributes::ForwardDiagonal:
1060                 return "ForwardDiagonal";
1061         case GraphAttributes::DiagonalCross:
1062                 return "DiagonalCross";
1063         default:
1064                 return "bpSolid";
1065         }//switch
1066 }
1067
1068
1069 // static helper method for exchanging X(HT)ML-tag specific chars
1070 String GraphAttributes::formatLabel(const String& labelText)
1071 {
1072         size_t length = labelText.length();
1073         String formattedString;
1074
1075         for (size_t i = 0; i < length; ++i) {
1076                 char c = labelText[i];
1077                 if (c == '<') {
1078                         formattedString += "&lt;";
1079                 } else {
1080                         if (c == '>') {
1081                                 formattedString += "&gt;";
1082                                 if ((i+1 < length) && (labelText[i+1] != '\n'))
1083                                         formattedString += '\n';
1084                         } else {
1085                                 formattedString += c;
1086                         }
1087                 }
1088         }
1089         return formattedString;
1090 }
1091
1092 void GraphAttributes::writeSVG(const String &fileName, int fontSize, const String &fontColor) const
1093         {
1094                 ofstream os(fileName.cstr());
1095                 writeSVG(os, fontSize, fontColor);
1096         }
1097
1098 void GraphAttributes::writeSVG(ostream &os, int fontSize, const String &fontColor) const
1099 {
1100         os.setf(ios::showpoint);
1101         os.precision(10);
1102
1103         os << "<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n";
1104         os << "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" xmlns:ev=\"http://www.w3.org/2001/xml-events\" version=\"1.1\" baseProfile=\"full\" ";
1105
1106         // determine bounding box of svg
1107         OGDF_ASSERT((*m_pGraph).numberOfNodes() > 0);
1108         double maxX = x((*m_pGraph).firstNode());
1109         double maxY = y((*m_pGraph).firstNode());
1110         double minX = x((*m_pGraph).firstNode());
1111         double minY = y((*m_pGraph).firstNode());
1112         double nodeStrokeWidth;
1113
1114         node v;
1115         forall_nodes(v, *m_pGraph) {
1116                 if (m_attributes & nodeStyle) {
1117                         nodeStrokeWidth = lineWidthNode(v);
1118                 } else {
1119                         nodeStrokeWidth = 1.0;
1120                 }
1121                 maxX = max(maxX, x(v) + m_width[v]/2 + nodeStrokeWidth);
1122                 maxY = max(maxY, y(v) + m_height[v]/2 + nodeStrokeWidth);
1123                 minX = min(minX, x(v) - m_width[v]/2 - nodeStrokeWidth);
1124                 minY = min(minY, y(v) - m_height[v]/2 - nodeStrokeWidth);
1125         }
1126
1127         edge e;
1128         ListConstIterator<DPoint> it;
1129         double edgeStrokeWidth;
1130         forall_edges(e, *m_pGraph) {
1131                 if (m_attributes & edgeGraphics) {
1132                         if (attributes() & GraphAttributes::edgeStyle) {
1133                                 edgeStrokeWidth = edgeWidth(e);
1134                         } else {
1135                                 edgeStrokeWidth = 1.0;
1136                         }
1137                         const DPolyline &dpl = m_bends[e];
1138                         if (!dpl.empty()) {
1139                                 for(it = dpl.begin(); it.valid(); ++it) {
1140                                         maxX = max(maxX, (*it).m_x + edgeStrokeWidth);
1141                                         maxY = max(maxY, (*it).m_y + edgeStrokeWidth);
1142                                         minX = min(minX, (*it).m_x - edgeStrokeWidth);
1143                                         minY = min(minY, (*it).m_y - edgeStrokeWidth);
1144                                 }
1145                         }
1146                 }
1147         }
1148
1149         os << "width=\"" << (maxX - minX) << "px\" ";
1150         os << "height=\"" << (maxY - minY) << "px\" ";
1151         os << "viewBox=\"" << 0 << " " << 0 << " " << (maxX - minX) << " " << (maxY - minY) << "\">\n";
1152
1153         forall_edges(e, *m_pGraph) {
1154
1155                 const DPolyline &dpl = m_bends[e];
1156                 if (m_attributes & edgeGraphics) {
1157                         if (!dpl.empty()) { //polyline
1158                                 os << "<polyline fill=\"none\" ";
1159
1160                                 if ((m_attributes & edgeColor) && (m_edgeColor[e].length() != 0)) {
1161                                         os << "stroke=\"" << m_edgeColor[e] << "\" ";
1162                                 }
1163
1164                                 if (attributes() & GraphAttributes::edgeStyle) {
1165                                         os << "stroke-width=\"" << edgeWidth(e) << "px\" ";
1166                                 } else {
1167                                         os << "stroke=\"#000000\" ";
1168                                 }
1169
1170                                 os << "points=\"";
1171                                 node v = e->source();
1172                                 if(dpl.front().m_x < m_x[v] - m_width[v]/2 ||
1173                                                 dpl.front().m_x > m_x[v] + m_width[v]/2 ||
1174                                                 dpl.front().m_y < m_y[v] - m_height[v]/2 ||
1175                                                 dpl.front().m_y > m_y[v] + m_height[v]/2)
1176                                 {
1177                                         os << (m_x[e->source()] - minX) << "," << (m_y[e->source()] - minY) << " ";
1178                                 }
1179
1180                                 for(it = dpl.begin(); it.valid(); ++it)
1181                                 os << ((*it).m_x - minX) << "," << ((*it).m_y - minY) << " ";
1182
1183                                 v = e->target();
1184                                 if(dpl.back().m_x < m_x[v] - m_width[v]/2 ||
1185                                                 dpl.back().m_x > m_x[v] + m_width[v]/2 ||
1186                                                 dpl.back().m_y < m_y[v] - m_height[v]/2 ||
1187                                                 dpl.back().m_y > m_y[v] + m_height[v]/2)
1188                                 {
1189                                         os << (m_x[e->target()] - minX) << "," << (m_y[e->target()] - minY) << " ";
1190                                 }
1191
1192                                 os << "\"/>\n";
1193                         } else { // single line
1194                                 os << "<line ";
1195                                 os << "x1=\"" << x(e->source()) - minX << "\" ";
1196                                 os << "y1=\"" << y(e->source()) - minY << "\" ";
1197                                 os << "x2=\"" << x(e->target()) - minX << "\" ";
1198                                 os << "y2=\"" << y(e->target()) - minY<< "\" ";
1199
1200                                 if ((m_attributes & edgeColor) && (m_edgeColor[e].length() != 0)) {
1201                                         os << "stroke=\"" << m_edgeColor[e] << "\" ";
1202                                 } else {
1203                                         os << "stroke=\"#000000\" ";
1204                                 }
1205
1206                                 if (attributes() & GraphAttributes::edgeStyle) {
1207                                         os << "stroke-width=\"" << edgeWidth(e) << "px\" ";
1208                                 }
1209
1210                                 os << "/>\n";
1211                         }
1212                 }
1213         }
1214
1215         forall_nodes(v,*m_pGraph) {
1216                 if (m_attributes & nodeGraphics) {
1217                         switch (m_nodeShape[v])
1218                         {
1219                                 case rectangle:
1220                                 os << "<rect ";
1221                                 os << "x=\"" << m_x[v] - minX - m_width[v]/2 << "\" ";
1222                                 os << "y=\"" << m_y[v] - minY - m_height[v]/2 << "\" ";
1223                                 os << "width=\"" << m_width[v] << "\" ";
1224                                 os << "height=\"" << m_height[v] << "\" ";
1225                                 break;
1226                                 case oval:
1227                                 os << "<ellipse ";
1228                                 os << "cx=\"" << m_x[v] - minX << "\" ";
1229                                 os << "cy=\"" << m_y[v] - minY << "\" ";
1230                                 os << "rx=\"" << m_width[v]/2 << "\" ";
1231                                 os << "ry=\"" << m_height[v]/2 << "\" ";
1232                                 break;
1233                         }
1234
1235                         if (m_attributes & nodeColor) {
1236                                 os << "fill=\"" << m_nodeColor[v] << "\" ";
1237                                 os << "stroke=\"" << m_nodeLine[v] << "\" ";
1238                         }
1239
1240                         if (m_attributes & nodeStyle)
1241                         {
1242                                 os << "stroke-width=\"" << lineWidthNode(v) << "px\" ";
1243                         }
1244
1245                         os << "/>\n";
1246
1247                         if(m_attributes & nodeLabel){
1248                                 os << "<text x=\"" << m_x[v] - minX - m_width[v]/2 << "\" y=\"" << m_y[v] - minY << "\" textLength=\"" << m_width[v] << "\" font-size=\"" << fontSize << "\" fill=\"" << fontColor << "\" lengthAdjust=\"spacingAndGlyphs\">" << m_nodeLabel[v] << "</text>\n";
1249                         }
1250                 }
1251         }
1252
1253         os << "</svg>\n";
1254 }
1255
1256 } // end namespace ogdf