/**********************************************************************/
/*                                                                    */
/*            (c) Copyright, 1997 by Professor Gabriel Robins         */
/*                                                                    */
/*      Department of Computer Science, University of Virginia        */
/*          Charlottesville, VA 22903-2442  (804) 982-2207            */
/*   robins@cs.virginia.edu    http://www.cs.virginia.edu/~robins/    */
/*                                                                    */
/*   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<actual_number_of_points;i++)
   for(j=0;j<actual_number_of_points;j++) if(i != j)
      {
      pointset[number_of_points - 1].X = pointset[i].X;
      pointset[number_of_points - 1].Y = pointset[j].Y;
      generate_MST2();
      if(mst_cost < lowest_MST_so_far) 
         {
         found_improvement = YES;
         SP = pointset[number_of_points - 1];
         lowest_MST_so_far = mst_cost;
         }
      }
if(found_improvement == YES)
   {
   nsp++;
   num_N_pts[heuristic_num][nsp]++;
   pre_improvement_mst_cost = lowest_MST_so_far;
   pointset[number_of_points - 1] = SP;
   if(GRAPHICS) draw_point(pointset[number_of_points - 1].X,
                           pointset[number_of_points - 1].Y, size+3);
   number_of_points--;
/*   delete_useless_SPs(2, actual_number_of_points); */
   number_of_points++;
   }
}

number_of_points--;
generate_MST2();
if(GRAPHICS == YES) 
   { 
   draw_edges();
   if(actual_number_of_points < number_of_points)
      for(i=actual_number_of_points;i<number_of_points;i++)
         draw_point(pointset[i].X, pointset[i].Y, size-1);
   }

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);
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]);

number_of_points = actual_number_of_points;
generate_MST2();
return(improvement_percent[heuristic_num]);
}

/**********************************************************************/

void qsort_N(int N[], int left, int right)
{
int i, last, t, m;

if(left>= 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<number_of_points;i++)
 for(j=0;j<vertices[i].neighbor_count;j++)
   mst_cost = mst_cost + geom_dist(vertices[i].v_num, 
                                   vertices[i].neighbors[j].vertex_number);
mst_cost = mst_cost / 2;
return(mst_cost);
}
*/