Graph partitioning

GtsGraphBisection

typedef struct {
  GtsGraph * g;
  GtsGraph * g1;
  GtsGraph * g2;
  GHashTable * bg1;
  GHashTable * bg2;
} GtsGraphBisection;

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

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.

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.

gts_graph_bisection_check ()

gboolean    gts_graph_bisection_check       (GtsGraphBisection *bg);

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

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.

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.

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.

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.

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.

gts_graph_edges_cut ()

guint       gts_graph_edges_cut             (GtsGraph *g);

gts_graph_edges_cut_weight ()

gfloat      gts_graph_edges_cut_weight      (GtsGraph *g);

gts_graph_partition_edges_cut ()

guint       gts_graph_partition_edges_cut   (GSList *partition);

gts_graph_partition_balance ()

gfloat      gts_graph_partition_balance     (GSList *partition);

gts_graph_partition_clone ()

GSList*     gts_graph_partition_clone       (GSList *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.

gts_graph_partition_edges_cut_weight ()

gfloat      gts_graph_partition_edges_cut_weight
                                            (GSList *partition);

gts_graph_partition_destroy ()

void        gts_graph_partition_destroy     (GSList *partition);

Destroys all the graphs in partition and frees partition.