#include <math.h>
#include <stdlib.h>
#include "gts.h"

Include dependency graph for graph.c:

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)
GtsGNodeClass *	gts_gnode_class (void)
GtsGNode *	gts_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)
GtsNGNodeClass *	gts_ngnode_class (void)
GtsNGNode *	gts_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)
GtsWGNodeClass *	gts_wgnode_class (void)
GtsWGNode *	gts_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)
GtsPNodeClass *	gts_pnode_class (void)
GtsPNode *	gts_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)
GtsFNodeClass *	gts_fnode_class (void)
GtsFNode *	gts_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)
GtsGEdgeClass *	gts_gedge_class (void)
GtsGEdge *	gts_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)
GtsPGEdgeClass *	gts_pgedge_class (void)
GtsPGEdge *	gts_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)
GtsWGEdgeClass *	gts_wgedge_class (void)
GtsWGEdge *	gts_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)
GtsGraphClass *	gts_graph_class (void)
GtsGraph *	gts_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)
GtsGraphTraverse *	gts_graph_traverse_new (GtsGraph g, GtsGNode n, GtsTraverseType type, gboolean reinit)
static void	push_neighbor (GtsGNode n, gpointer data)
GtsGNode *	gts_graph_traverse_next (GtsGraphTraverse *t)
GtsGNode *	gts_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)
GtsGNode *	gts_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)
GtsGraph *	gts_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)
GtsWGraphClass *	gts_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)
GtsGraph *	gts_surface_graph_new (GtsGraphClass klass, GtsSurface s)
static void	create_segment_edge (GtsSegment s, GtsGraph graph)
static void	reset_reserved (GtsSegment *s)
GtsGraph *	gts_segments_graph_new (GtsGraphClass klass, GSList segments)
static void	add_to_surface (GtsGNode n, GtsSurface s)
GtsSurface *	gts_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]`

Definition at line 1699 of file graph.c.

References GTS_CONTAINEE, GTS_CONTAINER, gts_container_add(), GTS_GNODE, GTS_OBJECT, gts_pgedge_class(), gts_pgedge_new(), gts_pnode_class(), gts_pnode_new(), _GtsSegment::v1, and _GtsSegment::v2.

Referenced by gts_segments_graph_new().

Here is the call graph for this function:

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]`

Definition at line 766 of file graph.c.

References gts_file_error(), gts_file_next_token(), GTS_GEDGE_CLASS, gts_gedge_class(), GTS_GNODE_CLASS, gts_gnode_class(), GTS_GRAPH, gts_object_class_from_name(), gts_object_class_is_from_class(), GTS_STRING, _GtsFile::token, and _GtsFile::type.

Referenced by graph_class_init().

Here is the call graph for this function:

static void graph_write	(	GtsObject *	object,
		FILE *	fp
	)		`[static]`

Definition at line 756 of file graph.c.

References _GtsGraph::edge_class, GTS_GRAPH, GTS_OBJECT_CLASS, _GtsObjectClass::info, _GtsObject::klass, _GtsObjectClassInfo::name, and _GtsGraph::node_class.

Referenced by graph_class_init().

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 )

gts_gnode_class:

Returns: the GtsGNodeClass.

Definition at line 54 of file graph.c.

References gnode_class_init(), gnode_init(), GTS_OBJECT_CLASS, gts_object_class_new(), and gts_slist_container_class().

Referenced by gnode_remove_container(), graph_init(), graph_read(), gts_fnode_class(), gts_graph_read(), gts_ngnode_class(), gts_pnode_class(), and gts_wgnode_class().

Here is the call graph for this function:

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:

GtsGraph* gts_graph_read ( GtsFile * fp )

gts_graph_read: : a GtsFile.

Reads a graph from a file.

Returns: the new GtsGraph or NULL if an error occured (in which case the field of is set).

Definition at line 1374 of file graph.c.

References _GtsGraph::edge_class, FALSE, fp, _GtsGraph::graph_class, gts_allow_floating_gnodes, GTS_CONTAINEE, GTS_CONTAINER, gts_container_add(), GTS_ERROR, gts_file_error(), gts_file_first_token_after(), gts_file_next_token(), gts_gedge_class(), gts_gedge_new(), GTS_GNODE, gts_gnode_class(), GTS_GRAPH, GTS_GRAPH_CLASS, gts_graph_class(), GTS_INT, GTS_OBJECT, GTS_OBJECT_CLASS, gts_object_class_from_name(), gts_object_class_is_from_class(), gts_object_destroy(), gts_object_new(), GTS_STRING, n, _GtsGraph::node_class, _GtsObjectClass::read, _GtsFile::token, TRUE, and _GtsFile::type.

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: