Listing

The complete listing is:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Windows;
using System.Windows.Controls;
using System.Windows.Data;
using System.Windows.Documents;
using System.Windows.Input;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using System.Windows.Navigation;
using System.Windows.Shapes;

namespace Prim
{

 public partial class MainWindow : Window
 {
  const int size = 10;
  private Point[] Positions = new Point[size];
  private Single[,] Network =
                       new Single[size, size];
  private Random R = new Random();

  public MainWindow()
  {
   InitializeComponent();
  }
 
  private void setnet(Single[,] Net, Point[] Pos)
  {
   int maxlength = (int)(Math.Min(canvas1.Width,
                           canvas1.Height) * 0.9);
   int minlength = maxlength / size;
   for (int i = 0; i < size; i++)
   {
    Pos[i].X = R.Next(minlength, maxlength);
    Pos[i].Y = R.Next(minlength, maxlength);
    for (int j = 0; j <= i; j++)
    {
     Net[i, j] = distance(Pos[i], Pos[j]);
     Net[j, i] = Net[i, j];
     if (i == j) Net[i, j] = 0;
    }
   }
  }

  private Single distance(Point a, Point b)
  {
   return (Single)Math.Sqrt((a.X - b.X) *
                               (a.X - b.X) +
                                (a.Y - b.Y) *
                                 (a.Y - b.Y));
  }

  private void shownet(Single[,] Net)
  {
   canvas1.Children.Clear();
   Line myLine;
   for (int i = 0; i < size; i++)
   {
    for (int j = 0; j < i; j++)
    {
     if (Net[i, j] != 0)
     {
      myLine = new Line();
      myLine.Stroke = Brushes.Black;
      myLine.X1 = Positions[i].X;
      myLine.X2 = Positions[j].X;
      myLine.Y1 = Positions[i].Y;
      myLine.Y2 = Positions[j].Y;
      myLine.StrokeThickness = 1;
      canvas1.Children.Add(myLine);
     }
    }
   }

   Rectangle myMarker;
   for (int i = 0; i < size; i++) 
   {
    myMarker = new Rectangle();
    myMarker.Stroke = Brushes.Black;
    myMarker.Fill = Brushes.Red;
    myMarker.Height = 10;
    myMarker.Width = 10;
    myMarker.SetValue(Canvas.TopProperty,
          Positions[i].Y - myMarker.Height / 2);
    myMarker.SetValue(Canvas.LeftProperty,
          Positions[i].X - myMarker.Width / 2);
    canvas1.Children.Add(myMarker);
   }
  }

  private void button_Click(object sender,
                             RoutedEventArgs e)
  {
   canvas1.Width = 600;
   canvas1.Height = 600;
   setnet(Network, Positions);
   shownet(Network);
  }

  private void Find_MST_Click(object sender, 
                             RoutedEventArgs e)
  {
   prims();
  }

  void prims()
  {
   int[] included = new int[size]; 
   int[] excluded = new int[size];
   Single[,] finished = new Single[size, size];
   int start = 0;
   int finish = 0;
   for (int i = 0; i < size; i++)

   {
    excluded[i] = i;
    included[i] = -1;
   }
   included[0] = excluded[R.Next(size)];
   excluded[included[0]] = -1;
   for (int n = 1; n < size; n++)
   {
    closest(n, ref start, ref finish,
                          included, excluded);
    included[n] = excluded[finish];
    excluded[finish] = -1;
    finished[included[n], included[start]] =
          Network[included[n], included[start]];
    finished[included[start], included[n]] =
          Network[included[start], included[n]];
   }
   shownet(finished);
  }

  private void closest(int n, ref int start,
    ref int finish,int[] included, int[] excluded)
  {
   Single smallest = -1;
   for (int i = 0; i < n; i++)
   {
    for (int j = 0; j < size; j++)
    {
     if (excluded[j] == -1) continue;
     if (smallest == -1) smallest =
          Network[included[i], excluded[j]];
     if (Network[included[i], excluded[j]] >
                            smallest) continue;
     smallest = Network[included[i], excluded[j]];
      start = i;
      finish = j;
     }
    }
   }
  }
 }

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

<ASIN:1584885491>