GTS Library Reference Manual |
---|
#include <gts.h> struct GtsGraphBisection; GtsGraphBisection* gts_graph_bisection_new (GtsWGraph *wg,guint ntry,guint mmax,guint nmin,gfloat imbalance); GtsGraphBisection* gts_graph_ggg_bisection (GtsGraph *g,guint ntry); GtsGraphBisection* gts_graph_bfgg_bisection (GtsGraph *g,guint ntry);gboolean gts_graph_bisection_check (GtsGraphBisection *bg);gdouble gts_graph_bisection_kl_refine (GtsGraphBisection *bg,guint mmax);gdouble gts_graph_bisection_bkl_refine (GtsGraphBisection *bg,guint mmax,gfloat imbalance);GSList * gts_graph_recursive_bisection (GtsWGraph *wg,guint n,guint ntry,guint mmax,guint nmin,gfloat imbalance); void gts_graph_bisection_destroy (GtsGraphBisection *bg,gboolean destroy_graphs);GSList * gts_graph_bubble_partition (GtsGraph *g,guint np,guint niter, GtsFunc step_info,gpointer data);guint gts_graph_edges_cut (GtsGraph *g);gfloat gts_graph_edges_cut_weight (GtsGraph *g);guint gts_graph_partition_edges_cut (GSList *partition);gfloat gts_graph_partition_balance (GSList *partition);GSList * gts_graph_partition_clone (GSList *partition); void gts_graph_partition_print_stats (GSList *partition,FILE *fp);gfloat gts_graph_partition_edges_cut_weight (GSList *partition); void gts_graph_partition_destroy (GSList *partition);
struct GtsGraphBisection { GtsGraph * g; GtsGraph * g1; GtsGraph * g2; GHashTable * bg1; GHashTable * bg2; };
GtsGraphBisection* gts_graph_bisection_new (GtsWGraph *wg,guint ntry,guint mmax,guint nmin,gfloat imbalance);
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().
wg : | a GtsWGraph. |
ntry : | the number of tries for the graph growing algorithm. |
mmax : | the number of unsucessful moves for the refinement algorithm. |
nmin : | the minimum number of nodes of the coarsest graph. |
imbalance : | the maximum relative imbalance allowed between the weights of both halves of the partition. |
Returns : | a new GtsGraphBisection of wg. |
GtsGraphBisection* gts_graph_ggg_bisection (GtsGraph *g,guint ntry);
An implementation of the "Greedy Graph Growing" algorithm of Karypis and Kumar (1997).
ntry randomly chosen seeds are used and the best partition is retained.
g : | a GtsGraph. |
ntry : | the number of randomly selected initial seeds. |
Returns : | a new GtsGraphBisection of g. |
GtsGraphBisection* gts_graph_bfgg_bisection (GtsGraph *g,guint ntry);
An implementation of a "Breadth-First Graph Growing" algorithm.
ntry randomly chosen seeds are used and the best partition is retained.
g : | a GtsGraph. |
ntry : | the number of randomly selected initial seeds. |
Returns : | a new GtsGraphBisection of g. |
gboolean gts_graph_bisection_check (GtsGraphBisection *bg);
Checks that the boundary of bg is correctly defined (used for debugging purposes).
bg : | |
Returns : | TRUE if bg is ok, FALSE otherwise. |
gdouble gts_graph_bisection_kl_refine (GtsGraphBisection *bg,guint mmax);
An implementation of the simplified Kernighan-Lin algorithm for graph bisection refinement as described in Karypis and Kumar (1997).
The algorithm stops if mmax consecutive modes do not lead to a decrease in the number of edges cut. This last mmax moves are undone.
bg : | |
mmax : | the maximum number of unsuccessful successive moves. |
Returns : | the decrease in the weight of the edges cut by the bisection. |
gdouble gts_graph_bisection_bkl_refine (GtsGraphBisection *bg,guint mmax,gfloat imbalance);
An implementation of the simplified boundary Kernighan-Lin algorithm for graph bisection refinement as described in Karypis and Kumar (1997).
The algorithm stops if mmax consecutive modes do not lead to a decrease in the number of edges cut. This last mmax moves are undone.
bg : | |
mmax : | the maximum number of unsuccessful successive moves. |
imbalance : | the maximum relative imbalance allowed between the weights of both halves of the partition. |
Returns : | the decrease in the weight of the edges cut by the bisection. |
GSList * gts_graph_recursive_bisection (GtsWGraph *wg,guint n,guint ntry,guint mmax,guint nmin,gfloat imbalance);
Calls gts_graph_bisection_new() recursively in order to obtain a 2^n partition of wg.
wg : | a GtsWGraph. |
n : | the number of bisection levels. |
ntry : | the number of tries for the graph growing algorithm. |
mmax : | the number of unsucessful moves for the refinement algorithm. |
nmin : | the minimum number of nodes of the coarsest graph. |
imbalance : | the maximum relative imbalance allowed between the weights of both halves of the partition. |
Returns : | a list of 2^n new GtsGraph representing the partition. |
void gts_graph_bisection_destroy (GtsGraphBisection *bg,gboolean destroy_graphs);
Frees all the memory allocated for bg. If destroy_graphs is TRUE the graphs created by bg are destroyed.
bg : | |
destroy_graphs : | controls graph destruction. |
GSList * gts_graph_bubble_partition (GtsGraph *g,guint np,guint niter, GtsFunc step_info,gpointer data);
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 niter.
If not NULL step_info is called after each iteration on the seeds positions passing the partition (a GSList) as argument.
g : | a GtsGraph. |
np : | number of partitions. |
niter : | the maximum number of iterations. |
step_info : | a GtsFunc or NULL. |
data : | user data to pass to step_info. |
Returns : | a list of np new GtsGraph representing the partition. |
guint gts_graph_partition_edges_cut (GSList *partition);
partition : | a list of GtsGraph representing a partition. |
Returns : | the number of edges cut by the partition. |
gfloat gts_graph_partition_balance (GSList *partition);
partition : | a list of GtsGraph representing a partition. |
Returns : | the difference between the maximum and the minimum weight of the graphs in partition. |
GSList * gts_graph_partition_clone (GSList *partition);
partition : | a list of GtsGraph representing a partition. |
Returns : | a new partition clone of partition (i.e. a list of new graphs clones of the graphs in partition). |
void gts_graph_partition_print_stats (GSList *partition,FILE *fp);
Writes to fp a summary of the properties of partition.
partition : | a list of GtsGraph representing a partition. |
fp : | a file pointer. |
gfloat gts_graph_partition_edges_cut_weight (GSList *partition);
partition : | a list of GtsGraph representing a partition. |
Returns : | the total weight of the edges cut by the partition. |
void gts_graph_partition_destroy (GSList *partition);
Destroys all the graphs in partition and frees partition.
partition : | a list of GtsGraph representing a partition. |
<<< Progressive graph |