gts/graph.c

   1 /* GTS - Library for the manipulation of triangulated surfaces
   2  * Copyright (C) 1999 Stéphane Popinet
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public
  15  * License along with this library; if not, write to the
  16  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  17  * Boston, MA 02111-1307, USA.
  18  */
  19
  20 #include <math.h>
  21 #include <stdlib.h>
  22 #include "gts.h"
  23
  24 /* GtsGNode */
  25
  26 gboolean gts_allow_floating_gnodes = FALSE;
  27
  28 static void gnode_remove_container (GtsContainee * i, GtsContainer * c)
  29 {
  30   (* GTS_CONTAINEE_CLASS (GTS_OBJECT_CLASS (gts_gnode_class ())->parent_class)->remove_container) (i, c);
  31   if (GTS_SLIST_CONTAINEE (i)->containers == NULL &&
  32       !gts_allow_floating_gnodes &&
  33       !GTS_OBJECT_DESTROYED(GTS_OBJECT (i)))
  34     gts_object_destroy (GTS_OBJECT (i));
  35 }
  36
  37 static void gnode_class_init (GtsGNodeClass * klass)
  38 {
  39   klass->weight = NULL;
  40
  41   GTS_CONTAINEE_CLASS (klass)->remove_container = gnode_remove_container;
  42 }
  43
  44 static void gnode_init (GtsGNode * n)
  45 {
  46   n->level = 0;
  47 }
  48
  49 /**
  50  * gts_gnode_class:
  51  *
  52  * Returns: the #GtsGNodeClass.
  53  */
  54 GtsGNodeClass * gts_gnode_class (void)
  55 {
  56   static GtsGNodeClass * klass = NULL;
  57
  58   if (klass == NULL) {
  59     GtsObjectClassInfo gnode_info = {
  60       "GtsGNode",
  61       sizeof (GtsGNode),
  62       sizeof (GtsGNodeClass),
  63       (GtsObjectClassInitFunc) gnode_class_init,
  64       (GtsObjectInitFunc) gnode_init,
  65       (GtsArgSetFunc) NULL,
  66       (GtsArgGetFunc) NULL
  67     };
  68     klass =
  69       gts_object_class_new (GTS_OBJECT_CLASS (gts_slist_container_class ()),
  70                             &gnode_info);
  71   }
  72
  73   return klass;
  74 }
  75
  76 /**
  77  * gts_gnode_new:
  78  * @klass: a #GtsGNodeClass.
  79  *
  80  * Returns: a new #GtsGNode.
  81  */
  82 GtsGNode * gts_gnode_new (GtsGNodeClass * klass)
  83 {
  84   GtsGNode * object;
  85
  86   object = GTS_GNODE (gts_object_new (GTS_OBJECT_CLASS (klass)));
  87
  88   return object;
  89 }
  90
  91 /**
  92  * gts_gnode_foreach_neighbor:
  93  * @n: a #GtsGNode.
  94  * @g: a #GtsGraph or %NULL.
  95  * @func: a #GtsFunc.
  96  * @data: user data to be passed to @func.
  97  *
  98  * Calls @func for each neighbor #GtsGNode of @n (belonging to @g if
  99  * @g is not %NULL.
 100  */
 101 void gts_gnode_foreach_neighbor (GtsGNode * n,
 102                                  GtsGraph * g,
 103                                  GtsFunc func,
 104                                  gpointer data)
 105 {
 106   GSList * i;
 107
 108   g_return_if_fail (n != NULL);
 109   g_return_if_fail (func != NULL);
 110
 111   i = GTS_SLIST_CONTAINER (n)->items;
 112   while (i) {
 113     GtsGNode * n1 = GTS_GNODE_NEIGHBOR (n, i->data);
 114     if (g == NULL || gts_containee_is_contained (GTS_CONTAINEE (n1),
 115                                                  GTS_CONTAINER (g)))
 116       (* func) (n1, data);
 117     i = i->next;
 118   }
 119 }
 120
 121 /**
 122  * gts_gnode_foreach_edge:
 123  * @n: a #GtsGNode.
 124  * @g: a #GtsGraph or %NULL.
 125  * @func: a #GtsFunc.
 126  * @data: user data to be passed to @func.
 127  *
 128  * Calls @func for each #GtsGEdge connecting @n to another #GtsGNode
 129  * (belonging to @g if @g is not %NULL.
 130  */
 131 void gts_gnode_foreach_edge (GtsGNode * n,
 132                              GtsGraph * g,
 133                              GtsFunc func,
 134                              gpointer data)
 135 {
 136   GSList * i;
 137
 138   g_return_if_fail (n != NULL);
 139   g_return_if_fail (func != NULL);
 140
 141   i = GTS_SLIST_CONTAINER (n)->items;
 142   while (i) {
 143     GtsGNode * n1 = GTS_GNODE_NEIGHBOR (n, i->data);
 144     if (g == NULL || gts_containee_is_contained (GTS_CONTAINEE (n1),
 145                                                  GTS_CONTAINER (g)))
 146       (* func) (i->data, data);
 147     i = i->next;
 148   }
 149 }
 150
 151 /**
 152  * gts_gnode_degree:
 153  * @n: a #GtsGNode.
 154  * @g: a #GtsGraph or %NULL.
 155  *
 156  * Returns: the number of neighbors of @n (belonging to @g if @g is not %NULL).
 157  */
 158 guint gts_gnode_degree (GtsGNode * n,
 159                         GtsGraph * g)
 160 {
 161   GSList * i;
 162   guint nn = 0;
 163
 164   g_return_val_if_fail (n != NULL, 0);
 165
 166   i = GTS_SLIST_CONTAINER (n)->items;
 167   while (i) {
 168     GtsGNode * n1 = GTS_GNODE_NEIGHBOR (n, i->data);
 169     if (g == NULL || gts_containee_is_contained (GTS_CONTAINEE (n1),
 170                                                  GTS_CONTAINER (g)))
 171       nn++;
 172     i = i->next;
 173   }
 174
 175   return nn;
 176 }
 177
 178 /**
 179  * gts_gnode_move_cost:
 180  * @n: a #GtsGNode.
 181  * @src: a #GtsGraph containing @n.
 182  * @dst: another #GtsGraph.
 183  *
 184  * Returns: the cost (increase in the sum of the weights of the edges cut) of
 185  * moving @n from @src to @dst.
 186  */
 187 gfloat gts_gnode_move_cost (GtsGNode * n,
 188                             GtsGraph * src,
 189                             GtsGraph * dst)
 190 {
 191   GSList * i;
 192   gfloat cost = 0.;
 193
 194   g_return_val_if_fail (n != NULL, G_MAXFLOAT);
 195   g_return_val_if_fail (src != NULL, G_MAXFLOAT);
 196   g_return_val_if_fail (dst != NULL, G_MAXFLOAT);
 197   g_return_val_if_fail (gts_containee_is_contained (GTS_CONTAINEE (n),
 198                                                     GTS_CONTAINER (src)),
 199                         G_MAXFLOAT);
 200
 201   i = GTS_SLIST_CONTAINER (n)->items;
 202   while (i) {
 203     GtsGEdge * ge = i->data;
 204     GtsGNode * neighbor = GTS_GNODE_NEIGHBOR (n, ge);
 205
 206     if (gts_containee_is_contained (GTS_CONTAINEE (neighbor),
 207                                     GTS_CONTAINER (src)))
 208       cost += gts_gedge_weight (ge);
 209     else if (gts_containee_is_contained (GTS_CONTAINEE (neighbor),
 210                                          GTS_CONTAINER (dst)))
 211       cost -= gts_gedge_weight (ge);
 212     i = i->next;
 213   }
 214
 215   return cost;
 216 }
 217
 218 /**
 219  * gts_gnode_weight:
 220  * @n: a #GtsGNode.
 221  *
 222  * Returns: the weight of @n as defined by the weight() method of the
 223  * #GtsGNodeClass.
 224  */
 225 gfloat gts_gnode_weight (GtsGNode * n)
 226 {
 227   g_return_val_if_fail (n != NULL, 0.);
 228
 229   if (GTS_GNODE_CLASS (GTS_OBJECT (n)->klass)->weight)
 230     return (* GTS_GNODE_CLASS (GTS_OBJECT (n)->klass)->weight) (n);
 231   return 1.;
 232 }
 233
 234 /* GtsNGNode */
 235
 236 static void ngnode_init (GtsNGNode * n)
 237 {
 238   n->id = 0;
 239 }
 240
 241 /**
 242  * gts_ngnode_class:
 243  *
 244  * Returns: the #GtsNGNodeClass.
 245  */
 246 GtsNGNodeClass * gts_ngnode_class (void)
 247 {
 248   static GtsNGNodeClass * klass = NULL;
 249
 250   if (klass == NULL) {
 251     GtsObjectClassInfo ngnode_info = {
 252       "GtsNGNode",
 253       sizeof (GtsNGNode),
 254       sizeof (GtsNGNodeClass),
 255       (GtsObjectClassInitFunc) NULL,
 256       (GtsObjectInitFunc) ngnode_init,
 257       (GtsArgSetFunc) NULL,
 258       (GtsArgGetFunc) NULL
 259     };
 260     klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_gnode_class ()),
 261                                   &ngnode_info);
 262   }
 263
 264   return klass;
 265 }
 266
 267 /**
 268  * gts_ngnode_new:
 269  * @klass: a #GtsNGNodeClass.
 270  *
 271  * Returns: a new #GtsNGNode with identity @id.
 272  */
 273 GtsNGNode * gts_ngnode_new (GtsNGNodeClass * klass,
 274                             guint id)
 275 {
 276   GtsNGNode * n;
 277
 278   n = GTS_NGNODE (gts_gnode_new (GTS_GNODE_CLASS (klass)));
 279   n->id = id;
 280
 281   return n;
 282 }
 283
 284 /* GtsWGNode */
 285
 286 static gfloat wgnode_weight (GtsGNode * n)
 287 {
 288   return GTS_WGNODE (n)->weight;
 289 }
 290
 291 static void wgnode_class_init (GtsWGNodeClass * klass)
 292 {
 293   GTS_GNODE_CLASS (klass)->weight = wgnode_weight;
 294 }
 295
 296 static void wgnode_init (GtsWGNode * n)
 297 {
 298   n->weight = 1.;
 299 }
 300
 301 /**
 302  * gts_wgnode_class:
 303  *
 304  * Returns: the #GtsWGNodeClass.
 305  */
 306 GtsWGNodeClass * gts_wgnode_class (void)
 307 {
 308   static GtsWGNodeClass * klass = NULL;
 309
 310   if (klass == NULL) {
 311     GtsObjectClassInfo wgnode_info = {
 312       "GtsWGNode",
 313       sizeof (GtsWGNode),
 314       sizeof (GtsWGNodeClass),
 315       (GtsObjectClassInitFunc) wgnode_class_init,
 316       (GtsObjectInitFunc) wgnode_init,
 317       (GtsArgSetFunc) NULL,
 318       (GtsArgGetFunc) NULL
 319     };
 320     klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_gnode_class ()),
 321                                   &wgnode_info);
 322   }
 323
 324   return klass;
 325 }
 326
 327 /**
 328  * gts_wgnode_new:
 329  * @klass: a #GtsWGNodeClass.
 330  * @weight: the weight of the #GtsWGNode to create.
 331  *
 332  * Returns: a new #GtsWGNode of weight @weight.
 333  */
 334 GtsWGNode * gts_wgnode_new (GtsWGNodeClass * klass,
 335                             gfloat weight)
 336 {
 337   GtsWGNode * n;
 338
 339   n = GTS_WGNODE (gts_gnode_new (GTS_GNODE_CLASS (klass)));
 340   n->weight = weight;
 341
 342   return n;
 343 }
 344
 345 /* GtsPNode */
 346
 347 static void pnode_write (GtsGNode * n, FILE * fp)
 348 {
 349   if (GTS_IS_NVERTEX (GTS_PNODE (n)->data))
 350     fprintf (fp, "label=\"%p:%s\",",
 351              GTS_PNODE (n)->data,
 352              GTS_NVERTEX (GTS_PNODE (n)->data)->name);
 353   else
 354     fprintf (fp, "label=\"%p\",", GTS_PNODE (n)->data);
 355 }
 356
 357 static void pnode_class_init (GtsPNodeClass * klass)
 358 {
 359   GTS_GNODE_CLASS (klass)->write = pnode_write;
 360 }
 361
 362 static void pnode_init (GtsPNode * pn)
 363 {
 364   pn->data = NULL;
 365 }
 366
 367 /**
 368  * gts_pnode_class:
 369  *
 370  * Returns: the #GtsPNodeClass.
 371  */
 372 GtsPNodeClass * gts_pnode_class (void)
 373 {
 374   static GtsPNodeClass * klass = NULL;
 375
 376   if (klass == NULL) {
 377     GtsObjectClassInfo pnode_info = {
 378       "GtsPNode",
 379       sizeof (GtsPNode),
 380       sizeof (GtsPNodeClass),
 381       (GtsObjectClassInitFunc) pnode_class_init,
 382       (GtsObjectInitFunc) pnode_init,
 383       (GtsArgSetFunc) NULL,
 384       (GtsArgGetFunc) NULL
 385     };
 386     klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_gnode_class ()),
 387                                   &pnode_info);
 388   }
 389
 390   return klass;
 391 }
 392
 393 /**
 394  * gts_pnode_new:
 395  * @klass: a #GtsPNodeClass.
 396  * @data: user data.
 397  *
 398  * Returns: a new #GtsPNode associated with @data.
 399  */
 400 GtsPNode * gts_pnode_new (GtsPNodeClass * klass, gpointer data)
 401 {
 402   GtsPNode * pn;
 403
 404   pn = GTS_PNODE (gts_object_new (GTS_OBJECT_CLASS (klass)));
 405   pn->data = data;
 406
 407   return pn;
 408 }
 409
 410 /* GtsFNode */
 411
 412 static void fnode_write (GtsGNode * n, FILE * fp)
 413 {
 414   fprintf (fp, "label=\"%p\",", GTS_FNODE (n)->f);
 415 }
 416
 417 static void fnode_class_init (GtsGNodeClass * klass)
 418 {
 419   klass->write = fnode_write;
 420 }
 421
 422 static void fnode_init (GtsFNode * fn)
 423 {
 424   fn->f = NULL;
 425 }
 426
 427 /**
 428  * gts_fnode_class:
 429  *
 430  * Returns: the #GtsFNodeClass.
 431  */
 432 GtsFNodeClass * gts_fnode_class (void)
 433 {
 434   static GtsFNodeClass * klass = NULL;
 435
 436   if (klass == NULL) {
 437     GtsObjectClassInfo fnode_info = {
 438       "GtsFNode",
 439       sizeof (GtsFNode),
 440       sizeof (GtsFNodeClass),
 441       (GtsObjectClassInitFunc) fnode_class_init,
 442       (GtsObjectInitFunc) fnode_init,
 443       (GtsArgSetFunc) NULL,
 444       (GtsArgGetFunc) NULL
 445     };
 446     klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_gnode_class ()),
 447                                   &fnode_info);
 448   }
 449
 450   return klass;
 451 }
 452
 453 /**
 454  * gts_fnode_new:
 455  * @klass: a #GtsFNodeClass.
 456  * @f: a #GtsFace.
 457  *
 458  * Returns: a new #GtsFNode associated with face @f.
 459  */
 460 GtsFNode * gts_fnode_new (GtsFNodeClass * klass, GtsFace * f)
 461 {
 462   GtsFNode * fn;
 463
 464   g_return_val_if_fail (f != NULL, NULL);
 465
 466   fn = GTS_FNODE (gts_object_new (GTS_OBJECT_CLASS (klass)));
 467   fn->f = f;
 468
 469   return fn;
 470 }
 471
 472 /* GtsGEdge */
 473
 474 static void gedge_destroy (GtsObject * object)
 475 {
 476   GtsGEdge * ge = GTS_GEDGE (object);
 477
 478   if (ge->n1)
 479     gts_container_remove (GTS_CONTAINER (ge->n1), GTS_CONTAINEE (ge));
 480   if (ge->n2)
 481     gts_container_remove (GTS_CONTAINER (ge->n2), GTS_CONTAINEE (ge));
 482
 483   (* GTS_OBJECT_CLASS (gts_gedge_class ())->parent_class->destroy) (object);
 484 }
 485
 486 static void gedge_remove_container (GtsContainee * i, GtsContainer * c)
 487 {
 488   GtsGEdge * ge = GTS_GEDGE (i);
 489   GtsGNode * n1 = ge->n1;
 490   GtsGNode * n2 = ge->n2;
 491
 492   ge->n1 = ge->n2 = NULL;
 493   if (n1 != NULL && n2 != NULL) {
 494     if (GTS_CONTAINER (n1) == c) {
 495       if (n2 && n2 != n1) gts_container_remove (GTS_CONTAINER (n2), i);
 496     }
 497     else if (GTS_CONTAINER (n2) == c) {
 498       if (n1 && n1 != n2) gts_container_remove (GTS_CONTAINER (n1), i);
 499     }
 500     else
 501       g_assert_not_reached ();
 502     (* GTS_OBJECT_CLASS (gts_gedge_class ())->parent_class->destroy)
 503       (GTS_OBJECT (i));
 504   }
 505 }
 506
 507 static gboolean gedge_is_contained (GtsContainee * i, GtsContainer * c)
 508 {
 509   GtsGEdge * ge = GTS_GEDGE (i);
 510
 511   if (GTS_CONTAINER (ge->n1) == c || GTS_CONTAINER (ge->n2) == c)
 512     return TRUE;
 513   return FALSE;
 514 }
 515
 516 static void gedge_class_init (GtsGEdgeClass * klass)
 517 {
 518   klass->link = NULL;
 519   klass->weight = NULL;
 520
 521   GTS_CONTAINEE_CLASS (klass)->remove_container = gedge_remove_container;
 522   GTS_CONTAINEE_CLASS (klass)->is_contained = gedge_is_contained;
 523
 524   GTS_OBJECT_CLASS (klass)->destroy = gedge_destroy;
 525 }
 526
 527 static void gedge_init (GtsGEdge * object)
 528 {
 529   object->n1 = object->n2 = NULL;
 530 }
 531
 532 /**
 533  * gts_gedge_class:
 534  *
 535  * Returns: the #GtsGEdgeClass.
 536  */
 537 GtsGEdgeClass * gts_gedge_class (void)
 538 {
 539   static GtsGEdgeClass * klass = NULL;
 540
 541   if (klass == NULL) {
 542     GtsObjectClassInfo gedge_info = {
 543       "GtsGEdge",
 544       sizeof (GtsGEdge),
 545       sizeof (GtsGEdgeClass),
 546       (GtsObjectClassInitFunc) gedge_class_init,
 547       (GtsObjectInitFunc) gedge_init,
 548       (GtsArgSetFunc) NULL,
 549       (GtsArgGetFunc) NULL
 550     };
 551     klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_containee_class ()),
 552                                   &gedge_info);
 553   }
 554
 555   return klass;
 556 }
 557
 558 /**
 559  * gts_gedge_new:
 560  * @klass: a #GtsGEdgeClass.
 561  * @n1: a #GtsGNode.
 562  * @n2: another #GtsGNode.
 563  *
 564  * Returns: a new #GtsGEdge linking @n1 and @n2.
 565  */
 566 GtsGEdge * gts_gedge_new (GtsGEdgeClass * klass, GtsGNode * n1, GtsGNode * n2)
 567 {
 568   GtsGEdge * object;
 569
 570   g_return_val_if_fail (n1 != NULL, NULL);
 571   g_return_val_if_fail (n2 != NULL, NULL);
 572
 573   object = GTS_GEDGE (gts_object_new (GTS_OBJECT_CLASS (klass)));
 574   object->n1 = n1;
 575   gts_container_add (GTS_CONTAINER (n1), GTS_CONTAINEE (object));
 576   object->n2 = n2;
 577   if (n1 != n2)
 578     gts_container_add (GTS_CONTAINER (n2), GTS_CONTAINEE (object));
 579
 580   if (klass->link)
 581     object = (* klass->link) (object, n1, n2);
 582
 583   return object;
 584 }
 585
 586 /**
 587  * gts_gedge_weight:
 588  * @e: a #GtsGEdge.
 589  *
 590  * Returns: the weight of edge @e as defined by the weight() method of
 591  * #GtsGEdgeClass.
 592  */
 593 gfloat gts_gedge_weight (GtsGEdge * e)
 594 {
 595   g_return_val_if_fail (e != NULL, 0.);
 596
 597   if (GTS_GEDGE_CLASS (GTS_OBJECT (e)->klass)->weight)
 598     return (* GTS_GEDGE_CLASS (GTS_OBJECT (e)->klass)->weight) (e);
 599   return 1.;
 600 }
 601
 602 /* GtsPGEdge */
 603
 604 static void pgedge_write (GtsGEdge * ge, FILE * fp)
 605 {
 606   if (GTS_IS_EDGE (GTS_PGEDGE (ge)->data)) {
 607     GtsEdge * e = GTS_PGEDGE (ge)->data;
 608     guint n = g_slist_length (e->triangles);
 609
 610     fprintf (fp, "label=\"%p:%s:%d\",color=%s", e,
 611              GTS_IS_NEDGE (e) ? GTS_NEDGE (e)->name : "",
 612              n,
 613              n == 0 ? "black" :
 614              n == 1 ? "blue" :
 615              n == 2 ? "green" :
 616              n == 3 ? "violet" :
 617              n == 4 ? "red" :
 618              "pink");
 619   }
 620   else
 621     fprintf (fp, "label=\"%p\",", GTS_PGEDGE (ge)->data);
 622 }
 623
 624 static void pgedge_class_init (GtsPGEdgeClass * klass)
 625 {
 626   GTS_GEDGE_CLASS (klass)->write = pgedge_write;
 627 }
 628
 629 static void pgedge_init (GtsPGEdge * e)
 630 {
 631   e->data = NULL;
 632 }
 633
 634 /**
 635  * gts_pgedge_class:
 636  *
 637  * Returns: the #GtsPGEdgeClass.
 638  */
 639 GtsPGEdgeClass * gts_pgedge_class (void)
 640 {
 641   static GtsPGEdgeClass * klass = NULL;
 642
 643   if (klass == NULL) {
 644     GtsObjectClassInfo pgedge_info = {
 645       "GtsPGEdge",
 646       sizeof (GtsPGEdge),
 647       sizeof (GtsPGEdgeClass),
 648       (GtsObjectClassInitFunc) pgedge_class_init,
 649       (GtsObjectInitFunc) pgedge_init,
 650       (GtsArgSetFunc) NULL,
 651       (GtsArgGetFunc) NULL
 652     };
 653     klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_gedge_class ()),
 654                                   &pgedge_info);
 655   }
 656
 657   return klass;
 658 }
 659
 660 /**
 661  * gts_pgedge_new:
 662  * @klass: a #GtsPGEdgeClass.
 663  * @n1: a #GtsGNode.
 664  * @n2: another #GtsGNode.
 665  * @data: user data.
 666  *
 667  * Returns: a new #GtsPGEdge associated with @data linking @n1 and @n2.
 668  */
 669 GtsPGEdge * gts_pgedge_new (GtsPGEdgeClass * klass,
 670                             GtsGNode * g1,
 671                             GtsGNode * g2,
 672                             gpointer data)
 673 {
 674   GtsPGEdge * we;
 675
 676   we = GTS_PGEDGE (gts_gedge_new (GTS_GEDGE_CLASS (klass), g1, g2));
 677   we->data = data;
 678
 679   return we;
 680 }
 681
 682 /* GtsWGEdge */
 683
 684 static gfloat wgedge_weight (GtsGEdge * e)
 685 {
 686   return GTS_WGEDGE (e)->weight;
 687 }
 688
 689 static void wgedge_class_init (GtsWGEdgeClass * klass)
 690 {
 691   GTS_GEDGE_CLASS (klass)->weight = wgedge_weight;
 692 }
 693
 694 static void wgedge_init (GtsWGEdge * e)
 695 {
 696   e->weight = 1.;
 697 }
 698
 699 /**
 700  * gts_wgedge_class:
 701  *
 702  * Returns: the #GtsWGEdgeClass.
 703  */
 704 GtsWGEdgeClass * gts_wgedge_class (void)
 705 {
 706   static GtsWGEdgeClass * klass = NULL;
 707
 708   if (klass == NULL) {
 709     GtsObjectClassInfo wgedge_info = {
 710       "GtsWGEdge",
 711       sizeof (GtsWGEdge),
 712       sizeof (GtsWGEdgeClass),
 713       (GtsObjectClassInitFunc) wgedge_class_init,
 714       (GtsObjectInitFunc) wgedge_init,
 715       (GtsArgSetFunc) NULL,
 716       (GtsArgGetFunc) NULL
 717     };
 718     klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_gedge_class ()),
 719                                   &wgedge_info);
 720   }
 721
 722   return klass;
 723 }
 724
 725 /**
 726  * gts_wgedge_new:
 727  * @klass: a #GtsWGEdgeClass.
 728  * @n1: a #GtsGNode.
 729  * @n2: another #GtsGNode.
 730  * @weight: the weight of the new edge.
 731  *
 732  * Returns: a new #GtsWGEdge of weight @weight linking @n1 and @n2.
 733  */
 734 GtsWGEdge * gts_wgedge_new (GtsWGEdgeClass * klass,
 735                             GtsGNode * g1,
 736                             GtsGNode * g2,
 737                             gfloat weight)
 738 {
 739   GtsWGEdge * we;
 740
 741   we = GTS_WGEDGE (gts_gedge_new (GTS_GEDGE_CLASS (klass), g1, g2));
 742   we->weight = weight;
 743
 744   return we;
 745 }
 746
 747 /* GtsGraph */
 748
 749 static void graph_init (GtsGraph * g)
 750 {
 751   g->graph_class = gts_graph_class ();
 752   g->node_class  = gts_gnode_class ();
 753   g->edge_class  = gts_gedge_class ();
 754 }
 755
 756 static void graph_write (GtsObject * object, FILE * fp)
 757 {
 758   GtsGraph * graph = GTS_GRAPH (object);
 759
 760   fprintf (fp, " %s %s %s",
 761            object->klass->info.name,
 762            GTS_OBJECT_CLASS (graph->node_class)->info.name,
 763            GTS_OBJECT_CLASS (graph->edge_class)->info.name);
 764 }
 765
 766 static void graph_read (GtsObject ** object, GtsFile * f)
 767 {
 768   GtsObjectClass * klass;
 769
 770   if (f->type != GTS_STRING) {
 771     gts_file_error (f, "expecting a string (GtsGNodeClass)");
 772     return;
 773   }
 774   klass = gts_object_class_from_name (f->token->str);
 775   if (klass == NULL) {
 776     gts_file_error (f, "unknown class `%s'", f->token->str);
 777     return;
 778   }
 779   if (!gts_object_class_is_from_class (klass, gts_gnode_class ())) {
 780     gts_file_error (f, "class `%s' is not a GtsGNodeClass", f->token->str);
 781     return;
 782   }
 783   GTS_GRAPH (*object)->node_class = GTS_GNODE_CLASS (klass);
 784   gts_file_next_token (f);
 785
 786   if (f->type != GTS_STRING) {
 787     gts_file_error (f, "expecting a string (GtsGEdgeClass)");
 788     return;
 789   }
 790   klass = gts_object_class_from_name (f->token->str);
 791   if (klass == NULL) {
 792     gts_file_error (f, "unknown class `%s'", f->token->str);
 793     return;
 794   }
 795   if (!gts_object_class_is_from_class (klass, gts_gedge_class ())) {
 796     gts_file_error (f, "class `%s' is not a GtsGEdgeClass", f->token->str);
 797     return;
 798   }
 799   GTS_GRAPH (*object)->edge_class = GTS_GEDGE_CLASS (klass);
 800   gts_file_next_token (f);
 801 }
 802
 803 static void graph_class_init (GtsGraphClass * klass)
 804 {
 805   klass->weight = NULL;
 806
 807   GTS_OBJECT_CLASS (klass)->write = graph_write;
 808   GTS_OBJECT_CLASS (klass)->read = graph_read;
 809 }
 810
 811 /**
 812  * gts_graph_class:
 813  *
 814  * Returns: the #GtsGraphClass.
 815  */
 816 GtsGraphClass * gts_graph_class (void)
 817 {
 818   static GtsGraphClass * klass = NULL;
 819
 820   if (klass == NULL) {
 821     GtsObjectClassInfo graph_info = {
 822       "GtsGraph",
 823       sizeof (GtsGraph),
 824       sizeof (GtsGraphClass),
 825       (GtsObjectClassInitFunc) graph_class_init,
 826       (GtsObjectInitFunc) graph_init,
 827       (GtsArgSetFunc) NULL,
 828       (GtsArgGetFunc) NULL
 829     };
 830     klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_hash_container_class ()),
 831                                   &graph_info);
 832   }
 833
 834   return klass;
 835 }
 836
 837 /**
 838  * gts_graph_new:
 839  * @klass: a #GtsGraphClass.
 840  * @node_class: a #GtsGNodeClass.
 841  * @edge_class: a #GtsGEdgeClass.
 842  *
 843  * Returns: a new #GtsGraph using @node_class and @edge_class as node types.
 844  */
 845 GtsGraph * gts_graph_new (GtsGraphClass * klass,
 846                           GtsGNodeClass * node_class,
 847                           GtsGEdgeClass * edge_class)
 848 {
 849   GtsGraph * g;
 850
 851   g_return_val_if_fail (klass != NULL, NULL);
 852   g_return_val_if_fail (node_class != NULL, NULL);
 853   g_return_val_if_fail (edge_class != NULL, NULL);
 854
 855   g = GTS_GRAPH (gts_object_new (GTS_OBJECT_CLASS (klass)));
 856   g->node_class = node_class;
 857   g->edge_class = edge_class;
 858
 859   return g;
 860 }
 861
 862 static void compute_degree (GtsGNode * n, gpointer * data)
 863 {
 864   GtsGraph * g = data[0];
 865   GtsRange * degree = data[1];
 866
 867   gts_range_add_value (degree, gts_gnode_degree (n, g));
 868 }
 869
 870 /**
 871  * gts_graph_print_stats:
 872  * @g: a #GtsGraph.
 873  * @fp: a file pointer.
 874  *
 875  * Writes to @fp a summary of the properties of @g.
 876  */
 877 void gts_graph_print_stats (GtsGraph * g, FILE * fp)
 878 {
 879   GtsRange degree;
 880   gpointer data[2];
 881
 882   g_return_if_fail (g != NULL);
 883   g_return_if_fail (fp != NULL);
 884
 885   fprintf (fp, "# nodes: %d weight: %g\n",
 886            gts_container_size (GTS_CONTAINER (g)),
 887            gts_graph_weight (g));
 888   fprintf (fp, "#   degree: ");
 889   gts_range_init (&degree);
 890   data[0] = g;
 891   data[1] = &degree;
 892   gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) compute_degree, data);
 893   gts_range_update (&degree);
 894   gts_range_print (&degree, fp);
 895   fprintf (fp, "\n");
 896   fprintf (fp, "#   edges cut: %d edges cut weight: %g\n",
 897            gts_graph_edges_cut (g),
 898            gts_graph_edges_cut_weight (g));
 899 }
 900
 901 struct _GtsGraphTraverse {
 902   GtsFifo * q;
 903   GtsGraph * g;
 904 };
 905
 906 static void reset_level (GtsGNode * n)
 907 {
 908   n->level = 0;
 909 }
 910
 911 /**
 912  * gts_graph_traverse_new:
 913  * @g: a #GtsGraph.
 914  * @n: a #GtsGNode belonging to @g.
 915  * @type: the type of traversal.
 916  * @reinit: if %TRUE, the traversal is reinitialized.
 917  *
 918  * Returns: a new #GtsGraphTraverse initialized for the traversal of
 919  * @g of type @type, starting from @n.
 920  */
 921 GtsGraphTraverse * gts_graph_traverse_new (GtsGraph * g,
 922                                            GtsGNode * n,
 923                                            GtsTraverseType type,
 924                                            gboolean reinit)
 925 {
 926   GtsGraphTraverse * t;
 927
 928   g_return_val_if_fail (g != NULL, NULL);
 929   g_return_val_if_fail (n != NULL, NULL);
 930   g_return_val_if_fail (gts_containee_is_contained (GTS_CONTAINEE (n),
 931                                                     GTS_CONTAINER (g)),
 932                         NULL);
 933
 934   if (reinit)
 935     gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) reset_level, NULL);
 936
 937   t = g_malloc (sizeof (GtsGraphTraverse));
 938   t->q = gts_fifo_new ();
 939   t->g = g;
 940   n->level = 1;
 941   gts_fifo_push (t->q, n);
 942
 943   return t;
 944 }
 945
 946 static void push_neighbor (GtsGNode * n, gpointer * data)
 947 {
 948   GtsFifo * q = data[0];
 949   GtsGNode * u = data[1];
 950
 951   if (n->level == 0) {
 952     n->level = u->level + 1;
 953     gts_fifo_push (q, n);
 954   }
 955 }
 956
 957 /**
 958  * gts_graph_traverse_next:
 959  * @t: a #GtsGraphTraverse.
 960  *
 961  * Returns: the next #GtsGNode of the traversal defined by @t or %NULL
 962  * if the traversal is complete.
 963  */
 964 GtsGNode * gts_graph_traverse_next (GtsGraphTraverse * t)
 965 {
 966   GtsGNode * u;
 967
 968   g_return_val_if_fail (t != NULL, NULL);
 969
 970   u = gts_fifo_pop (t->q);
 971   if (u) {
 972     gpointer data[2];
 973
 974     data[0] = t->q;
 975     data[1] = u;
 976     gts_gnode_foreach_neighbor (u, t->g, (GtsFunc) push_neighbor, data);
 977   }
 978
 979   return u;
 980 }
 981
 982 /**
 983  * gts_graph_traverse_what_next:
 984  * @t: a #GtsGraphTraverse.
 985  *
 986  * Returns: the next #GtsGNode of the traversal defined by @t or %NULL
 987  * if the traversal is complete but without advancing the traversal.
 988  */
 989 GtsGNode * gts_graph_traverse_what_next (GtsGraphTraverse * t)
 990 {
 991   g_return_val_if_fail (t != NULL, NULL);
 992
 993   return gts_fifo_top (t->q);
 994 }
 995
 996 /**
 997  * gts_graph_traverse_destroy:
 998  * @t: a #GtsGraphTraverse.
 999  *
1000  * Frees all the memory allocated for @t.
1001  */
1002 void gts_graph_traverse_destroy (GtsGraphTraverse * t)
1003 {
1004   g_return_if_fail (t != NULL);
1005
1006   gts_fifo_destroy (t->q);
1007   g_free (t);
1008 }
1009
1010 static void edge_foreach_node (GtsGNode * n, gpointer * info)
1011 {
1012   GtsFunc func = (GtsFunc) info[0];
1013   gpointer data = info[1];
1014   GHashTable * hash = info[2];
1015   GSList * i = GTS_SLIST_CONTAINER (n)->items;
1016
1017   while (i) {
1018     GtsGEdge * e = i->data;
1019     if (!g_hash_table_lookup (hash, e)) {
1020       (* func) (e, data);
1021       g_hash_table_insert (hash, e, e);
1022     }
1023     i = i->next;
1024   }
1025 }
1026
1027 /**
1028  * gts_graph_foreach_edge:
1029  * @g: a #GtsGraph.
1030  * @func: a #GtsFunc.
1031  * @data: user data to be passed to @func.
1032  *
1033  * Calls @func for each #GtsEdge of @g.
1034  */
1035 void gts_graph_foreach_edge (GtsGraph * g, GtsFunc func, gpointer data)
1036 {
1037   gpointer info[3];
1038   GHashTable * hash;
1039
1040   g_return_if_fail (g != NULL);
1041   g_return_if_fail (func != NULL);
1042
1043   info[0] = func;
1044   info[1] = data;
1045   info[2] = hash = g_hash_table_new (NULL, NULL);
1046   gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) edge_foreach_node, info);
1047   g_hash_table_destroy (hash);
1048 }
1049
1050 /**
1051  * gts_graph_weight:
1052  * @g: a #GtsGraph.
1053  *
1054  * Returns: the weight of graph @g as defined by the weight() method
1055  * of #GtsGraphClass.
1056  */
1057 gfloat gts_graph_weight (GtsGraph * g)
1058 {
1059   g_return_val_if_fail (g != NULL, 0.);
1060
1061   if (GTS_GRAPH_CLASS (GTS_OBJECT (g)->klass)->weight)
1062     return (* GTS_GRAPH_CLASS (GTS_OBJECT (g)->klass)->weight) (g);
1063   return (gfloat) gts_container_size (GTS_CONTAINER (g));
1064 }
1065
1066 /**
1067  * gts_graph_distance_sum:
1068  * @g: a #GtsGraph.
1069  * @center: a #GtsGNode of @g.
1070  *
1071  * Returns: the sum of the distances between all the other #GtsGNode
1072  * of @g and @center.
1073  */
1074 guint gts_graph_distance_sum (GtsGraph * g, GtsGNode * center)
1075 {
1076   GtsGraphTraverse * t;
1077   GtsGNode * n;
1078   guint sum = 0;
1079
1080   g_return_val_if_fail (g != NULL, 0);
1081   g_return_val_if_fail (center != NULL, 0);
1082
1083   t = gts_graph_traverse_new (g, center, GTS_BREADTH_FIRST, TRUE);
1084   while ((n = gts_graph_traverse_next (t)))
1085     sum += n->level - 1;
1086   gts_graph_traverse_destroy (t);
1087
1088   return sum;
1089 }
1090
1091 /**
1092  * gts_graph_farthest:
1093  * @g: a #GtsGraph.
1094  * @gnodes: a list of #GtsGNode belonging to @g.
1095  *
1096  * Returns: the #GtsGNode belonging to @g and farthest from all the nodes in
1097  * @gnodes (hmmm, definition of "farthest"?).
1098  */
1099 GtsGNode * gts_graph_farthest (GtsGraph * g, GSList * gnodes)
1100 {
1101   GtsGNode * farthest = NULL;
1102   GSList * i;
1103   gboolean reinit = TRUE, changed = TRUE;
1104   guint level = 1;
1105
1106   g_return_val_if_fail (g != NULL, NULL);
1107
1108   /* initialize traversals */
1109   i = gnodes;
1110   while (i) {
1111     GTS_OBJECT (i->data)->reserved =
1112       gts_graph_traverse_new (g, i->data, GTS_BREADTH_FIRST, reinit);
1113     reinit = FALSE;
1114     i = i->next;
1115   }
1116
1117   while (changed) {
1118     changed = FALSE;
1119     i = gnodes;
1120     while (i) {
1121       GtsGraphTraverse * t = GTS_OBJECT (i->data)->reserved;
1122       GtsGNode * n;
1123       while ((n = gts_graph_traverse_what_next (t)) && n->level == level) {
1124         changed = TRUE;
1125         farthest = n;
1126         gts_graph_traverse_next (t);
1127       }
1128       i = i->next;
1129     }
1130     level++;
1131   }
1132
1133   /* destroy traversals */
1134   i = gnodes;
1135   while (i) {
1136     gts_graph_traverse_destroy (GTS_OBJECT (i->data)->reserved);
1137     GTS_OBJECT (i->data)->reserved = NULL;
1138     i = i->next;
1139   }
1140   return farthest;
1141 }
1142
1143 static void neighbor_count (GtsGNode * n, gpointer * data)
1144 {
1145   guint * cuts = data[0];
1146   GtsGraph * g = data[1];
1147
1148   if (!gts_containee_is_contained (GTS_CONTAINEE (n), GTS_CONTAINER (g)))
1149     (*cuts)++;
1150 }
1151
1152 static void count_edge_cuts (GtsGNode * n, gpointer * data)
1153 {
1154   gts_gnode_foreach_neighbor (n, NULL, (GtsFunc) neighbor_count, data);
1155 }
1156
1157 /**
1158  * gts_graph_edges_cut:
1159  * @g: a #GtsGraph.
1160  *
1161  * Returns: the number of edges of @g connecting nodes belonging to @g
1162  * to nodes not belonging to @g.
1163  */
1164 guint gts_graph_edges_cut (GtsGraph * g)
1165 {
1166   guint cuts = 0;
1167   gpointer data[2];
1168
1169   g_return_val_if_fail (g != NULL, 0);
1170
1171   data[0] = &cuts;
1172   data[1] = g;
1173   gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) count_edge_cuts, data);
1174
1175   return cuts;
1176 }
1177
1178 static void sum_edge_cuts_weight (GtsGNode * n, gpointer * data)
1179 {
1180   gfloat * weight = data[0];
1181   GtsGraph * g = data[1];
1182   GSList * i = GTS_SLIST_CONTAINER (n)->items;
1183
1184   while (i) {
1185     GtsGNode * n1 = GTS_GNODE_NEIGHBOR (n, i->data);
1186     if (!gts_containee_is_contained (GTS_CONTAINEE (n1), GTS_CONTAINER (g)))
1187       *weight += gts_gedge_weight (i->data);
1188     i = i->next;
1189   }
1190 }
1191
1192 /**
1193  * gts_graph_edges_cut_weight:
1194  * @g: a #GtsGraph.
1195  *
1196  * Returns: the sum of the weights of the edges of @g connecting nodes
1197  * belonging to @g to nodes not belonging to @g.
1198  */
1199 gfloat gts_graph_edges_cut_weight (GtsGraph * g)
1200 {
1201   gfloat weight = 0.;
1202   gpointer data[2];
1203
1204   g_return_val_if_fail (g != NULL, 0);
1205
1206   data[0] = &weight;
1207   data[1] = g;
1208   gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) sum_edge_cuts_weight,
1209                          data);
1210
1211   return weight;
1212 }
1213
1214 /**
1215  * gts_graph_read_jostle:
1216  * @g: a #GtsGraph.
1217  * @fp: a #GtsFile.
1218  *
1219  * Adds to @g the nodes and edges defined in the file pointed to by
1220  * @fp. This file must use the Jostle "graph" ASCII format.
1221  * The nodes created are of type #GtsNGNode and their identities are the
1222  * line number at which they appear in @fp.
1223  *
1224  * Returns: 0 if the lecture was successful, the line number at which
1225  * an error occured otherwise (in which case the @error field of @fp
1226  * is set).
1227  */
1228 guint gts_graph_read_jostle (GtsGraph * g, GtsFile * fp)
1229 {
1230   guint nn, ne, n;
1231   GtsGNode ** nodes;
1232
1233   g_return_val_if_fail (g != NULL, 1);
1234   g_return_val_if_fail (fp != NULL, 1);
1235
1236   if (fp->type != GTS_INT) {
1237     gts_file_error (fp, "expecting an integer (number of nodes)");
1238     return fp->line;
1239   }
1240   nn = atoi (fp->token->str);
1241   gts_file_next_token (fp);
1242
1243   if (fp->type != GTS_INT) {
1244     gts_file_error (fp, "expecting an integer (number of edges)");
1245     return fp->line;
1246   }
1247   ne = atoi (fp->token->str);
1248
1249   gts_file_first_token_after (fp, '\n');
1250   nodes = g_malloc (sizeof (GtsGNode *)*(nn + 1));
1251
1252   n = 0;
1253   while (n < nn && fp->type != GTS_ERROR) {
1254     GtsNGNode * node = gts_ngnode_new (gts_ngnode_class (), fp->line);
1255
1256     nodes[n++] = GTS_GNODE (node);
1257     gts_container_add (GTS_CONTAINER (g), GTS_CONTAINEE (node));
1258     do {
1259       if (fp->type != GTS_INT)
1260         gts_file_error (fp, "expecting an integer (node index)");
1261       else {
1262         guint in = atoi (fp->token->str);
1263
1264         if (in == 0 || in > nn)
1265           gts_file_error (fp, "node index `%d' is out of range `[1,%d]'",
1266                           in, nn);
1267         else if (in == n)
1268           gts_file_error (fp, "node index `%d' references itself", in);
1269         else if (in < n) {
1270           gts_gedge_new (g->edge_class, GTS_GNODE (node), nodes[in - 1]);
1271           ne--;
1272           gts_file_next_token (fp);
1273         }
1274       }
1275     } while (fp->type != GTS_ERROR && fp->type != '\n');
1276   }
1277   g_free (nodes);
1278
1279   if (fp->type != GTS_ERROR) {
1280     if (n != nn)
1281       gts_file_error (fp, "only `%d' nodes read out of `%d'",
1282                       n, nn);
1283     else if (ne > 0)
1284       gts_file_error (fp, "`%d' unallocated edges remaining",
1285                       ne);
1286   }
1287
1288   if (fp->type == GTS_ERROR)
1289     return fp->line;
1290   return 0;
1291 }
1292
1293 static void count_edges (GtsGEdge * e, guint * nedge)
1294 {
1295   (*nedge)++;
1296 }
1297
1298 static void write_node (GtsObject * node, gpointer * data)
1299 {
1300   FILE * fp = data[0];
1301   guint * nnode = data[1];
1302
1303   node->reserved = GUINT_TO_POINTER ((*nnode)++);
1304   if (node->klass->write)
1305     (* node->klass->write) (node, fp);
1306   fputc ('\n', fp);
1307 }
1308
1309 static void write_edge (GtsGEdge * edge, FILE * fp)
1310 {
1311   fprintf (fp, "%u %u",
1312            GPOINTER_TO_UINT (GTS_OBJECT (edge->n1)->reserved),
1313            GPOINTER_TO_UINT (GTS_OBJECT (edge->n2)->reserved));
1314   if (GTS_OBJECT (edge)->klass->write)
1315     (* GTS_OBJECT (edge)->klass->write) (GTS_OBJECT (edge), fp);
1316   fputc ('\n', fp);
1317 }
1318
1319 /**
1320  * gts_graph_write:
1321  * @g: a #GtsGraph.
1322  * @fp: a file pointer.
1323  *
1324  * Writes in the file @fp an ASCII representation of @g. The file
1325  * format is as follows.
1326  *
1327  * All the lines beginning with #GTS_COMMENTS are ignored. The first line
1328  * contains two unsigned integers separated by spaces. The first
1329  * integer is the number of nodes, nn, the second is the number of
1330  * edges, ne.
1331  *
1332  * Follows nn lines containing node description.
1333  * Follows ne lines containing the two indices (starting
1334  * from one) of the nodes of each edge.
1335  *
1336  * The format described above is the least common denominator to all
1337  * GTS files.  Consistent with an object-oriented approach, the GTS
1338  * file format is extensible. Each of the lines of the file can be
1339  * extended with user-specific attributes accessible through the
1340  * read() and write() virtual methods of each of the objects written
1341  * (graph, nodes or edges). When read with different object classes,
1342  * these extra attributes are just ignored.
1343  */
1344 void gts_graph_write (GtsGraph * g, FILE * fp)
1345 {
1346   guint nnode = 1, nedge = 0;
1347   gpointer data[2];
1348
1349   g_return_if_fail (g != NULL);
1350   g_return_if_fail (fp != NULL);
1351
1352   gts_graph_foreach_edge (g, (GtsFunc) count_edges, &nedge);
1353   fprintf (fp, "%u %u", gts_container_size (GTS_CONTAINER (g)), nedge);
1354   if (GTS_OBJECT (g)->klass->write)
1355     (* GTS_OBJECT (g)->klass->write) (GTS_OBJECT (g), fp);
1356   fputc ('\n', fp);
1357   data[0] = fp;
1358   data[1] = &nnode;
1359   gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) write_node, data);
1360   gts_graph_foreach_edge (g, (GtsFunc) write_edge, fp);
1361   gts_container_foreach (GTS_CONTAINER (g),
1362                          (GtsFunc) gts_object_reset_reserved, NULL);
1363 }
1364
1365 /**
1366  * gts_graph_read:
1367  * @fp: a #GtsFile.
1368  *
1369  * Reads a graph from a file.
1370  *
1371  * Returns: the new #GtsGraph or %NULL if an error occured (in which
1372  * case the @error field of @fp is set).
1373  */
1374 GtsGraph * gts_graph_read (GtsFile * fp)
1375 {
1376   GtsGraph * g;
1377   GtsGNode ** nodes;
1378   guint nn, ne, n;
1379
1380   g_return_val_if_fail (fp != NULL, NULL);
1381
1382   if (fp->type != GTS_INT) {
1383     gts_file_error (fp, "expecting an integer (number of nodes)");
1384     return NULL;
1385   }
1386   nn = atoi (fp->token->str);
1387   gts_file_next_token (fp);
1388
1389   if (fp->type != GTS_INT) {
1390     gts_file_error (fp, "expecting an integer (number of edges)");
1391     return NULL;
1392   }
1393   ne = atoi (fp->token->str);
1394
1395   gts_file_next_token (fp);
1396   if (fp->type != '\n') {
1397     GtsObjectClass * klass;
1398
1399     gts_graph_class ();
1400     gts_gnode_class ();
1401     gts_gedge_class ();
1402
1403     if (fp->type != GTS_STRING) {
1404       gts_file_error (fp, "expecting a string (GtsGraphClass)");
1405       return NULL;
1406     }
1407     klass = gts_object_class_from_name (fp->token->str);
1408     if (klass == NULL) {
1409       gts_file_error (fp, "unknown class `%s'", fp->token->str);
1410       return NULL;
1411     }
1412     if (!gts_object_class_is_from_class (klass, gts_graph_class ())) {
1413       gts_file_error (fp, "class `%s' is not a GtsGraphClass", fp->token->str);
1414       return NULL;
1415     }
1416     g = GTS_GRAPH (gts_object_new (klass));
1417     g->graph_class = GTS_GRAPH_CLASS (klass);
1418     gts_file_next_token (fp);
1419     (* klass->read) ((GtsObject **) &g, fp);
1420     if (fp->type == GTS_ERROR) {
1421       gts_object_destroy (GTS_OBJECT (g));
1422       return NULL;
1423     }
1424   }
1425   else
1426     g = GTS_GRAPH (gts_object_new (GTS_OBJECT_CLASS (gts_graph_class ())));
1427   gts_file_first_token_after (fp, '\n');
1428   if (nn <= 0)
1429     return g;
1430
1431   nodes = g_malloc ((nn + 1)*sizeof (GtsGNode *));
1432
1433   n = 0;
1434   while (n < nn && fp->type != GTS_ERROR) {
1435     GtsObject * new_node =
1436       gts_object_new (GTS_OBJECT_CLASS (g->node_class));
1437
1438     gts_container_add (GTS_CONTAINER (g), GTS_CONTAINEE (new_node));
1439     if (GTS_OBJECT_CLASS (g->node_class)->read)
1440       (*GTS_OBJECT_CLASS (g->node_class)->read) (&new_node, fp);
1441     gts_file_first_token_after (fp, '\n');
1442     nodes[n++] = GTS_GNODE (new_node);
1443   }
1444   if (fp->type == GTS_ERROR)
1445     nn = n;
1446
1447   n = 0;
1448   while (n < ne && fp->type != GTS_ERROR) {
1449     guint n1, n2;
1450
1451     if (fp->type != GTS_INT)
1452       gts_file_error (fp, "expecting an integer (first node index)");
1453     else {
1454       n1 = atoi (fp->token->str);
1455       if (n1 == 0 || n1 > nn)
1456         gts_file_error (fp, "node index `%d' is out of range `[1,%d]'",
1457                         n1, nn);
1458       else {
1459         gts_file_next_token (fp);
1460         if (fp->type != GTS_INT)
1461           gts_file_error (fp, "expecting an integer (second node index)");
1462         else {
1463           n2 = atoi (fp->token->str);
1464           if (n2 == 0 || n2 > nn)
1465             gts_file_error (fp, "node index `%d' is out of range `[1,%d]'",
1466                             n2, nn);
1467           else {
1468             GtsGEdge * new_edge =
1469               gts_gedge_new (g->edge_class, nodes[n1 - 1], nodes [n2 - 1]);
1470
1471             gts_file_next_token (fp);
1472             if (fp->type != '\n')
1473               if (GTS_OBJECT_CLASS (g->edge_class)->read)
1474                 (*GTS_OBJECT_CLASS (g->edge_class)->read)
1475                   ((GtsObject **) &new_edge, fp);
1476             gts_file_first_token_after (fp, '\n');
1477             n++;
1478           }
1479         }
1480       }
1481     }
1482   }
1483
1484   if (fp->type == GTS_ERROR) {
1485     gts_allow_floating_gnodes = TRUE;
1486     while (nn)
1487       gts_object_destroy (GTS_OBJECT (nodes[nn-- - 1]));
1488     gts_allow_floating_gnodes = FALSE;
1489   }
1490   g_free (nodes);
1491
1492   if (fp->type == GTS_ERROR) {
1493     gts_object_destroy (GTS_OBJECT (g));
1494     return NULL;
1495   }
1496   return g;
1497 }
1498
1499 static void write_dot_node (GtsGNode * node, gpointer * data)
1500 {
1501   FILE * fp = data[0];
1502   guint * nnode = data[1];
1503
1504   fprintf (fp, "  n%u", *nnode);
1505   if (GTS_GNODE_CLASS (GTS_OBJECT (node)->klass)->write) {
1506     fputs (" [", fp);
1507     (* GTS_GNODE_CLASS (GTS_OBJECT (node)->klass)->write) (node, fp);
1508     fputc (']', fp);
1509   }
1510   fputs (";\n", fp);
1511   GTS_OBJECT (node)->reserved = GUINT_TO_POINTER ((*nnode)++);
1512 }
1513
1514 static void write_dot_edge (GtsGEdge * edge, FILE * fp)
1515 {
1516   fprintf (fp, "  n%u -> n%u",
1517            GPOINTER_TO_UINT (GTS_OBJECT (edge->n1)->reserved),
1518            GPOINTER_TO_UINT (GTS_OBJECT (edge->n2)->reserved));
1519   if (GTS_GEDGE_CLASS (GTS_OBJECT (edge)->klass)->write) {
1520     fputs (" [", fp);
1521     (* GTS_GEDGE_CLASS (GTS_OBJECT (edge)->klass)->write) (edge, fp);
1522     fputc (']', fp);
1523   }
1524   fputs (";\n", fp);
1525 }
1526
1527 /**
1528  * gts_graph_write_dot:
1529  * @g: a #GtsGraph.
1530  * @fp: a file pointer.
1531  *
1532  * Writes in the file @fp an ASCII representation of @g in the dot format of
1533  * AT&T Bell Labs.
1534  */
1535 void gts_graph_write_dot (GtsGraph * g, FILE * fp)
1536 {
1537   guint nnode = 1;
1538   gpointer data[2];
1539
1540   g_return_if_fail (g != NULL);
1541   g_return_if_fail (fp != NULL);
1542
1543   fprintf (fp, "digraph \"%p\" {\n", g);
1544   data[0] = fp;
1545   data[1] = &nnode;
1546   gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) write_dot_node, data);
1547   gts_graph_foreach_edge (g, (GtsFunc) write_dot_edge, fp);
1548   fputs ("}\n", fp);
1549
1550   gts_container_foreach (GTS_CONTAINER (g),
1551                          (GtsFunc) gts_object_reset_reserved, NULL);
1552 }
1553
1554 /* GtsWGraph */
1555
1556 static gfloat wgraph_weight (GtsGraph * g)
1557 {
1558   return GTS_WGRAPH (g)->weight;
1559 }
1560
1561 static void wgraph_add (GtsContainer * g, GtsContainee * n)
1562 {
1563   GtsWGraph * wg = GTS_WGRAPH (g);
1564   gfloat w = gts_gnode_weight (GTS_GNODE (n));
1565
1566   wg->weight += w;
1567
1568   (* GTS_CONTAINER_CLASS (GTS_OBJECT_CLASS (gts_wgraph_class ())->parent_class)->add) (g, n);
1569 }
1570
1571 static void wgraph_remove (GtsContainer * g, GtsContainee * n)
1572 {
1573   GTS_WGRAPH (g)->weight -= gts_gnode_weight (GTS_GNODE (n));
1574
1575   (* GTS_CONTAINER_CLASS (GTS_OBJECT_CLASS (gts_wgraph_class ())->parent_class)->remove) (g, n);
1576 }
1577
1578 static void wgraph_class_init (GtsWGraphClass * klass)
1579 {
1580   GTS_GRAPH_CLASS (klass)->weight = wgraph_weight;
1581
1582   GTS_CONTAINER_CLASS (klass)->add = wgraph_add;
1583   GTS_CONTAINER_CLASS (klass)->remove = wgraph_remove;
1584 }
1585
1586 static void wgraph_init (GtsWGraph * g)
1587 {
1588   g->weight = 0.;
1589 }
1590
1591 /**
1592  * gts_wgraph_class:
1593  *
1594  * Returns: the #GtsWGraphClass.
1595  */
1596 GtsWGraphClass * gts_wgraph_class (void)
1597 {
1598   static GtsWGraphClass * klass = NULL;
1599
1600   if (klass == NULL) {
1601     GtsObjectClassInfo wgraph_info = {
1602       "GtsWGraph",
1603       sizeof (GtsWGraph),
1604       sizeof (GtsWGraphClass),
1605       (GtsObjectClassInitFunc) wgraph_class_init,
1606       (GtsObjectInitFunc) wgraph_init,
1607       (GtsArgSetFunc) NULL,
1608       (GtsArgGetFunc) NULL
1609     };
1610     klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_graph_class ()),
1611                                   &wgraph_info);
1612   }
1613
1614   return klass;
1615 }
1616
1617 static void weight_max (GtsGNode * n, gfloat * wmax)
1618 {
1619   gfloat w = gts_gnode_weight (n);
1620
1621   if (w > *wmax)
1622     *wmax = w;
1623 }
1624
1625 /**
1626  * gts_wgraph_weight_max:
1627  * @wg: a #GtsWGraph.
1628  *
1629  * Returns: the maximum weight of any vertices belonging to @g.
1630  */
1631 gfloat gts_wgraph_weight_max (GtsWGraph * wg)
1632 {
1633   gfloat wmax = - G_MAXFLOAT;
1634
1635   g_return_val_if_fail (wg != NULL, 0.);
1636
1637   gts_container_foreach (GTS_CONTAINER (wg), (GtsFunc) weight_max, &wmax);
1638
1639   return wmax;
1640 }
1641
1642 /* Surface graph */
1643
1644 static void create_node (GtsFace * f, GtsGraph * graph)
1645 {
1646   GtsFNode * fn = gts_fnode_new (gts_fnode_class (), f);
1647
1648   gts_container_add (GTS_CONTAINER (graph), GTS_CONTAINEE (fn));
1649   GTS_OBJECT (f)->reserved = fn;
1650 }
1651
1652 static void create_edge (GtsEdge * e, GtsSurface * s)
1653 {
1654   GSList * i = e->triangles;
1655
1656   while (i) {
1657     GtsFace * f = i->data;
1658     if (GTS_IS_FACE (f) && gts_face_has_parent_surface (f, s)) {
1659       GSList * j = i->next;
1660       while (j) {
1661         GtsFace * f1 = j->data;
1662         if (GTS_IS_FACE (f1) && gts_face_has_parent_surface (f1, s))
1663           gts_pgedge_new (gts_pgedge_class (),
1664                           GTS_OBJECT (f)->reserved,
1665                           GTS_OBJECT (f1)->reserved,
1666                           e);
1667         j = j->next;
1668       }
1669     }
1670     i = i->next;
1671   }
1672 }
1673
1674 /**
1675  * gts_surface_graph_new:
1676  * @klass: a #GtsGraphClass.
1677  * @s: a #GtsSurface.
1678  *
1679  * Returns: a new #GtsGraph representing the connectivity of the faces
1680  * of @s. This graph uses #GtsFGNode as nodes which allows to store
1681  * the dependencies between nodes and faces of @s.
1682  */
1683 GtsGraph * gts_surface_graph_new (GtsGraphClass * klass,
1684                                   GtsSurface * s)
1685 {
1686   GtsGraph * graph;
1687
1688   g_return_val_if_fail (klass != NULL, NULL);
1689   g_return_val_if_fail (s != NULL, NULL);
1690
1691   graph = GTS_GRAPH (gts_object_new (GTS_OBJECT_CLASS (klass)));
1692   gts_surface_foreach_face (s, (GtsFunc) create_node, graph);
1693   gts_surface_foreach_edge (s, (GtsFunc) create_edge, s);
1694   gts_surface_foreach_face (s, (GtsFunc) gts_object_reset_reserved, NULL);
1695
1696   return graph;
1697 }
1698
1699 static void create_segment_edge (GtsSegment * s, GtsGraph * graph)
1700 {
1701   GtsGNode * n1 = GTS_OBJECT (s->v1)->reserved, * n2;
1702
1703   if (n1 == NULL) {
1704     n1 = GTS_GNODE (gts_pnode_new (gts_pnode_class (), s->v1));
1705     gts_container_add (GTS_CONTAINER (graph), GTS_CONTAINEE (n1));
1706     GTS_OBJECT (s->v1)->reserved = n1;
1707   }
1708
1709   n2 = GTS_OBJECT (s->v2)->reserved;
1710   if (n2 == NULL) {
1711     n2 = GTS_GNODE (gts_pnode_new (gts_pnode_class (), s->v2));
1712     gts_container_add (GTS_CONTAINER (graph), GTS_CONTAINEE (n2));
1713     GTS_OBJECT (s->v2)->reserved = n2;
1714   }
1715
1716   gts_pgedge_new (gts_pgedge_class (), n1, n2, s);
1717 }
1718
1719 static void reset_reserved (GtsSegment * s)
1720 {
1721   GTS_OBJECT (s->v1)->reserved = GTS_OBJECT (s->v2)->reserved = NULL;
1722 }
1723
1724 /**
1725  * gts_segments_graph_new:
1726  * @klass: a #GtsGraphClass.
1727  * @segments: a list of #GtsSegment.
1728  *
1729  * Returns: a new #GtsGraph representing the connectivity of the segments
1730  * in @segments.
1731  */
1732 GtsGraph * gts_segments_graph_new (GtsGraphClass * klass,
1733                                    GSList * segments)
1734 {
1735   GtsGraph * graph;
1736
1737   g_return_val_if_fail (klass != NULL, NULL);
1738
1739   graph = GTS_GRAPH (gts_object_new (GTS_OBJECT_CLASS (klass)));
1740   g_slist_foreach (segments, (GFunc) create_segment_edge, graph);
1741   g_slist_foreach (segments, (GFunc) reset_reserved, NULL);
1742
1743   return graph;
1744 }
1745
1746 static void add_to_surface (GtsGNode * n, GtsSurface * s)
1747 {
1748   if (GTS_IS_FNODE (n))
1749     gts_surface_add_face (s, GTS_FNODE (n)->f);
1750 }
1751
1752 /**
1753  * gts_surface_graph_surface:
1754  * @surface_graph: a #GtsGraph using #GtsFGNode as nodes.
1755  * @s: a #GtsSurface.
1756  *
1757  * Returns: a new #GtsSurface using the same classes as @s and
1758  * composed of the faces defined by @surface_graph.
1759  */
1760 GtsSurface * gts_surface_graph_surface (GtsGraph * surface_graph,
1761                                         GtsSurface * s)
1762 {
1763   GtsSurface * s1;
1764
1765   g_return_val_if_fail (surface_graph != NULL, NULL);
1766   g_return_val_if_fail (s != NULL, NULL);
1767
1768   s1 = gts_surface_new (GTS_SURFACE_CLASS (GTS_OBJECT (s)->klass),
1769                         s->face_class,
1770                         s->edge_class,
1771                         s->vertex_class);
1772   gts_container_foreach (GTS_CONTAINER (surface_graph),
1773                          (GtsFunc) add_to_surface, s1);
1774   return s1;
1775 }
1776