pcb 4.1.1
An interactive printed circuit board layout editor.

graph.c File Reference

#include <math.h>
#include <stdlib.h>
#include "gts.h"
Include dependency graph for graph.c:

Go to the source code of this file.

Data Structures

struct  _GtsGraphTraverse

Functions

static void gnode_remove_container (GtsContainee *i, GtsContainer *c)
static void gnode_class_init (GtsGNodeClass *klass)
static void gnode_init (GtsGNode *n)
GtsGNodeClassgts_gnode_class (void)
GtsGNodegts_gnode_new (GtsGNodeClass *klass)
void gts_gnode_foreach_neighbor (GtsGNode *n, GtsGraph *g, GtsFunc func, gpointer data)
void gts_gnode_foreach_edge (GtsGNode *n, GtsGraph *g, GtsFunc func, gpointer data)
guint gts_gnode_degree (GtsGNode *n, GtsGraph *g)
gfloat gts_gnode_move_cost (GtsGNode *n, GtsGraph *src, GtsGraph *dst)
gfloat gts_gnode_weight (GtsGNode *n)
static void ngnode_init (GtsNGNode *n)
GtsNGNodeClassgts_ngnode_class (void)
GtsNGNodegts_ngnode_new (GtsNGNodeClass *klass, guint id)
static gfloat wgnode_weight (GtsGNode *n)
static void wgnode_class_init (GtsWGNodeClass *klass)
static void wgnode_init (GtsWGNode *n)
GtsWGNodeClassgts_wgnode_class (void)
GtsWGNodegts_wgnode_new (GtsWGNodeClass *klass, gfloat weight)
static void pnode_write (GtsGNode *n, FILE *fp)
static void pnode_class_init (GtsPNodeClass *klass)
static void pnode_init (GtsPNode *pn)
GtsPNodeClassgts_pnode_class (void)
GtsPNodegts_pnode_new (GtsPNodeClass *klass, gpointer data)
static void fnode_write (GtsGNode *n, FILE *fp)
static void fnode_class_init (GtsGNodeClass *klass)
static void fnode_init (GtsFNode *fn)
GtsFNodeClassgts_fnode_class (void)
GtsFNodegts_fnode_new (GtsFNodeClass *klass, GtsFace *f)
static void gedge_destroy (GtsObject *object)
static void gedge_remove_container (GtsContainee *i, GtsContainer *c)
static gboolean gedge_is_contained (GtsContainee *i, GtsContainer *c)
static void gedge_class_init (GtsGEdgeClass *klass)
static void gedge_init (GtsGEdge *object)
GtsGEdgeClassgts_gedge_class (void)
GtsGEdgegts_gedge_new (GtsGEdgeClass *klass, GtsGNode *n1, GtsGNode *n2)
gfloat gts_gedge_weight (GtsGEdge *e)
static void pgedge_write (GtsGEdge *ge, FILE *fp)
static void pgedge_class_init (GtsPGEdgeClass *klass)
static void pgedge_init (GtsPGEdge *e)
GtsPGEdgeClassgts_pgedge_class (void)
GtsPGEdgegts_pgedge_new (GtsPGEdgeClass *klass, GtsGNode *g1, GtsGNode *g2, gpointer data)
static gfloat wgedge_weight (GtsGEdge *e)
static void wgedge_class_init (GtsWGEdgeClass *klass)
static void wgedge_init (GtsWGEdge *e)
GtsWGEdgeClassgts_wgedge_class (void)
GtsWGEdgegts_wgedge_new (GtsWGEdgeClass *klass, GtsGNode *g1, GtsGNode *g2, gfloat weight)
static void graph_init (GtsGraph *g)
static void graph_write (GtsObject *object, FILE *fp)
static void graph_read (GtsObject **object, GtsFile *f)
static void graph_class_init (GtsGraphClass *klass)
GtsGraphClassgts_graph_class (void)
GtsGraphgts_graph_new (GtsGraphClass *klass, GtsGNodeClass *node_class, GtsGEdgeClass *edge_class)
static void compute_degree (GtsGNode *n, gpointer *data)
void gts_graph_print_stats (GtsGraph *g, FILE *fp)
static void reset_level (GtsGNode *n)
GtsGraphTraversegts_graph_traverse_new (GtsGraph *g, GtsGNode *n, GtsTraverseType type, gboolean reinit)
static void push_neighbor (GtsGNode *n, gpointer *data)
GtsGNodegts_graph_traverse_next (GtsGraphTraverse *t)
GtsGNodegts_graph_traverse_what_next (GtsGraphTraverse *t)
void gts_graph_traverse_destroy (GtsGraphTraverse *t)
static void edge_foreach_node (GtsGNode *n, gpointer *info)
void gts_graph_foreach_edge (GtsGraph *g, GtsFunc func, gpointer data)
gfloat gts_graph_weight (GtsGraph *g)
guint gts_graph_distance_sum (GtsGraph *g, GtsGNode *center)
GtsGNodegts_graph_farthest (GtsGraph *g, GSList *gnodes)
static void neighbor_count (GtsGNode *n, gpointer *data)
static void count_edge_cuts (GtsGNode *n, gpointer *data)
guint gts_graph_edges_cut (GtsGraph *g)
static void sum_edge_cuts_weight (GtsGNode *n, gpointer *data)
gfloat gts_graph_edges_cut_weight (GtsGraph *g)
guint gts_graph_read_jostle (GtsGraph *g, GtsFile *fp)
static void count_edges (GtsGEdge *e, guint *nedge)
static void write_node (GtsObject *node, gpointer *data)
static void write_edge (GtsGEdge *edge, FILE *fp)
void gts_graph_write (GtsGraph *g, FILE *fp)
GtsGraphgts_graph_read (GtsFile *fp)
static void write_dot_node (GtsGNode *node, gpointer *data)
static void write_dot_edge (GtsGEdge *edge, FILE *fp)
void gts_graph_write_dot (GtsGraph *g, FILE *fp)
static gfloat wgraph_weight (GtsGraph *g)
static void wgraph_add (GtsContainer *g, GtsContainee *n)
static void wgraph_remove (GtsContainer *g, GtsContainee *n)
static void wgraph_class_init (GtsWGraphClass *klass)
static void wgraph_init (GtsWGraph *g)
GtsWGraphClassgts_wgraph_class (void)
static void weight_max (GtsGNode *n, gfloat *wmax)
gfloat gts_wgraph_weight_max (GtsWGraph *wg)
static void create_node (GtsFace *f, GtsGraph *graph)
static void create_edge (GtsEdge *e, GtsSurface *s)
GtsGraphgts_surface_graph_new (GtsGraphClass *klass, GtsSurface *s)
static void create_segment_edge (GtsSegment *s, GtsGraph *graph)
static void reset_reserved (GtsSegment *s)
GtsGraphgts_segments_graph_new (GtsGraphClass *klass, GSList *segments)
static void add_to_surface (GtsGNode *n, GtsSurface *s)
GtsSurfacegts_surface_graph_surface (GtsGraph *surface_graph, GtsSurface *s)

Variables

gboolean gts_allow_floating_gnodes = FALSE

Function Documentation

static void add_to_surface ( GtsGNode n,
GtsSurface s 
) [static]

Definition at line 1746 of file graph.c.

References f, GTS_FNODE, GTS_IS_FNODE, and gts_surface_add_face().

Referenced by gts_surface_graph_surface().

Here is the call graph for this function:

static void compute_degree ( GtsGNode n,
gpointer *  data 
) [static]

Definition at line 862 of file graph.c.

References gts_gnode_degree(), and gts_range_add_value().

Referenced by gts_graph_print_stats().

Here is the call graph for this function:

static void count_edge_cuts ( GtsGNode n,
gpointer *  data 
) [static]

Definition at line 1152 of file graph.c.

References gts_gnode_foreach_neighbor(), and neighbor_count().

Referenced by gts_graph_edges_cut().

Here is the call graph for this function:

static void count_edges ( GtsGEdge e,
guint *  nedge 
) [static]

Definition at line 1293 of file graph.c.

Referenced by gts_graph_write().

static void create_edge ( GtsEdge e,
GtsSurface s 
) [static]

Definition at line 1652 of file graph.c.

References f, gts_face_has_parent_surface(), GTS_IS_FACE, GTS_OBJECT, gts_pgedge_class(), gts_pgedge_new(), and _GtsEdge::triangles.

Referenced by gts_surface_graph_new().

Here is the call graph for this function:

static void create_node ( GtsFace f,
GtsGraph graph 
) [static]

Definition at line 1644 of file graph.c.

References GTS_CONTAINEE, GTS_CONTAINER, gts_container_add(), gts_fnode_class(), gts_fnode_new(), and GTS_OBJECT.

Referenced by gts_surface_graph_new().

Here is the call graph for this function:

static void create_segment_edge ( GtsSegment s,
GtsGraph graph 
) [static]
static void edge_foreach_node ( GtsGNode n,
gpointer *  info 
) [static]

Definition at line 1010 of file graph.c.

References GTS_SLIST_CONTAINER, and hash().

Referenced by gts_graph_foreach_edge().

Here is the call graph for this function:

static void fnode_class_init ( GtsGNodeClass klass) [static]

Definition at line 417 of file graph.c.

References fnode_write(), and _GtsGNodeClass::write.

Referenced by gts_fnode_class().

Here is the call graph for this function:

static void fnode_init ( GtsFNode fn) [static]

Definition at line 422 of file graph.c.

References _GtsFNode::f.

Referenced by gts_fnode_class().

static void fnode_write ( GtsGNode n,
FILE *  fp 
) [static]

Definition at line 412 of file graph.c.

References f, and GTS_FNODE.

Referenced by fnode_class_init().

static void gedge_class_init ( GtsGEdgeClass klass) [static]

Definition at line 516 of file graph.c.

References gedge_destroy(), gedge_is_contained(), gedge_remove_container(), GTS_CONTAINEE_CLASS, GTS_OBJECT_CLASS, _GtsGEdgeClass::link, and _GtsGEdgeClass::weight.

Referenced by gts_gedge_class().

Here is the call graph for this function:

static void gedge_destroy ( GtsObject object) [static]

Definition at line 474 of file graph.c.

References GTS_CONTAINEE, GTS_CONTAINER, gts_container_remove(), GTS_GEDGE, gts_gedge_class(), GTS_OBJECT_CLASS, _GtsGEdge::n1, and _GtsGEdge::n2.

Referenced by gedge_class_init().

Here is the call graph for this function:

static void gedge_init ( GtsGEdge object) [static]

Definition at line 527 of file graph.c.

Referenced by gts_gedge_class().

static gboolean gedge_is_contained ( GtsContainee i,
GtsContainer c 
) [static]

Definition at line 507 of file graph.c.

References FALSE, GTS_CONTAINER, GTS_GEDGE, _GtsGEdge::n1, _GtsGEdge::n2, and TRUE.

Referenced by gedge_class_init().

static void gedge_remove_container ( GtsContainee i,
GtsContainer c 
) [static]

Definition at line 486 of file graph.c.

References GTS_CONTAINER, gts_container_remove(), GTS_GEDGE, gts_gedge_class(), GTS_OBJECT, GTS_OBJECT_CLASS, _GtsGEdge::n1, and _GtsGEdge::n2.

Referenced by gedge_class_init().

Here is the call graph for this function:

static void gnode_class_init ( GtsGNodeClass klass) [static]

Definition at line 37 of file graph.c.

References gnode_remove_container(), GTS_CONTAINEE_CLASS, and _GtsGNodeClass::weight.

Referenced by gts_gnode_class().

Here is the call graph for this function:

static void gnode_init ( GtsGNode n) [static]

Definition at line 44 of file graph.c.

References _GtsGNode::level.

Referenced by gts_gnode_class().

static void gnode_remove_container ( GtsContainee i,
GtsContainer c 
) [static]

Definition at line 28 of file graph.c.

References gts_allow_floating_gnodes, GTS_CONTAINEE_CLASS, gts_gnode_class(), GTS_OBJECT, GTS_OBJECT_CLASS, gts_object_destroy(), GTS_OBJECT_DESTROYED, and GTS_SLIST_CONTAINEE.

Referenced by gnode_class_init().

Here is the call graph for this function:

static void graph_class_init ( GtsGraphClass klass) [static]

Definition at line 803 of file graph.c.

References graph_read(), graph_write(), GTS_OBJECT_CLASS, and _GtsGraphClass::weight.

Referenced by gts_graph_class().

Here is the call graph for this function:

static void graph_init ( GtsGraph g) [static]

Definition at line 749 of file graph.c.

References _GtsGraph::edge_class, _GtsGraph::graph_class, gts_gedge_class(), gts_gnode_class(), gts_graph_class(), and _GtsGraph::node_class.

Referenced by gts_graph_class().

Here is the call graph for this function:

static void graph_read ( GtsObject **  object,
GtsFile f 
) [static]
static void graph_write ( GtsObject object,
FILE *  fp 
) [static]
GtsFNodeClass* gts_fnode_class ( void  )

gts_fnode_class:

Returns: the GtsFNodeClass.

Definition at line 432 of file graph.c.

References fnode_class_init(), fnode_init(), gts_gnode_class(), GTS_OBJECT_CLASS, and gts_object_class_new().

Referenced by create_node().

Here is the call graph for this function:

GtsFNode* gts_fnode_new ( GtsFNodeClass klass,
GtsFace f 
)

gts_fnode_new: : a GtsFNodeClass. : a GtsFace.

Returns: a new GtsFNode associated with face .

Definition at line 460 of file graph.c.

References f, _GtsFNode::f, GTS_FNODE, GTS_OBJECT_CLASS, and gts_object_new().

Referenced by create_node().

Here is the call graph for this function:

GtsGEdgeClass* gts_gedge_class ( void  )

gts_gedge_class:

Returns: the GtsGEdgeClass.

Definition at line 537 of file graph.c.

References gedge_class_init(), gedge_init(), gts_containee_class(), GTS_OBJECT_CLASS, and gts_object_class_new().

Referenced by gedge_destroy(), gedge_remove_container(), graph_init(), graph_read(), gts_graph_read(), gts_pgedge_class(), and gts_wgedge_class().

Here is the call graph for this function:

GtsGEdge* gts_gedge_new ( GtsGEdgeClass klass,
GtsGNode n1,
GtsGNode n2 
)

gts_gedge_new: : a GtsGEdgeClass. : a GtsGNode. : another GtsGNode.

Returns: a new GtsGEdge linking and .

Definition at line 566 of file graph.c.

References GTS_CONTAINEE, GTS_CONTAINER, gts_container_add(), GTS_GEDGE, GTS_OBJECT_CLASS, gts_object_new(), and _GtsGEdgeClass::link.

Referenced by gts_graph_read(), gts_graph_read_jostle(), gts_pgedge_new(), and gts_wgedge_new().

Here is the call graph for this function:

gfloat gts_gedge_weight ( GtsGEdge e)

gts_gedge_weight: : a GtsGEdge.

Returns: the weight of edge as defined by the weight() method of GtsGEdgeClass.

Definition at line 593 of file graph.c.

References GTS_GEDGE_CLASS, and GTS_OBJECT.

Referenced by gts_gnode_move_cost(), gts_gnode_split_collapse(), match_neighbor(), node_cost(), and sum_edge_cuts_weight().

GtsGNodeClass* gts_gnode_class ( void  )
guint gts_gnode_degree ( GtsGNode n,
GtsGraph g 
)

gts_gnode_degree:
: a GtsGNode. : a GtsGraph or NULL.

Returns: the number of neighbors of
(belonging to if is not NULL).

Definition at line 158 of file graph.c.

References GTS_CONTAINEE, gts_containee_is_contained(), GTS_CONTAINER, GTS_GNODE_NEIGHBOR, and GTS_SLIST_CONTAINER.

Referenced by bisection_children(), check_bg(), compute_degree(), degree_cost(), find_smallest_degree(), gts_graph_bisection_bkl_refine(), and update_neighbors().

Here is the call graph for this function:

void gts_gnode_foreach_edge ( GtsGNode n,
GtsGraph g,
GtsFunc  func,
gpointer  data 
)

gts_gnode_foreach_edge:
: a GtsGNode. : a GtsGraph or NULL. : a GtsFunc. : user data to be passed to .

Calls for each GtsGEdge connecting
to another GtsGNode (belonging to if is not NULL.

Definition at line 131 of file graph.c.

References GTS_CONTAINEE, gts_containee_is_contained(), GTS_CONTAINER, GTS_GNODE_NEIGHBOR, and GTS_SLIST_CONTAINER.

Here is the call graph for this function:

void gts_gnode_foreach_neighbor ( GtsGNode n,
GtsGraph g,
GtsFunc  func,
gpointer  data 
)

gts_gnode_foreach_neighbor:
: a GtsGNode. : a GtsGraph or NULL. : a GtsFunc. : user data to be passed to .

Calls for each neighbor GtsGNode of
(belonging to if is not NULL.

Definition at line 101 of file graph.c.

References GTS_CONTAINEE, gts_containee_is_contained(), GTS_CONTAINER, GTS_GNODE_NEIGHBOR, and GTS_SLIST_CONTAINER.

Referenced by count_edge_cuts(), graph_new_seed(), gts_graph_ggg_bisection(), and gts_graph_traverse_next().

Here is the call graph for this function:

gfloat gts_gnode_move_cost ( GtsGNode n,
GtsGraph src,
GtsGraph dst 
)

gts_gnode_move_cost:
: a GtsGNode. : a GtsGraph containing
. : another GtsGraph.

Returns: the cost (increase in the sum of the weights of the edges cut) of moving
from to .

Definition at line 187 of file graph.c.

References GTS_CONTAINEE, gts_containee_is_contained(), GTS_CONTAINER, gts_gedge_weight(), GTS_GNODE_NEIGHBOR, GTS_SLIST_CONTAINER, and neighbor().

Referenced by node_move_cost1(), and node_move_cost2().

Here is the call graph for this function:

GtsGNode* gts_gnode_new ( GtsGNodeClass klass)

gts_gnode_new: : a GtsGNodeClass.

Returns: a new GtsGNode.

Definition at line 82 of file graph.c.

References GTS_GNODE, GTS_OBJECT_CLASS, and gts_object_new().

Referenced by gts_ngnode_new(), and gts_wgnode_new().

Here is the call graph for this function:

gfloat gts_gnode_weight ( GtsGNode n)

gts_gnode_weight:
: a GtsGNode.

Returns: the weight of
as defined by the weight() method of the GtsGNodeClass.

Definition at line 225 of file graph.c.

References GTS_GNODE_CLASS, GTS_OBJECT, and n.

Referenced by gts_graph_bfgg_bisection(), gts_graph_ggg_bisection(), gts_pgraph_new(), weight_max(), wgraph_add(), and wgraph_remove().

GtsGraphClass* gts_graph_class ( void  )

gts_graph_class:

Returns: the GtsGraphClass.

Definition at line 816 of file graph.c.

References graph_class_init(), graph_init(), gts_hash_container_class(), GTS_OBJECT_CLASS, and gts_object_class_new().

Referenced by graph_init(), gts_graph_read(), and gts_wgraph_class().

Here is the call graph for this function:

guint gts_graph_distance_sum ( GtsGraph g,
GtsGNode center 
)

gts_graph_distance_sum: : a GtsGraph. : a GtsGNode of .

Returns: the sum of the distances between all the other GtsGNode of and .

Definition at line 1074 of file graph.c.

References GTS_BREADTH_FIRST, gts_graph_traverse_destroy(), gts_graph_traverse_new(), gts_graph_traverse_next(), _GtsGNode::level, n, and TRUE.

Referenced by better_seed(), and graph_new_seed().

Here is the call graph for this function:

guint gts_graph_edges_cut ( GtsGraph g)

gts_graph_edges_cut: : a GtsGraph.

Returns: the number of edges of connecting nodes belonging to to nodes not belonging to .

Definition at line 1164 of file graph.c.

References count_edge_cuts(), GTS_CONTAINER, and gts_container_foreach().

Referenced by gts_graph_bisection_new(), gts_graph_partition_edges_cut(), and gts_graph_print_stats().

Here is the call graph for this function:

gfloat gts_graph_edges_cut_weight ( GtsGraph g)

gts_graph_edges_cut_weight: : a GtsGraph.

Returns: the sum of the weights of the edges of connecting nodes belonging to to nodes not belonging to .

Definition at line 1199 of file graph.c.

References GTS_CONTAINER, gts_container_foreach(), and sum_edge_cuts_weight().

Referenced by gts_graph_bfgg_bisection(), gts_graph_bisection_new(), gts_graph_ggg_bisection(), gts_graph_partition_edges_cut_weight(), and gts_graph_print_stats().

Here is the call graph for this function:

GtsGNode* gts_graph_farthest ( GtsGraph g,
GSList *  gnodes 
)

gts_graph_farthest: : a GtsGraph. : a list of GtsGNode belonging to .

Returns: the GtsGNode belonging to and farthest from all the nodes in (hmmm, definition of "farthest"?).

Definition at line 1099 of file graph.c.

References FALSE, GTS_BREADTH_FIRST, gts_graph_traverse_destroy(), gts_graph_traverse_new(), gts_graph_traverse_next(), gts_graph_traverse_what_next(), GTS_OBJECT, _GtsGNode::level, n, and TRUE.

Referenced by gts_graph_bubble_partition().

Here is the call graph for this function:

void gts_graph_foreach_edge ( GtsGraph g,
GtsFunc  func,
gpointer  data 
)

gts_graph_foreach_edge: : a GtsGraph. : a GtsFunc. : user data to be passed to .

Calls for each GtsEdge of .

Definition at line 1035 of file graph.c.

References edge_foreach_node(), GTS_CONTAINER, gts_container_foreach(), and hash().

Referenced by gts_graph_write(), and gts_graph_write_dot().

Here is the call graph for this function:

GtsGraph* gts_graph_new ( GtsGraphClass klass,
GtsGNodeClass node_class,
GtsGEdgeClass edge_class 
)

gts_graph_new: : a GtsGraphClass. : a GtsGNodeClass. : a GtsGEdgeClass.

Returns: a new GtsGraph using and as node types.

Definition at line 845 of file graph.c.

References _GtsGraph::edge_class, GTS_GRAPH, GTS_OBJECT_CLASS, gts_object_new(), and _GtsGraph::node_class.

Referenced by gts_graph_bfgg_bisection(), and gts_graph_ggg_bisection().

Here is the call graph for this function:

void gts_graph_print_stats ( GtsGraph g,
FILE *  fp 
)

gts_graph_print_stats: : a GtsGraph. : a file pointer.

Writes to a summary of the properties of .

Definition at line 877 of file graph.c.

References compute_degree(), GTS_CONTAINER, gts_container_foreach(), gts_container_size(), gts_graph_edges_cut(), gts_graph_edges_cut_weight(), gts_graph_weight(), gts_range_init(), gts_range_print(), and gts_range_update().

Here is the call graph for this function:

guint gts_graph_read_jostle ( GtsGraph g,
GtsFile fp 
)

gts_graph_read_jostle: : a GtsGraph. : a GtsFile.

Adds to the nodes and edges defined in the file pointed to by . 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 .

Returns: 0 if the lecture was successful, the line number at which an error occured otherwise (in which case the field of is set).

Definition at line 1228 of file graph.c.

References _GtsGraph::edge_class, GTS_CONTAINEE, GTS_CONTAINER, gts_container_add(), GTS_ERROR, gts_file_error(), gts_file_first_token_after(), gts_file_next_token(), gts_gedge_new(), GTS_GNODE, GTS_INT, gts_ngnode_class(), gts_ngnode_new(), _GtsFile::line, n, node, _GtsFile::token, and _GtsFile::type.

Here is the call graph for this function:

void gts_graph_traverse_destroy ( GtsGraphTraverse t)

gts_graph_traverse_destroy: : a GtsGraphTraverse.

Frees all the memory allocated for .

Definition at line 1002 of file graph.c.

References gts_fifo_destroy(), and _GtsGraphTraverse::q.

Referenced by gts_graph_bfgg_bisection(), gts_graph_distance_sum(), gts_graph_farthest(), and partition_update().

Here is the call graph for this function:

GtsGraphTraverse* gts_graph_traverse_new ( GtsGraph g,
GtsGNode n,
GtsTraverseType  type,
gboolean  reinit 
)

gts_graph_traverse_new: : a GtsGraph.
: a GtsGNode belonging to . : the type of traversal. : if TRUE, the traversal is reinitialized.

Returns: a new GtsGraphTraverse initialized for the traversal of of type , starting from
.

Definition at line 921 of file graph.c.

References _GtsGraphTraverse::g, GTS_CONTAINEE, gts_containee_is_contained(), GTS_CONTAINER, gts_container_foreach(), gts_fifo_new(), gts_fifo_push(), _GtsGNode::level, _GtsGraphTraverse::q, and reset_level().

Referenced by gts_graph_bfgg_bisection(), gts_graph_distance_sum(), gts_graph_farthest(), and partition_update().

Here is the call graph for this function:

GtsGNode* gts_graph_traverse_next ( GtsGraphTraverse t)

gts_graph_traverse_next: : a GtsGraphTraverse.

Returns: the next GtsGNode of the traversal defined by or NULL if the traversal is complete.

Definition at line 964 of file graph.c.

References _GtsGraphTraverse::g, gts_fifo_pop(), gts_gnode_foreach_neighbor(), push_neighbor(), _GtsGraphTraverse::q, and u().

Referenced by gts_graph_bfgg_bisection(), gts_graph_distance_sum(), gts_graph_farthest(), and partition_update().

Here is the call graph for this function:

GtsGNode* gts_graph_traverse_what_next ( GtsGraphTraverse t)

gts_graph_traverse_what_next: : a GtsGraphTraverse.

Returns: the next GtsGNode of the traversal defined by or NULL if the traversal is complete but without advancing the traversal.

Definition at line 989 of file graph.c.

References gts_fifo_top(), and _GtsGraphTraverse::q.

Referenced by gts_graph_farthest().

Here is the call graph for this function:

gfloat gts_graph_weight ( GtsGraph g)

gts_graph_weight: : a GtsGraph.

Returns: the weight of graph as defined by the weight() method of GtsGraphClass.

Definition at line 1057 of file graph.c.

References GTS_CONTAINER, gts_container_size(), GTS_GRAPH_CLASS, and GTS_OBJECT.

Referenced by graph_comp_weight(), gts_graph_bfgg_bisection(), gts_graph_bisection_bkl_refine(), gts_graph_bisection_kl_refine(), gts_graph_bisection_new(), gts_graph_ggg_bisection(), gts_graph_partition_balance(), gts_graph_partition_print_stats(), and gts_graph_print_stats().

Here is the call graph for this function:

void gts_graph_write ( GtsGraph g,
FILE *  fp 
)

gts_graph_write: : a GtsGraph. : a file pointer.

Writes in the file an ASCII representation of . 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.

Definition at line 1344 of file graph.c.

References count_edges(), fp, GTS_CONTAINER, gts_container_foreach(), gts_container_size(), gts_graph_foreach_edge(), GTS_OBJECT, gts_object_reset_reserved(), write_edge(), and write_node().

Here is the call graph for this function:

void gts_graph_write_dot ( GtsGraph g,
FILE *  fp 
)

gts_graph_write_dot: : a GtsGraph. : a file pointer.

Writes in the file an ASCII representation of in the dot format of AT&T Bell Labs.

Definition at line 1535 of file graph.c.

References fp, GTS_CONTAINER, gts_container_foreach(), gts_graph_foreach_edge(), gts_object_reset_reserved(), write_dot_edge(), and write_dot_node().

Here is the call graph for this function:

GtsNGNodeClass* gts_ngnode_class ( void  )

gts_ngnode_class:

Returns: the GtsNGNodeClass.

Definition at line 246 of file graph.c.

References gts_gnode_class(), GTS_OBJECT_CLASS, gts_object_class_new(), and ngnode_init().

Referenced by gts_graph_read_jostle().

Here is the call graph for this function:

GtsNGNode* gts_ngnode_new ( GtsNGNodeClass klass,
guint  id 
)

gts_ngnode_new: : a GtsNGNodeClass.

Returns: a new GtsNGNode with identity .

Definition at line 273 of file graph.c.

References GTS_GNODE_CLASS, gts_gnode_new(), GTS_NGNODE, _GtsNGNode::id, and n.

Referenced by gts_graph_read_jostle().

Here is the call graph for this function:

GtsPGEdgeClass* gts_pgedge_class ( void  )

gts_pgedge_class:

Returns: the GtsPGEdgeClass.

Definition at line 639 of file graph.c.

References gts_gedge_class(), GTS_OBJECT_CLASS, gts_object_class_new(), pgedge_class_init(), and pgedge_init().

Referenced by create_edge(), and create_segment_edge().

Here is the call graph for this function:

GtsPGEdge* gts_pgedge_new ( GtsPGEdgeClass klass,
GtsGNode g1,
GtsGNode g2,
gpointer  data 
)

gts_pgedge_new: : a GtsPGEdgeClass. : a GtsGNode. : another GtsGNode. : user data.

Returns: a new GtsPGEdge associated with linking and .

Definition at line 669 of file graph.c.

References _GtsPGEdge::data, GTS_GEDGE_CLASS, gts_gedge_new(), and GTS_PGEDGE.

Referenced by create_edge(), and create_segment_edge().

Here is the call graph for this function:

GtsPNodeClass* gts_pnode_class ( void  )

gts_pnode_class:

Returns: the GtsPNodeClass.

Definition at line 372 of file graph.c.

References gts_gnode_class(), GTS_OBJECT_CLASS, gts_object_class_new(), pnode_class_init(), and pnode_init().

Referenced by create_segment_edge().

Here is the call graph for this function:

GtsPNode* gts_pnode_new ( GtsPNodeClass klass,
gpointer  data 
)

gts_pnode_new: : a GtsPNodeClass. : user data.

Returns: a new GtsPNode associated with .

Definition at line 400 of file graph.c.

References _GtsPNode::data, GTS_OBJECT_CLASS, gts_object_new(), and GTS_PNODE.

Referenced by create_segment_edge().

Here is the call graph for this function:

GtsGraph* gts_segments_graph_new ( GtsGraphClass klass,
GSList *  segments 
)

gts_segments_graph_new: : a GtsGraphClass. : a list of GtsSegment.

Returns: a new GtsGraph representing the connectivity of the segments in .

Definition at line 1732 of file graph.c.

References create_segment_edge(), GTS_GRAPH, GTS_OBJECT_CLASS, gts_object_new(), and reset_reserved().

Here is the call graph for this function:

GtsGraph* gts_surface_graph_new ( GtsGraphClass klass,
GtsSurface s 
)

gts_surface_graph_new: : a GtsGraphClass. : a GtsSurface.

Returns: a new GtsGraph representing the connectivity of the faces of . This graph uses #GtsFGNode as nodes which allows to store the dependencies between nodes and faces of .

Definition at line 1683 of file graph.c.

References create_edge(), create_node(), GTS_GRAPH, GTS_OBJECT_CLASS, gts_object_new(), gts_object_reset_reserved(), gts_surface_foreach_edge(), and gts_surface_foreach_face().

Here is the call graph for this function:

GtsSurface* gts_surface_graph_surface ( GtsGraph surface_graph,
GtsSurface s 
)

gts_surface_graph_surface: : a GtsGraph using #GtsFGNode as nodes. : a GtsSurface.

Returns: a new GtsSurface using the same classes as and composed of the faces defined by .

Definition at line 1760 of file graph.c.

References add_to_surface(), _GtsSurface::edge_class, _GtsSurface::face_class, GTS_CONTAINER, gts_container_foreach(), GTS_OBJECT, GTS_SURFACE_CLASS, gts_surface_new(), and _GtsSurface::vertex_class.

Here is the call graph for this function:

GtsWGEdgeClass* gts_wgedge_class ( void  )

gts_wgedge_class:

Returns: the GtsWGEdgeClass.

Definition at line 704 of file graph.c.

References gts_gedge_class(), GTS_OBJECT_CLASS, gts_object_class_new(), wgedge_class_init(), and wgedge_init().

Referenced by gts_graph_bisection_new(), and pgraph_init().

Here is the call graph for this function:

GtsWGEdge* gts_wgedge_new ( GtsWGEdgeClass klass,
GtsGNode g1,
GtsGNode g2,
gfloat  weight 
)

gts_wgedge_new: : a GtsWGEdgeClass. : a GtsGNode. : another GtsGNode. : the weight of the new edge.

Returns: a new GtsWGEdge of weight linking and .

Definition at line 734 of file graph.c.

References GTS_GEDGE_CLASS, gts_gedge_new(), GTS_WGEDGE, and _GtsWGEdge::weight.

Referenced by gts_gnode_split_collapse().

Here is the call graph for this function:

GtsWGNodeClass* gts_wgnode_class ( void  )

gts_wgnode_class:

Returns: the GtsWGNodeClass.

Definition at line 306 of file graph.c.

References gts_gnode_class(), GTS_OBJECT_CLASS, gts_object_class_new(), wgnode_class_init(), and wgnode_init().

Referenced by gts_graph_bisection_new().

Here is the call graph for this function:

GtsWGNode* gts_wgnode_new ( GtsWGNodeClass klass,
gfloat  weight 
)

gts_wgnode_new: : a GtsWGNodeClass. : the weight of the GtsWGNode to create.

Returns: a new GtsWGNode of weight .

Definition at line 334 of file graph.c.

References GTS_GNODE_CLASS, gts_gnode_new(), GTS_WGNODE, n, and _GtsWGNode::weight.

Referenced by gts_pgraph_new().

Here is the call graph for this function:

GtsWGraphClass* gts_wgraph_class ( void  )

gts_wgraph_class:

Returns: the GtsWGraphClass.

Definition at line 1596 of file graph.c.

References gts_graph_class(), GTS_OBJECT_CLASS, gts_object_class_new(), wgraph_class_init(), and wgraph_init().

Referenced by wgraph_add(), and wgraph_remove().

Here is the call graph for this function:

gfloat gts_wgraph_weight_max ( GtsWGraph wg)

gts_wgraph_weight_max: : a GtsWGraph.

Returns: the maximum weight of any vertices belonging to .

Definition at line 1631 of file graph.c.

References GTS_CONTAINER, gts_container_foreach(), and weight_max().

Here is the call graph for this function:

static void neighbor_count ( GtsGNode n,
gpointer *  data 
) [static]

Definition at line 1143 of file graph.c.

References GTS_CONTAINEE, gts_containee_is_contained(), and GTS_CONTAINER.

Referenced by count_edge_cuts().

Here is the call graph for this function:

static void ngnode_init ( GtsNGNode n) [static]

Definition at line 236 of file graph.c.

References _GtsNGNode::id.

Referenced by gts_ngnode_class().

static void pgedge_class_init ( GtsPGEdgeClass klass) [static]

Definition at line 624 of file graph.c.

References GTS_GEDGE_CLASS, and pgedge_write().

Referenced by gts_pgedge_class().

Here is the call graph for this function:

static void pgedge_init ( GtsPGEdge e) [static]

Definition at line 629 of file graph.c.

References _GtsPGEdge::data.

Referenced by gts_pgedge_class().

static void pgedge_write ( GtsGEdge ge,
FILE *  fp 
) [static]

Definition at line 604 of file graph.c.

References GTS_IS_EDGE, GTS_IS_NEDGE, GTS_NEDGE, GTS_PGEDGE, n, and _GtsEdge::triangles.

Referenced by pgedge_class_init().

static void pnode_class_init ( GtsPNodeClass klass) [static]

Definition at line 357 of file graph.c.

References GTS_GNODE_CLASS, and pnode_write().

Referenced by gts_pnode_class().

Here is the call graph for this function:

static void pnode_init ( GtsPNode pn) [static]

Definition at line 362 of file graph.c.

References _GtsPNode::data.

Referenced by gts_pnode_class().

static void pnode_write ( GtsGNode n,
FILE *  fp 
) [static]

Definition at line 347 of file graph.c.

References GTS_IS_NVERTEX, GTS_NVERTEX, and GTS_PNODE.

Referenced by pnode_class_init().

static void push_neighbor ( GtsGNode n,
gpointer *  data 
) [static]

Definition at line 946 of file graph.c.

References gts_fifo_push(), _GtsGNode::level, and u().

Referenced by gts_graph_traverse_next().

Here is the call graph for this function:

static void reset_level ( GtsGNode n) [static]

Definition at line 906 of file graph.c.

References _GtsGNode::level.

Referenced by gts_graph_traverse_new().

static void reset_reserved ( GtsSegment s) [static]

Definition at line 1719 of file graph.c.

References GTS_OBJECT, _GtsSegment::v1, and _GtsSegment::v2.

Referenced by gts_segments_graph_new().

static void sum_edge_cuts_weight ( GtsGNode n,
gpointer *  data 
) [static]

Definition at line 1178 of file graph.c.

References GTS_CONTAINEE, gts_containee_is_contained(), GTS_CONTAINER, gts_gedge_weight(), GTS_GNODE_NEIGHBOR, and GTS_SLIST_CONTAINER.

Referenced by gts_graph_edges_cut_weight().

Here is the call graph for this function:

static void weight_max ( GtsGNode n,
gfloat *  wmax 
) [static]

Definition at line 1617 of file graph.c.

References gts_gnode_weight().

Referenced by gts_wgraph_weight_max().

Here is the call graph for this function:

static void wgedge_class_init ( GtsWGEdgeClass klass) [static]

Definition at line 689 of file graph.c.

References GTS_GEDGE_CLASS, and wgedge_weight().

Referenced by gts_wgedge_class().

Here is the call graph for this function:

static void wgedge_init ( GtsWGEdge e) [static]

Definition at line 694 of file graph.c.

References _GtsWGEdge::weight.

Referenced by gts_wgedge_class().

static gfloat wgedge_weight ( GtsGEdge e) [static]

Definition at line 684 of file graph.c.

References GTS_WGEDGE.

Referenced by wgedge_class_init().

static void wgnode_class_init ( GtsWGNodeClass klass) [static]

Definition at line 291 of file graph.c.

References GTS_GNODE_CLASS, and wgnode_weight().

Referenced by gts_wgnode_class().

Here is the call graph for this function:

static void wgnode_init ( GtsWGNode n) [static]

Definition at line 296 of file graph.c.

References _GtsWGNode::weight.

Referenced by gts_wgnode_class().

static gfloat wgnode_weight ( GtsGNode n) [static]

Definition at line 286 of file graph.c.

References GTS_WGNODE.

Referenced by wgnode_class_init().

static void wgraph_add ( GtsContainer g,
GtsContainee n 
) [static]

Definition at line 1561 of file graph.c.

References GTS_CONTAINER_CLASS, GTS_GNODE, gts_gnode_weight(), GTS_OBJECT_CLASS, GTS_WGRAPH, gts_wgraph_class(), and _GtsWGraph::weight.

Referenced by wgraph_class_init().

Here is the call graph for this function:

static void wgraph_class_init ( GtsWGraphClass klass) [static]

Definition at line 1578 of file graph.c.

References GTS_CONTAINER_CLASS, GTS_GRAPH_CLASS, wgraph_add(), wgraph_remove(), and wgraph_weight().

Referenced by gts_wgraph_class().

Here is the call graph for this function:

static void wgraph_init ( GtsWGraph g) [static]

Definition at line 1586 of file graph.c.

References _GtsWGraph::weight.

Referenced by gts_wgraph_class().

static void wgraph_remove ( GtsContainer g,
GtsContainee n 
) [static]

Definition at line 1571 of file graph.c.

References GTS_CONTAINER_CLASS, GTS_GNODE, gts_gnode_weight(), GTS_OBJECT_CLASS, GTS_WGRAPH, and gts_wgraph_class().

Referenced by wgraph_class_init().

Here is the call graph for this function:

static gfloat wgraph_weight ( GtsGraph g) [static]

Definition at line 1556 of file graph.c.

References GTS_WGRAPH.

Referenced by wgraph_class_init().

static void write_dot_edge ( GtsGEdge edge,
FILE *  fp 
) [static]

Definition at line 1514 of file graph.c.

References GTS_GEDGE_CLASS, GTS_OBJECT, _GtsGEdge::n1, and _GtsGEdge::n2.

Referenced by gts_graph_write_dot().

static void write_dot_node ( GtsGNode node,
gpointer *  data 
) [static]

Definition at line 1499 of file graph.c.

References fp, GTS_GNODE_CLASS, and GTS_OBJECT.

Referenced by gts_graph_write_dot().

static void write_edge ( GtsGEdge edge,
FILE *  fp 
) [static]

Definition at line 1309 of file graph.c.

References fp, GTS_OBJECT, _GtsGEdge::n1, and _GtsGEdge::n2.

Referenced by gts_graph_write().

static void write_node ( GtsObject node,
gpointer *  data 
) [static]

Definition at line 1298 of file graph.c.

References fp, _GtsObject::klass, _GtsObject::reserved, and _GtsObjectClass::write.

Referenced by gts_graph_write().


Variable Documentation