1 /* GTS - Library for the manipulation of triangulated surfaces
2 * Copyright (C) 1999 Stéphane Popinet
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Library General Public License for more details.
14 * You should have received a copy of the GNU Library General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
29 * gts_graph_partition_edges_cut:
30 * @partition: a list of @GtsGraph representing a partition.
32 * Returns: the number of edges cut by the partition.
34 guint
gts_graph_partition_edges_cut (GSList
* partition
)
39 cuts
+= gts_graph_edges_cut (partition
->data
);
40 partition
= partition
->next
;
47 * gts_graph_partition_edges_cut_weight:
48 * @partition: a list of @GtsGraph representing a partition.
50 * Returns: the total weight of the edges cut by the partition.
52 gfloat
gts_graph_partition_edges_cut_weight (GSList
* partition
)
57 weight
+= gts_graph_edges_cut_weight (partition
->data
);
58 partition
= partition
->next
;
65 * gts_graph_partition_print_stats:
66 * @partition: a list of @GtsGraph representing a partition.
67 * @fp: a file pointer.
69 * Writes to @fp a summary of the properties of @partition.
71 void gts_graph_partition_print_stats (GSList
* partition
,
77 g_return_if_fail (partition
!= NULL
);
78 g_return_if_fail (fp
!= NULL
);
80 gts_range_init (&weight
);
83 gts_range_add_value (&weight
, gts_graph_weight (i
->data
));
86 gts_range_update (&weight
);
90 "# edge cuts: %5d edge cuts weight: %5g\n"
92 g_slist_length (partition
),
93 gts_graph_partition_edges_cut (partition
),
94 gts_graph_partition_edges_cut_weight (partition
));
95 gts_range_print (&weight
, fp
);
100 * gts_graph_partition_balance:
101 * @partition: a list of @GtsGraph representing a partition.
103 * Returns: the difference between the maximum and the minimum weight
104 * of the graphs in @partition.
106 gfloat
gts_graph_partition_balance (GSList
* partition
)
108 gfloat wmin
= G_MAXFLOAT
;
109 gfloat wmax
= - G_MAXFLOAT
;
111 g_return_val_if_fail (partition
!= NULL
, 0.);
114 gfloat weight
= gts_graph_weight (partition
->data
);
119 partition
= partition
->next
;
125 * gts_graph_partition_clone:
126 * @partition: a list of @GtsGraph representing a partition.
128 * Returns: a new partition clone of @partition (i.e. a list of new
129 * graphs clones of the graphs in @partition).
131 GSList
* gts_graph_partition_clone (GSList
* partition
)
133 GSList
* cparts
= NULL
;
137 g_slist_prepend (cparts
,
138 gts_object_clone (GTS_OBJECT (partition
->data
)));
139 partition
= partition
->next
;
145 * gts_graph_partition_destroy:
146 * @partition: a list of @GtsGraph representing a partition.
148 * Destroys all the graphs in @partition and frees @partition.
150 void gts_graph_partition_destroy (GSList
* partition
)
152 GSList
* i
= partition
;
155 gts_object_destroy (GTS_OBJECT (i
->data
));
158 g_slist_free (partition
);
161 static void find_smallest_degree (GtsGNode
* n
, gpointer
* data
)
163 GtsGNode
** nmin
= data
[0];
164 GtsGraph
* g
= data
[1];
165 guint
* min
= data
[2];
166 guint degree
= gts_gnode_degree (n
, g
);
174 static gint
graph_comp_weight (GtsGraph
* g1
, GtsGraph
* g2
)
176 if (gts_graph_weight (g1
) > gts_graph_weight (g2
))
181 static void partition_update (GSList
* list
, GtsGraph
* g
)
186 gboolean reinit
= TRUE
;
188 /* initialize traversals */
191 GtsGNode
* seed
= GTS_OBJECT (i
->data
)->reserved
;
192 GTS_OBJECT (seed
)->reserved
=
193 gts_graph_traverse_new (g
, seed
, GTS_BREADTH_FIRST
, reinit
);
198 size_heap
= gts_heap_new ((GCompareFunc
) graph_comp_weight
);
201 gts_heap_insert (size_heap
, i
->data
);
204 while ((g1
= gts_heap_remove_top (size_heap
))) {
205 GtsGraphTraverse
* t
= GTS_OBJECT (GTS_OBJECT (g1
)->reserved
)->reserved
;
206 GtsGNode
* n
= gts_graph_traverse_next (t
);
208 gts_container_add (GTS_CONTAINER (g1
), GTS_CONTAINEE (n
));
209 gts_heap_insert (size_heap
, g1
);
212 gts_heap_destroy (size_heap
);
214 /* destroy traversals */
217 GtsGNode
* seed
= GTS_OBJECT (i
->data
)->reserved
;
218 gts_graph_traverse_destroy (GTS_OBJECT (seed
)->reserved
);
219 GTS_OBJECT (seed
)->reserved
= NULL
;
224 static void better_seed (GtsGNode
* n
, gpointer
* data
)
226 guint
* sum
= data
[0];
227 GtsGNode
** seed
= data
[1];
228 GtsGraph
* g
= data
[2];
229 guint sum1
= gts_graph_distance_sum (g
, n
);
237 static GtsGNode
* graph_new_seed (GtsGraph
* g
, GtsGNode
* seed
)
239 guint sum
= gts_graph_distance_sum (g
, seed
);
241 GtsGNode
* new_seed
= seed
;
246 gts_gnode_foreach_neighbor (seed
, g
, (GtsFunc
) better_seed
, data
);
252 * gts_graph_bubble_partition:
254 * @np: number of partitions.
255 * @niter: the maximum number of iterations.
256 * @step_info: a #GtsFunc or %NULL.
257 * @data: user data to pass to @step_info.
259 * An implementation of the "bubble partitioning algorithm" of
260 * Diekmann, Preis, Schlimbach and Walshaw (2000). The maximum number
261 * of iteration on the positions of the graph growing seeds is
262 * controlled by @niter.
264 * If not %NULL @step_info is called after each iteration on the seeds
265 * positions passing the partition (a GSList) as argument.
267 * Returns: a list of @np new #GtsGraph representing the partition.
269 GSList
* gts_graph_bubble_partition (GtsGraph
* g
,
275 GSList
* list
= NULL
, * seeds
= NULL
;
276 GtsGNode
* seed
= NULL
;
277 guint min
= G_MAXINT
/2 - 1;
280 gboolean changed
= TRUE
;
282 g_return_val_if_fail (g
!= NULL
, NULL
);
283 g_return_val_if_fail (np
> 0, NULL
);
288 gts_container_foreach (GTS_CONTAINER (g
),
289 (GtsFunc
) find_smallest_degree
,
294 g1
= GTS_GRAPH (gts_object_new (GTS_OBJECT (g
)->klass
));
295 gts_container_add (GTS_CONTAINER (g1
), GTS_CONTAINEE (seed
));
296 list
= g_slist_prepend (list
, g1
);
297 GTS_OBJECT (g1
)->reserved
= seed
;
298 seeds
= g_slist_prepend (seeds
, seed
);
301 if ((seed
= gts_graph_farthest (g
, seeds
))) {
302 g1
= GTS_GRAPH (gts_object_new (GTS_OBJECT (g
)->klass
));
303 gts_container_add (GTS_CONTAINER (g1
), GTS_CONTAINEE (seed
));
304 list
= g_slist_prepend (list
, g1
);
305 GTS_OBJECT (g1
)->reserved
= seed
;
306 seeds
= g_slist_prepend (seeds
, seed
);
308 g_slist_free (seeds
);
310 partition_update (list
, g
);
312 while (changed
&& niter
--) {
318 GtsGraph
* g1
= i
->data
;
319 GtsGNode
* seed
= GTS_OBJECT (g1
)->reserved
;
320 GtsGNode
* new_seed
= graph_new_seed (g1
, seed
);
321 if (new_seed
!= seed
) {
323 GTS_OBJECT (g1
)->reserved
= new_seed
;
331 GtsGraph
* g1
= i
->data
;
332 GtsGNode
* seed
= GTS_OBJECT (g1
)->reserved
;
334 gts_object_destroy (GTS_OBJECT (g1
));
335 i
->data
= g1
= GTS_GRAPH (gts_object_new (GTS_OBJECT (g
)->klass
));
336 gts_container_add (GTS_CONTAINER (g1
), GTS_CONTAINEE (seed
));
337 GTS_OBJECT (g1
)->reserved
= seed
;
340 partition_update (list
, g
);
342 (* step_info
) (list
, data
);
345 g_slist_foreach (list
, (GFunc
) gts_object_reset_reserved
, NULL
);
349 /* Graph bisection */
351 static gdouble
node_cost (GtsGNode
* n
, gpointer
* data
)
353 GtsGraph
* g
= data
[0];
354 GtsGraph
* g1
= data
[1];
355 GSList
* i
= GTS_SLIST_CONTAINER (n
)->items
;
359 GtsGEdge
* e
= i
->data
;
360 GtsGNode
* n1
= GTS_GNODE_NEIGHBOR (n
, e
);
362 if (gts_containee_is_contained (GTS_CONTAINEE (n1
), GTS_CONTAINER (g
))) {
363 if (gts_containee_is_contained (GTS_CONTAINEE (n1
), GTS_CONTAINER (g1
)))
364 cost
-= gts_gedge_weight (e
);
366 cost
+= gts_gedge_weight (e
);
374 static void add_neighbor (GtsGNode
* n
, GtsEHeap
* heap
)
376 if (GTS_OBJECT (n
)->reserved
== n
)
378 if (GTS_OBJECT (n
)->reserved
)
379 gts_eheap_remove (heap
, GTS_OBJECT (n
)->reserved
);
380 GTS_OBJECT (n
)->reserved
= gts_eheap_insert (heap
, n
);
383 static void add_unused (GtsGNode
* n
, GtsGraph
* g2
)
385 if (GTS_OBJECT (n
)->reserved
)
386 GTS_OBJECT (n
)->reserved
= NULL
;
388 gts_container_add (GTS_CONTAINER (g2
), GTS_CONTAINEE (n
));
391 static gdouble
degree_cost (GtsGNode
* n
, GtsGraph
* g
)
393 return gts_gnode_degree (n
, g
);
396 static void add_seed (GtsGNode
* n
, GtsEHeap
* heap
)
398 gts_eheap_insert (heap
, n
);
401 static void boundary_node1 (GtsGNode
* n
, GtsGraphBisection
* bg
)
403 GSList
* i
= GTS_SLIST_CONTAINER (n
)->items
;
406 GtsGNode
* n1
= GTS_GNODE_NEIGHBOR (n
, i
->data
);
407 if (gts_containee_is_contained (GTS_CONTAINEE (n1
),
408 GTS_CONTAINER (bg
->g2
))) {
409 g_hash_table_insert (bg
->bg1
, n
, n1
);
416 static void boundary_node2 (GtsGNode
* n
, GtsGraphBisection
* bg
)
418 GSList
* i
= GTS_SLIST_CONTAINER (n
)->items
;
421 GtsGNode
* n1
= GTS_GNODE_NEIGHBOR (n
, i
->data
);
422 if (gts_containee_is_contained (GTS_CONTAINEE (n1
),
423 GTS_CONTAINER (bg
->g1
))) {
424 g_hash_table_insert (bg
->bg2
, n
, n1
);
431 static void check_bg (GtsGNode
* n
, gpointer
* data
)
433 GHashTable
* bg
= data
[0];
434 GtsGraph
* g
= data
[1];
435 gboolean
* ok
= data
[2];
436 guint
* nb
= data
[3];
437 guint nn
= gts_gnode_degree (n
, g
);
441 if ((nn
> 0 && !g_hash_table_lookup (bg
, n
)) ||
442 (nn
== 0 && g_hash_table_lookup (bg
, n
))) {
443 g_warning ("nn: %d lookup: %p\n",
444 nn
, g_hash_table_lookup (bg
, n
));
450 * gts_graph_bisection_check:
451 * @bg: a #GtsGraphBisection.
453 * Checks that the boundary of @bg is correctly defined (used for
454 * debugging purposes).
456 * Returns: %TRUE if @bg is ok, %FALSE otherwise.
458 gboolean
gts_graph_bisection_check (GtsGraphBisection
* bg
)
464 g_return_val_if_fail (bg
!= NULL
, FALSE
);
471 gts_container_foreach (GTS_CONTAINER (bg
->g1
), (GtsFunc
) check_bg
, data
);
472 g_return_val_if_fail (g_hash_table_size (bg
->bg1
) == nb
, FALSE
);
477 gts_container_foreach (GTS_CONTAINER (bg
->g2
), (GtsFunc
) check_bg
, data
);
478 g_return_val_if_fail (g_hash_table_size (bg
->bg2
) == nb
, FALSE
);
484 * gts_graph_ggg_bisection:
486 * @ntry: the number of randomly selected initial seeds.
488 * An implementation of the "Greedy Graph Growing" algorithm of
489 * Karypis and Kumar (1997).
491 * @ntry randomly chosen seeds are used and the best partition is retained.
493 * Returns: a new #GtsGraphBisection of @g.
495 GtsGraphBisection
* gts_graph_ggg_bisection (GtsGraph
* g
, guint ntry
)
497 gfloat size
, bestcost
= G_MAXFLOAT
, smin
;
498 GtsGraph
* bestg1
= NULL
, * bestg2
= NULL
;
499 gboolean balanced
= FALSE
;
500 GtsEHeap
* degree_heap
;
502 GtsGraphBisection
* bg
;
504 g_return_val_if_fail (g
!= NULL
, NULL
);
506 bg
= g_malloc (sizeof (GtsGraphBisection
));
509 size
= gts_graph_weight (g
)/2.;
512 degree_heap
= gts_eheap_new ((GtsKeyFunc
) degree_cost
, g
);
513 gts_eheap_freeze (degree_heap
);
514 gts_container_foreach (GTS_CONTAINER (g
), (GtsFunc
) add_seed
, degree_heap
);
515 gts_eheap_thaw (degree_heap
);
517 while (ntry
&& ((seed
= gts_eheap_remove_top (degree_heap
, NULL
)))) {
524 g1
= gts_graph_new (GTS_GRAPH_CLASS (GTS_OBJECT (g
)->klass
),
525 g
->node_class
, g
->edge_class
);
526 g2
= gts_graph_new (GTS_GRAPH_CLASS (GTS_OBJECT (g
)->klass
),
527 g
->node_class
, g
->edge_class
);
531 heap
= gts_eheap_new ((GtsKeyFunc
) node_cost
, data
);
533 gts_container_add (GTS_CONTAINER (g1
), GTS_CONTAINEE (seed
));
534 GTS_OBJECT (seed
)->reserved
= seed
;
535 gts_gnode_foreach_neighbor (seed
, g
, (GtsFunc
) add_neighbor
, heap
);
537 while ((n
= gts_eheap_remove_top (heap
, &cost
)))
538 if (gts_graph_weight (g1
) + gts_gnode_weight (n
) <= size
) {
539 gts_container_add (GTS_CONTAINER (g1
), GTS_CONTAINEE (n
));
540 GTS_OBJECT (n
)->reserved
= n
;
541 gts_gnode_foreach_neighbor (n
, g
, (GtsFunc
) add_neighbor
, heap
);
544 GTS_OBJECT (n
)->reserved
= NULL
;
545 gts_eheap_destroy (heap
);
547 gts_container_foreach (GTS_CONTAINER (g
), (GtsFunc
) add_unused
, g2
);
549 cost
= gts_graph_edges_cut_weight (g1
);
551 (!balanced
&& gts_graph_weight (g1
) >= smin
) ||
552 (cost
< bestcost
&& gts_graph_weight (g1
) >= smin
)) {
556 gts_object_destroy (GTS_OBJECT (bestg1
));
558 gts_object_destroy (GTS_OBJECT (bestg2
));
561 if (gts_graph_weight (g1
) >= smin
)
565 gts_object_destroy (GTS_OBJECT (g1
));
566 gts_object_destroy (GTS_OBJECT (g2
));
571 gts_eheap_destroy (degree_heap
);
574 fprintf (stderr
, "bestcost: %5g g1: %5g|%5d g2: %5g|%5d\n",
576 gts_graph_weight (bestg1
),
577 gts_container_size (GTS_CONTAINER (bestg1
)),
578 gts_graph_weight (bestg2
),
579 gts_container_size (GTS_CONTAINER (bestg2
)));
582 g_assert (bestg1
!= NULL
);
584 g_assert (bestg2
!= NULL
);
588 bg
->bg1
= g_hash_table_new (NULL
, NULL
);
589 gts_container_foreach (GTS_CONTAINER (bg
->g1
), (GtsFunc
) boundary_node1
, bg
);
590 bg
->bg2
= g_hash_table_new (NULL
, NULL
);
591 gts_container_foreach (GTS_CONTAINER (bg
->g2
), (GtsFunc
) boundary_node2
, bg
);
597 * gts_graph_bfgg_bisection:
599 * @ntry: the number of randomly selected initial seeds.
601 * An implementation of a "Breadth-First Graph Growing" algorithm.
603 * @ntry randomly chosen seeds are used and the best partition is retained.
605 * Returns: a new #GtsGraphBisection of @g.
607 GtsGraphBisection
* gts_graph_bfgg_bisection (GtsGraph
* g
, guint ntry
)
609 gfloat size
, bestcost
= G_MAXFLOAT
, smin
;
610 GtsGraph
* bestg1
= NULL
, * bestg2
= NULL
;
611 GtsEHeap
* degree_heap
;
613 GtsGraphBisection
* bg
;
615 g_return_val_if_fail (g
!= NULL
, NULL
);
617 bg
= g_malloc (sizeof (GtsGraphBisection
));
620 size
= gts_graph_weight (g
)/2.;
623 degree_heap
= gts_eheap_new ((GtsKeyFunc
) degree_cost
, g
);
624 gts_eheap_freeze (degree_heap
);
625 gts_container_foreach (GTS_CONTAINER (g
), (GtsFunc
) add_seed
, degree_heap
);
626 gts_eheap_thaw (degree_heap
);
628 while (ntry
&& ((seed
= gts_eheap_remove_top (degree_heap
, NULL
)))) {
632 GtsGraphTraverse
* t
= gts_graph_traverse_new (g
, seed
,
633 GTS_BREADTH_FIRST
, TRUE
);
635 g1
= gts_graph_new (GTS_GRAPH_CLASS (GTS_OBJECT (g
)->klass
),
636 g
->node_class
, g
->edge_class
);
637 g2
= gts_graph_new (GTS_GRAPH_CLASS (GTS_OBJECT (g
)->klass
),
638 g
->node_class
, g
->edge_class
);
640 while ((n
= gts_graph_traverse_next (t
)))
641 if (gts_graph_weight (g1
) + gts_gnode_weight (n
) <= size
) {
642 gts_container_add (GTS_CONTAINER (g1
), GTS_CONTAINEE (n
));
643 GTS_OBJECT (n
)->reserved
= n
;
645 gts_graph_traverse_destroy (t
);
647 gts_container_foreach (GTS_CONTAINER (g
), (GtsFunc
) add_unused
, g2
);
649 cost
= gts_graph_edges_cut_weight (g1
);
650 if (!bestg1
|| (cost
< bestcost
&& gts_graph_weight (g1
) >= smin
)) {
654 gts_object_destroy (GTS_OBJECT (bestg1
));
656 gts_object_destroy (GTS_OBJECT (bestg2
));
661 gts_object_destroy (GTS_OBJECT (g1
));
662 gts_object_destroy (GTS_OBJECT (g2
));
667 gts_eheap_destroy (degree_heap
);
670 fprintf (stderr
, "bestcost: %5g g1: %5g|%5d g2: %5g|%5d\n",
672 gts_graph_weight (bestg1
),
673 gts_container_size (GTS_CONTAINER (bestg1
)),
674 gts_graph_weight (bestg2
),
675 gts_container_size (GTS_CONTAINER (bestg2
)));
682 bg
->bg1
= g_hash_table_new (NULL
, NULL
);
683 gts_container_foreach (GTS_CONTAINER (bg
->g1
), (GtsFunc
) boundary_node1
, bg
);
684 bg
->bg2
= g_hash_table_new (NULL
, NULL
);
685 gts_container_foreach (GTS_CONTAINER (bg
->g2
), (GtsFunc
) boundary_node2
, bg
);
690 static gdouble
node_move_cost1 (GtsGNode
* n
, GtsGraphBisection
* bg
)
692 return gts_gnode_move_cost (n
, bg
->g1
, bg
->g2
);
695 static gdouble
node_move_cost2 (GtsGNode
* n
, GtsGraphBisection
* bg
)
697 return gts_gnode_move_cost (n
, bg
->g2
, bg
->g1
);
700 static void build_heap (GtsGNode
* n
, GtsEHeap
* heap
)
702 GTS_OBJECT (n
)->reserved
= gts_eheap_insert (heap
, n
);
706 * gts_graph_bisection_kl_refine:
707 * @bg: a #GtsGraphBisection.
708 * @mmax: the maximum number of unsuccessful successive moves.
710 * An implementation of the simplified Kernighan-Lin algorithm for
711 * graph bisection refinement as described in Karypis and Kumar
714 * The algorithm stops if @mmax consecutive modes do not lead to a
715 * decrease in the number of edges cut. This last @mmax moves are
718 * Returns: the decrease in the weight of the edges cut by the bisection.
720 gdouble
gts_graph_bisection_kl_refine (GtsGraphBisection
* bg
,
727 gdouble bestcost
= 0., totalcost
= 0., best_balance
;
729 g_return_val_if_fail (bg
!= NULL
, 0.);
730 g_return_val_if_fail (mmax
> 0, 0.);
732 h1
= gts_eheap_new ((GtsKeyFunc
) node_move_cost1
, bg
);
733 gts_eheap_freeze (h1
);
734 gts_container_foreach (GTS_CONTAINER (bg
->g1
), (GtsFunc
) build_heap
, h1
);
737 h2
= gts_eheap_new ((GtsKeyFunc
) node_move_cost2
, bg
);
738 gts_eheap_freeze (h2
);
739 gts_container_foreach (GTS_CONTAINER (bg
->g2
), (GtsFunc
) build_heap
, h2
);
742 moves
= g_malloc (sizeof (GtsGNode
*)*mmax
);
743 best_balance
= fabs (gts_graph_weight (bg
->g1
) - gts_graph_weight (bg
->g2
));
749 if (gts_graph_weight (bg
->g1
) > gts_graph_weight (bg
->g2
)) {
750 n
= gts_eheap_remove_top (h1
, &cost
);
755 n
= gts_eheap_remove_top (h2
, &cost
);
762 GTS_OBJECT (n
)->reserved
= NULL
;
763 gts_container_add (GTS_CONTAINER (g2
), GTS_CONTAINEE (n
));
764 gts_container_remove (GTS_CONTAINER (g1
), GTS_CONTAINEE (n
));
767 if (totalcost
< bestcost
) {
768 bestcost
= totalcost
;
771 else if (totalcost
== bestcost
) {
772 gdouble balance
= fabs (gts_graph_weight (g1
) - gts_graph_weight (g2
));
774 if (balance
< best_balance
) {
775 best_balance
= balance
;
782 i
= GTS_SLIST_CONTAINER (n
)->items
;
784 GtsGNode
* n1
= GTS_GNODE_NEIGHBOR (n
, i
->data
);
785 if (GTS_OBJECT (n1
)->reserved
&&
786 gts_containee_is_contained (GTS_CONTAINEE (n1
),
787 GTS_CONTAINER (bg
->g
))) {
789 gts_containee_is_contained (GTS_CONTAINEE (n1
),
790 GTS_CONTAINER (bg
->g1
)) ? h1
: h2
;
791 gts_eheap_remove (h
, GTS_OBJECT (n1
)->reserved
);
792 GTS_OBJECT (n1
)->reserved
= gts_eheap_insert (h
, n1
);
797 } while (n
&& nm
< mmax
);
799 gts_eheap_foreach (h1
, (GFunc
) gts_object_reset_reserved
, NULL
);
800 gts_eheap_foreach (h2
, (GFunc
) gts_object_reset_reserved
, NULL
);
801 gts_eheap_destroy (h1
);
802 gts_eheap_destroy (h2
);
804 /* undo last nm moves */
805 for (i
= 0; i
< nm
; i
++) {
806 GtsGNode
* n
= moves
[i
];
808 gts_containee_is_contained (GTS_CONTAINEE (n
),
809 GTS_CONTAINER (bg
->g1
)) ? bg
->g1
: bg
->g2
;
810 GtsGraph
* g2
= g1
== bg
->g1
? bg
->g2
: bg
->g1
;
812 gts_container_add (GTS_CONTAINER (g2
), GTS_CONTAINEE (n
));
813 gts_container_remove (GTS_CONTAINER (g1
), GTS_CONTAINEE (n
));
820 static void build_bheap (GtsGNode
* n
, GtsGNode
* n1
, GtsEHeap
* heap
)
822 GTS_OBJECT (n
)->reserved
= gts_eheap_insert (heap
, n
);
825 static void update_neighbors (GtsGNode
* n
, GtsGraphBisection
* bg
,
826 GtsEHeap
* h1
, GtsEHeap
* h2
)
830 i
= GTS_SLIST_CONTAINER (n
)->items
;
832 GtsGNode
* n1
= GTS_GNODE_NEIGHBOR (n
, i
->data
);
833 if (gts_containee_is_contained (GTS_CONTAINEE (n1
),
834 GTS_CONTAINER (bg
->g
))) {
836 GtsGraph
/* * g1,*/ * g2
;
839 if (gts_containee_is_contained (GTS_CONTAINEE (n1
),
840 GTS_CONTAINER (bg
->g1
))) {
852 g_hash_table_remove (bg1
, n1
);
853 if (h
&& GTS_OBJECT (n1
)->reserved
&& GTS_OBJECT (n1
)->reserved
!= n1
) {
854 gts_eheap_remove (h
, GTS_OBJECT (n1
)->reserved
);
855 GTS_OBJECT (n1
)->reserved
= NULL
;
857 if (gts_gnode_degree (n1
, g2
)) {
858 g_hash_table_insert (bg1
, n1
, n1
);
859 if (h
&& GTS_OBJECT (n1
)->reserved
!= n1
)
860 GTS_OBJECT (n1
)->reserved
= gts_eheap_insert (h
, n1
);
868 * gts_graph_bisection_bkl_refine:
869 * @bg: a #GtsGraphBisection.
870 * @mmax: the maximum number of unsuccessful successive moves.
871 * @imbalance: the maximum relative imbalance allowed between the
872 * weights of both halves of the partition.
874 * An implementation of the simplified boundary Kernighan-Lin
875 * algorithm for graph bisection refinement as described in Karypis
878 * The algorithm stops if @mmax consecutive modes do not lead to a
879 * decrease in the number of edges cut. This last @mmax moves are
882 * Returns: the decrease in the weight of the edges cut by the bisection.
884 gdouble
gts_graph_bisection_bkl_refine (GtsGraphBisection
* bg
,
892 gdouble bestcost
= 0., totalcost
= 0., best_balance
;
893 gboolean balanced
= FALSE
;
895 g_return_val_if_fail (bg
!= NULL
, 0.);
896 g_return_val_if_fail (mmax
> 0, 0.);
897 g_return_val_if_fail (imbalance
>= 0. && imbalance
<= 1., 0.);
899 h1
= gts_eheap_new ((GtsKeyFunc
) node_move_cost1
, bg
);
900 gts_eheap_freeze (h1
);
901 g_hash_table_foreach (bg
->bg1
, (GHFunc
) build_bheap
, h1
);
904 h2
= gts_eheap_new ((GtsKeyFunc
) node_move_cost2
, bg
);
905 gts_eheap_freeze (h2
);
906 g_hash_table_foreach (bg
->bg2
, (GHFunc
) build_bheap
, h2
);
909 moves
= g_malloc (sizeof (GtsGNode
*)*mmax
);
910 imbalance
*= gts_graph_weight (bg
->g
);
911 best_balance
= fabs (gts_graph_weight (bg
->g1
) - gts_graph_weight (bg
->g2
));
912 if (best_balance
<= imbalance
)
917 GHashTable
* bg1
, * bg2
;
920 if (gts_graph_weight (bg
->g1
) > gts_graph_weight (bg
->g2
)) {
921 n
= gts_eheap_remove_top (h1
, &cost
);
928 n
= gts_eheap_remove_top (h2
, &cost
);
937 GTS_OBJECT (n
)->reserved
= n
;
938 gts_container_add (GTS_CONTAINER (g2
), GTS_CONTAINEE (n
));
939 gts_container_remove (GTS_CONTAINER (g1
), GTS_CONTAINEE (n
));
940 g_hash_table_remove (bg1
, n
);
941 if (gts_gnode_degree (n
, g1
))
942 g_hash_table_insert (bg2
, n
, n
);
944 update_neighbors (n
, bg
, h1
, h2
);
947 balance
= fabs (gts_graph_weight (g1
) - gts_graph_weight (g2
));
949 if (!balanced
&& balance
<= imbalance
) {
950 bestcost
= totalcost
;
951 best_balance
= balance
;
955 else if (totalcost
< bestcost
&&
956 (balance
< best_balance
|| balance
<= imbalance
)) {
957 bestcost
= totalcost
;
958 best_balance
= balance
;
961 else if (totalcost
== bestcost
&& balance
< best_balance
) {
962 best_balance
= balance
;
968 } while (n
&& nm
< mmax
);
970 gts_container_foreach (GTS_CONTAINER (bg
->g
),
971 (GtsFunc
) gts_object_reset_reserved
, NULL
);
972 gts_eheap_destroy (h1
);
973 gts_eheap_destroy (h2
);
975 /* undo last nm moves */
976 for (i
= 0; i
< nm
; i
++) {
977 GtsGNode
* n
= moves
[i
];
979 GHashTable
* bg1
, * bg2
;
981 if (gts_containee_is_contained (GTS_CONTAINEE (n
),
982 GTS_CONTAINER (bg
->g1
))) {
995 gts_container_add (GTS_CONTAINER (g2
), GTS_CONTAINEE (n
));
996 gts_container_remove (GTS_CONTAINER (g1
), GTS_CONTAINEE (n
));
997 g_hash_table_remove (bg1
, n
);
998 if (gts_gnode_degree (n
, g1
))
999 g_hash_table_insert (bg2
, n
, n
);
1001 update_neighbors (n
, bg
, NULL
, NULL
);
1008 /* Multilevel partitioning */
1010 static void bisection_children (GtsGNodeSplit
* ns
, GtsGraphBisection
* bg
)
1014 GtsGNode
* n1
= GTS_GNODE_SPLIT_N1 (ns
);
1015 GtsGNode
* n2
= GTS_GNODE_SPLIT_N2 (ns
);
1017 if (gts_containee_is_contained (GTS_CONTAINEE (ns
->n
),
1018 GTS_CONTAINER (bg
->g1
))) {
1029 gts_allow_floating_gnodes
= TRUE
;
1030 gts_container_remove (GTS_CONTAINER (g
), GTS_CONTAINEE (ns
->n
));
1031 gts_allow_floating_gnodes
= FALSE
;
1032 gts_container_add (GTS_CONTAINER (g
), GTS_CONTAINEE (n1
));
1033 gts_container_add (GTS_CONTAINER (g
), GTS_CONTAINEE (n2
));
1035 if (g_hash_table_lookup (bbg
, ns
->n
)) {
1036 g_hash_table_remove (bbg
, ns
->n
);
1037 if (gts_gnode_degree (n1
, g1
) > 0)
1038 g_hash_table_insert (bbg
, n1
, n1
);
1039 if (gts_gnode_degree (n2
, g1
) > 0)
1040 g_hash_table_insert (bbg
, n2
, n2
);
1045 * gts_graph_bisection_new:
1046 * @wg: a #GtsWGraph.
1047 * @ntry: the number of tries for the graph growing algorithm.
1048 * @mmax: the number of unsucessful moves for the refinement algorithm.
1049 * @nmin: the minimum number of nodes of the coarsest graph.
1050 * @imbalance: the maximum relative imbalance allowed between the
1051 * weights of both halves of the partition.
1053 * An implementation of a multilevel bisection algorithm as presented
1054 * in Karypis and Kumar (1997). A multilevel hierarchy of graphs is
1055 * created using the #GtsPGraph object. The bisection of the coarsest
1056 * graph is created using the gts_graph_ggg_bisection() function. The
1057 * graph is then uncoarsened using gts_pgraph_down() and at each level
1058 * the bisection is refined using gts_graph_bisection_bkl_refine().
1060 * Returns: a new #GtsGraphBisection of @wg.
1062 GtsGraphBisection
* gts_graph_bisection_new (GtsWGraph
* wg
,
1070 GtsGraphBisection
* bg
;
1073 g_return_val_if_fail (wg
!= NULL
, NULL
);
1076 pg
= gts_pgraph_new (gts_pgraph_class (), g
,
1077 gts_gnode_split_class (),
1078 gts_wgnode_class (),
1079 gts_wgedge_class (),
1082 bg
= gts_graph_ggg_bisection (g
, ntry
);
1084 fprintf (stderr
, "before size: %5d weight: %5g cuts: %5d cweight: %5g\n",
1085 gts_container_size (GTS_CONTAINER (bg
->g1
)),
1086 gts_graph_weight (bg
->g1
),
1087 gts_graph_edges_cut (bg
->g1
),
1088 gts_graph_edges_cut_weight (bg
->g1
));
1089 g_assert (gts_graph_bisection_check (bg
));
1091 while ((cost
= gts_graph_bisection_bkl_refine (bg
, mmax
, imbalance
))) {
1093 fprintf (stderr
, " cost: %g\n", cost
);
1094 g_assert (gts_graph_bisection_check (bg
));
1098 fprintf (stderr
, "after size: %5d weight: %5g cuts: %5d cweight: %5g\n",
1099 gts_container_size (GTS_CONTAINER (bg
->g1
)),
1100 gts_graph_weight (bg
->g1
),
1101 gts_graph_edges_cut (bg
->g1
),
1102 gts_graph_edges_cut_weight (bg
->g1
));
1104 while (gts_pgraph_down (pg
, (GtsFunc
) bisection_children
, bg
)) {
1106 fprintf (stderr
, "before size: %5d weight: %5g cuts: %5d cweight: %5g\n",
1107 gts_container_size (GTS_CONTAINER (bg
->g1
)),
1108 gts_graph_weight (bg
->g1
),
1109 gts_graph_edges_cut (bg
->g1
),
1110 gts_graph_edges_cut_weight (bg
->g1
));
1112 while ((cost
= gts_graph_bisection_bkl_refine (bg
, mmax
, imbalance
))) {
1114 fprintf (stderr
, " cost: %g\n", cost
);
1115 g_assert (gts_graph_bisection_check (bg
));
1119 fprintf (stderr
, "after size: %5d weight: %5g cuts: %5d cweight: %5g\n",
1120 gts_container_size (GTS_CONTAINER (bg
->g1
)),
1121 gts_graph_weight (bg
->g1
),
1122 gts_graph_edges_cut (bg
->g1
),
1123 gts_graph_edges_cut_weight (bg
->g1
));
1126 gts_object_destroy (GTS_OBJECT (pg
));
1132 * gts_graph_bisection_destroy:
1133 * @bg: a #GtsGraphBisection.
1134 * @destroy_graphs: controls graph destruction.
1136 * Frees all the memory allocated for @bg. If @destroy_graphs is %TRUE
1137 * the graphs created by @bg are destroyed.
1139 void gts_graph_bisection_destroy (GtsGraphBisection
* bg
,
1140 gboolean destroy_graphs
)
1142 g_return_if_fail (bg
!= NULL
);
1144 g_hash_table_destroy (bg
->bg1
);
1145 g_hash_table_destroy (bg
->bg2
);
1147 if (destroy_graphs
) {
1148 gts_object_destroy (GTS_OBJECT (bg
->g1
));
1149 gts_object_destroy (GTS_OBJECT (bg
->g2
));
1155 static void recursive_bisection (GtsWGraph
* wg
,
1164 *list
= g_slist_prepend (*list
, wg
);
1166 GtsGraphBisection
* bg
=
1167 gts_graph_bisection_new (wg
, ntry
, mmax
, nmin
, imbalance
);
1168 GtsGraph
* g1
= bg
->g1
;
1169 GtsGraph
* g2
= bg
->g2
;
1171 gts_object_destroy (GTS_OBJECT (wg
));
1172 gts_graph_bisection_destroy (bg
, FALSE
);
1173 recursive_bisection (GTS_WGRAPH (g1
), np
- 1, ntry
, mmax
, nmin
, imbalance
,
1175 recursive_bisection (GTS_WGRAPH (g2
), np
- 1, ntry
, mmax
, nmin
, imbalance
,
1181 * gts_graph_recursive_bisection:
1182 * @wg: a #GtsWGraph.
1183 * @n: the number of bisection levels.
1184 * @ntry: the number of tries for the graph growing algorithm.
1185 * @mmax: the number of unsucessful moves for the refinement algorithm.
1186 * @nmin: the minimum number of nodes of the coarsest graph.
1187 * @imbalance: the maximum relative imbalance allowed between the
1188 * weights of both halves of the partition.
1190 * Calls gts_graph_bisection_new() recursively in order to obtain a
1191 * 2^@n partition of @wg.
1193 * Returns: a list of 2^@n new #GtsGraph representing the partition.
1195 GSList
* gts_graph_recursive_bisection (GtsWGraph
* wg
,
1202 GtsGraphBisection
* bg
;
1203 GtsGraph
* g1
, * g2
;
1204 GSList
* list
= NULL
;
1206 g_return_val_if_fail (wg
!= NULL
, NULL
);
1207 g_return_val_if_fail (n
> 0, NULL
);
1209 bg
= gts_graph_bisection_new (wg
, ntry
, mmax
, nmin
, imbalance
);
1212 gts_graph_bisection_destroy (bg
, FALSE
);
1213 recursive_bisection (GTS_WGRAPH (g1
), n
- 1, ntry
, mmax
, nmin
, imbalance
,
1215 recursive_bisection (GTS_WGRAPH (g2
), n
- 1, ntry
, mmax
, nmin
, imbalance
,