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

Include dependency graph for partition.c:

Functions
guint	gts_graph_partition_edges_cut (GSList *partition)
gfloat	gts_graph_partition_edges_cut_weight (GSList *partition)
void	gts_graph_partition_print_stats (GSList partition, FILE fp)
gfloat	gts_graph_partition_balance (GSList *partition)
GSList *	gts_graph_partition_clone (GSList *partition)
void	gts_graph_partition_destroy (GSList *partition)
static void	find_smallest_degree (GtsGNode n, gpointer data)
static gint	graph_comp_weight (GtsGraph g1, GtsGraph g2)
static void	partition_update (GSList list, GtsGraph g)
static void	better_seed (GtsGNode n, gpointer data)
static GtsGNode *	graph_new_seed (GtsGraph g, GtsGNode seed)
GSList *	gts_graph_bubble_partition (GtsGraph *g, guint np, guint niter, GtsFunc step_info, gpointer data)
static gdouble	node_cost (GtsGNode n, gpointer data)
static void	add_neighbor (GtsGNode n, GtsEHeap heap)
static void	add_unused (GtsGNode n, GtsGraph g2)
static gdouble	degree_cost (GtsGNode n, GtsGraph g)
static void	add_seed (GtsGNode n, GtsEHeap heap)
static void	boundary_node1 (GtsGNode n, GtsGraphBisection bg)
static void	boundary_node2 (GtsGNode n, GtsGraphBisection bg)
static void	check_bg (GtsGNode n, gpointer data)
gboolean	gts_graph_bisection_check (GtsGraphBisection *bg)
GtsGraphBisection *	gts_graph_ggg_bisection (GtsGraph *g, guint ntry)
GtsGraphBisection *	gts_graph_bfgg_bisection (GtsGraph *g, guint ntry)
static gdouble	node_move_cost1 (GtsGNode n, GtsGraphBisection bg)
static gdouble	node_move_cost2 (GtsGNode n, GtsGraphBisection bg)
static void	build_heap (GtsGNode n, GtsEHeap heap)
gdouble	gts_graph_bisection_kl_refine (GtsGraphBisection *bg, guint mmax)
static void	build_bheap (GtsGNode n, GtsGNode n1, GtsEHeap *heap)
static void	update_neighbors (GtsGNode n, GtsGraphBisection bg, GtsEHeap h1, GtsEHeap h2)
gdouble	gts_graph_bisection_bkl_refine (GtsGraphBisection *bg, guint mmax, gfloat imbalance)
static void	bisection_children (GtsGNodeSplit ns, GtsGraphBisection bg)
GtsGraphBisection *	gts_graph_bisection_new (GtsWGraph *wg, guint ntry, guint mmax, guint nmin, gfloat imbalance)
void	gts_graph_bisection_destroy (GtsGraphBisection *bg, gboolean destroy_graphs)
static void	recursive_bisection (GtsWGraph wg, guint np, guint ntry, guint mmax, guint nmin, gfloat imbalance, GSList *list)
GSList *	gts_graph_recursive_bisection (GtsWGraph *wg, guint n, guint ntry, guint mmax, guint nmin, gfloat imbalance)

Function Documentation

static void add_neighbor	(	GtsGNode *	n,
		GtsEHeap *	heap
	)		`[static]`

Definition at line 374 of file partition.c.

References gts_eheap_insert(), gts_eheap_remove(), and GTS_OBJECT.

Referenced by gts_graph_ggg_bisection().

Here is the call graph for this function:

static void add_seed	(	GtsGNode *	n,
		GtsEHeap *	heap
	)		`[static]`

Definition at line 396 of file partition.c.

References gts_eheap_insert().

Referenced by gts_graph_bfgg_bisection(), and gts_graph_ggg_bisection().

Here is the call graph for this function:

static void add_unused	(	GtsGNode *	n,
		GtsGraph *	g2
	)		`[static]`

Definition at line 383 of file partition.c.

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

Referenced by gts_graph_bfgg_bisection(), and gts_graph_ggg_bisection().

Here is the call graph for this function:

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

Definition at line 224 of file partition.c.

References gts_graph_distance_sum(), and n.

Referenced by graph_new_seed().

Here is the call graph for this function:

static void bisection_children	(	GtsGNodeSplit *	ns,
		GtsGraphBisection *	bg
	)		`[static]`

Definition at line 1010 of file partition.c.

References _GtsGraphBisection::bg1, _GtsGraphBisection::bg2, FALSE, _GtsGraphBisection::g1, _GtsGraphBisection::g2, gts_allow_floating_gnodes, GTS_CONTAINEE, gts_containee_is_contained(), GTS_CONTAINER, gts_container_add(), gts_container_remove(), gts_gnode_degree(), GTS_GNODE_SPLIT_N1, GTS_GNODE_SPLIT_N2, _GtsGNodeSplit::n, and TRUE.

Referenced by gts_graph_bisection_new().

Here is the call graph for this function:

static void boundary_node1	(	GtsGNode *	n,
		GtsGraphBisection *	bg
	)		`[static]`

Definition at line 401 of file partition.c.

References _GtsGraphBisection::bg1, _GtsGraphBisection::g2, GTS_CONTAINEE, gts_containee_is_contained(), GTS_CONTAINER, GTS_GNODE_NEIGHBOR, and GTS_SLIST_CONTAINER.

Referenced by gts_graph_bfgg_bisection(), and gts_graph_ggg_bisection().

Here is the call graph for this function:

static void boundary_node2	(	GtsGNode *	n,
		GtsGraphBisection *	bg
	)		`[static]`

Definition at line 416 of file partition.c.

References _GtsGraphBisection::bg2, _GtsGraphBisection::g1, GTS_CONTAINEE, gts_containee_is_contained(), GTS_CONTAINER, GTS_GNODE_NEIGHBOR, and GTS_SLIST_CONTAINER.

Referenced by gts_graph_bfgg_bisection(), and gts_graph_ggg_bisection().

Here is the call graph for this function:

static void build_bheap	(	GtsGNode *	n,
		GtsGNode *	n1,
		GtsEHeap *	heap
	)		`[static]`

Definition at line 820 of file partition.c.

References gts_eheap_insert(), and GTS_OBJECT.

Referenced by gts_graph_bisection_bkl_refine().

Here is the call graph for this function:

static void build_heap	(	GtsGNode *	n,
		GtsEHeap *	heap
	)		`[static]`

Definition at line 700 of file partition.c.

References gts_eheap_insert(), and GTS_OBJECT.

Referenced by gts_graph_bisection_kl_refine().

Here is the call graph for this function:

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

Definition at line 431 of file partition.c.

References FALSE, gts_gnode_degree(), and ok.

Referenced by gts_graph_bisection_check().

Here is the call graph for this function:

static gdouble degree_cost	(	GtsGNode *	n,
		GtsGraph *	g
	)		`[static]`

Definition at line 391 of file partition.c.

References gts_gnode_degree().

Referenced by gts_graph_bfgg_bisection(), and gts_graph_ggg_bisection().

Here is the call graph for this function:

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

Definition at line 161 of file partition.c.

References gts_gnode_degree(), min, and n.

Referenced by gts_graph_bubble_partition().

Here is the call graph for this function:

static gint graph_comp_weight	(	GtsGraph *	g1,
		GtsGraph *	g2
	)		`[static]`

Definition at line 174 of file partition.c.

References gts_graph_weight().

Referenced by partition_update().

Here is the call graph for this function:

static GtsGNode* graph_new_seed	(	GtsGraph *	g,
		GtsGNode *	seed
	)		`[static]`

Definition at line 237 of file partition.c.

References better_seed(), gts_gnode_foreach_neighbor(), and gts_graph_distance_sum().

Referenced by gts_graph_bubble_partition().

Here is the call graph for this function:

GtsGraphBisection* gts_graph_bfgg_bisection	(	GtsGraph *	g,
		guint	ntry
	)

gts_graph_bfgg_bisection: : a GtsGraph. : the number of randomly selected initial seeds.

An implementation of a "Breadth-First Graph Growing" algorithm.

randomly chosen seeds are used and the best partition is retained.

Returns: a new GtsGraphBisection of .

Definition at line 607 of file partition.c.

References add_seed(), add_unused(), _GtsGraphBisection::bg1, _GtsGraphBisection::bg2, boundary_node1(), boundary_node2(), degree_cost(), _GtsGraph::edge_class, _GtsGraphBisection::g, _GtsGraphBisection::g1, _GtsGraphBisection::g2, GTS_BREADTH_FIRST, GTS_CONTAINEE, GTS_CONTAINER, gts_container_add(), gts_container_foreach(), gts_container_size(), gts_eheap_destroy(), gts_eheap_freeze(), gts_eheap_new(), gts_eheap_remove_top(), gts_eheap_thaw(), gts_gnode_weight(), GTS_GRAPH_CLASS, gts_graph_edges_cut_weight(), gts_graph_new(), gts_graph_traverse_destroy(), gts_graph_traverse_new(), gts_graph_traverse_next(), gts_graph_weight(), GTS_OBJECT, gts_object_destroy(), n, _GtsGraph::node_class, and TRUE.

Here is the call graph for this function:

gdouble gts_graph_bisection_bkl_refine	(	GtsGraphBisection *	bg,
		guint	mmax,
		gfloat	imbalance
	)

gts_graph_bisection_bkl_refine: : a GtsGraphBisection. : the maximum number of unsuccessful successive moves. : the maximum relative imbalance allowed between the weights of both halves of the partition.

An implementation of the simplified boundary Kernighan-Lin algorithm for graph bisection refinement as described in Karypis and Kumar (1997).

The algorithm stops if consecutive modes do not lead to a decrease in the number of edges cut. This last moves are undone.

Returns: the decrease in the weight of the edges cut by the bisection.

Definition at line 884 of file partition.c.

References _GtsGraphBisection::bg1, _GtsGraphBisection::bg2, build_bheap(), FALSE, _GtsGraphBisection::g, _GtsGraphBisection::g1, _GtsGraphBisection::g2, GTS_CONTAINEE, gts_containee_is_contained(), GTS_CONTAINER, gts_container_add(), gts_container_foreach(), gts_container_remove(), gts_eheap_destroy(), gts_eheap_freeze(), gts_eheap_new(), gts_eheap_remove_top(), gts_eheap_thaw(), gts_gnode_degree(), gts_graph_weight(), GTS_OBJECT, gts_object_reset_reserved(), n, node_move_cost1(), node_move_cost2(), TRUE, and update_neighbors().

Referenced by gts_graph_bisection_new().

Here is the call graph for this function:

gboolean gts_graph_bisection_check ( GtsGraphBisection * bg )

gts_graph_bisection_check: : a GtsGraphBisection.

Checks that the boundary of is correctly defined (used for debugging purposes).

Returns: TRUE if is ok, FALSE otherwise.

Definition at line 458 of file partition.c.

References _GtsGraphBisection::bg1, _GtsGraphBisection::bg2, check_bg(), FALSE, _GtsGraphBisection::g1, _GtsGraphBisection::g2, GTS_CONTAINER, gts_container_foreach(), ok, and TRUE.

Referenced by gts_graph_bisection_new().

Here is the call graph for this function:

void gts_graph_bisection_destroy	(	GtsGraphBisection *	bg,
		gboolean	destroy_graphs
	)

gts_graph_bisection_destroy: : a GtsGraphBisection. : controls graph destruction.

Frees all the memory allocated for . If is TRUE the graphs created by are destroyed.

Definition at line 1139 of file partition.c.

References _GtsGraphBisection::bg1, _GtsGraphBisection::bg2, _GtsGraphBisection::g1, _GtsGraphBisection::g2, GTS_OBJECT, and gts_object_destroy().

Referenced by gts_graph_recursive_bisection(), and recursive_bisection().

Here is the call graph for this function:

gdouble gts_graph_bisection_kl_refine	(	GtsGraphBisection *	bg,
		guint	mmax
	)

gts_graph_bisection_kl_refine: : a GtsGraphBisection. : the maximum number of unsuccessful successive moves.

An implementation of the simplified Kernighan-Lin algorithm for graph bisection refinement as described in Karypis and Kumar (1997).

The algorithm stops if consecutive modes do not lead to a decrease in the number of edges cut. This last moves are undone.

Returns: the decrease in the weight of the edges cut by the bisection.

Definition at line 720 of file partition.c.

References build_heap(), _GtsGraphBisection::g, _GtsGraphBisection::g1, _GtsGraphBisection::g2, GTS_CONTAINEE, gts_containee_is_contained(), GTS_CONTAINER, gts_container_add(), gts_container_foreach(), gts_container_remove(), gts_eheap_destroy(), gts_eheap_foreach(), gts_eheap_freeze(), gts_eheap_insert(), gts_eheap_new(), gts_eheap_remove(), gts_eheap_remove_top(), gts_eheap_thaw(), GTS_GNODE_NEIGHBOR, gts_graph_weight(), GTS_OBJECT, gts_object_reset_reserved(), GTS_SLIST_CONTAINER, n, node_move_cost1(), and node_move_cost2().

Here is the call graph for this function:

GtsGraphBisection* gts_graph_bisection_new	(	GtsWGraph *	wg,
		guint	ntry,
		guint	mmax,
		guint	nmin,
		gfloat	imbalance
	)

gts_graph_bisection_new: : a GtsWGraph. : the number of tries for the graph growing algorithm. : the number of unsucessful moves for the refinement algorithm. : the minimum number of nodes of the coarsest graph. : the maximum relative imbalance allowed between the weights of both halves of the partition.

An implementation of a multilevel bisection algorithm as presented in Karypis and Kumar (1997). A multilevel hierarchy of graphs is created using the GtsPGraph object. The bisection of the coarsest graph is created using the gts_graph_ggg_bisection() function. The graph is then uncoarsened using gts_pgraph_down() and at each level the bisection is refined using gts_graph_bisection_bkl_refine().

Returns: a new GtsGraphBisection of .

Definition at line 1062 of file partition.c.

References bisection_children(), _GtsGraphBisection::g1, GTS_CONTAINER, gts_container_size(), gts_gnode_split_class(), GTS_GRAPH, gts_graph_bisection_bkl_refine(), gts_graph_bisection_check(), gts_graph_edges_cut(), gts_graph_edges_cut_weight(), gts_graph_ggg_bisection(), gts_graph_weight(), GTS_OBJECT, gts_object_destroy(), gts_pgraph_class(), gts_pgraph_down(), gts_pgraph_new(), gts_wgedge_class(), and gts_wgnode_class().

Referenced by gts_graph_recursive_bisection(), and recursive_bisection().

Here is the call graph for this function:

GSList* gts_graph_bubble_partition	(	GtsGraph *	g,
		guint	np,
		guint	niter,
		GtsFunc	step_info,
		gpointer	data
	)

gts_graph_bubble_partition: : a GtsGraph. : number of partitions. : the maximum number of iterations. : a GtsFunc or NULL. : user data to pass to .

An implementation of the "bubble partitioning algorithm" of Diekmann, Preis, Schlimbach and Walshaw (2000). The maximum number of iteration on the positions of the graph growing seeds is controlled by .

If not NULL is called after each iteration on the seeds positions passing the partition (a GSList) as argument.

Returns: a list of new GtsGraph representing the partition.

Definition at line 269 of file partition.c.

References FALSE, find_smallest_degree(), graph_new_seed(), GTS_CONTAINEE, GTS_CONTAINER, gts_container_add(), gts_container_foreach(), GTS_GRAPH, gts_graph_farthest(), GTS_OBJECT, gts_object_destroy(), gts_object_new(), gts_object_reset_reserved(), min, partition_update(), and TRUE.

Here is the call graph for this function:

GtsGraphBisection* gts_graph_ggg_bisection	(	GtsGraph *	g,
		guint	ntry
	)

gts_graph_ggg_bisection: : a GtsGraph. : the number of randomly selected initial seeds.

An implementation of the "Greedy Graph Growing" algorithm of Karypis and Kumar (1997).

randomly chosen seeds are used and the best partition is retained.

Returns: a new GtsGraphBisection of .

Definition at line 495 of file partition.c.

References add_neighbor(), add_seed(), add_unused(), _GtsGraphBisection::bg1, _GtsGraphBisection::bg2, boundary_node1(), boundary_node2(), degree_cost(), _GtsGraph::edge_class, FALSE, _GtsGraphBisection::g, _GtsGraphBisection::g1, _GtsGraphBisection::g2, GTS_CONTAINEE, GTS_CONTAINER, gts_container_add(), gts_container_foreach(), gts_container_size(), gts_eheap_destroy(), gts_eheap_freeze(), gts_eheap_new(), gts_eheap_remove_top(), gts_eheap_thaw(), gts_gnode_foreach_neighbor(), gts_gnode_weight(), GTS_GRAPH_CLASS, gts_graph_edges_cut_weight(), gts_graph_new(), gts_graph_weight(), GTS_OBJECT, gts_object_destroy(), n, _GtsGraph::node_class, node_cost(), and TRUE.

Referenced by gts_graph_bisection_new().

Here is the call graph for this function:

gfloat gts_graph_partition_balance ( GSList * partition )

gts_graph_partition_balance: : a list of representing a partition.

Returns: the difference between the maximum and the minimum weight of the graphs in .

Definition at line 106 of file partition.c.

References gts_graph_weight().

Here is the call graph for this function:

GSList* gts_graph_partition_clone ( GSList * partition )

gts_graph_partition_clone: : a list of representing a partition.

Returns: a new partition clone of (i.e. a list of new graphs clones of the graphs in ).

Definition at line 131 of file partition.c.

References GTS_OBJECT, and gts_object_clone().

Here is the call graph for this function:

void gts_graph_partition_destroy ( GSList * partition )

gts_graph_partition_destroy: : a list of representing a partition.

Destroys all the graphs in and frees .

Definition at line 150 of file partition.c.

References GTS_OBJECT, and gts_object_destroy().

Here is the call graph for this function:

guint gts_graph_partition_edges_cut ( GSList * partition )

gts_graph_partition_edges_cut: : a list of representing a partition.

Returns: the number of edges cut by the partition.

Definition at line 34 of file partition.c.

References gts_graph_edges_cut().

Referenced by gts_graph_partition_print_stats().

Here is the call graph for this function:

gfloat gts_graph_partition_edges_cut_weight ( GSList * partition )

gts_graph_partition_edges_cut_weight: : a list of representing a partition.

Returns: the total weight of the edges cut by the partition.

Definition at line 52 of file partition.c.

References gts_graph_edges_cut_weight().

Referenced by gts_graph_partition_print_stats().

Here is the call graph for this function:

void gts_graph_partition_print_stats	(	GSList *	partition,
		FILE *	fp
	)

gts_graph_partition_print_stats: : a list of representing a partition. : a file pointer.

Writes to a summary of the properties of .

Definition at line 71 of file partition.c.

References gts_graph_partition_edges_cut(), gts_graph_partition_edges_cut_weight(), gts_graph_weight(), gts_range_add_value(), gts_range_init(), gts_range_print(), and gts_range_update().

Here is the call graph for this function:

GSList* gts_graph_recursive_bisection	(	GtsWGraph *	wg,
		guint	n,
		guint	ntry,
		guint	mmax,
		guint	nmin,
		gfloat	imbalance
	)

gts_graph_recursive_bisection: : a GtsWGraph.
: the number of bisection levels. : the number of tries for the graph growing algorithm. : the number of unsucessful moves for the refinement algorithm. : the minimum number of nodes of the coarsest graph. : the maximum relative imbalance allowed between the weights of both halves of the partition.

Calls gts_graph_bisection_new() recursively in order to obtain a 2^
partition of .

Returns: a list of 2^
new GtsGraph representing the partition.

Definition at line 1195 of file partition.c.

References FALSE, _GtsGraphBisection::g1, _GtsGraphBisection::g2, gts_graph_bisection_destroy(), gts_graph_bisection_new(), GTS_WGRAPH, and recursive_bisection().

Here is the call graph for this function:

static gdouble node_cost	(	GtsGNode *	n,
		gpointer *	data
	)		`[static]`

Definition at line 351 of file partition.c.

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

Referenced by gts_graph_ggg_bisection().

Here is the call graph for this function:

static gdouble node_move_cost1	(	GtsGNode *	n,
		GtsGraphBisection *	bg
	)		`[static]`

Definition at line 690 of file partition.c.

References _GtsGraphBisection::g1, _GtsGraphBisection::g2, and gts_gnode_move_cost().

Referenced by gts_graph_bisection_bkl_refine(), and gts_graph_bisection_kl_refine().

Here is the call graph for this function:

static gdouble node_move_cost2	(	GtsGNode *	n,
		GtsGraphBisection *	bg
	)		`[static]`

Definition at line 695 of file partition.c.

References _GtsGraphBisection::g1, _GtsGraphBisection::g2, and gts_gnode_move_cost().

Referenced by gts_graph_bisection_bkl_refine(), and gts_graph_bisection_kl_refine().

Here is the call graph for this function:

static void partition_update	(	GSList *	list,
		GtsGraph *	g
	)		`[static]`

Definition at line 181 of file partition.c.

References FALSE, graph_comp_weight(), GTS_BREADTH_FIRST, GTS_CONTAINEE, GTS_CONTAINER, gts_container_add(), gts_graph_traverse_destroy(), gts_graph_traverse_new(), gts_graph_traverse_next(), gts_heap_destroy(), gts_heap_insert(), gts_heap_new(), gts_heap_remove_top(), GTS_OBJECT, n, and TRUE.

Referenced by gts_graph_bubble_partition().

Here is the call graph for this function:

static void recursive_bisection	(	GtsWGraph *	wg,
		guint	np,
		guint	ntry,
		guint	mmax,
		guint	nmin,
		gfloat	imbalance,
		GSList **	list
	)		`[static]`

Definition at line 1155 of file partition.c.

References FALSE, _GtsGraphBisection::g1, _GtsGraphBisection::g2, gts_graph_bisection_destroy(), gts_graph_bisection_new(), GTS_OBJECT, gts_object_destroy(), and GTS_WGRAPH.

Referenced by gts_graph_recursive_bisection().

Here is the call graph for this function:

static void update_neighbors	(	GtsGNode *	n,
		GtsGraphBisection *	bg,
		GtsEHeap *	h1,
		GtsEHeap *	h2
	)		`[static]`

Definition at line 825 of file partition.c.

References _GtsGraphBisection::bg1, _GtsGraphBisection::bg2, _GtsGraphBisection::g, _GtsGraphBisection::g1, _GtsGraphBisection::g2, GTS_CONTAINEE, gts_containee_is_contained(), GTS_CONTAINER, gts_eheap_insert(), gts_eheap_remove(), gts_gnode_degree(), GTS_GNODE_NEIGHBOR, GTS_OBJECT, and GTS_SLIST_CONTAINER.

Referenced by gts_graph_bisection_bkl_refine().

Here is the call graph for this function:

partition.c File Reference

Functions

Function Documentation