/**********************************************************************/
/*                                                                    */
/*            (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.       */
/*                                                                    */
/**********************************************************************/

/**********************************************************************/
/*                      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<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 < current_MST_cost) 
          { 
           nsp++;
           current_MST_cost = mst_cost;
/*           delete_useless_SPs(3, actual_number_of_points); */
           if(GRAPHICS) draw_point(pointset[number_of_points - 1].X,
                                   pointset[number_of_points - 1].Y, size-1);
           number_of_points++;
         }
      }

number_of_points--;
generate_MST2();
if(GRAPHICS == YES) draw_edges();

for(k=actual_number_of_points;k<number_of_points;k++)
   if(GRAPHICS) draw_point(pointset[k].X, pointset[k].Y, size+3);

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

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

/*
int delete_useless_SPs(int h_num, int actual_nop)
{
int  old_mst_cost;
int    k, ptr1, ptr2;

generate_MST();
old_mst_cost = mst_cost;

ptr1 = actual_nop;
for(ptr2=actual_nop; ptr2 < number_of_points; ptr2++)
   if(vertices[ptr2].neighbor_count > 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<number_of_points;k++)
       printf("%d:(%d,%d):%d, ", k, pointset[k].X, pointset[k].Y,
              vertices[k].neighbor_count);
   printf("\n");
   }
}   

*/