Minimum Spanning Tree
Written by Mike James   
Monday, 04 January 2010
Article Index
Minimum Spanning Tree
Prim's algorithm
Implementing Prim's algorithm

 

How do you find a minimum spanning tree given a network? It turns out that there are two general algorithms – Prim's and Kruskal's. Of the two Prim's is the easier to implement and to understand, so it makes a very good starting place to understand any graph algorithm. It is also an excellent example of a "greedy" algorithm, i.e one that always takes the best option at each step, that actually works!

Prim's algorithm

This algorithm was developed in 1930 by Czech mathematician Vojtěch Jarník and independently in 1957 by computer scientist Robert C. Prim and was rediscovered by Edsger Dijkstra in 1959:

0) Place all of the vertices in an "excluded" set and initialise an "included" set to be empty.
1) Select any vertex as the starting vertex of the tree. Place this vertex in the "included" set.
2) Find a vertex which is closest to any vertex in the "included" set. If there is more than one such vertex select one at random.
3) Repeat 1 and 2 until all of the vertices are in the included set and the excluded set is empty.

The result is a minimum spanning tree – as long as you remember to store which path between which pair of nodes was the shortest distance at each step!

Making it work

The above may seem simple but there are some interesting problems in implementing any graph algorithm using C#.

The first is how are we to represent a graph or network. The simplest solution is to use a two-dimensional array to record the distance between each node. For example:

 Network[a,b];

would be used to store the distance between vertex a and vertex b. Notice that this matrix is symmetric and the diagonal is zero because the distance between "a" and "a" is zero.

The next problem is how to generate a network to try the algorithm out on?

In a real world problem the network would be entered as data to the array but it is a common requirement to generate valid examples of any data structure that a program is working with.

In this case the problem isn't difficult in that all we have to do is generate a set of random numbers between particular limits and make sure that the array is symmetrical and has a zero diagonal. This would produce a fully connected network which is difficult to represent graphically. To produce something that had fewer connections per vertex it would be necessary to set to zero entries picked at random.

While on the subject of representing the network graphically it is worth commenting that the distances in the network matrix don't have to be Euclidean distances. For example they might well be costs or subjective judgements. The algorithm works even if the distances aren't Euclidean but you can't draw the vertices in a 2D space with the given distances between them. This is a problem only if we want a to produce a graphical display – but in this case we do!

The solution is to work the other way around. First generate the vertices as random points in a 2D space and then work out the distances between them to store in the network matrix. If we also keep the locations of the points then drawing the network is even easier.

I did consider implementing a fully object-oriented version of the algorithm but this seems to go against the idea of a "classic" algorithm. The object-oriented approach works well when the problem breaks down into natural groupings of methods and property but it is often less good at representing algorithms. In this case the focus is on the algorithm, i.e. exactly how the code implements the idea, and this is best achieved by breaking the algorithm down into functions.

Starting with a new C# WPF project we need to add a button labelled "Generate Network" and a Canvas object. A Canvas object is often a good thing to use when you need to draw using x,y co-ordinates but there are other ways of doing the same job.

Moving to the code. We need an array to hold the co-ordinates of the points:

 private Point[] Positions = 
new Point[size];

size is a constant that sets the size of the network in number of vertices.

 const int size = 10;

The array to hold the network data can be defined as

private Single[,] Network = 
new Single[size, size];

We are also going to need a random number generator throughout the program so creating a global object is a good idea:

private Random R = new Random();

We can now write a subroutine that fills both Position and Network with random values:

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

The points are generated randomly with co-ordinates between minlength and maxlength which are derived from the size of the Canvas object.

Notice that the distance array is made to be symmetric and the diagonal is also set to zero. The distance between points is computed using an additional function.

The distance function is simply the usual Euclidean formula:

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

Recall that C# has no power operator and simply multiplying things together is better than having to use the Maths object to square a value.

After generating the network it would be nice to view it. A drawing routine is quite easy – as long as you don't worry too much about efficiency. We can simply use Line objects to draw lines on the Canvas.

First we clear the Canvas of any child nodes it may already contain:

 private void shownet(Single[,] Net)
{
canvas1.Children.Clear();

Next we create a new Line object for each pair of points that have a non-zero distance between them:

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

Next we can plot suitable marker shapes at the position of each node:

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

Notice the way the that the position of the rectangle is set using an attached property on the Canvas object. This is a feature of WPF that beginners often find difficult. Attached properties are a good idea from the implementation point of view but they often don't help with readability and clarity. You might also ask why the Line object sets its own position without the need for an attached property and yet most of the other WFP shapes can't.

To try these out place a button on the form, if you already haven't and enter the following as the button's click routine:

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

You can now try the program out and see if it really does generate reasonable graphs. It should! You can size the canvas control to make best use of the space and the graph will adjust itself to fill it, more or less. It is fun just to see the range of graphs that can be produced.

network
A typical random graph with ten vertices

<ASIN:1565924533>

<ASIN:1584883960>

 



Last Updated ( Wednesday, 31 March 2010 )
 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.