gts/pgraph.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 "gts.h"
  21
  22 /* GtsGNodeSplit */
  23
  24 static void gnode_split_destroy (GtsObject * object)
  25 {
  26   GtsGNodeSplit * ns = GTS_GNODE_SPLIT (object);
  27
  28   if (gts_container_size (GTS_CONTAINER (ns->n)) == 0) {
  29     g_assert (GTS_SLIST_CONTAINEE (ns->n)->containers == NULL);
  30     gts_object_destroy (GTS_OBJECT (ns->n));
  31   }
  32   else {
  33     /* GtsGNode * n1 = GTS_GNODE_SPLIT_N1 (ns); */
  34     /* GtsGNode * n2 = GTS_GNODE_SPLIT_N2 (ns); */
  35
  36     g_warning ("Memory deallocation for GtsGNodeSplit not fully implemented yet: memory leak!");
  37   }
  38
  39   (* GTS_OBJECT_CLASS (gts_gnode_split_class ())->parent_class->destroy)
  40     (object);
  41 }
  42
  43 static void gnode_split_class_init (GtsGNodeSplitClass * klass)
  44 {
  45   GTS_OBJECT_CLASS (klass)->destroy = gnode_split_destroy;
  46 }
  47
  48 static void gnode_split_init (GtsGNodeSplit * ns)
  49 {
  50   ns->n = NULL;
  51   ns->n1 = ns->n2 = NULL;
  52 }
  53
  54 /**
  55  * gts_gnode_split_class:
  56  *
  57  * Returns: the #GtsGNodeSplitClass.
  58  */
  59 GtsGNodeSplitClass * gts_gnode_split_class (void)
  60 {
  61   static GtsGNodeSplitClass * klass = NULL;
  62
  63   if (klass == NULL) {
  64     GtsObjectClassInfo gnode_split_info = {
  65       "GtsGNodeSplit",
  66       sizeof (GtsGNodeSplit),
  67       sizeof (GtsGNodeSplitClass),
  68       (GtsObjectClassInitFunc) gnode_split_class_init,
  69       (GtsObjectInitFunc) gnode_split_init,
  70       (GtsArgSetFunc) NULL,
  71       (GtsArgGetFunc) NULL
  72     };
  73     klass = gts_object_class_new (gts_object_class (), &gnode_split_info);
  74   }
  75
  76   return klass;
  77 }
  78
  79 /**
  80  * gts_gnode_split_new:
  81  * @klass: a #GtsGNodeSplitClass.
  82  * @n: a #GtsGNode.
  83  * @n1: a #GtsGNodeSplit or #GtsGNode.
  84  * @n2: a #GtsGNodeSplit or #GtsGNode.
  85  *
  86  * Creates a new #GtsGNodeSplit which would collapse @n1 and @n2 into
  87  * @n. The collapse itself is not performed.
  88  *
  89  * Returns: the new #GtsGNodeSplit.
  90  */
  91 GtsGNodeSplit * gts_gnode_split_new (GtsGNodeSplitClass * klass,
  92                                      GtsGNode * n,
  93                                      GtsObject * n1,
  94                                      GtsObject * n2)
  95 {
  96   GtsGNodeSplit * ns;
  97
  98   g_return_val_if_fail (klass != NULL, NULL);
  99   g_return_val_if_fail (n != NULL, NULL);
 100   g_return_val_if_fail (GTS_IS_GNODE_SPLIT (n1) || GTS_IS_GNODE (n1), NULL);
 101   g_return_val_if_fail (GTS_IS_GNODE_SPLIT (n2) || GTS_IS_GNODE (n2), NULL);
 102
 103   ns = GTS_GNODE_SPLIT (gts_object_new (GTS_OBJECT_CLASS (klass)));
 104   ns->n = n;
 105   ns->n1 = n1;
 106   ns->n2 = n2;
 107
 108   return ns;
 109 }
 110
 111 static void connect_edge (GtsGEdge * e, gpointer * data)
 112 {
 113   GtsGNode * n = data[0];
 114   GtsGNode * n1 = data[1];
 115   GtsGNode * n2 = data[2];
 116
 117   if (GTS_OBJECT (e)->reserved || /* edge is disconnected */
 118       gts_gedge_connects (e, n1, n2))
 119     return;
 120   if (e->n1 == n1 || e->n1 == n2)
 121     e->n1 = n;
 122   else if (e->n2 == n1 || e->n2 == n2)
 123     e->n2 = n;
 124   else
 125     g_assert_not_reached ();
 126   gts_container_add (GTS_CONTAINER (n), GTS_CONTAINEE (e));
 127 }
 128
 129 /**
 130  * gts_gnode_split_collapse:
 131  * @ns: a #GtsGNodeSplit.
 132  * @g: a #GtsGraph.
 133  * @klass: a #GtsWGEdgeClass.
 134  *
 135  * Collapses the node split @ns. Any new edge created during the
 136  * process will be of class @klass.
 137  */
 138 void gts_gnode_split_collapse (GtsGNodeSplit * ns,
 139                                GtsGraph * g,
 140                                GtsWGEdgeClass * klass)
 141 {
 142   GtsGNode * n1, * n2;
 143   GSList * i;
 144   gpointer data[3];
 145
 146   g_return_if_fail (ns != NULL);
 147   g_return_if_fail (g != NULL);
 148   g_return_if_fail (gts_container_size (GTS_CONTAINER (ns->n)) == 0);
 149
 150   n1 = GTS_GNODE_SPLIT_N1 (ns);
 151   n2 = GTS_GNODE_SPLIT_N2 (ns);
 152
 153   /* look for triangles */
 154   i = GTS_SLIST_CONTAINER (n1)->items;
 155   while (i) {
 156     GtsGEdge * e13 = i->data;
 157     GtsGNode * n3 = GTS_GNODE_NEIGHBOR (n1, e13);
 158     if (n3 != n2) {
 159       GSList * j = GTS_SLIST_CONTAINER (n3)->items;
 160       while (j) {
 161         GtsGEdge * e32 = j->data;
 162         GSList * next = j->next;
 163         GtsGNode * n4 = GTS_GNODE_NEIGHBOR (n3, e32);
 164         if (n4 == n2) { /* found triangle n1 (e13) n3 (e32) n2 */
 165           gts_wgedge_new (klass, ns->n, n3,
 166                           gts_gedge_weight (e13) + gts_gedge_weight (e32));
 167           GTS_OBJECT (e13)->reserved = n3;
 168           GTS_OBJECT (e32)->reserved = n3;
 169           GTS_SLIST_CONTAINER (n3)->items =
 170             g_slist_remove (GTS_SLIST_CONTAINER (n3)->items, e32);
 171         }
 172         j = next;
 173       }
 174       if (GTS_OBJECT (e13)->reserved == n3)
 175         GTS_SLIST_CONTAINER (n3)->items =
 176           g_slist_remove (GTS_SLIST_CONTAINER (n3)->items, e13);
 177     }
 178     i = i->next;
 179   }
 180
 181   /* connect edges to new node */
 182   data[0] = ns->n;
 183   data[1] = n1;
 184   data[2] = n2;
 185   gts_container_foreach (GTS_CONTAINER (n1), (GtsFunc) connect_edge, data);
 186   gts_container_foreach (GTS_CONTAINER (n2), (GtsFunc) connect_edge, data);
 187
 188   gts_allow_floating_gnodes = TRUE;
 189   gts_container_remove (GTS_CONTAINER (g), GTS_CONTAINEE (n1));
 190   gts_container_remove (GTS_CONTAINER (g), GTS_CONTAINEE (n2));
 191   gts_allow_floating_gnodes = FALSE;
 192   gts_container_add (GTS_CONTAINER (g), GTS_CONTAINEE (ns->n));
 193 }
 194
 195 static void restore_edge (GtsGEdge * e, gpointer * data)
 196 {
 197   GtsGNode * n = data[0];
 198   GtsGNode * n1 = data[1];
 199   GtsGNode * n2 = data[2];
 200   GtsGNode * n3 = GTS_OBJECT (e)->reserved;
 201
 202   if (n3) { /* e is a disconnected edge */
 203     GTS_OBJECT (e)->reserved = NULL;
 204     gts_container_add (GTS_CONTAINER (n3), GTS_CONTAINEE (e));
 205     return;
 206   }
 207
 208   if (gts_gedge_connects (e, n1, n2))
 209     return;
 210
 211   if (e->n1 == n)
 212     e->n1 = n1;
 213   else if (e->n2 == n)
 214     e->n2 = n1;
 215   else
 216     g_assert_not_reached ();
 217   GTS_SLIST_CONTAINER (n)->items =
 218     g_slist_remove (GTS_SLIST_CONTAINER (n)->items, e);
 219 }
 220
 221 /**
 222  * gts_gnode_split_expand:
 223  * @ns: a #GtsGNodeSplit.
 224  * @g: a #GtsGraph.
 225  *
 226  * Expands the node split ns adding the new nodes to @g.
 227  */
 228 void gts_gnode_split_expand (GtsGNodeSplit * ns,
 229                              GtsGraph * g)
 230 {
 231   GtsGNode * n1, * n2;
 232   gpointer data[3];
 233   GSList * i;
 234
 235   g_return_if_fail (ns != NULL);
 236   g_return_if_fail (g != NULL);
 237   g_return_if_fail (gts_containee_is_contained (GTS_CONTAINEE (ns->n),
 238                                                 GTS_CONTAINER (g)));
 239
 240   n1 = GTS_GNODE_SPLIT_N1 (ns);
 241   n2 = GTS_GNODE_SPLIT_N2 (ns);
 242
 243   data[0] = ns->n;
 244   data[1] = n1;
 245   data[2] = n2;
 246   gts_container_foreach (GTS_CONTAINER (n1), (GtsFunc) restore_edge, data);
 247   data[1] = n2;
 248   data[2] = n1;
 249   gts_container_foreach (GTS_CONTAINER (n2), (GtsFunc) restore_edge, data);
 250
 251   i = GTS_SLIST_CONTAINER (ns->n)->items;
 252   while (i) {
 253     GSList * next = i->next;
 254     gts_container_remove (GTS_CONTAINER (ns->n), GTS_CONTAINEE (i->data));
 255     i = next;
 256   }
 257   g_assert (gts_container_size (GTS_CONTAINER (ns->n)) == 0);
 258
 259   gts_allow_floating_gnodes = TRUE;
 260   gts_container_remove (GTS_CONTAINER (g), GTS_CONTAINEE (ns->n));
 261   gts_allow_floating_gnodes = FALSE;
 262
 263   gts_container_add (GTS_CONTAINER (g), GTS_CONTAINEE (n1));
 264   gts_container_add (GTS_CONTAINER (g), GTS_CONTAINEE (n2));
 265 }
 266
 267 /* GtsPGraph */
 268
 269 static void pgraph_destroy (GtsObject * object)
 270 {
 271   GtsPGraph * pg = GTS_PGRAPH (object);
 272   guint i;
 273
 274   for (i = 0; i < pg->split->len; i++)
 275     gts_object_destroy (GTS_OBJECT (g_ptr_array_index (pg->split, i)));
 276   g_ptr_array_free (pg->split, TRUE);
 277   g_array_free (pg->levels, TRUE);
 278
 279   (* GTS_OBJECT_CLASS (gts_pgraph_class ())->parent_class->destroy) (object);
 280 }
 281
 282 static void pgraph_class_init (GtsPGraphClass * klass)
 283 {
 284   GTS_OBJECT_CLASS (klass)->destroy = pgraph_destroy;
 285 }
 286
 287 static void pgraph_init (GtsPGraph * pg)
 288 {
 289   pg->g = NULL;
 290   pg->split = g_ptr_array_new ();
 291   pg->levels = g_array_new (FALSE, FALSE, sizeof (guint));
 292   pg->level = 0;
 293   pg->split_class = gts_gnode_split_class ();
 294   pg->edge_class = gts_wgedge_class ();
 295   pg->pos = pg->min = 0;
 296 }
 297
 298 /**
 299  * gts_pgraph_class:
 300  *
 301  * Returns: the #GtsPGraphClass.
 302  */
 303 GtsPGraphClass * gts_pgraph_class (void)
 304 {
 305   static GtsPGraphClass * klass = NULL;
 306
 307   if (klass == NULL) {
 308     GtsObjectClassInfo pgraph_info = {
 309       "GtsPGraph",
 310       sizeof (GtsPGraph),
 311       sizeof (GtsPGraphClass),
 312       (GtsObjectClassInitFunc) pgraph_class_init,
 313       (GtsObjectInitFunc) pgraph_init,
 314       (GtsArgSetFunc) NULL,
 315       (GtsArgGetFunc) NULL
 316     };
 317     klass = gts_object_class_new (gts_object_class (), &pgraph_info);
 318   }
 319
 320   return klass;
 321 }
 322
 323 static void match_neighbor (GtsGNode * n, gpointer * data)
 324 {
 325   if (!GTS_OBJECT (n)->reserved) {
 326     GtsGraph * g = data[0];
 327     GSList ** list = data[1];
 328     GSList * i = GTS_SLIST_CONTAINER (n)->items;
 329     gfloat wmax = - G_MAXFLOAT;
 330     GtsGEdge * emax = NULL;
 331
 332     while (i) {
 333       GtsGNode * n1 = GTS_GNODE_NEIGHBOR (n, i->data);
 334       if (!GTS_OBJECT (n1)->reserved &&
 335           gts_gedge_weight (i->data) > wmax &&
 336           gts_containee_is_contained (GTS_CONTAINEE (n1), GTS_CONTAINER (g))) {
 337         emax = i->data;
 338         wmax = gts_gedge_weight (emax);
 339       }
 340       i = i->next;
 341     }
 342     if (emax) {
 343       GtsGNode * n1 = GTS_GNODE_NEIGHBOR (n, emax);
 344
 345       GTS_OBJECT (n1)->reserved = n;
 346       GTS_OBJECT (n)->reserved = n1;
 347       *list = g_slist_prepend (*list, emax);
 348     }
 349   }
 350 }
 351
 352 static GSList * maximal_matching (GtsGraph * g)
 353 {
 354   GSList * list = NULL;
 355   gpointer data[2];
 356
 357   data[0] = g;
 358   data[1] = &list;
 359   gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) match_neighbor, data);
 360   gts_container_foreach (GTS_CONTAINER (g),
 361                          (GtsFunc) gts_object_reset_reserved,
 362                          NULL);
 363
 364   return list;
 365 }
 366
 367 /**
 368  * gts_pgraph_new:
 369  * @klass: a #GtsPGraphClass.
 370  * @g: a #GtsGraph.
 371  * @split_class: a #GtsGNodeSplitClass.
 372  * @node_class: a #GtsWGNodeClass.
 373  * @edge_class: a #GtsWGEdgeClass.
 374  * @min: the minimum number of nodes.
 375  *
 376  * Creates a new multilevel approximation of graph @g. At each level a
 377  * maximal matching is created using the Heavy Edge Matching (HEM)
 378  * technique of Karypis and Kumar (1997). The newly created nodes are
 379  * of type @node_class and their weight is set to the sum of the
 380  * weights of their children. The newly created edges are of type
 381  * @edge_class and their weight is set to the sum of the weight of the
 382  * collapsed edges. The last level is reached when the maximal
 383  * matching obtained would lead to a graph with less than @min nodes.
 384  *
 385  * Returns: the new #GtsPGraph containing the multilevel
 386  * representation of @g.
 387  */
 388 GtsPGraph * gts_pgraph_new (GtsPGraphClass * klass,
 389                             GtsGraph * g,
 390                             GtsGNodeSplitClass * split_class,
 391                             GtsWGNodeClass * node_class,
 392                             GtsWGEdgeClass * edge_class,
 393                             guint min)
 394 {
 395   GtsPGraph * pg;
 396   GSList * matching;
 397
 398   g_return_val_if_fail (klass != NULL, NULL);
 399   g_return_val_if_fail (g != NULL, NULL);
 400   g_return_val_if_fail (split_class != NULL, NULL);
 401   g_return_val_if_fail (node_class != NULL, NULL);
 402   g_return_val_if_fail (edge_class != NULL, NULL);
 403
 404   pg = GTS_PGRAPH (gts_object_new (GTS_OBJECT_CLASS (klass)));
 405   pg->g = g;
 406   pg->split_class = split_class;
 407   pg->edge_class = edge_class;
 408
 409   while (gts_container_size (GTS_CONTAINER (g)) > min &&
 410          (matching = maximal_matching (g))) {
 411     GSList * i = matching;
 412     guint size = gts_container_size (GTS_CONTAINER (g));
 413
 414     g_array_append_val (pg->levels, size);
 415
 416     while (i && gts_container_size (GTS_CONTAINER (g)) > min) {
 417       GtsGEdge * e = i->data;
 418       GtsGNode * n = GTS_GNODE (gts_wgnode_new (node_class,
 419                                                 gts_gnode_weight (e->n1) +
 420                                                 gts_gnode_weight (e->n2)));
 421       GtsGNodeSplit * ns = gts_gnode_split_new (split_class, n,
 422                                                 GTS_OBJECT (e->n1),
 423                                                 GTS_OBJECT (e->n2));
 424       gts_gnode_split_collapse (ns, g, edge_class);
 425       g_ptr_array_add (pg->split, ns);
 426       i = i->next;
 427     }
 428     g_slist_free (matching);
 429   }
 430
 431   pg->pos = pg->split->len;
 432   pg->min = gts_container_size (GTS_CONTAINER (g));
 433   pg->level = pg->levels->len;
 434
 435   return pg;
 436 }
 437
 438 /**
 439  * gts_pgraph_add_node:
 440  * @pg: a #GtsPGraph.
 441  *
 442  * Adds one node to the multilevel graph @pg by expanding the next
 443  * available #GtsGNodeSplit.
 444  *
 445  * Returns: the expanded #GtsGNodeSplit or #NULL if all the
 446  * #GtsGNodeSplit have already been expanded.
 447  */
 448 GtsGNodeSplit * gts_pgraph_add_node (GtsPGraph * pg)
 449 {
 450   GtsGNodeSplit * ns;
 451
 452   g_return_val_if_fail (pg != NULL, NULL);
 453
 454   if (pg->pos == 0)
 455     return NULL;
 456
 457   ns = g_ptr_array_index (pg->split, --pg->pos);
 458   gts_gnode_split_expand (ns, pg->g);
 459
 460   return ns;
 461 }
 462
 463 /**
 464  * gts_pgraph_remove_node:
 465  * @pg: a #GtsPGraph.
 466  *
 467  * Removes one node from the multilevel graph @pg by collapsing the
 468  * first available #GtsGNodeSplit.
 469  *
 470  * Returns: the collapsed #GtsGNodeSplit or %NULL if all the
 471  * #GtsGNodeSplit have already been collapsed.
 472  */
 473 GtsGNodeSplit * gts_pgraph_remove_node (GtsPGraph * pg)
 474 {
 475   GtsGNodeSplit * ns;
 476
 477   g_return_val_if_fail (pg != NULL, NULL);
 478
 479   if (pg->pos == pg->split->len)
 480     return NULL;
 481
 482   ns = g_ptr_array_index (pg->split, pg->pos++);
 483   gts_gnode_split_collapse (ns, pg->g, pg->edge_class);
 484
 485   return ns;
 486 }
 487
 488 /**
 489  * gts_pgraph_max_node_number:
 490  * @pg: a #GtsPGraph.
 491  *
 492  * Returns: the maximum number of nodes of @pg i.e. the number of
 493  * nodes if all the #GtsGNodeSplit were expanded.
 494  */
 495 guint gts_pgraph_max_node_number (GtsPGraph * pg)
 496 {
 497   g_return_val_if_fail (pg != NULL, 0);
 498
 499   return pg->min + pg->split->len;
 500 }
 501
 502 /**
 503  * gts_pgraph_min_node_number:
 504  * @pg: a #GtsPGraph.
 505  *
 506  * Returns: the minimum number of nodes of @pg i.e. the number of
 507  * nodes if all the #GtsGNodeSplit were collapsed.
 508  */
 509 guint gts_pgraph_min_node_number (GtsPGraph * pg)
 510 {
 511   g_return_val_if_fail (pg != NULL, 0);
 512
 513   return pg->min;
 514 }
 515
 516 /**
 517  * gts_pgraph_set_node_number:
 518  * @pg: a #GtsPGraph.
 519  * @n: a number of nodes.
 520  *
 521  * Performs the required number of collapses or expansions to set the
 522  * number of nodes of @pg to @n.
 523  */
 524 void gts_pgraph_set_node_number (GtsPGraph * pg, guint n)
 525 {
 526   g_return_if_fail (pg != NULL);
 527
 528   n = pg->min + pg->split->len - n;
 529   while (pg->pos > n && gts_pgraph_add_node (pg))
 530     ;
 531   while (pg->pos < n && gts_pgraph_remove_node (pg))
 532     ;
 533 }
 534
 535 /**
 536  * gts_pgraph_get_node_number:
 537  * @pg: a #GtsPGraph.
 538  *
 539  * Returns: the current number of nodes of @pg.
 540  */
 541 guint gts_pgraph_get_node_number (GtsPGraph * pg)
 542 {
 543   g_return_val_if_fail (pg != NULL, 0);
 544
 545   return pg->min + pg->split->len - pg->pos;
 546 }
 547
 548 /**
 549  * gts_pgraph_down:
 550  * @pg: a #GtsPGraph.
 551  * @func: a #GtsFunc or %NULL.
 552  * @data: user data to pass to @func.
 553  *
 554  * Performs the required number of expansions to go from the current
 555  * level to the level immediately below.
 556  *
 557  * If @func is not %NULL, it is called after each #GtsGNodeSplit has
 558  * been expanded.
 559  *
 560  * Returns: %FALSE if it is not possible to go down one level, %TRUE
 561  * otherwise.
 562  */
 563 gboolean gts_pgraph_down (GtsPGraph * pg,
 564                           GtsFunc func,
 565                           gpointer data)
 566 {
 567   guint size;
 568
 569   g_return_val_if_fail (pg != NULL, FALSE);
 570
 571   if (pg->level == 0)
 572     return FALSE;
 573
 574   size = g_array_index (pg->levels, guint, --(pg->level));
 575   while (gts_container_size (GTS_CONTAINER (pg->g)) < size) {
 576     GtsGNodeSplit * ns = gts_pgraph_add_node (pg);
 577
 578     g_assert (ns);
 579     if (func)
 580       (* func) (ns, data);
 581   }
 582   return TRUE;
 583 }
 584