Graph partitioning

Name

Graph partitioning -- 

Synopsis


#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);

Description

Details

struct GtsGraphBisection

struct GtsGraphBisection {

  GtsGraph * g;
  GtsGraph * g1;
  GtsGraph * g2;
  GHashTable * bg1;
  GHashTable * bg2;
};


gts_graph_bisection_new ()

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.


gts_graph_ggg_bisection ()

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.


gts_graph_bfgg_bisection ()

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.


gts_graph_bisection_check ()

gboolean    gts_graph_bisection_check       (GtsGraphBisection *bg);

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

bg :

a GtsGraphBisection.

Returns :

TRUE if bg is ok, FALSE otherwise.


gts_graph_bisection_kl_refine ()

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 :

a GtsGraphBisection.

mmax :

the maximum number of unsuccessful successive moves.

Returns :

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


gts_graph_bisection_bkl_refine ()

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 :

a GtsGraphBisection.

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.


gts_graph_recursive_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.


gts_graph_bisection_destroy ()

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 :

a GtsGraphBisection.

destroy_graphs :

controls graph destruction.


gts_graph_bubble_partition ()

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.


gts_graph_edges_cut ()

guint       gts_graph_edges_cut             (GtsGraph *g);

g :

Returns :


gts_graph_edges_cut_weight ()

gfloat      gts_graph_edges_cut_weight      (GtsGraph *g);

g :

Returns :


gts_graph_partition_edges_cut ()

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.


gts_graph_partition_balance ()

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.


gts_graph_partition_clone ()

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).


gts_graph_partition_print_stats ()

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.


gts_graph_partition_edges_cut_weight ()

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.


gts_graph_partition_destroy ()

void        gts_graph_partition_destroy     (GSList *partition);

Destroys all the graphs in partition and frees partition.

partition :

a list of GtsGraph representing a partition.