ext/OGDF/src/fileformats/simple_graph_load.cpp

   1 /*
   2  * $Revision: 2565 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-07 17:14:54 +0200 (Sa, 07. Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Implementation of simple graph loaders.
  11  *
  12  * See header-file simple_graph_load.h for more information.
  13  *
  14  * \author Markus Chimani, Carsten Gutwenger, Karsten Klein
  15  *
  16  * \par License:
  17  * This file is part of the Open Graph Drawing Framework (OGDF).
  18  *
  19  * \par
  20  * Copyright (C)<br>
  21  * See README.txt in the root directory of the OGDF installation for details.
  22  *
  23  * \par
  24  * This program is free software; you can redistribute it and/or
  25  * modify it under the terms of the GNU General Public License
  26  * Version 2 or 3 as published by the Free Software Foundation;
  27  * see the file LICENSE.txt included in the packaging of this file
  28  * for details.
  29  *
  30  * \par
  31  * This program is distributed in the hope that it will be useful,
  32  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  33  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  34  * GNU General Public License for more details.
  35  *
  36  * \par
  37  * You should have received a copy of the GNU General Public
  38  * License along with this program; if not, write to the Free
  39  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  40  * Boston, MA 02110-1301, USA.
  41  *
  42  * \see  http://www.gnu.org/copyleft/gpl.html
  43  ***************************************************************/
  44
  45 #include <ogdf/fileformats/simple_graph_load.h>
  46 #include <ogdf/basic/Logger.h>
  47 #include <ogdf/basic/HashArray.h>
  48 #include <ogdf/basic/String.h>
  49 #include <string.h>
  50 #include <sstream>
  51
  52 #define SIMPLE_LOAD_BUFFER_SIZE 2048
  53
  54 namespace ogdf {
  55
  56 bool loadRomeGraph(Graph &G, const char *fileName) {
  57         ifstream is(fileName);
  58         if(!is.good()) return false;
  59         return loadRomeGraph(G, is);
  60 }
  61
  62
  63 bool loadRomeGraph(Graph &G, istream &is) {
  64         G.clear();
  65
  66         char buffer[SIMPLE_LOAD_BUFFER_SIZE];
  67         bool readNodes = true;
  68         Array<node> indexToNode(1,250,0);
  69
  70         while(!is.eof())
  71         {
  72                 is.getline(buffer, SIMPLE_LOAD_BUFFER_SIZE-1);
  73
  74                 if(readNodes) {
  75                         if(buffer[0] == '#') {
  76                                 readNodes = false;
  77                                 continue;
  78                         }
  79
  80                         int index;
  81                         sscanf(buffer, "%d", &index);
  82                         if(index < 1 || index > 250 || indexToNode[index] != 0) {
  83                                 Logger::slout() << "loadRomeGraph: illegal node index!\n";
  84                                 return false;
  85                         }
  86
  87                         indexToNode[index] = G.newNode();
  88
  89                 } else {
  90                         int index, dummy, srcIndex, tgtIndex;
  91                         sscanf(buffer, "%d%d%d%d", &index, &dummy, &srcIndex, &tgtIndex);
  92
  93                         if(buffer[0] == 0)
  94                                 continue;
  95
  96                         if(srcIndex < 1 || srcIndex > 250 || tgtIndex < 1 || tgtIndex > 250 ||
  97                                 indexToNode[srcIndex] == 0 || indexToNode[tgtIndex] == 0)
  98                         {
  99                                 Logger::slout() << "loadRomeGraph: illegal node index in edge specification.\n";
 100                                 return false;
 101                         }
 102
 103                         G.newEdge(indexToNode[srcIndex], indexToNode[tgtIndex]);
 104                 }
 105         }
 106         return true;
 107 }
 108
 109
 110 bool loadChacoGraph(Graph &G, const char *fileName) {
 111         ifstream is(fileName);
 112         if(!is.good()) return false;
 113         return loadChacoGraph(G, is);
 114 }
 115
 116
 117 //Reads the chaco (graph partitioning) file format (usually a .graph file).
 118 bool loadChacoGraph(Graph &G, istream &is)
 119 {
 120         G.clear();
 121         char buffer[SIMPLE_LOAD_BUFFER_SIZE];
 122         int numN = 0, runEdges = 0, lineNum = 0;
 123         char* pch = NULL;
 124
 125         //try to read the first line to get the graph size
 126         if (!is.eof())
 127         {
 128                 //contains the size numbers
 129                 is.getline(buffer, SIMPLE_LOAD_BUFFER_SIZE-1);
 130                 //char* context = NULL;
 131                 //now read the number of nodes
 132                 pch = strtok(buffer, " ");//strtok_s(buffer, " ", &context);
 133                 if (pch == NULL) return false;
 134                 numN = atoi(pch);
 135                 //now read the number of edges
 136                 pch = strtok(NULL, " ");//strtok_s(NULL, " ", &context);
 137                 if (pch == NULL) return false;
 138                 // extension: check here for weights
 139         }
 140         else return false;
 141
 142         if (numN == 0) return true;
 143
 144         Array<node> indexToNode(1,numN,0);
 145         for (int i = 1; i <= numN; i++)
 146         {
 147                 //we assign new indexes here if they are not consecutive
 148                 //starting from 1 in the file! Thus, if the file is not in the correct
 149                 //format, node indices do not correspond to indices from the file.
 150                 indexToNode[i] = G.newNode();
 151         }
 152
 153         while(!is.eof())
 154         {
 155                 is.getline(buffer, SIMPLE_LOAD_BUFFER_SIZE-1);
 156                 if (strlen(buffer) == 0) continue;
 157                 lineNum++;
 158                 if (lineNum > numN)
 159                 {
 160                         cerr<< "File read error: More lines than expected number of nodes "<< lineNum <<":"<<numN<<"\n";
 161                         return false;
 162                 }
 163                 //char* context = NULL;
 164                 pch = strtok(buffer, " ");//strtok_s(buffer, " ", &context);
 165
 166                 while (pch != NULL)
 167                 {
 168                         int wind = atoi(pch);
 169                         if (wind < 1 || wind > numN)
 170                         {
 171                                 cerr<<"File read error: Illegal node index encountered\n";
 172                                 return false;
 173                         }
 174
 175                         //create edges
 176                         if (wind >= lineNum)
 177                         {
 178                                 G.newEdge( indexToNode[lineNum], indexToNode[wind] );
 179                                 runEdges++;
 180                         }
 181
 182                         pch = strtok(NULL, " ");//strtok_s(NULL, " ", &context);
 183                 }//while node entries
 184         }//while file
 185         //cout <<"Read #nodes: "<<numN<<", #edges "<<runEdges<<"\n";
 186         return true;
 187 }
 188
 189
 190 bool loadSimpleGraph(Graph &G, const char *fileName) {
 191         ifstream is(fileName);
 192         if(!is.good()) return false;
 193         return loadSimpleGraph(G, is);
 194 }
 195
 196
 197 bool loadSimpleGraph(Graph &G, istream &is) {
 198         G.clear();
 199
 200         char buffer[SIMPLE_LOAD_BUFFER_SIZE];
 201         int numN = 0;
 202
 203         //try to read the two first lines to get the graph size
 204         if (!is.eof())
 205         {
 206                 char* pch;
 207                 //contains the name
 208                 is.getline(buffer, SIMPLE_LOAD_BUFFER_SIZE-1);
 209                 pch = strtok(buffer, " ");
 210                 if (strcmp(pch, "*BEGIN") != 0) return false;
 211                 if (!is.eof())
 212                 {       //contains the size of the graph
 213                         is.getline(buffer, SIMPLE_LOAD_BUFFER_SIZE-1);
 214                         pch = strtok(buffer, " ");
 215                         if (strcmp(pch, "*GRAPH") != 0) return false;
 216                         //now read the number of nodes
 217                         pch = strtok(NULL, " ");
 218                         if (pch == NULL) return false;
 219                         numN = atoi(pch);
 220                         //now read the number of edges
 221                         pch = strtok(NULL, " ");
 222                         if (pch == NULL) return false;
 223                 }
 224                 else return false;
 225         }
 226         else return false;
 227
 228         if (numN == 0) return true;
 229
 230         Array<node> indexToNode(1,numN,0);
 231         for (int i = 1; i <= numN; i++)
 232         {
 233                 //we assign new indexes here if they are not consecutive
 234                 //starting from 1 in the file!
 235                 indexToNode[i] = G.newNode();
 236         }
 237
 238         while(!is.eof())
 239         {
 240                 is.getline(buffer, SIMPLE_LOAD_BUFFER_SIZE-1);
 241
 242                 if(buffer[0] == 0)
 243                         continue;
 244
 245                 int srcIndex, tgtIndex;
 246                 sscanf(buffer, "%d%d", &srcIndex, &tgtIndex);
 247                 char* pch;
 248                 pch = strtok(buffer, " ");
 249                 if ( (strcmp(pch, "*END") == 0) || (strcmp(pch, "*CHECKSUM") == 0) )
 250                         continue;
 251
 252                 if(srcIndex < 1 || srcIndex > numN || tgtIndex < 1 || tgtIndex > numN)
 253                         {
 254                                 Logger::slout() << "loadSimpleGraph: illegal node index in edge specification.\n";
 255                                 return false;
 256                         }
 257
 258                         G.newEdge(indexToNode[srcIndex], indexToNode[tgtIndex]);
 259         }
 260         return true;
 261 }
 262
 263
 264 #define YG_NEXTBYTE(x) x = fgetc(lineStream);   if(x == EOF || x == '\n') { Logger::slout() << "loadYGraph: line too short!"; return false; } x &= 0x3F;
 265
 266 bool loadYGraph(Graph &G, FILE *lineStream) {
 267         G.clear();
 268
 269         char c,s;
 270         int n,i,j;
 271
 272         YG_NEXTBYTE(n);
 273         Array<node> A(n);
 274         for(i=n; i-->0;)
 275                 A[i] = G.newNode();
 276
 277         s = 0;
 278         for(i = 1; i<n; ++i) {
 279                 for(j = 0; j<i; ++j) {
 280                         if(!s) {
 281                                 YG_NEXTBYTE(c);
 282                                 s = 5;
 283                         } else --s;
 284                         if(c & (1 << s))
 285                                 G.newEdge(A[i],A[j]);
 286                 }
 287         }
 288
 289         c = fgetc(lineStream);
 290         if(c != EOF && c != '\n') {
 291                 Logger::slout(Logger::LL_MINOR) << "loadYGraph: Warning: line too long! ignoring...";
 292         }
 293         return true;
 294 }
 295
 296
 297 bool loadBenchHypergraph(Graph &G, List<node>& hypernodes, List<edge> *shell, const char *fileName) {
 298         ifstream is(fileName);
 299         if(!is.good()) return false;
 300         return loadBenchHypergraph(G, hypernodes, shell, is);
 301 }
 302
 303
 304 bool loadPlaHypergraph(Graph &G, List<node>& hypernodes, List<edge> *shell, const char *fileName) {
 305         ifstream is(fileName);
 306         if(!is.good()) return false;
 307         return loadPlaHypergraph(G, hypernodes, shell, is);
 308 }
 309
 310
 311 int extractIdentifierLength(char* from, int line) {
 312         int p = 1;
 313         while(from[p]!=',' && from[p]!=')' && from[p]!=' ' && from[p]!='(') {
 314                 ++p;
 315                 if(from[p]=='\0') {
 316                         cerr << "Loading Hypergraph: Error in line " << line <<
 317                                 ". Expected comma, bracket or whitespace before EOL; Ignoring.\n";
 318                         break;
 319                 }
 320         }
 321         return p;
 322 }
 323
 324
 325 int newStartPos(char* from, int line) {
 326         int p = 0;
 327         while(from[p]=='\t' || from[p]==' ' || from[p]==',') {
 328                 ++p;
 329                 if(from[p]=='\0') {
 330                         cerr << "Loading Hypergraph: Error in line " << line <<
 331                                 ". Expected whitespace or delimiter before EOL; Ignoring.\n";
 332                         break;
 333                 }
 334         }
 335
 336         return p;
 337 }
 338
 339
 340 int findOpen(char* from, int line) {
 341         int p = 0;
 342         while(from[p]!='(') {
 343                 ++p;
 344                 if(from[p]=='\0') {
 345                         cerr << "Loading Hypergraph: Error in line " << line <<
 346                                 ". Expected opening bracket before EOL; Ignoring.\n";
 347                         break;
 348                 }
 349         }
 350         return p;
 351 }
 352
 353
 354 String inName(const String& s) {
 355         size_t n = s.length();
 356         char *t = new char[n+4];
 357         ogdf::strcpy(t,s.length()+1,s.cstr());
 358         t[n] = '%';t[n+1] = '$';t[n+2] = '@';t[n+3] = '\0';
 359         String u(t);
 360         delete[] t;
 361         return u;
 362 }
 363
 364
 365 bool loadBenchHypergraph(Graph &G, List<node>& hypernodes, List<edge> *shell, istream &is) {
 366         G.clear();
 367         hypernodes.clear();
 368         if(shell) shell->clear();
 369         node si,so;
 370
 371         char buffer[SIMPLE_LOAD_BUFFER_SIZE];
 372
 373 //      Array<node> indexToNode(1,250,0);
 374
 375         HashArray<String,node> hm(0);
 376
 377         if(shell) {
 378 //              hypernodes.pushBack( si=G.newNode() );
 379 //              hypernodes.pushBack( so=G.newNode() );
 380 //              shell.pushBack( G.newEdge( si, so ) );
 381                 shell->pushBack( G.newEdge( si=G.newNode(), so=G.newNode() ) );
 382         }
 383
 384         int line = 0;
 385         while(!is.eof())
 386         {
 387                 ++line;
 388                 is.getline(buffer, SIMPLE_LOAD_BUFFER_SIZE-1);
 389                 size_t l = strlen(buffer);
 390                 if( l > 0 && buffer[l-1]=='\r' ) { // DOS line
 391                         buffer[l-1]='\0';
 392                 }
 393                 if(!strlen(buffer) || buffer[0]==' ' || buffer[0]=='#') continue;
 394                 if(!strncmp("INPUT(",buffer,6)) {
 395                         String s(extractIdentifierLength(buffer+6, line),buffer+6);
 396                         node n = G.newNode();
 397                         hm[s] = n;
 398                         hypernodes.pushBack(n);
 399                         if(shell) shell->pushBack( G.newEdge(si,n) );
 400 //                      cout << "input: " << s << " -> " << n->index() << "\n";
 401                 } else if(!strncmp("OUTPUT(",buffer,7)) {
 402                         String s(extractIdentifierLength(buffer+7, line),buffer+7);
 403                         node n = G.newNode();
 404                         hm[s] = n;
 405                         hypernodes.pushBack(n);
 406                         if(shell) shell->pushBack( G.newEdge(n,so) );
 407 //                      cout << "output: " << s << " -> " << n->index() << "\n";
 408                 } else {
 409                         int p = extractIdentifierLength(buffer, line);
 410                         String s(p,buffer); // gatename
 411                         node m = hm[s]; // found as outputname -> refOut
 412                         if(!m) {
 413                                 m = hm[inName(s)]; // found as innernode input.
 414                                 if(!m) { // generate it anew.
 415                                         node in = G.newNode();
 416                                         node out = G.newNode();
 417                                         hm[inName(s)] = in;
 418                                         hm[s] = out;
 419                                         hypernodes.pushBack(out);
 420                                         G.newEdge(in,out);
 421                                         m = in;
 422                                 }
 423                         }
 424                         p = findOpen(buffer, line);
 425                         do {
 426                                 ++p;
 427                                 p += newStartPos(buffer+p, line);
 428                                 int pp = extractIdentifierLength(buffer+p, line);
 429                                 String s(pp,buffer+p);
 430                                 p += pp;
 431                                 node mm = hm[s];
 432                                 if(!mm) {
 433                                         // new
 434                                         node in = G.newNode();
 435                                         node out = G.newNode();
 436                                         hm[inName(s)] = in;
 437                                         hm[s] = out;
 438                                         hypernodes.pushBack(out);
 439                                         G.newEdge(in,out);
 440                                         mm = out;
 441                                 }
 442                                 G.newEdge(mm,m);
 443 //                              cout << "Edge: " << s << "(" << hm[s]->index() << ") TO " << m->index() << "\n";
 444                         } while(buffer[p] == ',');
 445                 }
 446         }
 447
 448         return true;
 449 }
 450
 451 bool loadPlaHypergraph(Graph &G, List<node>& hypernodes, List<edge> *shell, istream &is) {
 452         G.clear();
 453         hypernodes.clear();
 454         if(shell) shell->clear();
 455         node si,so;
 456
 457         int i;
 458         int numGates;
 459         is >> numGates;
 460 //      cout << "numGates=" << numGates << "\n";
 461
 462         Array<node> outport(1,numGates);
 463         for(i = 1; i<=numGates; ++i) {
 464                 node out = G.newNode();
 465                 outport[i] = out;
 466                 hypernodes.pushBack(out);
 467         }
 468
 469         for(i = 1; i<=numGates; ++i) {
 470                 int id, type, numinput;
 471                 is >> id >> type >> numinput;
 472 //              cout << "Gate=" << i << ", type=" << type << ", numinput=" << numinput << ":";
 473                 if(id != i) cerr << "Error loading PLA hypergraph: ID and linenum does not match\n";
 474                 node in = G.newNode();
 475                 G.newEdge(in,outport[i]);
 476                 for(int j=0; j<numinput; ++j) {
 477                         int from;
 478                         is >> from;
 479 //                      cout << " " << from;
 480                         G.newEdge(outport[from],in);
 481                 }
 482 //              cout << "\n";
 483                 is.ignore(500,'\n');
 484         }
 485
 486         if(shell) {
 487                 shell->pushBack( G.newEdge( si=G.newNode(), so=G.newNode() ) );
 488                 node n;
 489                 forall_nodes(n,G) {
 490                         if(n->degree()==1) {
 491                                 if(n->firstAdj()->theEdge()->source()==n) { //input
 492                                         shell->pushBack( G.newEdge( si, n ) );
 493                                 } else { // output
 494                                         shell->pushBack( G.newEdge( n, so ) );
 495                                 }
 496                         }
 497                 }
 498         }
 499
 500         return true;
 501 }
 502
 503
 504
 505 bool loadEdgeListSubgraph(Graph &G, List<edge> &delEdges, const char *fileName)
 506 {
 507         ifstream is(fileName);
 508         if(!is.good()) return false;
 509         return loadEdgeListSubgraph(G, delEdges, is);
 510 }
 511
 512
 513 bool loadEdgeListSubgraph(Graph &G, List<edge> &delEdges, istream &is)
 514 {
 515         G.clear();
 516         delEdges.clear();
 517
 518         char buffer[SIMPLE_LOAD_BUFFER_SIZE];
 519
 520         if(is.eof()) return false;
 521         is.getline(buffer, SIMPLE_LOAD_BUFFER_SIZE-1);
 522
 523         int n = 0, m = 0, m_del = 0;
 524         sscanf(buffer, "%d%d%d", &n, &m, &m_del);
 525
 526         if(n < 0 || m < 0 || m_del < 0)
 527                 return false;
 528
 529         Array<node> indexToNode(n);
 530         for(int i = 0; i < n; ++i)
 531                 indexToNode[i] = G.newNode();
 532
 533         int m_all = m + m_del;
 534         for(int i = 0; i < m_all; ++i) {
 535                 if(is.eof()) return false;
 536
 537                 is.getline(buffer, SIMPLE_LOAD_BUFFER_SIZE-1);
 538                 int src, tgt;
 539                 sscanf(buffer, "%d%d", &src, &tgt);
 540                 if(src < 0 || src >= n || tgt < 0 || tgt >= n)
 541                         return false;
 542
 543                 edge e = G.newEdge(indexToNode[src], indexToNode[tgt]);
 544
 545                 if(i >= m)
 546                         delEdges.pushBack(e);
 547         }
 548
 549         return true;
 550 }
 551
 552
 553 bool saveEdgeListSubgraph(const Graph &G, const List<edge> &delEdges, const char *fileName)
 554 {
 555         ofstream os(fileName);
 556         return saveEdgeListSubgraph(G,delEdges,os);
 557 }
 558
 559
 560 bool saveEdgeListSubgraph(const Graph &G, const List<edge> &delEdges, ostream &os)
 561 {
 562         if(!os.good()) return false;
 563
 564         const int m_del = delEdges.size();
 565         const int n = G.numberOfNodes();
 566         const int m = G.numberOfEdges() - m_del;
 567
 568         os << n << " " << m << " " << m_del << "\n";
 569
 570         EdgeArray<bool> markSub(G,true);
 571         for(ListConstIterator<edge> it = delEdges.begin(); it.valid(); ++it)
 572                 markSub[*it] = false;
 573
 574         NodeArray<int> index(G);
 575         int i = 0;
 576         node v;
 577         forall_nodes(v,G)
 578                 index[v] = i++;
 579
 580         edge e;
 581         forall_edges(e,G)
 582                 if(markSub[e])
 583                         os << index[e->source()] << " " << index[e->target()] << "\n";
 584
 585         for(ListConstIterator<edge> it = delEdges.begin(); it.valid(); ++it)
 586                 os << index[(*it)->source()] << " " << index[(*it)->target()] << "\n";
 587
 588
 589         return true;
 590 }
 591
 592
 593 bool loadChallengeGraph(Graph &G, GridLayout &gl, const char *fileName)
 594 {
 595         ifstream is(fileName);
 596         if(!is.good()) return false;
 597         return loadChallengeGraph(G, gl, is);
 598 }
 599
 600
 601 #define CHALLENGE_LOAD_BUFFER_SIZE 4096
 602
 603 bool loadChallengeGraph(Graph &G, GridLayout &gl, istream &is)
 604 {
 605         G.clear();
 606         char buffer[CHALLENGE_LOAD_BUFFER_SIZE];
 607
 608         int n = -1;
 609         do {
 610                 if(is.eof()) return false;
 611                 is.getline(buffer,CHALLENGE_LOAD_BUFFER_SIZE);
 612                 if(buffer[0] != '#') {
 613                         sscanf(buffer, "%d", &n);
 614                         if(n < 0) return false;
 615                 }
 616         } while(n < 0);
 617
 618         Array<node> indexToNode(n);
 619         for(int i = 0; i < n; ) {
 620                 if(is.eof()) return false;
 621                 is.getline(buffer,CHALLENGE_LOAD_BUFFER_SIZE);
 622
 623                 if(buffer[0] != '#') {
 624                         node v = G.newNode();
 625                         sscanf(buffer, "%d%d", &gl.x(v), &gl.y(v));
 626                         indexToNode[i++] = v;
 627                 }
 628         }
 629
 630         while(!is.eof()) {
 631                 is.getline(buffer,CHALLENGE_LOAD_BUFFER_SIZE);
 632
 633                 if(buffer[0] != '#' && buffer[0] != 0) {
 634                         std::stringstream ss(buffer);
 635                         int srcIndex, tgtIndex;
 636
 637                         if(ss.eof()) return false;
 638                         ss >> srcIndex;
 639                         if(srcIndex < 0 || srcIndex >= n) return false;
 640
 641                         if(ss.eof()) return false;
 642                         ss >> tgtIndex;
 643                         if(tgtIndex < 0 || tgtIndex >= n) return false;
 644
 645                         node src = indexToNode[srcIndex];
 646                         node tgt = indexToNode[tgtIndex];
 647                         edge e = G.newEdge(src,tgt);
 648
 649                         std::string symbol;
 650                         if(ss.eof()) return false;
 651                         ss >> symbol;
 652                         if(symbol != "[") return false;
 653
 654                         IPolyline &ipl = gl.bends(e);;
 655                         for(;;) {
 656                                 if(ss.eof()) return false;
 657                                 ss >> symbol;
 658                                 if(symbol == "]") break;
 659
 660                                 IPoint ip;
 661                                 ip.m_x = atoi(symbol.c_str());
 662                                 if(ss.eof()) return false;
 663                                 ss >> ip.m_y;
 664                                 ipl.pushBack(ip);
 665                         }
 666                 }
 667         }
 668
 669         return true;
 670 }
 671
 672
 673 bool saveChallengeGraph(const Graph &G, const GridLayout &gl, const char *fileName)
 674 {
 675         ofstream os(fileName);
 676         return saveChallengeGraph(G, gl, os);
 677 }
 678
 679
 680 bool saveChallengeGraph(const Graph &G, const GridLayout &gl, ostream &os)
 681 {
 682         if(!os.good()) return false;
 683
 684         os << "# Number of Nodes\n";
 685         os << G.numberOfNodes() << "\n";
 686
 687         os << "# Nodes\n";
 688         NodeArray<int> index(G);
 689         int i = 0;
 690         node v;
 691         forall_nodes(v,G) {
 692                 os << gl.x(v) << " " << gl.y(v) << "\n";
 693                 index[v] = i++;
 694         }
 695
 696         os << "# Edges\n";
 697         edge e;
 698         forall_edges(e,G) {
 699                 os << index[e->source()] << " " << index[e->target()] << " [";
 700                 const IPolyline &ipl = gl.bends(e);
 701                 for(ListConstIterator<IPoint> it = ipl.begin(); it.valid(); ++it)
 702                         os << " " << (*it).m_x << " " << (*it).m_y;
 703                 os << " ]\n";
 704         }
 705
 706         return true;
 707 }
 708
 709
 710 }