/* GTS - Library for the manipulation of triangulated surfaces
* Copyright (C) 1999 Stéphane Popinet
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public
* License along with this library; if not, write to the
* Free Software Foundation, Inc., 59 Temple Place - Suite 330,
* Boston, MA 02111-1307, USA.
*/
#include <math.h>
#include <stdlib.h>
#include "gts.h"
/* GtsGNode */
gboolean gts_allow_floating_gnodes = FALSE;
static void gnode_remove_container (GtsContainee * i, GtsContainer * c)
{
(* GTS_CONTAINEE_CLASS (GTS_OBJECT_CLASS (gts_gnode_class ())->parent_class)->remove_container) (i, c);
if (GTS_SLIST_CONTAINEE (i)->containers == NULL &&
!gts_allow_floating_gnodes &&
!GTS_OBJECT_DESTROYED(GTS_OBJECT (i)))
gts_object_destroy (GTS_OBJECT (i));
}
static void gnode_class_init (GtsGNodeClass * klass)
{
klass->weight = NULL;
GTS_CONTAINEE_CLASS (klass)->remove_container = gnode_remove_container;
}
static void gnode_init (GtsGNode * n)
{
n->level = 0;
}
/**
* gts_gnode_class:
*
* Returns: the #GtsGNodeClass.
*/
GtsGNodeClass * gts_gnode_class (void)
{
static GtsGNodeClass * klass = NULL;
if (klass == NULL) {
GtsObjectClassInfo gnode_info = {
"GtsGNode",
sizeof (GtsGNode),
sizeof (GtsGNodeClass),
(GtsObjectClassInitFunc) gnode_class_init,
(GtsObjectInitFunc) gnode_init,
(GtsArgSetFunc) NULL,
(GtsArgGetFunc) NULL
};
klass =
gts_object_class_new (GTS_OBJECT_CLASS (gts_slist_container_class ()),
&gnode_info);
}
return klass;
}
/**
* gts_gnode_new:
* @klass: a #GtsGNodeClass.
*
* Returns: a new #GtsGNode.
*/
GtsGNode * gts_gnode_new (GtsGNodeClass * klass)
{
GtsGNode * object;
object = GTS_GNODE (gts_object_new (GTS_OBJECT_CLASS (klass)));
return object;
}
/**
* gts_gnode_foreach_neighbor:
* @n: a #GtsGNode.
* @g: a #GtsGraph or %NULL.
* @func: a #GtsFunc.
* @data: user data to be passed to @func.
*
* Calls @func for each neighbor #GtsGNode of @n (belonging to @g if
* @g is not %NULL.
*/
void gts_gnode_foreach_neighbor (GtsGNode * n,
GtsGraph * g,
GtsFunc func,
gpointer data)
{
GSList * i;
g_return_if_fail (n != NULL);
g_return_if_fail (func != NULL);
i = GTS_SLIST_CONTAINER (n)->items;
while (i) {
GtsGNode * n1 = GTS_GNODE_NEIGHBOR (n, i->data);
if (g == NULL || gts_containee_is_contained (GTS_CONTAINEE (n1),
GTS_CONTAINER (g)))
(* func) (n1, data);
i = i->next;
}
}
/**
* gts_gnode_foreach_edge:
* @n: a #GtsGNode.
* @g: a #GtsGraph or %NULL.
* @func: a #GtsFunc.
* @data: user data to be passed to @func.
*
* Calls @func for each #GtsGEdge connecting @n to another #GtsGNode
* (belonging to @g if @g is not %NULL.
*/
void gts_gnode_foreach_edge (GtsGNode * n,
GtsGraph * g,
GtsFunc func,
gpointer data)
{
GSList * i;
g_return_if_fail (n != NULL);
g_return_if_fail (func != NULL);
i = GTS_SLIST_CONTAINER (n)->items;
while (i) {
GtsGNode * n1 = GTS_GNODE_NEIGHBOR (n, i->data);
if (g == NULL || gts_containee_is_contained (GTS_CONTAINEE (n1),
GTS_CONTAINER (g)))
(* func) (i->data, data);
i = i->next;
}
}
/**
* gts_gnode_degree:
* @n: a #GtsGNode.
* @g: a #GtsGraph or %NULL.
*
* Returns: the number of neighbors of @n (belonging to @g if @g is not %NULL).
*/
guint gts_gnode_degree (GtsGNode * n,
GtsGraph * g)
{
GSList * i;
guint nn = 0;
g_return_val_if_fail (n != NULL, 0);
i = GTS_SLIST_CONTAINER (n)->items;
while (i) {
GtsGNode * n1 = GTS_GNODE_NEIGHBOR (n, i->data);
if (g == NULL || gts_containee_is_contained (GTS_CONTAINEE (n1),
GTS_CONTAINER (g)))
nn++;
i = i->next;
}
return nn;
}
/**
* gts_gnode_move_cost:
* @n: a #GtsGNode.
* @src: a #GtsGraph containing @n.
* @dst: another #GtsGraph.
*
* Returns: the cost (increase in the sum of the weights of the edges cut) of
* moving @n from @src to @dst.
*/
gfloat gts_gnode_move_cost (GtsGNode * n,
GtsGraph * src,
GtsGraph * dst)
{
GSList * i;
gfloat cost = 0.;
g_return_val_if_fail (n != NULL, G_MAXFLOAT);
g_return_val_if_fail (src != NULL, G_MAXFLOAT);
g_return_val_if_fail (dst != NULL, G_MAXFLOAT);
g_return_val_if_fail (gts_containee_is_contained (GTS_CONTAINEE (n),
GTS_CONTAINER (src)),
G_MAXFLOAT);
i = GTS_SLIST_CONTAINER (n)->items;
while (i) {
GtsGEdge * ge = i->data;
GtsGNode * neighbor = GTS_GNODE_NEIGHBOR (n, ge);
if (gts_containee_is_contained (GTS_CONTAINEE (neighbor),
GTS_CONTAINER (src)))
cost += gts_gedge_weight (ge);
else if (gts_containee_is_contained (GTS_CONTAINEE (neighbor),
GTS_CONTAINER (dst)))
cost -= gts_gedge_weight (ge);
i = i->next;
}
return cost;
}
/**
* gts_gnode_weight:
* @n: a #GtsGNode.
*
* Returns: the weight of @n as defined by the weight() method of the
* #GtsGNodeClass.
*/
gfloat gts_gnode_weight (GtsGNode * n)
{
g_return_val_if_fail (n != NULL, 0.);
if (GTS_GNODE_CLASS (GTS_OBJECT (n)->klass)->weight)
return (* GTS_GNODE_CLASS (GTS_OBJECT (n)->klass)->weight) (n);
return 1.;
}
/* GtsNGNode */
static void ngnode_init (GtsNGNode * n)
{
n->id = 0;
}
/**
* gts_ngnode_class:
*
* Returns: the #GtsNGNodeClass.
*/
GtsNGNodeClass * gts_ngnode_class (void)
{
static GtsNGNodeClass * klass = NULL;
if (klass == NULL) {
GtsObjectClassInfo ngnode_info = {
"GtsNGNode",
sizeof (GtsNGNode),
sizeof (GtsNGNodeClass),
(GtsObjectClassInitFunc) NULL,
(GtsObjectInitFunc) ngnode_init,
(GtsArgSetFunc) NULL,
(GtsArgGetFunc) NULL
};
klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_gnode_class ()),
&ngnode_info);
}
return klass;
}
/**
* gts_ngnode_new:
* @klass: a #GtsNGNodeClass.
*
* Returns: a new #GtsNGNode with identity @id.
*/
GtsNGNode * gts_ngnode_new (GtsNGNodeClass * klass,
guint id)
{
GtsNGNode * n;
n = GTS_NGNODE (gts_gnode_new (GTS_GNODE_CLASS (klass)));
n->id = id;
return n;
}
/* GtsWGNode */
static gfloat wgnode_weight (GtsGNode * n)
{
return GTS_WGNODE (n)->weight;
}
static void wgnode_class_init (GtsWGNodeClass * klass)
{
GTS_GNODE_CLASS (klass)->weight = wgnode_weight;
}
static void wgnode_init (GtsWGNode * n)
{
n->weight = 1.;
}
/**
* gts_wgnode_class:
*
* Returns: the #GtsWGNodeClass.
*/
GtsWGNodeClass * gts_wgnode_class (void)
{
static GtsWGNodeClass * klass = NULL;
if (klass == NULL) {
GtsObjectClassInfo wgnode_info = {
"GtsWGNode",
sizeof (GtsWGNode),
sizeof (GtsWGNodeClass),
(GtsObjectClassInitFunc) wgnode_class_init,
(GtsObjectInitFunc) wgnode_init,
(GtsArgSetFunc) NULL,
(GtsArgGetFunc) NULL
};
klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_gnode_class ()),
&wgnode_info);
}
return klass;
}
/**
* gts_wgnode_new:
* @klass: a #GtsWGNodeClass.
* @weight: the weight of the #GtsWGNode to create.
*
* Returns: a new #GtsWGNode of weight @weight.
*/
GtsWGNode * gts_wgnode_new (GtsWGNodeClass * klass,
gfloat weight)
{
GtsWGNode * n;
n = GTS_WGNODE (gts_gnode_new (GTS_GNODE_CLASS (klass)));
n->weight = weight;
return n;
}
/* GtsPNode */
static void pnode_write (GtsGNode * n, FILE * fp)
{
if (GTS_IS_NVERTEX (GTS_PNODE (n)->data))
fprintf (fp, "label=\"%p:%s\",",
GTS_PNODE (n)->data,
GTS_NVERTEX (GTS_PNODE (n)->data)->name);
else
fprintf (fp, "label=\"%p\",", GTS_PNODE (n)->data);
}
static void pnode_class_init (GtsPNodeClass * klass)
{
GTS_GNODE_CLASS (klass)->write = pnode_write;
}
static void pnode_init (GtsPNode * pn)
{
pn->data = NULL;
}
/**
* gts_pnode_class:
*
* Returns: the #GtsPNodeClass.
*/
GtsPNodeClass * gts_pnode_class (void)
{
static GtsPNodeClass * klass = NULL;
if (klass == NULL) {
GtsObjectClassInfo pnode_info = {
"GtsPNode",
sizeof (GtsPNode),
sizeof (GtsPNodeClass),
(GtsObjectClassInitFunc) pnode_class_init,
(GtsObjectInitFunc) pnode_init,
(GtsArgSetFunc) NULL,
(GtsArgGetFunc) NULL
};
klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_gnode_class ()),
&pnode_info);
}
return klass;
}
/**
* gts_pnode_new:
* @klass: a #GtsPNodeClass.
* @data: user data.
*
* Returns: a new #GtsPNode associated with @data.
*/
GtsPNode * gts_pnode_new (GtsPNodeClass * klass, gpointer data)
{
GtsPNode * pn;
pn = GTS_PNODE (gts_object_new (GTS_OBJECT_CLASS (klass)));
pn->data = data;
return pn;
}
/* GtsFNode */
static void fnode_write (GtsGNode * n, FILE * fp)
{
fprintf (fp, "label=\"%p\",", GTS_FNODE (n)->f);
}
static void fnode_class_init (GtsGNodeClass * klass)
{
klass->write = fnode_write;
}
static void fnode_init (GtsFNode * fn)
{
fn->f = NULL;
}
/**
* gts_fnode_class:
*
* Returns: the #GtsFNodeClass.
*/
GtsFNodeClass * gts_fnode_class (void)
{
static GtsFNodeClass * klass = NULL;
if (klass == NULL) {
GtsObjectClassInfo fnode_info = {
"GtsFNode",
sizeof (GtsFNode),
sizeof (GtsFNodeClass),
(GtsObjectClassInitFunc) fnode_class_init,
(GtsObjectInitFunc) fnode_init,
(GtsArgSetFunc) NULL,
(GtsArgGetFunc) NULL
};
klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_gnode_class ()),
&fnode_info);
}
return klass;
}
/**
* gts_fnode_new:
* @klass: a #GtsFNodeClass.
* @f: a #GtsFace.
*
* Returns: a new #GtsFNode associated with face @f.
*/
GtsFNode * gts_fnode_new (GtsFNodeClass * klass, GtsFace * f)
{
GtsFNode * fn;
g_return_val_if_fail (f != NULL, NULL);
fn = GTS_FNODE (gts_object_new (GTS_OBJECT_CLASS (klass)));
fn->f = f;
return fn;
}
/* GtsGEdge */
static void gedge_destroy (GtsObject * object)
{
GtsGEdge * ge = GTS_GEDGE (object);
if (ge->n1)
gts_container_remove (GTS_CONTAINER (ge->n1), GTS_CONTAINEE (ge));
if (ge->n2)
gts_container_remove (GTS_CONTAINER (ge->n2), GTS_CONTAINEE (ge));
(* GTS_OBJECT_CLASS (gts_gedge_class ())->parent_class->destroy) (object);
}
static void gedge_remove_container (GtsContainee * i, GtsContainer * c)
{
GtsGEdge * ge = GTS_GEDGE (i);
GtsGNode * n1 = ge->n1;
GtsGNode * n2 = ge->n2;
ge->n1 = ge->n2 = NULL;
if (n1 != NULL && n2 != NULL) {
if (GTS_CONTAINER (n1) == c) {
if (n2 && n2 != n1) gts_container_remove (GTS_CONTAINER (n2), i);
}
else if (GTS_CONTAINER (n2) == c) {
if (n1 && n1 != n2) gts_container_remove (GTS_CONTAINER (n1), i);
}
else
g_assert_not_reached ();
(* GTS_OBJECT_CLASS (gts_gedge_class ())->parent_class->destroy)
(GTS_OBJECT (i));
}
}
static gboolean gedge_is_contained (GtsContainee * i, GtsContainer * c)
{
GtsGEdge * ge = GTS_GEDGE (i);
if (GTS_CONTAINER (ge->n1) == c || GTS_CONTAINER (ge->n2) == c)
return TRUE;
return FALSE;
}
static void gedge_class_init (GtsGEdgeClass * klass)
{
klass->link = NULL;
klass->weight = NULL;
GTS_CONTAINEE_CLASS (klass)->remove_container = gedge_remove_container;
GTS_CONTAINEE_CLASS (klass)->is_contained = gedge_is_contained;
GTS_OBJECT_CLASS (klass)->destroy = gedge_destroy;
}
static void gedge_init (GtsGEdge * object)
{
object->n1 = object->n2 = NULL;
}
/**
* gts_gedge_class:
*
* Returns: the #GtsGEdgeClass.
*/
GtsGEdgeClass * gts_gedge_class (void)
{
static GtsGEdgeClass * klass = NULL;
if (klass == NULL) {
GtsObjectClassInfo gedge_info = {
"GtsGEdge",
sizeof (GtsGEdge),
sizeof (GtsGEdgeClass),
(GtsObjectClassInitFunc) gedge_class_init,
(GtsObjectInitFunc) gedge_init,
(GtsArgSetFunc) NULL,
(GtsArgGetFunc) NULL
};
klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_containee_class ()),
&gedge_info);
}
return klass;
}
/**
* gts_gedge_new:
* @klass: a #GtsGEdgeClass.
* @n1: a #GtsGNode.
* @n2: another #GtsGNode.
*
* Returns: a new #GtsGEdge linking @n1 and @n2.
*/
GtsGEdge * gts_gedge_new (GtsGEdgeClass * klass, GtsGNode * n1, GtsGNode * n2)
{
GtsGEdge * object;
g_return_val_if_fail (n1 != NULL, NULL);
g_return_val_if_fail (n2 != NULL, NULL);
object = GTS_GEDGE (gts_object_new (GTS_OBJECT_CLASS (klass)));
object->n1 = n1;
gts_container_add (GTS_CONTAINER (n1), GTS_CONTAINEE (object));
object->n2 = n2;
if (n1 != n2)
gts_container_add (GTS_CONTAINER (n2), GTS_CONTAINEE (object));
if (klass->link)
object = (* klass->link) (object, n1, n2);
return object;
}
/**
* gts_gedge_weight:
* @e: a #GtsGEdge.
*
* Returns: the weight of edge @e as defined by the weight() method of
* #GtsGEdgeClass.
*/
gfloat gts_gedge_weight (GtsGEdge * e)
{
g_return_val_if_fail (e != NULL, 0.);
if (GTS_GEDGE_CLASS (GTS_OBJECT (e)->klass)->weight)
return (* GTS_GEDGE_CLASS (GTS_OBJECT (e)->klass)->weight) (e);
return 1.;
}
/* GtsPGEdge */
static void pgedge_write (GtsGEdge * ge, FILE * fp)
{
if (GTS_IS_EDGE (GTS_PGEDGE (ge)->data)) {
GtsEdge * e = GTS_PGEDGE (ge)->data;
guint n = g_slist_length (e->triangles);
fprintf (fp, "label=\"%p:%s:%d\",color=%s", e,
GTS_IS_NEDGE (e) ? GTS_NEDGE (e)->name : "",
n,
n == 0 ? "black" :
n == 1 ? "blue" :
n == 2 ? "green" :
n == 3 ? "violet" :
n == 4 ? "red" :
"pink");
}
else
fprintf (fp, "label=\"%p\",", GTS_PGEDGE (ge)->data);
}
static void pgedge_class_init (GtsPGEdgeClass * klass)
{
GTS_GEDGE_CLASS (klass)->write = pgedge_write;
}
static void pgedge_init (GtsPGEdge * e)
{
e->data = NULL;
}
/**
* gts_pgedge_class:
*
* Returns: the #GtsPGEdgeClass.
*/
GtsPGEdgeClass * gts_pgedge_class (void)
{
static GtsPGEdgeClass * klass = NULL;
if (klass == NULL) {
GtsObjectClassInfo pgedge_info = {
"GtsPGEdge",
sizeof (GtsPGEdge),
sizeof (GtsPGEdgeClass),
(GtsObjectClassInitFunc) pgedge_class_init,
(GtsObjectInitFunc) pgedge_init,
(GtsArgSetFunc) NULL,
(GtsArgGetFunc) NULL
};
klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_gedge_class ()),
&pgedge_info);
}
return klass;
}
/**
* gts_pgedge_new:
* @klass: a #GtsPGEdgeClass.
* @n1: a #GtsGNode.
* @n2: another #GtsGNode.
* @data: user data.
*
* Returns: a new #GtsPGEdge associated with @data linking @n1 and @n2.
*/
GtsPGEdge * gts_pgedge_new (GtsPGEdgeClass * klass,
GtsGNode * g1,
GtsGNode * g2,
gpointer data)
{
GtsPGEdge * we;
we = GTS_PGEDGE (gts_gedge_new (GTS_GEDGE_CLASS (klass), g1, g2));
we->data = data;
return we;
}
/* GtsWGEdge */
static gfloat wgedge_weight (GtsGEdge * e)
{
return GTS_WGEDGE (e)->weight;
}
static void wgedge_class_init (GtsWGEdgeClass * klass)
{
GTS_GEDGE_CLASS (klass)->weight = wgedge_weight;
}
static void wgedge_init (GtsWGEdge * e)
{
e->weight = 1.;
}
/**
* gts_wgedge_class:
*
* Returns: the #GtsWGEdgeClass.
*/
GtsWGEdgeClass * gts_wgedge_class (void)
{
static GtsWGEdgeClass * klass = NULL;
if (klass == NULL) {
GtsObjectClassInfo wgedge_info = {
"GtsWGEdge",
sizeof (GtsWGEdge),
sizeof (GtsWGEdgeClass),
(GtsObjectClassInitFunc) wgedge_class_init,
(GtsObjectInitFunc) wgedge_init,
(GtsArgSetFunc) NULL,
(GtsArgGetFunc) NULL
};
klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_gedge_class ()),
&wgedge_info);
}
return klass;
}
/**
* gts_wgedge_new:
* @klass: a #GtsWGEdgeClass.
* @n1: a #GtsGNode.
* @n2: another #GtsGNode.
* @weight: the weight of the new edge.
*
* Returns: a new #GtsWGEdge of weight @weight linking @n1 and @n2.
*/
GtsWGEdge * gts_wgedge_new (GtsWGEdgeClass * klass,
GtsGNode * g1,
GtsGNode * g2,
gfloat weight)
{
GtsWGEdge * we;
we = GTS_WGEDGE (gts_gedge_new (GTS_GEDGE_CLASS (klass), g1, g2));
we->weight = weight;
return we;
}
/* GtsGraph */
static void graph_init (GtsGraph * g)
{
g->graph_class = gts_graph_class ();
g->node_class = gts_gnode_class ();
g->edge_class = gts_gedge_class ();
}
static void graph_write (GtsObject * object, FILE * fp)
{
GtsGraph * graph = GTS_GRAPH (object);
fprintf (fp, " %s %s %s",
object->klass->info.name,
GTS_OBJECT_CLASS (graph->node_class)->info.name,
GTS_OBJECT_CLASS (graph->edge_class)->info.name);
}
static void graph_read (GtsObject ** object, GtsFile * f)
{
GtsObjectClass * klass;
if (f->type != GTS_STRING) {
gts_file_error (f, "expecting a string (GtsGNodeClass)");
return;
}
klass = gts_object_class_from_name (f->token->str);
if (klass == NULL) {
gts_file_error (f, "unknown class `%s'", f->token->str);
return;
}
if (!gts_object_class_is_from_class (klass, gts_gnode_class ())) {
gts_file_error (f, "class `%s' is not a GtsGNodeClass", f->token->str);
return;
}
GTS_GRAPH (*object)->node_class = GTS_GNODE_CLASS (klass);
gts_file_next_token (f);
if (f->type != GTS_STRING) {
gts_file_error (f, "expecting a string (GtsGEdgeClass)");
return;
}
klass = gts_object_class_from_name (f->token->str);
if (klass == NULL) {
gts_file_error (f, "unknown class `%s'", f->token->str);
return;
}
if (!gts_object_class_is_from_class (klass, gts_gedge_class ())) {
gts_file_error (f, "class `%s' is not a GtsGEdgeClass", f->token->str);
return;
}
GTS_GRAPH (*object)->edge_class = GTS_GEDGE_CLASS (klass);
gts_file_next_token (f);
}
static void graph_class_init (GtsGraphClass * klass)
{
klass->weight = NULL;
GTS_OBJECT_CLASS (klass)->write = graph_write;
GTS_OBJECT_CLASS (klass)->read = graph_read;
}
/**
* gts_graph_class:
*
* Returns: the #GtsGraphClass.
*/
GtsGraphClass * gts_graph_class (void)
{
static GtsGraphClass * klass = NULL;
if (klass == NULL) {
GtsObjectClassInfo graph_info = {
"GtsGraph",
sizeof (GtsGraph),
sizeof (GtsGraphClass),
(GtsObjectClassInitFunc) graph_class_init,
(GtsObjectInitFunc) graph_init,
(GtsArgSetFunc) NULL,
(GtsArgGetFunc) NULL
};
klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_hash_container_class ()),
&graph_info);
}
return klass;
}
/**
* gts_graph_new:
* @klass: a #GtsGraphClass.
* @node_class: a #GtsGNodeClass.
* @edge_class: a #GtsGEdgeClass.
*
* Returns: a new #GtsGraph using @node_class and @edge_class as node types.
*/
GtsGraph * gts_graph_new (GtsGraphClass * klass,
GtsGNodeClass * node_class,
GtsGEdgeClass * edge_class)
{
GtsGraph * g;
g_return_val_if_fail (klass != NULL, NULL);
g_return_val_if_fail (node_class != NULL, NULL);
g_return_val_if_fail (edge_class != NULL, NULL);
g = GTS_GRAPH (gts_object_new (GTS_OBJECT_CLASS (klass)));
g->node_class = node_class;
g->edge_class = edge_class;
return g;
}
static void compute_degree (GtsGNode * n, gpointer * data)
{
GtsGraph * g = data[0];
GtsRange * degree = data[1];
gts_range_add_value (degree, gts_gnode_degree (n, g));
}
/**
* gts_graph_print_stats:
* @g: a #GtsGraph.
* @fp: a file pointer.
*
* Writes to @fp a summary of the properties of @g.
*/
void gts_graph_print_stats (GtsGraph * g, FILE * fp)
{
GtsRange degree;
gpointer data[2];
g_return_if_fail (g != NULL);
g_return_if_fail (fp != NULL);
fprintf (fp, "# nodes: %d weight: %g\n",
gts_container_size (GTS_CONTAINER (g)),
gts_graph_weight (g));
fprintf (fp, "# degree: ");
gts_range_init (°ree);
data[0] = g;
data[1] = °ree;
gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) compute_degree, data);
gts_range_update (°ree);
gts_range_print (°ree, fp);
fprintf (fp, "\n");
fprintf (fp, "# edges cut: %d edges cut weight: %g\n",
gts_graph_edges_cut (g),
gts_graph_edges_cut_weight (g));
}
struct _GtsGraphTraverse {
GtsFifo * q;
GtsGraph * g;
};
static void reset_level (GtsGNode * n)
{
n->level = 0;
}
/**
* gts_graph_traverse_new:
* @g: a #GtsGraph.
* @n: a #GtsGNode belonging to @g.
* @type: the type of traversal.
* @reinit: if %TRUE, the traversal is reinitialized.
*
* Returns: a new #GtsGraphTraverse initialized for the traversal of
* @g of type @type, starting from @n.
*/
GtsGraphTraverse * gts_graph_traverse_new (GtsGraph * g,
GtsGNode * n,
GtsTraverseType type,
gboolean reinit)
{
GtsGraphTraverse * t;
g_return_val_if_fail (g != NULL, NULL);
g_return_val_if_fail (n != NULL, NULL);
g_return_val_if_fail (gts_containee_is_contained (GTS_CONTAINEE (n),
GTS_CONTAINER (g)),
NULL);
if (reinit)
gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) reset_level, NULL);
t = g_malloc (sizeof (GtsGraphTraverse));
t->q = gts_fifo_new ();
t->g = g;
n->level = 1;
gts_fifo_push (t->q, n);
return t;
}
static void push_neighbor (GtsGNode * n, gpointer * data)
{
GtsFifo * q = data[0];
GtsGNode * u = data[1];
if (n->level == 0) {
n->level = u->level + 1;
gts_fifo_push (q, n);
}
}
/**
* gts_graph_traverse_next:
* @t: a #GtsGraphTraverse.
*
* Returns: the next #GtsGNode of the traversal defined by @t or %NULL
* if the traversal is complete.
*/
GtsGNode * gts_graph_traverse_next (GtsGraphTraverse * t)
{
GtsGNode * u;
g_return_val_if_fail (t != NULL, NULL);
u = gts_fifo_pop (t->q);
if (u) {
gpointer data[2];
data[0] = t->q;
data[1] = u;
gts_gnode_foreach_neighbor (u, t->g, (GtsFunc) push_neighbor, data);
}
return u;
}
/**
* gts_graph_traverse_what_next:
* @t: a #GtsGraphTraverse.
*
* Returns: the next #GtsGNode of the traversal defined by @t or %NULL
* if the traversal is complete but without advancing the traversal.
*/
GtsGNode * gts_graph_traverse_what_next (GtsGraphTraverse * t)
{
g_return_val_if_fail (t != NULL, NULL);
return gts_fifo_top (t->q);
}
/**
* gts_graph_traverse_destroy:
* @t: a #GtsGraphTraverse.
*
* Frees all the memory allocated for @t.
*/
void gts_graph_traverse_destroy (GtsGraphTraverse * t)
{
g_return_if_fail (t != NULL);
gts_fifo_destroy (t->q);
g_free (t);
}
static void edge_foreach_node (GtsGNode * n, gpointer * info)
{
GtsFunc func = (GtsFunc) info[0];
gpointer data = info[1];
GHashTable * hash = info[2];
GSList * i = GTS_SLIST_CONTAINER (n)->items;
while (i) {
GtsGEdge * e = i->data;
if (!g_hash_table_lookup (hash, e)) {
(* func) (e, data);
g_hash_table_insert (hash, e, e);
}
i = i->next;
}
}
/**
* gts_graph_foreach_edge:
* @g: a #GtsGraph.
* @func: a #GtsFunc.
* @data: user data to be passed to @func.
*
* Calls @func for each #GtsEdge of @g.
*/
void gts_graph_foreach_edge (GtsGraph * g, GtsFunc func, gpointer data)
{
gpointer info[3];
GHashTable * hash;
g_return_if_fail (g != NULL);
g_return_if_fail (func != NULL);
info[0] = func;
info[1] = data;
info[2] = hash = g_hash_table_new (NULL, NULL);
gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) edge_foreach_node, info);
g_hash_table_destroy (hash);
}
/**
* gts_graph_weight:
* @g: a #GtsGraph.
*
* Returns: the weight of graph @g as defined by the weight() method
* of #GtsGraphClass.
*/
gfloat gts_graph_weight (GtsGraph * g)
{
g_return_val_if_fail (g != NULL, 0.);
if (GTS_GRAPH_CLASS (GTS_OBJECT (g)->klass)->weight)
return (* GTS_GRAPH_CLASS (GTS_OBJECT (g)->klass)->weight) (g);
return (gfloat) gts_container_size (GTS_CONTAINER (g));
}
/**
* gts_graph_distance_sum:
* @g: a #GtsGraph.
* @center: a #GtsGNode of @g.
*
* Returns: the sum of the distances between all the other #GtsGNode
* of @g and @center.
*/
guint gts_graph_distance_sum (GtsGraph * g, GtsGNode * center)
{
GtsGraphTraverse * t;
GtsGNode * n;
guint sum = 0;
g_return_val_if_fail (g != NULL, 0);
g_return_val_if_fail (center != NULL, 0);
t = gts_graph_traverse_new (g, center, GTS_BREADTH_FIRST, TRUE);
while ((n = gts_graph_traverse_next (t)))
sum += n->level - 1;
gts_graph_traverse_destroy (t);
return sum;
}
/**
* gts_graph_farthest:
* @g: a #GtsGraph.
* @gnodes: a list of #GtsGNode belonging to @g.
*
* Returns: the #GtsGNode belonging to @g and farthest from all the nodes in
* @gnodes (hmmm, definition of "farthest"?).
*/
GtsGNode * gts_graph_farthest (GtsGraph * g, GSList * gnodes)
{
GtsGNode * farthest = NULL;
GSList * i;
gboolean reinit = TRUE, changed = TRUE;
guint level = 1;
g_return_val_if_fail (g != NULL, NULL);
/* initialize traversals */
i = gnodes;
while (i) {
GTS_OBJECT (i->data)->reserved =
gts_graph_traverse_new (g, i->data, GTS_BREADTH_FIRST, reinit);
reinit = FALSE;
i = i->next;
}
while (changed) {
changed = FALSE;
i = gnodes;
while (i) {
GtsGraphTraverse * t = GTS_OBJECT (i->data)->reserved;
GtsGNode * n;
while ((n = gts_graph_traverse_what_next (t)) && n->level == level) {
changed = TRUE;
farthest = n;
gts_graph_traverse_next (t);
}
i = i->next;
}
level++;
}
/* destroy traversals */
i = gnodes;
while (i) {
gts_graph_traverse_destroy (GTS_OBJECT (i->data)->reserved);
GTS_OBJECT (i->data)->reserved = NULL;
i = i->next;
}
return farthest;
}
static void neighbor_count (GtsGNode * n, gpointer * data)
{
guint * cuts = data[0];
GtsGraph * g = data[1];
if (!gts_containee_is_contained (GTS_CONTAINEE (n), GTS_CONTAINER (g)))
(*cuts)++;
}
static void count_edge_cuts (GtsGNode * n, gpointer * data)
{
gts_gnode_foreach_neighbor (n, NULL, (GtsFunc) neighbor_count, data);
}
/**
* gts_graph_edges_cut:
* @g: a #GtsGraph.
*
* Returns: the number of edges of @g connecting nodes belonging to @g
* to nodes not belonging to @g.
*/
guint gts_graph_edges_cut (GtsGraph * g)
{
guint cuts = 0;
gpointer data[2];
g_return_val_if_fail (g != NULL, 0);
data[0] = &cuts;
data[1] = g;
gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) count_edge_cuts, data);
return cuts;
}
static void sum_edge_cuts_weight (GtsGNode * n, gpointer * data)
{
gfloat * weight = data[0];
GtsGraph * g = data[1];
GSList * i = GTS_SLIST_CONTAINER (n)->items;
while (i) {
GtsGNode * n1 = GTS_GNODE_NEIGHBOR (n, i->data);
if (!gts_containee_is_contained (GTS_CONTAINEE (n1), GTS_CONTAINER (g)))
*weight += gts_gedge_weight (i->data);
i = i->next;
}
}
/**
* gts_graph_edges_cut_weight:
* @g: a #GtsGraph.
*
* Returns: the sum of the weights of the edges of @g connecting nodes
* belonging to @g to nodes not belonging to @g.
*/
gfloat gts_graph_edges_cut_weight (GtsGraph * g)
{
gfloat weight = 0.;
gpointer data[2];
g_return_val_if_fail (g != NULL, 0);
data[0] = &weight;
data[1] = g;
gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) sum_edge_cuts_weight,
data);
return weight;
}
/**
* gts_graph_read_jostle:
* @g: a #GtsGraph.
* @fp: a #GtsFile.
*
* Adds to @g the nodes and edges defined in the file pointed to by
* @fp. This file must use the Jostle "graph" ASCII format.
* The nodes created are of type #GtsNGNode and their identities are the
* line number at which they appear in @fp.
*
* Returns: 0 if the lecture was successful, the line number at which
* an error occured otherwise (in which case the @error field of @fp
* is set).
*/
guint gts_graph_read_jostle (GtsGraph * g, GtsFile * fp)
{
guint nn, ne, n;
GtsGNode ** nodes;
g_return_val_if_fail (g != NULL, 1);
g_return_val_if_fail (fp != NULL, 1);
if (fp->type != GTS_INT) {
gts_file_error (fp, "expecting an integer (number of nodes)");
return fp->line;
}
nn = atoi (fp->token->str);
gts_file_next_token (fp);
if (fp->type != GTS_INT) {
gts_file_error (fp, "expecting an integer (number of edges)");
return fp->line;
}
ne = atoi (fp->token->str);
gts_file_first_token_after (fp, '\n');
nodes = g_malloc (sizeof (GtsGNode *)*(nn + 1));
n = 0;
while (n < nn && fp->type != GTS_ERROR) {
GtsNGNode * node = gts_ngnode_new (gts_ngnode_class (), fp->line);
nodes[n++] = GTS_GNODE (node);
gts_container_add (GTS_CONTAINER (g), GTS_CONTAINEE (node));
do {
if (fp->type != GTS_INT)
gts_file_error (fp, "expecting an integer (node index)");
else {
guint in = atoi (fp->token->str);
if (in == 0 || in > nn)
gts_file_error (fp, "node index `%d' is out of range `[1,%d]'",
in, nn);
else if (in == n)
gts_file_error (fp, "node index `%d' references itself", in);
else if (in < n) {
gts_gedge_new (g->edge_class, GTS_GNODE (node), nodes[in - 1]);
ne--;
gts_file_next_token (fp);
}
}
} while (fp->type != GTS_ERROR && fp->type != '\n');
}
g_free (nodes);
if (fp->type != GTS_ERROR) {
if (n != nn)
gts_file_error (fp, "only `%d' nodes read out of `%d'",
n, nn);
else if (ne > 0)
gts_file_error (fp, "`%d' unallocated edges remaining",
ne);
}
if (fp->type == GTS_ERROR)
return fp->line;
return 0;
}
static void count_edges (GtsGEdge * e, guint * nedge)
{
(*nedge)++;
}
static void write_node (GtsObject * node, gpointer * data)
{
FILE * fp = data[0];
guint * nnode = data[1];
node->reserved = GUINT_TO_POINTER ((*nnode)++);
if (node->klass->write)
(* node->klass->write) (node, fp);
fputc ('\n', fp);
}
static void write_edge (GtsGEdge * edge, FILE * fp)
{
fprintf (fp, "%u %u",
GPOINTER_TO_UINT (GTS_OBJECT (edge->n1)->reserved),
GPOINTER_TO_UINT (GTS_OBJECT (edge->n2)->reserved));
if (GTS_OBJECT (edge)->klass->write)
(* GTS_OBJECT (edge)->klass->write) (GTS_OBJECT (edge), fp);
fputc ('\n', fp);
}
/**
* gts_graph_write:
* @g: a #GtsGraph.
* @fp: a file pointer.
*
* Writes in the file @fp an ASCII representation of @g. The file
* format is as follows.
*
* All the lines beginning with #GTS_COMMENTS are ignored. The first line
* contains two unsigned integers separated by spaces. The first
* integer is the number of nodes, nn, the second is the number of
* edges, ne.
*
* Follows nn lines containing node description.
* Follows ne lines containing the two indices (starting
* from one) of the nodes of each edge.
*
* The format described above is the least common denominator to all
* GTS files. Consistent with an object-oriented approach, the GTS
* file format is extensible. Each of the lines of the file can be
* extended with user-specific attributes accessible through the
* read() and write() virtual methods of each of the objects written
* (graph, nodes or edges). When read with different object classes,
* these extra attributes are just ignored.
*/
void gts_graph_write (GtsGraph * g, FILE * fp)
{
guint nnode = 1, nedge = 0;
gpointer data[2];
g_return_if_fail (g != NULL);
g_return_if_fail (fp != NULL);
gts_graph_foreach_edge (g, (GtsFunc) count_edges, &nedge);
fprintf (fp, "%u %u", gts_container_size (GTS_CONTAINER (g)), nedge);
if (GTS_OBJECT (g)->klass->write)
(* GTS_OBJECT (g)->klass->write) (GTS_OBJECT (g), fp);
fputc ('\n', fp);
data[0] = fp;
data[1] = &nnode;
gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) write_node, data);
gts_graph_foreach_edge (g, (GtsFunc) write_edge, fp);
gts_container_foreach (GTS_CONTAINER (g),
(GtsFunc) gts_object_reset_reserved, NULL);
}
/**
* gts_graph_read:
* @fp: a #GtsFile.
*
* Reads a graph from a file.
*
* Returns: the new #GtsGraph or %NULL if an error occured (in which
* case the @error field of @fp is set).
*/
GtsGraph * gts_graph_read (GtsFile * fp)
{
GtsGraph * g;
GtsGNode ** nodes;
guint nn, ne, n;
g_return_val_if_fail (fp != NULL, NULL);
if (fp->type != GTS_INT) {
gts_file_error (fp, "expecting an integer (number of nodes)");
return NULL;
}
nn = atoi (fp->token->str);
gts_file_next_token (fp);
if (fp->type != GTS_INT) {
gts_file_error (fp, "expecting an integer (number of edges)");
return NULL;
}
ne = atoi (fp->token->str);
gts_file_next_token (fp);
if (fp->type != '\n') {
GtsObjectClass * klass;
gts_graph_class ();
gts_gnode_class ();
gts_gedge_class ();
if (fp->type != GTS_STRING) {
gts_file_error (fp, "expecting a string (GtsGraphClass)");
return NULL;
}
klass = gts_object_class_from_name (fp->token->str);
if (klass == NULL) {
gts_file_error (fp, "unknown class `%s'", fp->token->str);
return NULL;
}
if (!gts_object_class_is_from_class (klass, gts_graph_class ())) {
gts_file_error (fp, "class `%s' is not a GtsGraphClass", fp->token->str);
return NULL;
}
g = GTS_GRAPH (gts_object_new (klass));
g->graph_class = GTS_GRAPH_CLASS (klass);
gts_file_next_token (fp);
(* klass->read) ((GtsObject **) &g, fp);
if (fp->type == GTS_ERROR) {
gts_object_destroy (GTS_OBJECT (g));
return NULL;
}
}
else
g = GTS_GRAPH (gts_object_new (GTS_OBJECT_CLASS (gts_graph_class ())));
gts_file_first_token_after (fp, '\n');
if (nn <= 0)
return g;
nodes = g_malloc ((nn + 1)*sizeof (GtsGNode *));
n = 0;
while (n < nn && fp->type != GTS_ERROR) {
GtsObject * new_node =
gts_object_new (GTS_OBJECT_CLASS (g->node_class));
gts_container_add (GTS_CONTAINER (g), GTS_CONTAINEE (new_node));
if (GTS_OBJECT_CLASS (g->node_class)->read)
(*GTS_OBJECT_CLASS (g->node_class)->read) (&new_node, fp);
gts_file_first_token_after (fp, '\n');
nodes[n++] = GTS_GNODE (new_node);
}
if (fp->type == GTS_ERROR)
nn = n;
n = 0;
while (n < ne && fp->type != GTS_ERROR) {
guint n1, n2;
if (fp->type != GTS_INT)
gts_file_error (fp, "expecting an integer (first node index)");
else {
n1 = atoi (fp->token->str);
if (n1 == 0 || n1 > nn)
gts_file_error (fp, "node index `%d' is out of range `[1,%d]'",
n1, nn);
else {
gts_file_next_token (fp);
if (fp->type != GTS_INT)
gts_file_error (fp, "expecting an integer (second node index)");
else {
n2 = atoi (fp->token->str);
if (n2 == 0 || n2 > nn)
gts_file_error (fp, "node index `%d' is out of range `[1,%d]'",
n2, nn);
else {
GtsGEdge * new_edge =
gts_gedge_new (g->edge_class, nodes[n1 - 1], nodes [n2 - 1]);
gts_file_next_token (fp);
if (fp->type != '\n')
if (GTS_OBJECT_CLASS (g->edge_class)->read)
(*GTS_OBJECT_CLASS (g->edge_class)->read)
((GtsObject **) &new_edge, fp);
gts_file_first_token_after (fp, '\n');
n++;
}
}
}
}
}
if (fp->type == GTS_ERROR) {
gts_allow_floating_gnodes = TRUE;
while (nn)
gts_object_destroy (GTS_OBJECT (nodes[nn-- - 1]));
gts_allow_floating_gnodes = FALSE;
}
g_free (nodes);
if (fp->type == GTS_ERROR) {
gts_object_destroy (GTS_OBJECT (g));
return NULL;
}
return g;
}
static void write_dot_node (GtsGNode * node, gpointer * data)
{
FILE * fp = data[0];
guint * nnode = data[1];
fprintf (fp, " n%u", *nnode);
if (GTS_GNODE_CLASS (GTS_OBJECT (node)->klass)->write) {
fputs (" [", fp);
(* GTS_GNODE_CLASS (GTS_OBJECT (node)->klass)->write) (node, fp);
fputc (']', fp);
}
fputs (";\n", fp);
GTS_OBJECT (node)->reserved = GUINT_TO_POINTER ((*nnode)++);
}
static void write_dot_edge (GtsGEdge * edge, FILE * fp)
{
fprintf (fp, " n%u -> n%u",
GPOINTER_TO_UINT (GTS_OBJECT (edge->n1)->reserved),
GPOINTER_TO_UINT (GTS_OBJECT (edge->n2)->reserved));
if (GTS_GEDGE_CLASS (GTS_OBJECT (edge)->klass)->write) {
fputs (" [", fp);
(* GTS_GEDGE_CLASS (GTS_OBJECT (edge)->klass)->write) (edge, fp);
fputc (']', fp);
}
fputs (";\n", fp);
}
/**
* gts_graph_write_dot:
* @g: a #GtsGraph.
* @fp: a file pointer.
*
* Writes in the file @fp an ASCII representation of @g in the dot format of
* AT&T Bell Labs.
*/
void gts_graph_write_dot (GtsGraph * g, FILE * fp)
{
guint nnode = 1;
gpointer data[2];
g_return_if_fail (g != NULL);
g_return_if_fail (fp != NULL);
fprintf (fp, "digraph \"%p\" {\n", g);
data[0] = fp;
data[1] = &nnode;
gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) write_dot_node, data);
gts_graph_foreach_edge (g, (GtsFunc) write_dot_edge, fp);
fputs ("}\n", fp);
gts_container_foreach (GTS_CONTAINER (g),
(GtsFunc) gts_object_reset_reserved, NULL);
}
/* GtsWGraph */
static gfloat wgraph_weight (GtsGraph * g)
{
return GTS_WGRAPH (g)->weight;
}
static void wgraph_add (GtsContainer * g, GtsContainee * n)
{
GtsWGraph * wg = GTS_WGRAPH (g);
gfloat w = gts_gnode_weight (GTS_GNODE (n));
wg->weight += w;
(* GTS_CONTAINER_CLASS (GTS_OBJECT_CLASS (gts_wgraph_class ())->parent_class)->add) (g, n);
}
static void wgraph_remove (GtsContainer * g, GtsContainee * n)
{
GTS_WGRAPH (g)->weight -= gts_gnode_weight (GTS_GNODE (n));
(* GTS_CONTAINER_CLASS (GTS_OBJECT_CLASS (gts_wgraph_class ())->parent_class)->remove) (g, n);
}
static void wgraph_class_init (GtsWGraphClass * klass)
{
GTS_GRAPH_CLASS (klass)->weight = wgraph_weight;
GTS_CONTAINER_CLASS (klass)->add = wgraph_add;
GTS_CONTAINER_CLASS (klass)->remove = wgraph_remove;
}
static void wgraph_init (GtsWGraph * g)
{
g->weight = 0.;
}
/**
* gts_wgraph_class:
*
* Returns: the #GtsWGraphClass.
*/
GtsWGraphClass * gts_wgraph_class (void)
{
static GtsWGraphClass * klass = NULL;
if (klass == NULL) {
GtsObjectClassInfo wgraph_info = {
"GtsWGraph",
sizeof (GtsWGraph),
sizeof (GtsWGraphClass),
(GtsObjectClassInitFunc) wgraph_class_init,
(GtsObjectInitFunc) wgraph_init,
(GtsArgSetFunc) NULL,
(GtsArgGetFunc) NULL
};
klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_graph_class ()),
&wgraph_info);
}
return klass;
}
static void weight_max (GtsGNode * n, gfloat * wmax)
{
gfloat w = gts_gnode_weight (n);
if (w > *wmax)
*wmax = w;
}
/**
* gts_wgraph_weight_max:
* @wg: a #GtsWGraph.
*
* Returns: the maximum weight of any vertices belonging to @g.
*/
gfloat gts_wgraph_weight_max (GtsWGraph * wg)
{
gfloat wmax = - G_MAXFLOAT;
g_return_val_if_fail (wg != NULL, 0.);
gts_container_foreach (GTS_CONTAINER (wg), (GtsFunc) weight_max, &wmax);
return wmax;
}
/* Surface graph */
static void create_node (GtsFace * f, GtsGraph * graph)
{
GtsFNode * fn = gts_fnode_new (gts_fnode_class (), f);
gts_container_add (GTS_CONTAINER (graph), GTS_CONTAINEE (fn));
GTS_OBJECT (f)->reserved = fn;
}
static void create_edge (GtsEdge * e, GtsSurface * s)
{
GSList * i = e->triangles;
while (i) {
GtsFace * f = i->data;
if (GTS_IS_FACE (f) && gts_face_has_parent_surface (f, s)) {
GSList * j = i->next;
while (j) {
GtsFace * f1 = j->data;
if (GTS_IS_FACE (f1) && gts_face_has_parent_surface (f1, s))
gts_pgedge_new (gts_pgedge_class (),
GTS_OBJECT (f)->reserved,
GTS_OBJECT (f1)->reserved,
e);
j = j->next;
}
}
i = i->next;
}
}
/**
* gts_surface_graph_new:
* @klass: a #GtsGraphClass.
* @s: a #GtsSurface.
*
* Returns: a new #GtsGraph representing the connectivity of the faces
* of @s. This graph uses #GtsFGNode as nodes which allows to store
* the dependencies between nodes and faces of @s.
*/
GtsGraph * gts_surface_graph_new (GtsGraphClass * klass,
GtsSurface * s)
{
GtsGraph * graph;
g_return_val_if_fail (klass != NULL, NULL);
g_return_val_if_fail (s != NULL, NULL);
graph = GTS_GRAPH (gts_object_new (GTS_OBJECT_CLASS (klass)));
gts_surface_foreach_face (s, (GtsFunc) create_node, graph);
gts_surface_foreach_edge (s, (GtsFunc) create_edge, s);
gts_surface_foreach_face (s, (GtsFunc) gts_object_reset_reserved, NULL);
return graph;
}
static void create_segment_edge (GtsSegment * s, GtsGraph * graph)
{
GtsGNode * n1 = GTS_OBJECT (s->v1)->reserved, * n2;
if (n1 == NULL) {
n1 = GTS_GNODE (gts_pnode_new (gts_pnode_class (), s->v1));
gts_container_add (GTS_CONTAINER (graph), GTS_CONTAINEE (n1));
GTS_OBJECT (s->v1)->reserved = n1;
}
n2 = GTS_OBJECT (s->v2)->reserved;
if (n2 == NULL) {
n2 = GTS_GNODE (gts_pnode_new (gts_pnode_class (), s->v2));
gts_container_add (GTS_CONTAINER (graph), GTS_CONTAINEE (n2));
GTS_OBJECT (s->v2)->reserved = n2;
}
gts_pgedge_new (gts_pgedge_class (), n1, n2, s);
}
static void reset_reserved (GtsSegment * s)
{
GTS_OBJECT (s->v1)->reserved = GTS_OBJECT (s->v2)->reserved = NULL;
}
/**
* gts_segments_graph_new:
* @klass: a #GtsGraphClass.
* @segments: a list of #GtsSegment.
*
* Returns: a new #GtsGraph representing the connectivity of the segments
* in @segments.
*/
GtsGraph * gts_segments_graph_new (GtsGraphClass * klass,
GSList * segments)
{
GtsGraph * graph;
g_return_val_if_fail (klass != NULL, NULL);
graph = GTS_GRAPH (gts_object_new (GTS_OBJECT_CLASS (klass)));
g_slist_foreach (segments, (GFunc) create_segment_edge, graph);
g_slist_foreach (segments, (GFunc) reset_reserved, NULL);
return graph;
}
static void add_to_surface (GtsGNode * n, GtsSurface * s)
{
if (GTS_IS_FNODE (n))
gts_surface_add_face (s, GTS_FNODE (n)->f);
}
/**
* gts_surface_graph_surface:
* @surface_graph: a #GtsGraph using #GtsFGNode as nodes.
* @s: a #GtsSurface.
*
* Returns: a new #GtsSurface using the same classes as @s and
* composed of the faces defined by @surface_graph.
*/
GtsSurface * gts_surface_graph_surface (GtsGraph * surface_graph,
GtsSurface * s)
{
GtsSurface * s1;
g_return_val_if_fail (surface_graph != NULL, NULL);
g_return_val_if_fail (s != NULL, NULL);
s1 = gts_surface_new (GTS_SURFACE_CLASS (GTS_OBJECT (s)->klass),
s->face_class,
s->edge_class,
s->vertex_class);
gts_container_foreach (GTS_CONTAINER (surface_graph),
(GtsFunc) add_to_surface, s1);
return s1;
}
syntax highlighted by Code2HTML, v. 0.9.1