/* GTS - Library for the manipulation of triangulated surfaces * Copyright (C) 1999 Stéphane Popinet * * This library is free software; you can redistribute it and/or * modify it under the terms of the GNU Library General Public * License as published by the Free Software Foundation; either * version 2 of the License, or (at your option) any later version. * * This library is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Library General Public License for more details. * * You should have received a copy of the GNU Library General Public * License along with this library; if not, write to the * Free Software Foundation, Inc., 59 Temple Place - Suite 330, * Boston, MA 02111-1307, USA. */ #include #include #include #ifdef HAVE_CONFIG_H # include "config.h" #endif #ifdef HAVE_GETOPT_H # include #endif /* HAVE_GETOPT_H */ #ifdef HAVE_UNISTD_H # include #endif /* HAVE_UNISTD_H */ #include "gts.h" static GtsColor default_face_color = { 1., 1., 1.}; static GtsColor random_color (void) { GtsColor c; c.r = rand ()/(gfloat) RAND_MAX; c.g = rand ()/(gfloat) RAND_MAX; c.b = rand ()/(gfloat) RAND_MAX; return c; } static GtsColor face_color (GtsObject * o) { return default_face_color; } static gint compare_line (GtsNGNode * n1, GtsNGNode * n2) { if (n1->id < n2->id) return -1; return 1; } static void create_heap (GtsGNode * n, GtsHeap * heap) { gts_heap_insert (heap, n); } int main (int argc, char * argv[]) { GtsSurface * s; GtsGraph * g; GtsFile * fp; guint np; guint nmin = 100; guint mmax = 50; guint ntry = 10; GSList * partition; int c = 0; gboolean verbose = FALSE; gfloat imbalance = 0.1; if (!setlocale (LC_ALL, "POSIX")) g_warning ("cannot set locale to POSIX"); /* parse options using getopt */ while (c != EOF) { #ifdef HAVE_GETOPT_LONG static struct option long_options[] = { {"help", no_argument, NULL, 'h'}, {"verbose", no_argument, NULL, 'v'}, {"try", required_argument, NULL, 't'}, {"mmax", required_argument, NULL, 'm'}, {"nmin", required_argument, NULL, 'n'}, {"imbalance", required_argument, NULL, 'i'}, { NULL } }; int option_index = 0; switch ((c = getopt_long (argc, argv, "hvt:m:n:i:", long_options, &option_index))) { #else /* not HAVE_GETOPT_LONG */ switch ((c = getopt (argc, argv, "hvt:m:n:i:"))) { #endif /* not HAVE_GETOPT_LONG */ case 'i': /* imbalance */ imbalance = atof (optarg); break; case 't': /* try */ ntry = atoi (optarg); break; case 'm': /* mmax */ mmax = atoi (optarg); break; case 'n': /* nmin */ nmin = atoi (optarg); break; case 'v': /* verbose */ verbose = TRUE; break; case 'h': /* help */ fprintf (stderr, "Usage: partition [OPTION] N < FILE\n" "Partition the graph defined by FILE into 2^N parts using recursive multilevel\n" "bisection.\n" "FILE can be either a GTS file or a GRAPH file (Jostle graph format).\n" "For GTS input the output is a OOGL (Geomview) description of the partitions.\n" "For GRAPH input the output is a graph partition (.ptn format) as defined in\n" "\"The Graph Partitioning Archive\" (http://www.gre.ac.uk/~c.walshaw/partition/).\n" "\n" " -t N --try=N number of tries for graph growing (default 10)\n" " -m N --mmax=N number of unsuccessful moves for Kernighan-Lin (default 50)\n" " -n N --nmin=N minimum number of nodes on coarsest graph (default 100)\n" " -i I --imbalance=I relative imbalance (default is 0.1)\n" " -v --verbose print statistics about the graph and partition\n" " -h --help display this help and exit\n" "\n" "Reports bugs to %s\n", GTS_MAINTAINER); return 0; /* success */ break; case '?': /* wrong options */ fprintf (stderr, "Try `partition --help' for more information.\n"); return 1; /* failure */ } } if (optind >= argc) { /* missing N */ fprintf (stderr, "partition: missing N\n" "Try `partition --help' for more information.\n"); return 1; /* failure */ } np = atoi (argv[optind]); s = gts_surface_new (gts_surface_class (), gts_face_class (), gts_edge_class (), gts_vertex_class ()); fp = gts_file_new (stdin); if (gts_surface_read (s, fp)) { GtsFile * fp1; gts_object_destroy (GTS_OBJECT (s)); s = NULL; rewind (stdin); fp1 = gts_file_new (stdin); g = gts_graph_new (GTS_GRAPH_CLASS (gts_wgraph_class ()), gts_gnode_class (), gts_gedge_class ()); if (gts_graph_read_jostle (g, fp1)) { fputs ("partition: file on standard input is neither a valid GTS file nor a valid GRAPH file\n", stderr); fprintf (stderr, "GTS stdin:%d:%d: %s\n", fp->line, fp->pos, fp->error); fprintf (stderr, "GRAPH stdin:%d:%d: %s\n", fp1->line, fp1->pos, fp1->error); return 1; /* failure */ } } else { g = gts_surface_graph_new (GTS_GRAPH_CLASS (gts_wgraph_class ()), s); if (verbose) gts_surface_print_stats (s, stderr); } if (verbose) gts_graph_print_stats (g, stderr); partition = gts_graph_recursive_bisection (GTS_WGRAPH (g), np, ntry, mmax, nmin, imbalance); if (verbose) gts_graph_partition_print_stats (partition, stderr); if (s) { GSList * i; printf ("LIST {\n"); GTS_OBJECT_CLASS (gts_face_class ())->color = face_color; i = partition; while (i) { GtsSurface * s1 = gts_surface_graph_surface (i->data, s); gts_surface_write_oogl_boundary (s1, stdout); default_face_color = random_color (); gts_surface_write_oogl (s1, stdout); gts_object_destroy (GTS_OBJECT (s1)); i = i->next; } printf ("}\n"); } else { GSList * i = partition; guint np = 0; GtsHeap * heap; GtsGNode * n; while (i) { GTS_OBJECT (i->data)->reserved = GUINT_TO_POINTER (np++); i = i->next; } heap = gts_heap_new ((GCompareFunc) compare_line); gts_container_foreach (GTS_CONTAINER (g), (GtsFunc) create_heap, heap); while ((n = gts_heap_remove_top (heap))) { GSList * j = partition; GtsGraph * own = NULL; while (j && !own) { if (gts_containee_is_contained (GTS_CONTAINEE (n), j->data)) own = j->data; j = j->next; } g_assert (own); printf ("%d\n", GPOINTER_TO_UINT (GTS_OBJECT (own)->reserved)); } gts_heap_destroy (heap); } return 0; }