From tz4a@cs.virginia.edu Fri Sep 20 19:54:09 1996 Received: from virginia.edu (mars.itc.Virginia.EDU [128.143.2.9]) by cs.sunysb.edu (8.6.12/8.6.9) with SMTP id TAA24822 for ; Fri, 20 Sep 1996 19:54:06 -0400 Received: from mail.cs.virginia.edu by mail.virginia.edu id aa28804; 20 Sep 96 19:47 EDT Received: from mamba.cs.Virginia.EDU (mamba-fo.cs.Virginia.EDU [128.143.136.18]) by archive.cs.Virginia.EDU (8.7.5/8.7.3) with ESMTP id TAA20369 for ; Fri, 20 Sep 1996 19:47:57 -0400 (EDT) From: Tong-Tong Zhang Received: (from tz4a@localhost) by mamba.cs.Virginia.EDU (8.7.5/8.7.3) id TAA09976 for skiena@CS.SunySB.EDU; Fri, 20 Sep 1996 19:47:56 -0400 (EDT) Date: Fri, 20 Sep 1996 19:47:56 -0400 (EDT) Message-Id: <199609202347.TAA09976@mamba.cs.Virginia.EDU> X-Mailer: Mail User's Shell (7.2.5 10/14/92) To: skiena@cs.sunysb.edu Subject: Steiner Code Cont. Status: RO # To unbundle, sh this file echo calculations.c 1>&2 sed 's/^-//' >calculations.c <<'End of calculations.c' -/**********************************************************************/ -/* */ -/* (c) Copyright 1992, by Gabriel Robins */ -/* */ -/* UVa CS Department, Charlottesville, VA, CA 22903 (804) 982-2207 */ -/* */ -/* This code may be freely used for all non-commercial purposes. */ -/* All copies/portions of this code must contain this header. */ -/* */ -/**********************************************************************/ - -/**********************************************************************/ -/* Calculations.c */ -/**********************************************************************/ - -#include "geometry.h" - - -/**********************************************************************/ - -/*char *errorstrings[] = { - "***** Error: Storage allocation for %s\n", - "***** Error: Cannot open file %s\n", -};*/ - -extern void generate_steiner5(void); -extern void error(enum errors, char *); - -void multi_loop_stats(void) -{ -int i, j, old_gridsize, old_nop; - -old_gridsize = grid_size; -old_nop = number_of_points; - -for(i=3;i<=50;i++) - { - for(j=0;j<9;j++) - { - number_of_points = i; - grid_size = grid_sizes[j]; - loop_stats(); - } - print_separator(); - } - -grid_size = old_gridsize; -number_of_points = old_nop; - -} - -/**********************************************************************/ - -void loop_stats(void) -{ -int i, span_cost, stei_cost, mst_total, steiner_total; -float total_perf; - -/*printf("Seed = %u\n", (int) next); fflush(stdout);*/ - -mst_total = steiner_total = 0; -total_perf = 0.0; -for(i=0; i< number_of_iterations;i++) - { - if(choice !=2) do_randomize(); - - generate_MST3(number_of_points); - span_cost = mst_cost; - - mst_total = mst_total + span_cost; - generate_steiner5(); - stei_cost = mst_cost; /*steiner_cost[4];*/ - steiner_total = steiner_total + stei_cost; - - total_perf = total_perf + (float)( span_cost - stei_cost) / (float) span_cost; - -/* - if(((i % stats_how_often) == 0) || (i == number_of_iterations) - || (number_of_points >= 25)) - { - printf("(grid: %5d, %d pts, %d sets) Ave perf = %.4f\n", grid_size, - number_of_points, i, (float) total_perf / (float) i * 100); - fflush(stdout); - } - } - print_separator(); fflush(stdout); - -*/ - getchar(); - -} -} - -/**********************************************************************/ - -int max(int i, int j) { if (i > j) return(i); else return(j); } -int min(int i, int j) { if (i < j) return(i); else return(j); } -double fmax(double i, double j) { if (i > j) return(i); else return(j); } -double fmin(double i, double j) { if (i < j) return(i); else return(j); } -int sig(int i){ if (i>0) return(1); else if (i<0) return(-1); else return(0); } - -/*********************************************************************/ - -int generate_unique_identifier(void) -{ -return(unique_identifier++); -} - -/**********************************************************************/ - -void draw_left_half_L(struct point p1, struct point p2, int thickness) -{ -struct point p3, p4; - - p3.X = min(p1.X, p2.X); p3.Y = min(p1.Y, p2.Y); - p4.X = min(p1.X, p2.X); p4.Y = max(p1.Y, p2.Y); - draw_line(p3, p4, thickness); -} - -void draw_right_half_L(struct point p1, struct point p2, int thickness) -{ -struct point p3, p4; - - p3.X = max(p1.X, p2.X); p3.Y = min(p1.Y, p2.Y); - p4.X = max(p1.X, p2.X); p4.Y = max(p1.Y, p2.Y); - draw_line(p3, p4, thickness); -} - -void draw_top_half_L(struct point p1, struct point p2, int thickness) -{ -struct point p3, p4; - - p3.X = min(p1.X, p2.X); p3.Y = max(p1.Y, p2.Y); - p4.X = max(p1.X, p2.X); p4.Y = max(p1.Y, p2.Y); - draw_line(p3, p4, thickness); -} - -void draw_bottom_half_L(struct point p1, struct point p2, int thickness) -{ -struct point p3, p4; - - p3.X = min(p1.X, p2.X); p3.Y = min(p1.Y, p2.Y); - p4.X = max(p1.X, p2.X); p4.Y = min(p1.Y, p2.Y); - draw_line(p3, p4, thickness); -} - -/**********************************************************************/ - -void draw_rectilinear_edge(struct point p1, struct point p2, - int thickness, int L_orientation) -{ -/*#ifdef MAC*/ -int rnd_orientation[4] = { high_L, low_L, left_L, right_L }; - -switch (L_orientation) - { - case left_L: - draw_left_half_L(p1, p2, thickness); - if( sig(p1.X - p2.X) == sig(p1.Y - p2.Y) ) - draw_top_half_L(p1, p2, thickness); - else draw_bottom_half_L(p1, p2, thickness); - break; - case right_L: - draw_right_half_L(p1, p2, thickness); - if( sig(p1.X - p2.X) == sig(p1.Y - p2.Y) ) - draw_bottom_half_L(p1, p2, thickness); - else draw_top_half_L(p1, p2, thickness); - break; - case low_L: - draw_bottom_half_L(p1, p2, thickness); - if( sig(p1.X - p2.X) == sig(p1.Y - p2.Y) ) - draw_right_half_L(p1, p2, thickness); - else draw_left_half_L(p1, p2, thickness); - break; - case high_L: - draw_top_half_L(p1, p2, thickness); - if( sig(p1.X - p2.X) == sig(p1.Y - p2.Y) ) - draw_left_half_L(p1, p2, thickness); - else draw_right_half_L(p1, p2, thickness); - break; - case random_L: - draw_rectilinear_edge(p1, p2, thickness, rnd_orientation[random(0,3)]); - break; -} - -/*#endif*/ - -} - -/**********************************************************************/ - -void draw_edge(struct point p1, struct point p2, int thickness) -{ - -/*#ifdef MAC*/ - -switch (metric_type) - { - case Euclidean : - draw_line(p1,p2,thickness); - break; - - case Manhattan: - draw_rectilinear_edge(p1, p2, thickness, L_edge_orientation); - break; - - case Linfinity: - draw_rectilinear_edge(p1, p2, thickness, L_edge_orientation); - break; - } - -/*#endif*/ - -} - -/**********************************************************************/ - -void draw_points(void) -{ -/*#ifdef MAC*/ -int i; - -for(i=0;i= right) return; - -if(left>= (right-5)) - { - for(i=left; i < right; i++) - { - smallest_dist = edges[i].weight; smallest_edge = i; - for(j=i + 1; j <= right; j++) - { - if(edges[j].weight < smallest_dist) - { smallest_dist = edges[j].weight; smallest_edge = j; } - } - tmp = edges[i]; edges[i] = edges[smallest_edge]; edges[smallest_edge] = tmp; - } - return; - } -mid = (left + right) / 2; -tmp = edges[left]; edges[left] = edges[mid]; edges[mid] = tmp; -last = left; -for(i=left+1; i <= right; i++) - if (edges[i].weight < edges[left].weight) - { - last++; - tmp = edges[last]; edges[last] = edges[i]; edges[i] = tmp; - } -tmp = edges[last]; edges[last] = edges[left]; edges[left] = tmp; -qsort_edges(left, last - 1); -qsort_edges(last + 1, right); -} - -/**********************************************************************/ - -void draw_edges(void) -{ -/*#ifdef MAC*/ - -int j; - -for(j=0;j&2 sed 's/^-//' >control.c <<'End of control.c' -/**********************************************************************/ -/* */ -/* (c) Copyright 1992, by Gabriel Robins */ -/* */ -/* UVa CS Department, Charlottesville, VA, CA 22903 (804) 982-2207 */ -/* */ -/* This code may be freely used for all non-commercial purposes. */ -/* All copies/portions of this code must contain this header. */ -/* */ -/**********************************************************************/ - -/**********************************************************************/ -/* Control.c */ -/**********************************************************************/ - -#include "geometry.h" - -/**********************************************************************/ - -void InitMacintosh(void) -{ - MaxApplZone(); - InitGraf(&thePort); - InitFonts(); - FlushEvents(everyEvent, 0); - InitWindows(); - InitMenus(); - TEInit(); - InitDialogs(0L); - InitCursor(); -} - -/**********************************************************************/ - -void HandleMouseDown(EventRecord *theEvent) -{ - WindowPtr theWindow; - int windowCode = FindWindow (theEvent->where, &theWindow); - extern Rect dragRect; - - switch (windowCode) - { - case inSysWindow: - SystemClick (theEvent, theWindow); - break; - - case inMenuBar: - AdjustMenus(); - HandleMenu(MenuSelect(theEvent->where)); - break; - - case inDrag: - DragWindow(theWindow, theEvent->where, &dragRect); - break; - - case inContent: - if (theWindow != FrontWindow()) SelectWindow(theWindow); - else InvalRect(&theWindow->portRect); - break; - - case inGoAway: - if (TrackGoAway(theWindow, theEvent->where)) - HideWindow(theWindow); - break; - } -} - -/**********************************************************************/ - -void HandleEvent(WindowPtr Window) -{ - int ok; - EventRecord theEvent; - - HiliteMenu(0); - SystemTask(); /* Handle desk accessories */ - ok = GetNextEvent (everyEvent, &theEvent); - if (ok) - switch (theEvent.what) - { - case mouseDown: - HandleMouseDown(&theEvent); - break; - - case keyDown: - case autoKey: - if ((theEvent.modifiers & cmdKey) != 0) - { - AdjustMenus(); - HandleMenu(MenuKey((char) (theEvent.message & charCodeMask))); - } - break; - - case updateEvt: - BeginUpdate(Window); - /* redraw contents of window here. */ - EndUpdate(Window); - break; - - case activateEvt: - InvalRect(&Window->portRect); - break; - } -} - -/**********************************************************************/ - - End of control.c echo foo.c 1>&2 sed 's/^-//' >foo.c <<'End of foo.c' -/**********************************************************************/ -/* */ -/* (c) Copyright 1992, by Gabriel Robins */ -/* */ -/* UVa CS Department, Charlottesville, VA 22903 (804) 982-2207 */ -/* */ -/* This code may be freely used for all non-commercial purposes. */ -/* All copies/portions of this code must contain this header. */ -/* */ -/*********************************************************************/ - -/**********************************************************************/ -/* foo.c */ -/**********************************************************************/ - -#include "geometry.h" -/*#define DEBUG2*/ - - -/**********************************************************************/ - -extern char **errorstrings; - - - - -/**********************************************************************/ - -extern void error(enum errors, char *), - update_neighbour(FILE*,int quadrant, int dist,int j), - find_neighbours(int), - closest_neighbour(void), - generate_MST3(void); -/* - * debugging functions - */ -extern void print_points(void), - print_tree(FILE *, int); - - -#define MAXINT 32767 -#define FMT1 "number of points:\t%d\tmst_cost=\t%d\n" -#define DEBUGFMT1 "\n$$ beginning of linear_MST %d $$\n" -#define DEBUGFMT2 "working on S.P. point X=%d, Y=%d\n" -#define DEBUGFMT3 "side %d: now on point %d, the max%d is %d, po%d is %d\n" - - - -FILE *fp; -int num_candidates, - id_num = 0; - -/**********************************************************************/ -/* -** This function finds the closest neighbour for a node in -** its neighbour array -*/ - -void closest_neighbour() -{ - struct edge tmp; - int i, - smallest_edge=0; - - - for ( i = 0; i < 5; i++) - if (Neighbour[i].weight < Neighbour[smallest_edge].weight) - smallest_edge = i; - if (smallest_edge != 0){ - tmp = Neighbour[0]; - Neighbour[0] = Neighbour[smallest_edge]; - Neighbour[smallest_edge]= tmp; - } -} - -/**********************************************************************/ -/* -** This function updates a node's neighbour array -*/ - -void update_neighbour(FILE * fp,int quadrant, int dist,int j) -{ - Neighbour[quadrant].P2 = j; - Neighbour[quadrant].weight = dist; - -#ifdef DEBUG2 -fprintf(fp,"\nupdate Neighbour[%d]= %d",quadrant, Neighbour[quadrant].weight); -#endif -} - - -/**********************************************************************/ -/* -** This function finds up to four closest neighbours for a node -** in each quadrant -*/ - -void find_neighbours(int index) -{ - int i,j, - dx,dy, - dist, - quadrant; - EDGE* temp; - - - - for (i = 0; i < 5; i++) /*initial the neighbour array */ - { - Neighbour[i].P2 = NONE; - Neighbour[i].weight= MAXINT; - } - - for (j=0;j0) if(dx>0) if(dy0) quadrant = 1; else quadrant = 2; - else if(dx<0) if(dy>dx) quadrant = 2; else quadrant = 3; - else if(dy+dx<0) quadrant = 3; else quadrant = 0; -*/ - - if(dx > dy) if(dx + dy < 0) quadrant = 3; else quadrant = 0; - else if(dx + dy <0) quadrant = 2; else quadrant = 1; - - - if (dy <0) dy = -dy; - if (dx <0) dx = -dx; - dist = dy + dx; - - temp = &Neighbour[quadrant]; - if (dist < temp ->weight){ - temp ->P2 = j; - temp ->weight = dist; - } - - } -/* closest_neighbour();*/ -} - - - -/**********************************************************************/ -/* -** This function updates the tree by deleting the longest edge along -** the cycle generated by adding the new point -** called by linear_MST -*/ -void update_Tree(int first, int last) -{ - int prev,curr,next; - NODE preNode,curNode; - -#ifdef DEBUG - FILE* fp; - if (!(fp = fopen("c.update","a"))) { - fprintf(stderr,"***Error: cannot open file update for write.\n"); - exit(-1); - } -#endif - - if (first== last) return; - - if (Tree[first].parent == last){ - Tree[last]= Tree[first]; - Tree[last].parent = first; - return; - } - else { - prev = first; - curr= Tree[prev].parent; - next = Tree[curr].parent; - - preNode = Tree[prev]; - curNode = Tree[curr]; - - while (prev != last){ -#ifdef DEBUG -fprintf(fp, "prev=%d, curr= %d, next= %d \n", prev, curr, next); -#endif - Tree[curr]= preNode; - Tree[curr].parent = prev; - preNode = curNode; - curNode = Tree[next]; - prev= curr; - curr= next; - next= Tree[next].parent; - -#ifdef DEBUG -fflush(fp); - fclose(fp); -#endif -} - } -#ifdef DEBUG -fprintf(fp,"********end of function update_tree\n"); -fflush(fp); -fclose(fp); -#endif -} - -/**********************************************************************/ -/* -** traverse the tree from a bottom node to a up level one -*/ -void move_up(int *index, int *po) -{ - if (Tree[*index].parent != NONE) { - *index = Tree[*index].parent; - Tree[*index].id = id_num; - if (Tree[*index].weight > Tree[*po].weight) - *po = *index; - } -} - -/**********************************************************************/ -/* trace back to the starting point -** -*/ - -int reset_po(int first,int last) -{ - int i,tmp; - - tmp = first; - for(i=first; i != last;i=Tree[i].parent) - if (Tree[i].weight > Tree[tmp].weight) - tmp = i; - return tmp; -} - -/**********************************************************************/ -/* -** This function updates the MST by connecting the new node with -** its up to four neighbours in the tree and deleting the longest -** edge along the induced cycle -*/ - -int linear_MST(int new_point) -{ - int cost=0, i = 1, j, index1, index2, dif, po1, po2, savings=0, PATH; -#ifdef DEBUG2 - FILE* fp; - if (!(fp = fopen("c.out","a"))) error(EOPEN, "c.out"); -fprintf(fp, DEBUGFMT1, new_point); -fprintf(fp,DEBUGFMT2,pointset[new_point].X,pointset[new_point].Y); -fprintf(fp,"the original cost is %d \n", cost); -#endif - - Tree[new_point].parent = Neighbour[0].P2; - if (new_point) /* if not first point */ - Tree[new_point].weight = cost = Neighbour[0].weight; - /*for (; i < 4 && Neighbour[i].P2 != NONE ; i++)*/ - for (; i < 4 ; i++) - if ( Neighbour[i].P2 != NONE ) { - int parent1, - parent2, - weight1, - weight2, - po2 = index2 = Neighbour[i].P2; - Tree[index2].id = ++id_num; - po1 = index1 = new_point; - Tree[index1].id = id_num; - dif = 0; - PATH = 0; - parent1 = Tree[index1].parent; - parent2 = Tree[index2].parent; - while (Tree[parent1].id != id_num - && Tree[parent2].id != id_num - && parent1 != parent2) { - move_up(&index1, &po1); - move_up(&index2, &po2); -#ifdef DEBUG2 -fprintf(fp, DEBUGFMT3, 1, index1, 1, Tree[po1].weight, 1, po1); -fprintf(fp, DEBUGFMT3, 2, index2, 2, Tree[po2].weight, 2, po2); -#endif - - parent1 = Tree[index1].parent; - parent2 = Tree[index2].parent; - } - - if (Tree[parent1].id == id_num) { - if (parent1 == Neighbour[i].P2) - PATH = 1; - else po2 = reset_po(Neighbour[i].P2, parent1); - } - if (Tree[parent2].id == id_num) { - if (parent2 == new_point) - PATH = 2; - else po1 = reset_po(new_point, parent2); - } -#ifdef DEBUG2 -fprintf(fp,"PATH %d, po1 is %d, po2 is %d\n", PATH, po1, po2); -#endif - - weight1 = Tree[po1].weight; - weight2 = Tree[po2].weight; - if (!PATH) - PATH = (weight1 > weight2) ? 1 : 2; - switch (PATH) { - case 1: if (weight1 > Neighbour[i].weight) { - dif = weight1 - Neighbour[i].weight; - update_Tree(new_point, po1); - Tree[new_point].parent = Neighbour[i].P2; - Tree[new_point].weight = Neighbour[i].weight; - - }break; - case 2: if (weight2 > Neighbour[i].weight) { - dif = weight2 - Neighbour[i].weight; - update_Tree(Neighbour[i].P2, po2); - Tree[Neighbour[i].P2].parent = new_point; - Tree[Neighbour[i].P2].weight - = Neighbour[i].weight; - }break; - } -#ifdef DEBUG2 -fprintf(fp,"****PATH %d, new_point %d, po1 %d, po2 %d, dif %d\n\n", -PATH,new_point,po1,po2,dif); -#endif - savings += dif; -#ifdef DEBUG2 -fprintf(fp, "------------Tree of this run on Neighbour %d----------\n",i); -print_tree(fp, new_point); -#endif - - } -#ifdef DEBUG2 -fprintf(fp,"DONE checking neighbours on this S.P. SAVE = %d \n", savings); -fclose(fp); -#endif - - return (savings - cost); -} - -/***************************************************************************/ - -void error(enum errors i, char *s) -{ - fprintf(stderr, errorstrings[i], s); - exit(-1); -} - -/**********************************************************************/ - -void print_points(void) -{ - int i; - - for(i = 0; i < number_of_points; i++) { - printf("\n i= %d pointset[i].X =%d, pointset[i].Y = %d\n", - i, - pointset[i].X, - pointset[i].Y); - } -} - -/**********************************************************************/ - -void print_tree(FILE *fp, int new_point) -{ -#ifdef DEBUG2 - int i; - for (i = 0; i <= new_point; i++) { - fprintf(fp, - "tree[%d] p=%d weight= %d \n", - i, - Tree[i].parent, - Tree[i].weight); - fflush(fp); - } -#endif - -} - -/**********************************************************************/ -/* This function generates MST by adding the new nodes one at a time -** calling linear_MST -** -*/ - -void generate_MST3() -{ - int i, - j, - savings; - - Tree[0].weight = Tree[0].parent = Tree[0].id = NONE; - mst_cost = 0; - for (j = 0; j < number_of_points; j++) { - find_neighbours(j); - savings = linear_MST(j); - mst_cost -= savings; - } - /*printf("\nMST cost computed = %d\n", mst_cost);*/ - if(GRAPHICS == YES){ - draw_point(pointset[0].X, pointset[0].Y, size); - for (i = 1; i < number_of_points; i++) { - draw_point(pointset[i].X, pointset[i].Y, size); - draw_edge(pointset[i], pointset[Tree[i].parent], 1); - } - } -} - -/**********************************************************************/ -/* This function removes SPs of degree one and two -** -*/ -void remove_invalid_SPs(int actual_number_of_points, int *SPs) { - -int first_new_SP,i,j, k, prior_mst_cost; - -number_of_points--; - - prior_mst_cost = mst_cost; - -first_new_SP = number_of_points - *SPs; - -for(j=actual_number_of_points;j=actual_number_of_points;i--) -if (degree_count[i] <= 2) -{ - if(i >= first_new_SP) - *SPs = *SPs - 1; - - for(j=i;j&2 sed 's/^-//' >geometry.h <<'End of geometry.h' -/**********************************************************************/ -/* (c) Copyright 1992, by Gabriel Robins */ -/* */ -/* UVa CS Department, Charlottesville, VA, CA 22903 (804) 982-2207 */ -/* */ -/* This code may be freely used for all non-commercial purposes. */ -/* All copies/portions of this code must contain this header. */ -/* */ -/**********************************************************************/ - -/**********************************************************************/ -/* Geometry.h */ -/**********************************************************************/ - -/**********************************************************************/ -/* two of the following three definitions must be commented out, */ -/* depending on what hardware is being used. The rest of the code */ -/* will compile accordingly. */ -/**********************************************************************/ -/* - * #define MAC 1 - */ - -#define SUN 1 -#ifdef MAC -#include -#include -#endif -#ifdef SUN -#include -#include -#endif -#include -#include -#include -#ifdef MAC -#define window_height 300 -#define max_number_of_points 500 -#endif -#ifdef SUN -#define window_height 500 /* 1000 */ -#define max_number_of_points 500 -#define wait 0 -#endif -#define window_width window_height -#define window_depth window_height -#define window_left 100 /* 310 */ -#define window_top 10 /* 40 */ - -#define max_neighbor_count 8 - -#define string_length 200 -#ifdef MAC -#define infinity 9999 -#else -#define infinity 99999999 -#endif -#ifdef MAC -#define stats_how_often 10 -#else -#define stats_how_often 100 -#endif -#define HEURISTICS 6 -#define NONE -1 -#define MAXINT 32767 - -struct point { - int X, Y, id, flag; -}; - -struct edge { - int P1, P2, flag, weight; -}; -typedef struct edge EDGE; - -typedef struct NODE { - int parent, - id, - weight; -} NODE; - -enum errors { - ECALLOC, - EOPEN -}; - -enum flags { - ADD, - NOT_ADD, - ADD_IF_SAVE -}; - -enum mark { - NOT_MARKED, MARKED -}; - -enum metric { - Euclidean = 1, Manhattan, Linfinity -}; -enum L_heuristics { - high_L = 1, low_L, left_L, right_L, random_L -}; -enum boolean { - NO, YES -}; -/**********************************************************************/ - -extern unsigned long int initial_seed, next; -extern int *hit_list, *degree_count, *num_N_pts[], *Steiner_savings; - -extern struct point *pointset, *SP_candidates; -extern struct edge *edges; -extern NODE *Tree, *old_Tree; -extern EDGE *Neighbour; - -#ifdef MAC -extern WindowPtr CGWindow; -extern Rect windowBounds, dragRect; -extern MenuHandle appleMenu, fileMenu, editMenu, sizeMenu, iterationsMenu, pointMenu, - metricMenu, CGMenu, gridMenu; -#endif - - -extern int metric_type, pointset_cardinality, iterations_cardinality, grid_size_cardinality, uncross_edges, - flip_hs, unique_identifier, metric_type, L_edge_orientation, number_of_points, - size, number_of_edges, mst_cost, choice, GRAPHICS, number_of_points, - number_of_iterations, uncross_edges, set_sizes[], iterations[], - grid_sizes[], total_mst_cost, total_steiner_cost[], sum[], - max_improvement[], min_improvement[], steiner_cost[], improvement_percent[], - ave_num_steiner_pts[], num_steiner_pts[], min_num_steiner_pts[], - max_num_steiner_pts[], sum[], total_mst_cost, min_improvement[], min_num_steiner_pts[], - min_round, total_round, max_round, grid_size; -extern int OUT_TREE; -#ifdef SUN -extern Window window, rootwindow; -extern int the_screen; -extern XSizeHints *the_sizehints; -extern GC gc; -extern Display *the_display; -#endif - - -/**********************************************************************/ - -void read_in_pointset(void); -void qsort_candidates(int, int); -void loop_stats(void); -void qsort_edges(int, int); -void interactive(void); -#ifdef MAC -void enable(MenuHandle, int, Boolean); -#endif -/**********************************************************************/ End of geometry.h echo globals.c 1>&2 sed 's/^-//' >globals.c <<'End of globals.c' -/**********************************************************************/ -/* */ -/* (c) Copyright 1992, by Gabriel Robins */ -/* */ -/* UVa CS Department, Charlottesville, VA, CA 22903 (804) 982-2207 */ -/* */ -/* This code may be freely used for all non-commercial purposes. */ -/* All copies/portions of this code must contain this header. */ -/* */ -/**********************************************************************/ - -/**********************************************************************/ -/* Globals.c */ -/**********************************************************************/ - -#include "geometry.h" - -/**********************************************************************/ - -int set_sizes[18] = { 3,4,5,6,8,10,16,20,25,35,50,64,128,256,512,1024,2048,4096 }; -int iterations[13] = { 1,2,3,5,10,50,100,300,1000,3000,5000,10000,15000 }; -int grid_sizes[9] = { 10,20,50,100,300,500,1000,5000,10000 }; - -unsigned long int next = 1; -unsigned long int initial_seed = 1; - -#ifdef MAC -int GRAPHICS = YES; -#endif -#ifdef SUN -int GRAPHICS = YES; -#endif - - -/* double SCALE_FACTOR = 1.5; */ - -int number_of_points = 4; -int pointset_cardinality = 2; - -int number_of_iterations = 3; -int iterations_cardinality = 3; - -int grid_size = 10000; -int grid_size_cardinality = 5; - -int size = 5; - -extern int choice; - -int OUT_TREE = 0; - -#ifdef MAC - -Rect dragRect; -Rect windowBounds = { window_top, window_left, - window_height + window_top, - window_width + window_left }; - -MenuHandle appleMenu, fileMenu, editMenu, pointMenu, sizeMenu, iterationsMenu, - metricMenu, CGMenu, gridMenu; - -WindowPtr CGWindow; - -#endif - -#ifdef SUN -XSizeHints *the_sizehints; -GC gc; -Display *the_display; -Window window,rootwindow; -int the_screen; -#endif - -/**********************************************************************/ - -struct edge *edges; -struct point *pointset, *SP_candidates; - -NODE *Tree,*old_Tree; - -; -EDGE *Neighbour; - -int *hit_list, *num_N_pts[HEURISTICS], *degree_count, number_of_edges; -int *Steiner_savings; - -int metric_type = Manhattan, L_edge_orientation = low_L; - -int mst_cost, sum[HEURISTICS], total_mst_cost=0, - steiner_cost[HEURISTICS], total_steiner_cost[HEURISTICS], - improvement_percent[HEURISTICS], max_improvement[HEURISTICS], - min_improvement[HEURISTICS], ave_num_steiner_pts[HEURISTICS], - normalization_constant; - -int num_steiner_pts[HEURISTICS], min_num_steiner_pts[HEURISTICS], - max_num_steiner_pts[HEURISTICS], - min_round= MAXINT, max_round=0, total_round=0; - -int unique_identifier = 0; -char msg[string_length]; -int num_edges, num_graph_edges, original_nop; -char *errorstrings[] = { - "***** Error: Storage allocation for %s\n", - "***** Error: Cannot open file %s\n"}; -char graphic_flag; - -/**********************************************************************/ - End of globals.c echo graphics.c 1>&2 sed 's/^-//' >graphics.c <<'End of graphics.c' -/**********************************************************************/ -/* */ -/* (c) Copyright 1992, by Gabriel Robins */ -/* */ -/* UVa CS Department, Charlottesville, VA, CA 22903 (804) 982-2207 */ -/* */ -/* This code may be freely used for all non-commercial purposes. */ -/* All copies/portions of this code must contain this header. */ -/* */ -/**********************************************************************/ - -/**********************************************************************/ -/* Graphics.c */ -/**********************************************************************/ - -#include "geometry.h" - - -/**********************************************************************/ - -int scale(int value) -{ -return((int) (value * ((float) window_height) / grid_size)); - -} - -/**********************************************************************/ - -void draw_point(int x, int y, int diameter) -{ - -#ifdef MAC - -int offset= diameter/2; -Rect myRect; - -if(GRAPHICS) -{ -SetPort(CGWindow); -SelectWindow(CGWindow); -SetRect(&myRect, scale(x) - offset, scale(y) - offset, - scale(x) - offset + diameter, scale(y) - offset + diameter); -FillOval(&myRect, black); -} -#endif - - -#ifdef SUN - -int offset= diameter; - -if(GRAPHICS) -{ -XFillArc(the_display,window,gc, - scale(x) - offset, scale(y) - offset, - offset, offset, - 0,64*360); -XFlush(the_display); -sleep(wait); -} -#endif -} - - -/**********************************************************************/ - -void draw_line(struct point p1, struct point p2, int thickness) -{ - -#ifdef MAC -int offset= thickness/2; -if(GRAPHICS) -{ -SetPort(CGWindow); -SelectWindow(CGWindow); -PenSize(thickness,thickness); -MoveTo(scale(p1.X) - offset, scale(p1.Y) - offset ); -LineTo(scale(p2.X) - offset, scale(p2.Y) - offset); -} -#endif - -#ifdef SUN -int offset= thickness; -if (GRAPHICS) -{ -XDrawLine ( the_display, window, gc, - scale(p1.X) - offset, scale(p1.Y) - offset, - scale(p2.X) - offset, scale(p2.Y) - offset); -XFlush(the_display); -sleep(wait); -} -#endif -} - - -void write_index(struct point p1, int index) -{ - -#ifdef SUN - -char str1[10]; -if (GRAPHICS) -{ - sprintf(str1,"%d",index); - XDrawString ( the_display, window, gc, - scale(p1.X), scale(p1.Y),str1,2); - XFlush(the_display); - sleep(wait); -} -#endif -} - -/**********************************************************************/ - -void erase_window(void) -{ - -#ifdef MAC - -int x, y, diameter; - -if(GRAPHICS) -{ -Rect myRect; -SetPort(CGWindow); -SelectWindow(CGWindow); -SetRect(&myRect, 0, 0, window_width, window_height); -EraseRect(&myRect); -} -#endif - -#ifdef SUN -if (GRAPHICS) -{ - XClearArea(the_display,window,0,0,0,0,1); -} -#endif -} - - - -/**********************************************************************/ - -void print_stats(char format[], double value) -{ -/* -printf(format,value); -*/ -} - -/**********************************************************************/ - End of graphics.c echo main.c 1>&2 sed 's/^-//' >main.c <<'End of main.c' -/**********************************************************************/ -/* */ -/* (c) Copyright 1992, by Gabriel Robins */ -/* */ -/* UVa CS Department, Charlottesville, VA, CA 22903 (804) 982-2207 */ -/* */ -/* This code may be freely used for all non-commercial purposes. */ -/* All copies/portions of this code must contain this header. */ -/* */ -/**********************************************************************/ - -/**********************************************************************/ -/* main.c */ -/**********************************************************************/ - -#include "geometry.h" - -int choice; -/**********************************************************************/ - -main(int argc, - char *argv[] - ) -{ -int h1, h2,run_count=0; - -init_vars(); - -/* randomize_seed(); */ - -#ifdef MAC - -InitMacintosh(); -SetUpMenus(); -SetUpWindow( argc, argv); -erase_window(); -generate_random_points(); -draw_points(); -for (;;) HandleEvent(CGWindow); - -#endif - -#ifdef SUN - -SetUpWindow( argc, argv); -interactive(); - -#else - -interactive(); -#endif -} - -/**********************************************************************/ - -void interactive(void) -{ - int get_seed, old_noi, old_nop; - - printf("Choose: 1) Random pointsets, 2) Read in pointset, or 3) Automatic runs: "); - scanf("%d", &choice); - - if(choice==1) - { - printf("Enter the number of points: "); - scanf("%d", &number_of_points); - - printf("Enter the number of iterations: "); - scanf("%d", &number_of_iterations); - printf("Enter the gridsize: "); - scanf("%d", &grid_size); - printf("Enter the initial random seed (0 for random): "); - scanf("%d", &get_seed); - if(get_seed==0) { printf("randomizing seed!\n"); randomize_seed(); } - else next = (unsigned long int) get_seed; - loop_stats(); - } - else if(choice==2) - { - printf("Enter the number of points: "); - scanf("%d", &number_of_points); - printf("Enter the gridsize: "); - scanf("%d", &grid_size); - old_noi = number_of_iterations; - old_nop = number_of_points; - - read_in_pointset(); - - number_of_iterations = 1; - - loop_stats(); - - number_of_iterations = old_noi; - number_of_points = old_nop; - } -else if(choice==3) - { - printf("Enter the number of iterations: "); - scanf("%d", &number_of_iterations); - printf("Enter the initial random seed (0 for random): "); - scanf("%d", &get_seed); - if(get_seed==0) { printf("randomizing seed!\n"); randomize_seed(); } - else next = (unsigned long int) get_seed; - multi_loop_stats(); - } -} - -/********************************************************************* - - This function reads in a pointset. - -*********************************************************************/ - -void read_in_pointset(void) -{ -int x, y, i = 0; - - -printf("Enter the pairs of integer coordinates of each point : \n"); - -/* -printf("end with -1, -1 if want to print out #SP and their coordinates\n"); -printf("otherwise end with (-0, -0) \n"); -while(YES) -{ -if(scanf("%d %d", &x, &y) < 0) break; -if(x < 0) break; -pointset[i].X = x; -pointset[i].Y = y; -pointset[i].flag = NO; -pointset[i].id = generate_unique_identifier(); -i++; -} -number_of_points = i; -*/ - - -for (i=0; i< number_of_points; i++) -{ - scanf("%d %d", &x, &y); - pointset[i].X = x; - pointset[i].Y = y; -/* - pointset[i].flag = NO; - pointset[i].id = generate_unique_identifier(); -*/ -} - -} - - -/**********************************************************************/ - End of main.c echo menus.c 1>&2 sed 's/^-//' >menus.c <<'End of menus.c' -/**********************************************************************/ -/* */ -/* (c) Copyright 1992, by Gabriel Robins */ -/* */ -/* UVa CS Department, Charlottesville, VA, CA 22903 (804) 982-2207 */ -/* */ -/* This code may be freely used for all non-commercial purposes. */ -/* All copies/portions of this code must contain this header. */ -/* */ -/**********************************************************************/ - -/**********************************************************************/ -/* Menus.c */ -/**********************************************************************/ - -#include "geometry.h" - -/**********************************************************************/ - -enum { appleID = 1, fileID, editID, sizeID, pointID, iterationsID, - gridID, metricID, CGID}; -enum { openItem = 1, closeItem, quitItem = 4 }; -enum { randomizeItem = 1, MSTItem, steiner2Item, steiner3Item, steiner4Item, - loopItem, multiloopItem, interItem, redrawItem }; -enum { euclideanItem = 1, manhattanItem, LinfinityItem }; -enum { leftLItem = 1, rightLItem, topLItem, bottomLItem, randomLItem }; - -/**********************************************************************/ - -void SetUpMenus(void) - -{ -char sizes_string[string_length], iterations_string[string_length], - grid_string[string_length]; -int i; - -for(i=0;iwindowKind : 0; - Boolean DA = kind < 0; - - enable(editMenu, 1, DA); - enable(editMenu, 3, DA); - enable(editMenu, 4, DA); - enable(editMenu, 5, DA); - enable(editMenu, 6, DA); - - enable(fileMenu, openItem, !((WindowPeek) CGWindow)->visible); - enable(fileMenu, closeItem, DA || ((WindowPeek) CGWindow)->visible); - - CheckItem(sizeMenu, size, true); - CheckItem(pointMenu, pointset_cardinality, true); - CheckItem(iterationsMenu, iterations_cardinality, true); - CheckItem(gridMenu, grid_size_cardinality, true); - CheckItem(metricMenu, metric_type, true); -} - -void enable(MenuHandle menu, int item, Boolean ok) -{ - if (ok) - EnableItem(menu, item); - else - DisableItem(menu, item); -} - -/***** - * HandleMenu(mSelect) - * - * Handle the menu selection. mSelect is what MenuSelect() and - * MenuKey() return: the high word is the menu ID, the low word - * is the menu item - * - *****/ - -void HandleMenu (long mSelect) -{ - int menuID = HiWord(mSelect), menuItem = LoWord(mSelect); - Str255 name; - GrafPtr savePort; - WindowPeek frontWindow; - Rect myRect; - - switch (menuID) - { - case appleID: - GetPort(&savePort); - GetItem(appleMenu, menuItem, name); - OpenDeskAcc(name); - SetPort(savePort); - break; - - case fileID: - switch (menuItem) - { - case openItem: - ShowWindow(CGWindow); - SelectWindow(CGWindow); - break; - - case closeItem: - if ((frontWindow = (WindowPeek) FrontWindow()) == 0L) break; - if (frontWindow->windowKind < 0) - CloseDeskAcc(frontWindow->windowKind); - else if (frontWindow = (WindowPeek) CGWindow) - HideWindow(CGWindow); - break; - - case quitItem: - ExitToShell(); - break; - } - break; - - case editID: - if (!SystemEdit(menuItem-1)) - SysBeep(5); - break; - - case sizeID: - CheckItem(sizeMenu, size, false); - size = menuItem; - InvalRect(&CGWindow->portRect); - break; - - case pointID: - CheckItem(pointMenu, pointset_cardinality, false); - pointset_cardinality = menuItem; - number_of_points = set_sizes[menuItem-1]; - break; - - case iterationsID: - CheckItem(iterationsMenu, iterations_cardinality, false); - iterations_cardinality = menuItem; - number_of_iterations = iterations[menuItem-1]; - break; - - case metricID: - CheckItem(metricMenu, metric_type, false); - metric_type = menuItem; - break; - - case gridID: - CheckItem(gridMenu, grid_size_cardinality, false); - grid_size_cardinality = menuItem; - grid_size = grid_sizes[menuItem-1]; - break; - - case CGID: - switch (menuItem) - { - case randomizeItem: - do_randomize(); - break; - - case MSTItem: - do_mst(); - break; - - case steiner2Item: - do_steiner(2); - break; - - case steiner3Item: - do_steiner(3); - break; - - case steiner4Item: - - do_steiner(4); - break; - - case loopItem: - loop_stats(); - break; - - case multiloopItem: - multi_loop_stats(); - break; - - case interItem: - interactive(); - break; - - case redrawItem: - redraw_points(); - break; - - } - break; - } -} - -/**********************************************************************/ End of menus.c echo misc.c 1>&2 sed 's/^-//' >misc.c <<'End of misc.c' -/**********************************************************************/ -/* */ -/* (c) Copyright 1992, by Gabriel Robins */ -/* */ -/* UVa CS Department, Charlottesville, VA, CA 22903 (804) 982-2207 */ -/* */ -/* This code may be freely used for all non-commercial purposes. */ -/* All copies/portions of this code must contain this header. */ -/* */ -/**********************************************************************/ - -/**********************************************************************/ -/* misc.c */ -/**********************************************************************/ - -#include "geometry.h" - -/**********************************************************************/ - -void redraw_points(void) -{ - -/*#ifdef MAC*/ -if(GRAPHICS) { erase_window(); draw_points(); } -/*#endif*/ -} - -/**********************************************************************/ - -int do_steiner(int k) -{ -int tmp; -int i, king; - -switch (k) - { - case 2: - tmp = generate_steiner2(); - return(tmp); - break; - - case 3: - tmp = generate_steiner3(); - return(tmp); - break; - - case 4: - tmp = generate_steiner4(); - return(tmp); - break; - - case 5: - steiner_cost[k] = infinity; - - for(i=2; i < (HEURISTICS - 1); i++) - if(steiner_cost[i] < steiner_cost[k]) - { - steiner_cost[k] = steiner_cost[i]; - improvement_percent[k] = improvement_percent[i]; - king = i; - } - ave_num_steiner_pts[k] = ave_num_steiner_pts[k] + num_steiner_pts[king]; - min_num_steiner_pts[k] = min(min_num_steiner_pts[k], num_steiner_pts[king]); - max_num_steiner_pts[k] = max(max_num_steiner_pts[k], num_steiner_pts[king]); - - return(improvement_percent[k]); - break; - } -} - -/**********************************************************************/ - -void do_mst(void) -{ -extern int GRAPHICS; - -generate_MST2(); - -/*#ifdef MAC*/ -if(GRAPHICS) draw_edges(); -/*#endif*/ -} - -/**********************************************************************/ - -void do_randomize(void) -{ -generate_random_points(); -/*redraw_points();*/ -} - -/**********************************************************************/ - -void print_separator(void) -{ -printf("==============================================================\n"); -} - -/**********************************************************************/ End of misc.c echo steiner2.c 1>&2 sed 's/^-//' >steiner2.c <<'End of steiner2.c' -/**********************************************************************/ -/* */ -/* (c) Copyright 1992, by Gabriel Robins */ -/* */ -/* UVa CS Department, Charlottesville, VA, CA 22903 (804) 982-2207 */ -/* */ -/* This code may be freely used for all non-commercial purposes. */ -/* All copies/portions of this code must contain this header. */ -/* */ -/**********************************************************************/ - -/**********************************************************************/ -/* Steiner2.c */ -/**********************************************************************/ - -#include "geometry.h" - -/**********************************************************************/ - -int generate_steiner2(void) -{ -struct point SP; -int lowest_MST_so_far, original_MST_cost, pre_improvement_mst_cost; -int i, j, found_improvement, heuristic_num = 2, - actual_number_of_points, nsp = 0; - -actual_number_of_points = number_of_points; -generate_MST2(); -pre_improvement_mst_cost = lowest_MST_so_far = original_MST_cost = mst_cost; - -found_improvement = YES; -while(found_improvement == YES) -{ -found_improvement = NO; -number_of_points++; -for(i=0;i= right) return; -m = (left + right) / 2; -t = N[left]; N[left] = N[m]; N[m] = t; -last = left; -for(i=left+1; i <= right; i++) - if (N[i] > N[left]) { ++last; t = N[i]; N[i] = N[last]; N[last] = t; } -t = N[left]; N[left] = N[last]; N[last] = t; -qsort_N(N, left, last - 1); -qsort_N(N, last + 1, right); -} - -/**********************************************************************/ - -/* -int compute_mst_cost(void) -{ -int i, j; - -mst_cost = 0; -for(i=0;i&2 sed 's/^-//' >steiner3.c <<'End of steiner3.c' -/**********************************************************************/ -/* */ -/* (c) Copyright 1992, by Gabriel Robins */ -/* */ -/* UVa CS Department, Charlottesville, VA, CA 22903 (804) 982-2207 */ -/* */ -/* This code may be freely used for all non-commercial purposes. */ -/* All copies/portions of this code must contain this header. */ -/* */ -/**********************************************************************/ - -/**********************************************************************/ -/* Steiner3.c */ -/**********************************************************************/ - -#include "geometry.h" - -/**********************************************************************/ - -int generate_steiner3(void) -{ -int current_MST_cost, original_MST_cost; -int i, j, k, heuristic_num = 3, actual_number_of_points, - nsp = 0; - -actual_number_of_points = number_of_points; -generate_MST2(); -original_MST_cost = current_MST_cost = mst_cost; - -number_of_points++; - -for(i=0;i 2) - { pointset[ptr1] = pointset[ptr2]; ptr1++; } - else if(h_num != 3) printf("H%d: Deleted a SP with deg %d!\n", - h_num, vertices[ptr2].neighbor_count); - -number_of_points = ptr1; -generate_MST(); - -if((old_mst_cost > mst_cost) && (h_num!=3)) - { - printf("H3: Deletion resulted in MST cost savings of %.0f!!!!\n", - old_mst_cost - mst_cost); - printf("Pointset is now: "); - for(k=0;k&2 sed 's/^-//' >steiner4.c <<'End of steiner4.c' -/**********************************************************************/ -/* */ -/* (c) Copyright 1992, by Gabriel Robins */ -/* */ -/* UVa CS Department, Charlottesville, VA, CA 22903 (804) 982-2207 */ -/* */ -/* This code may be freely used for all non-commercial purposes. */ -/* All copies/portions of this code must contain this header. */ -/* */ -/**********************************************************************/ - -/**********************************************************************/ -/* Steiner4.c */ -/**********************************************************************/ - -#include "geometry.h" - -/**********************************************************************/ - -int num_candidates; - -int generate_steiner4(void) -{ -int original_MST_cost, prior_MST_cost, pre_round_mst_cost; -int s, i, j, k, heuristic_num = 4, round = 0, nsp, - actual_number_of_points, SPs_this_round; -FILE *fd; - -generate_MST2(); -original_MST_cost = mst_cost; - -prior_MST_cost = mst_cost; -actual_number_of_points = number_of_points; -number_of_points++; - -while(YES) -{ -num_candidates = 0; -for(i=0;i= Steiner_savings[k]) - { - number_of_points++; - SPs_this_round++; - if(GRAPHICS) draw_point(SP_candidates[k].X,SP_candidates[k].Y, size+4); - nsp = number_of_points - actual_number_of_points - 1; - prior_MST_cost = mst_cost; - } - } - -if(SPs_this_round == 0) break; - -round++; - -number_of_points--; -/* delete_useless_SPs(4, actual_number_of_points); */ -number_of_points++; - -} - -number_of_points--; -generate_MST2(); - -if(GRAPHICS == YES) draw_edges(); - - -steiner_cost[heuristic_num] = mst_cost; -improvement_percent[heuristic_num] = - (original_MST_cost - steiner_cost[heuristic_num]) * 100.0 / original_MST_cost; - -num_steiner_pts[heuristic_num] = number_of_points - actual_number_of_points; -num_N_pts[heuristic_num][num_steiner_pts[heuristic_num]] ++; -ave_num_steiner_pts[heuristic_num] = ave_num_steiner_pts[heuristic_num] - + num_steiner_pts[heuristic_num]; -min_num_steiner_pts[heuristic_num] = min(min_num_steiner_pts[heuristic_num], - num_steiner_pts[heuristic_num]); -max_num_steiner_pts[heuristic_num] = max(max_num_steiner_pts[heuristic_num], - num_steiner_pts[heuristic_num]); - -min_round = min (round, min_round); -max_round = max (round, max_round); -total_round = total_round + round; - -generate_MST2(); - -/* -fd = fopen("ST","w"); -for(j=0;j= right) return; -m = (left + right) / 2; - -t = Steiner_savings[left]; -Steiner_savings[left] = Steiner_savings[m]; -Steiner_savings[m] = t; - -SP = SP_candidates[left]; -SP_candidates[left] = SP_candidates[m]; -SP_candidates[m] = SP; - -last = left; -for(i=left+1; i <= right; i++) - if (Steiner_savings[i] > Steiner_savings[left]) - { ++last; - t = Steiner_savings[i]; - Steiner_savings[i] = Steiner_savings[last]; - Steiner_savings [last] = t; - - SP = SP_candidates[i]; - SP_candidates[i] = SP_candidates[last]; - SP_candidates[last] = SP; - } - -t = Steiner_savings[left]; -Steiner_savings[left] = Steiner_savings[last]; -Steiner_savings[last] = t; - -SP = SP_candidates[left]; -SP_candidates[left] = SP_candidates[last]; -SP_candidates[last] = SP; - -qsort_candidates(left, last - 1); -qsort_candidates(last + 1, right); -} - -/**********************************************************************/ - End of steiner4.c echo steiner5.c 1>&2 sed 's/^-//' >steiner5.c <<'End of steiner5.c' -/**********************************************************************/ -/* */ -/* (c) Copyright 1992, by Gabriel Robins */ -/* */ -/* UVa CS Department, Charlottesville, VA 22903 (804) 982-2207 */ -/* */ -/* This code may be freely used for all non-commercial purposes. */ -/* All copies/portions of this code must contain this header. */ -/* */ -/**********************************************************************/ - -/**********************************************************************/ -/* Steiner5.c */ -/**********************************************************************/ - -#include "geometry.h" - -/**********************************************************************/ - -int num_candidates; - -int generate_steiner5(void) -{ -int original_MST_cost,savings; -int s, i, j, k, heuristic_num = 5, round = 0, nsp, - actual_number_of_points, SPs_this_round; - - - -mst_cost = 0; -generate_MST3(); -original_MST_cost = mst_cost; -erase_window(); -if(GRAPHICS == YES){ - draw_point(pointset[0].X, pointset[0].Y, size); - for (i = 1; i < number_of_points; i++){ - draw_point(pointset[i].X, pointset[i].Y, size); - draw_edge(pointset[i], pointset[Tree[i].parent],1); - } - } -for(i=0;i 0) { - SP_candidates[num_candidates].X = pointset[number_of_points - 1].X; - SP_candidates[num_candidates].Y = pointset[number_of_points - 1].Y; - Steiner_savings[num_candidates] = savings; - num_candidates++; - } - for(k=0;k= Steiner_savings[k]) - { - mst_cost -= savings; - number_of_points++; - SPs_this_round++; - /* - if(GRAPHICS) - draw_point(SP_candidates[k].X,SP_candidates[k].Y, size+2); - */ - for(i=0;i&2 sed 's/^-//' >windows.c <<'End of windows.c' -/**********************************************************************/ -/* */ -/* (c) Copyright 1992, by Gabriel Robins */ -/* */ -/* UVa CS Department, Charlottesville, VA, CA 22903 (804) 982-2207 */ -/* */ -/* This code may be freely used for all non-commercial purposes. */ -/* All copies/portions of this code must contain this header. */ -/* */ -/**********************************************************************/ - -/**********************************************************************/ -/* Windows.c */ -/**********************************************************************/ - -#include "geometry.h" - -/**********************************************************************/ - -void SetUpWindow(int argc, - char *argv[] - ) -{ -#ifdef MAC - -CGWindow = NewWindow(0L, &windowBounds, - "\pComputational Geometry Workbench", - true, - documentProc, - 0, /* -1L, */ - true, - 0); - -dragRect = screenBits.bounds; -SetPort(CGWindow); - -#endif - -#ifdef SUN -if (GRAPHICS == YES) -{ -/* -** Establish a connection to local X server for local display -** -*/ - -the_display = XOpenDisplay((char *)NULL); -if (the_display == NULL) -{ - fprintf(stderr,"ERROR: could not open a connection to X \n"); - exit(1); -} - - -the_screen = DefaultScreen(the_display); -rootwindow = RootWindow(the_display,the_screen); - - -/* -** Open a window with a x,y pixel location for it upper left corner -** and width and height for its size -** -*/ - -window = XCreateSimpleWindow(the_display, rootwindow, - window_left, window_top, - window_width,window_height, - 1, /* border width */ - BlackPixel(the_display, the_screen), /* border color */ - WhitePixel(the_display, the_screen));/* background color */ - - - -/* -** Set up hints about the window -** -*/ -the_sizehints = (XSizeHints*) malloc (sizeof(XSizeHints)); - -the_sizehints -> x = window_left; -the_sizehints -> y = window_top; -the_sizehints ->width = window_width; -the_sizehints ->height = window_height; -the_sizehints ->flags = PPosition|PSize; /*program chose */ - - -/* -** Set up standard window preperties -** -*/ -XSetStandardProperties(the_display,window, - "Xlib1", /*window name */ - "Xlib1", /*icon name */ - (Pixmap) None, /*icon pixmap */ - argv,argc, - the_sizehints); - -free (the_sizehints); - -/* -** Ask for Expose and mouse input ( not necessary right now) -** -*/ -/*XSelectInput(the_display,window,ButtonPressMask|ExposureMask);*/ - - -/* -** create a graphic context to draw with -** -*/ -gc = XCreateGC(the_display,window,0L,(XGCValues*) NULL); -XSetForeground(the_display,gc,BlackPixel(the_display,the_screen)); - -/* -** Make window appear on the screen -** -*/ -XMapWindow(the_display,window); -XFlush(the_display); - - -} -#endif - -} -/**********************************************************************/ - - End of windows.c echo makefile 1>&2 sed 's/^-//' >makefile <<'End of makefile' -# use -g flags on all gcc commands to use the dbx debugger. -#OPTIMIZE = -O -finline_functions -#DEBUG = -g -#PROFILE = -pg -CFLAGS = $(OPTIMIZE) $(DEBUG) $(PROFILE) - -CC = gcc - -LDFLAGS = -static -LIBS = -lm -lX11 -OBJS = calculations.o steiner2.o steiner3.o steiner4.o steiner5.o \ - foo.o globals.o graphics.o windows.o misc.o main.o - -s: geometry.h $(OBJS) - $(CC) $(LDFLAGS) $(CFLAGS) -o s $(OBJS) $(LIBS) - -clean : - rm -f s $(OBJS) - -new : clean s - -tags : - etags *.c - -calculations.o: calculations.c geometry.h - -steiner2.o: steiner2.c geometry.h - -steiner3.o: steiner3.c geometry.h - -steiner4.o: steiner4.c geometry.h - -steiner5.o: steiner5.c geometry.h - -foo.o: foo.c geometry.h - -globals.o: globals.c geometry.h - -graphics.o: graphics.c geometry.h - -windows.o: windows.c geometry.h - -main.o: main.c geometry.h - -misc.o: misc.c geometry.h - End of makefile