#include "gts.h"

Include dependency graph for pgraph.c:

Functions
static void	gnode_split_destroy (GtsObject *object)
static void	gnode_split_class_init (GtsGNodeSplitClass *klass)
static void	gnode_split_init (GtsGNodeSplit *ns)
GtsGNodeSplitClass *	gts_gnode_split_class (void)
GtsGNodeSplit *	gts_gnode_split_new (GtsGNodeSplitClass klass, GtsGNode n, GtsObject n1, GtsObject n2)
static void	connect_edge (GtsGEdge e, gpointer data)
void	gts_gnode_split_collapse (GtsGNodeSplit ns, GtsGraph g, GtsWGEdgeClass *klass)
static void	restore_edge (GtsGEdge e, gpointer data)
void	gts_gnode_split_expand (GtsGNodeSplit ns, GtsGraph g)
static void	pgraph_destroy (GtsObject *object)
static void	pgraph_class_init (GtsPGraphClass *klass)
static void	pgraph_init (GtsPGraph *pg)
GtsPGraphClass *	gts_pgraph_class (void)
static void	match_neighbor (GtsGNode n, gpointer data)
static GSList *	maximal_matching (GtsGraph *g)
GtsPGraph *	gts_pgraph_new (GtsPGraphClass klass, GtsGraph g, GtsGNodeSplitClass split_class, GtsWGNodeClass node_class, GtsWGEdgeClass *edge_class, guint min)
GtsGNodeSplit *	gts_pgraph_add_node (GtsPGraph *pg)
GtsGNodeSplit *	gts_pgraph_remove_node (GtsPGraph *pg)
guint	gts_pgraph_max_node_number (GtsPGraph *pg)
guint	gts_pgraph_min_node_number (GtsPGraph *pg)
void	gts_pgraph_set_node_number (GtsPGraph *pg, guint n)
guint	gts_pgraph_get_node_number (GtsPGraph *pg)
gboolean	gts_pgraph_down (GtsPGraph *pg, GtsFunc func, gpointer data)

Function Documentation

static void connect_edge	(	GtsGEdge *	e,
		gpointer *	data
	)		`[static]`

Definition at line 111 of file pgraph.c.

References GTS_CONTAINEE, GTS_CONTAINER, gts_container_add(), gts_gedge_connects, GTS_OBJECT, n, _GtsGEdge::n1, and _GtsGEdge::n2.

Referenced by gts_gnode_split_collapse().

Here is the call graph for this function:

static void gnode_split_class_init ( GtsGNodeSplitClass * klass ) [static]

Definition at line 43 of file pgraph.c.

References gnode_split_destroy(), and GTS_OBJECT_CLASS.

Referenced by gts_gnode_split_class().

Here is the call graph for this function:

static void gnode_split_destroy ( GtsObject * object ) [static]

Definition at line 24 of file pgraph.c.

References GTS_CONTAINER, gts_container_size(), GTS_GNODE_SPLIT, gts_gnode_split_class(), GTS_OBJECT, GTS_OBJECT_CLASS, gts_object_destroy(), GTS_SLIST_CONTAINEE, and _GtsGNodeSplit::n.

Referenced by gnode_split_class_init().

Here is the call graph for this function:

static void gnode_split_init ( GtsGNodeSplit * ns ) [static]

Definition at line 48 of file pgraph.c.

References _GtsGNodeSplit::n, _GtsGNodeSplit::n1, and _GtsGNodeSplit::n2.

Referenced by gts_gnode_split_class().

GtsGNodeSplitClass* gts_gnode_split_class ( void )

gts_gnode_split_class:

Returns: the GtsGNodeSplitClass.

Definition at line 59 of file pgraph.c.

References gnode_split_class_init(), gnode_split_init(), gts_object_class(), and gts_object_class_new().

Referenced by gnode_split_destroy(), gts_graph_bisection_new(), and pgraph_init().

Here is the call graph for this function:

void gts_gnode_split_collapse	(	GtsGNodeSplit *	ns,
		GtsGraph *	g,
		GtsWGEdgeClass *	klass
	)

gts_gnode_split_collapse: : a GtsGNodeSplit. : a GtsGraph. : a GtsWGEdgeClass.

Collapses the node split . Any new edge created during the process will be of class .

Definition at line 138 of file pgraph.c.

References connect_edge(), FALSE, gts_allow_floating_gnodes, GTS_CONTAINEE, GTS_CONTAINER, gts_container_add(), gts_container_foreach(), gts_container_remove(), gts_container_size(), gts_gedge_weight(), GTS_GNODE_NEIGHBOR, GTS_GNODE_SPLIT_N1, GTS_GNODE_SPLIT_N2, GTS_OBJECT, GTS_SLIST_CONTAINER, gts_wgedge_new(), _GtsGNodeSplit::n, and TRUE.

Referenced by gts_pgraph_new(), and gts_pgraph_remove_node().

Here is the call graph for this function:

void gts_gnode_split_expand	(	GtsGNodeSplit *	ns,
		GtsGraph *	g
	)

gts_gnode_split_expand: : a GtsGNodeSplit. : a GtsGraph.

Expands the node split ns adding the new nodes to .

Definition at line 228 of file pgraph.c.

References FALSE, gts_allow_floating_gnodes, GTS_CONTAINEE, gts_containee_is_contained(), GTS_CONTAINER, gts_container_add(), gts_container_foreach(), gts_container_remove(), gts_container_size(), GTS_GNODE_SPLIT_N1, GTS_GNODE_SPLIT_N2, GTS_SLIST_CONTAINER, _GtsGNodeSplit::n, restore_edge(), and TRUE.

Referenced by gts_pgraph_add_node().

Here is the call graph for this function:

GtsGNodeSplit* gts_gnode_split_new	(	GtsGNodeSplitClass *	klass,
		GtsGNode *	n,
		GtsObject *	n1,
		GtsObject *	n2
	)

gts_gnode_split_new: : a GtsGNodeSplitClass.
: a GtsGNode. : a GtsGNodeSplit or GtsGNode. : a GtsGNodeSplit or GtsGNode.

Creates a new GtsGNodeSplit which would collapse and into
. The collapse itself is not performed.

Returns: the new GtsGNodeSplit.

Definition at line 91 of file pgraph.c.

References GTS_GNODE_SPLIT, GTS_IS_GNODE, GTS_IS_GNODE_SPLIT, GTS_OBJECT_CLASS, gts_object_new(), n, _GtsGNodeSplit::n, _GtsGNodeSplit::n1, and _GtsGNodeSplit::n2.

Referenced by gts_pgraph_new().

Here is the call graph for this function:

GtsGNodeSplit* gts_pgraph_add_node ( GtsPGraph * pg )

gts_pgraph_add_node: : a GtsPGraph.

Adds one node to the multilevel graph by expanding the next available GtsGNodeSplit.

Returns: the expanded GtsGNodeSplit or #NULL if all the GtsGNodeSplit have already been expanded.

Definition at line 448 of file pgraph.c.

References _GtsPGraph::g, gts_gnode_split_expand(), _GtsPGraph::pos, and _GtsPGraph::split.

Referenced by gts_pgraph_down(), and gts_pgraph_set_node_number().

Here is the call graph for this function:

GtsPGraphClass* gts_pgraph_class ( void )

gts_pgraph_class:

Returns: the GtsPGraphClass.

Definition at line 303 of file pgraph.c.

References gts_object_class(), gts_object_class_new(), pgraph_class_init(), and pgraph_init().

Referenced by gts_graph_bisection_new(), and pgraph_destroy().

Here is the call graph for this function:

gboolean gts_pgraph_down	(	GtsPGraph *	pg,
		GtsFunc	func,
		gpointer	data
	)

gts_pgraph_down: : a GtsPGraph. : a GtsFunc or NULL. : user data to pass to .

Performs the required number of expansions to go from the current level to the level immediately below.

If is not NULL, it is called after each GtsGNodeSplit has been expanded.

Returns: FALSE if it is not possible to go down one level, TRUE otherwise.

Definition at line 563 of file pgraph.c.

References FALSE, _GtsPGraph::g, GTS_CONTAINER, gts_container_size(), gts_pgraph_add_node(), _GtsPGraph::level, _GtsPGraph::levels, and TRUE.

Referenced by gts_graph_bisection_new().

Here is the call graph for this function:

guint gts_pgraph_get_node_number ( GtsPGraph * pg )

gts_pgraph_get_node_number: : a GtsPGraph.

Returns: the current number of nodes of .

Definition at line 541 of file pgraph.c.

References _GtsPGraph::min, _GtsPGraph::pos, and _GtsPGraph::split.

guint gts_pgraph_max_node_number ( GtsPGraph * pg )

gts_pgraph_max_node_number: : a GtsPGraph.

Returns: the maximum number of nodes of i.e. the number of nodes if all the GtsGNodeSplit were expanded.

Definition at line 495 of file pgraph.c.

References _GtsPGraph::min, and _GtsPGraph::split.

guint gts_pgraph_min_node_number ( GtsPGraph * pg )

gts_pgraph_min_node_number: : a GtsPGraph.

Returns: the minimum number of nodes of i.e. the number of nodes if all the GtsGNodeSplit were collapsed.

Definition at line 509 of file pgraph.c.

References _GtsPGraph::min.

GtsPGraph* gts_pgraph_new	(	GtsPGraphClass *	klass,
		GtsGraph *	g,
		GtsGNodeSplitClass *	split_class,
		GtsWGNodeClass *	node_class,
		GtsWGEdgeClass *	edge_class,
		guint	min
	)

gts_pgraph_new: : a GtsPGraphClass. : a GtsGraph. : a GtsGNodeSplitClass. : a GtsWGNodeClass. : a GtsWGEdgeClass. : the minimum number of nodes.

Creates a new multilevel approximation of graph . At each level a maximal matching is created using the Heavy Edge Matching (HEM) technique of Karypis and Kumar (1997). The newly created nodes are of type and their weight is set to the sum of the weights of their children. The newly created edges are of type and their weight is set to the sum of the weight of the collapsed edges. The last level is reached when the maximal matching obtained would lead to a graph with less than nodes.

Returns: the new GtsPGraph containing the multilevel representation of .

Definition at line 388 of file pgraph.c.

References _GtsPGraph::edge_class, _GtsPGraph::g, GTS_CONTAINER, gts_container_size(), GTS_GNODE, gts_gnode_split_collapse(), gts_gnode_split_new(), gts_gnode_weight(), GTS_OBJECT, GTS_OBJECT_CLASS, gts_object_new(), GTS_PGRAPH, gts_wgnode_new(), _GtsPGraph::level, _GtsPGraph::levels, maximal_matching(), _GtsPGraph::min, n, _GtsGEdge::n1, _GtsGEdge::n2, _GtsPGraph::pos, _GtsPGraph::split, and _GtsPGraph::split_class.