Details
struct GtsGraphBisection
struct GtsGraphBisection {
GtsGraph * g;
GtsGraph * g1;
GtsGraph * g2;
GHashTable * bg1;
GHashTable * bg2;
}; |
gts_graph_bisection_new ()
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 ()
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 ()
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 ()
Checks that the boundary of bg is correctly defined (used for
debugging purposes).
gts_graph_bisection_kl_refine ()
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 ()
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.