This post is essentially a blatant lifting of Omar Gamil’s CodeProject article on the same subject. I have been using the project as means of getting into C# programming and using things like Windows Forms etc in Visual Studio environments for the first time. Lots of screen shots and code samples have been included as a means of showing the reader how to create such a project from A to B. For a good explanation of what Kruskal is and how it works, you could do worse than to visit the Wiki Page on it. In a nutshell, Kruskal is used to find the set of links in a network such that their overall weight is minimized, while avoiding network cycles (loops) in the solution.
VS 2008 C# project downloadable from here.
Create a new Windows Forms Application
Set the Form Properties
In the main form that get created, right click on it and set its properties, such as name etc. I also chose to rename the default name from Form1 to Kruskal:
Open up the toolbox, select a panel control, drag it over to your form, and resizing it as necessary. Feel free to set any other properties, in this example I have let them all as defaults:
Using the toolbox dialog again, select the button control and create two new ones. Right-click on them and set their text/name properties to “Solve” and “Clear” as shown:
Double-click on the “Solve” button and double-click on the “Clear” button in order to generate their respective event handling codes:
private void Solve_Click(object sender, EventArgs e)
{
}
private void Clear_Click(object sender, EventArgs e)
{
}
Create another, smaller windows form with which we can use to modify the link connection weights. Right-click on your project folder, select Add -> New Item… -> Visual C# Items -> Windows Form. Name your form as Cost.cs and click the Add button:
On your newly added Cost form, add a text edit control and a button. You may wish to rename the button text to “OK”, resize the form etc in the way shown:
Double-click the OK button to generate the event handling code as shown:
private void OK_Click(object sender, EventArgs e)
{
}
Implement the Graph Modelling code
Create the C# class to implement tha handling of network links. Right-click the project folder, and select Add -> New Item -> Visual C# Items -> Code and name the class as “Link.cs”.
Repeat the above by adding a class named “Node.cs”. Go to the Link.cs code and copy the following code which is used to implement the sorting of links according to weight, return link end nodes etc:
class Link : IComparable
{
#region Members
Node v1, v2;
int nCost;
System.Drawing.Point pStringPosition;
#endregion
#region Properties
public Node V1
{
get
{
return v1;
}
}
public Node V2
{
get
{
return v2;
}
}
public int Cost
{
get
{
return nCost;
}
}
public System.Drawing.Point StringPosition
{
get
{
return pStringPosition;
}
}
#endregion
public Link(Node v1, Node v2, int nCost, System.Drawing.Point pStringPosition)
{
this.v1 = v1;
this.v2 = v2;
this.nCost = nCost;
this.pStringPosition = pStringPosition;
}
#region IComparable Members
public int CompareTo(object obj)
{
Link e = (Link)obj;
return this.nCost.CompareTo(e.nCost);
}
#endregion
internal static void QuickSort(List<Link> m_lstEdgesInitial, int nLeft, int nRight)
{
int i, j, x;
i = nLeft; j = nRight;
x = m_lstEdgesInitial[(nLeft + nRight) / 2].Cost;
do
{
while ((m_lstEdgesInitial[i].Cost < x) && (i < nRight)) i++;
while ((x < m_lstEdgesInitial[j].Cost) && (j > nLeft)) j--;
if (i <= j)
{
Link y = m_lstEdgesInitial[i];
m_lstEdgesInitial[i] = m_lstEdgesInitial[j];
m_lstEdgesInitial[j] = y;
i++; j--;
}
} while (i <= j);
if (nLeft < j) QuickSort(m_lstEdgesInitial, nLeft, j);
if (i < nRight) QuickSort(m_lstEdgesInitial, i, nRight);
}
}
Go to the “Node.cs” class code and insert the following code needed to set the node properties and “Join” end nodes:
class Node
{
#region Members
int nName;
public int nRank;
public Node vRoot;
public System.Drawing.Point pPosition;
#endregion
#region Properties
public int Name
{
get
{
return nName;
}
}
#endregion
public Node(int nName, System.Drawing.Point pPosition)
{
this.nName = nName;
nRank = 0;
this.vRoot = this;
this.pPosition = pPosition;
}
#region Methods
internal Node GetRoot()
{
if (this.vRoot != this)// am I my own parent ? (am i the root ?)
{
this.vRoot = this.vRoot.GetRoot();// No? then get my parent
}
return this.vRoot;
}
internal static void Join(Node vRoot1, Node vRoot2)
{
if (vRoot2.nRank < vRoot1.nRank)//is the rank of Root2 less than that of Root1 ?
{
vRoot2.vRoot = vRoot1;//yes! then Root1 is the parent of Root2 (since it has the higher rank)
}
else //rank of Root2 is greater than or equal to that of Root1
{
vRoot1.vRoot = vRoot2;//make Root2 the parent
if (vRoot1.nRank == vRoot2.nRank)//both ranks are equal ?
{
vRoot1.nRank++;//increment one of them, we need to reach a single root for the whole tree
}
}
}
#endregion
}
Right-click on the Code form you created earlier, and select “View Code”. Insert the code needed to implement the event handling when the user clicks the OK button and add a member variable for hold the cost value:
public partial class Cost : Form
{
public int m_nCost;
public Cost()
{
InitializeComponent();
}
private void OK_Click(object sender, EventArgs e)
{
if (textCost.Text == string.Empty)
errorProvider1.SetError(textCost, "please enter value");
else
{
m_nCost = int.Parse(textCost.Text);
this.Close();
}
}
}
Implement the Kruskal’s Algorithm and drawing code:
Right-click on the main form you created first of all, select View Code. You will need to insert all the code needed to implement the drawing functions, event handling etc. This is the full code listing:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
namespace Kruskal
{
public partial class Kruskal : Form
{
public Kruskal()
{
InitializeComponent();
Reset();
}
#region Member Variables
const int m_nRadius = 20;
const int m_nHalfRadius = (m_nRadius / 2);
Color m_colVertex = Color.Aqua;
Color m_colEdge = Color.Red;
List<Node> m_lstVertices;
List<Link> m_lstEdgesInitial, m_lstEdgesFinal;
Node m_vFirstVertex, m_vSecondVertex;
bool m_bDrawEdge, m_bSolved;
#endregion
#region Events
private void panel1_MouseClick(object sender, MouseEventArgs e)
{
Point pClicked = new Point(e.X - m_nHalfRadius, e.Y - m_nHalfRadius);
if (Control.ModifierKeys == Keys.Control)//if Ctrl is pressed
{
if (!m_bDrawEdge)
{
m_vFirstVertex = GetSelectedVertex(pClicked);
m_bDrawEdge = true;
}
else
{
m_vSecondVertex = GetSelectedVertex(pClicked);
m_bDrawEdge = false;
if (m_vFirstVertex != null && m_vSecondVertex != null && m_vFirstVertex.Name != m_vSecondVertex.Name)
{
Cost formCost = new Cost();
formCost.ShowDialog();
Point pStringPoint = GetStringPoint(m_vFirstVertex.pPosition, m_vSecondVertex.pPosition);
m_lstEdgesInitial.Add(new Link(m_vFirstVertex, m_vSecondVertex, formCost.m_nCost, pStringPoint));
panelKruskal.Invalidate();
}
}
}
else
{
m_lstVertices.Add(new Node(m_lstVertices.Count, pClicked));
panelKruskal.Invalidate();
}
}
private void panel1_Paint(object sender, PaintEventArgs e)
{
Graphics g = e.Graphics;
DrawVertices(g);
DrawEdges(g);
g.Dispose();
}
// Find Minimal spanning tree using Kruskal
private void Solve_Click(object sender, EventArgs e)
{
if (m_lstVertices.Count > 2)
{
if (m_lstEdgesInitial.Count < m_lstVertices.Count - 1)
{
MessageBox.Show("Missing Edges", "Alert", MessageBoxButtons.OK, MessageBoxIcon.Exclamation);
}
else
{
Solve.Enabled = false;
int nTotalCost = 0;
m_lstEdgesFinal = SolveGraph(ref nTotalCost);
m_bSolved = true;
panelKruskal.Invalidate();
MessageBox.Show("Total Cost:" + nTotalCost.ToString(), "Solution", MessageBoxButtons.OK, MessageBoxIcon.Information);
}
}
}
// Clear the drawing area
private void Clear_Click(object sender, EventArgs e)
{
DialogResult dr = MessageBox.Show("Clear form ?", "Alert", MessageBoxButtons.YesNo, MessageBoxIcon.Exclamation);
if (dr == DialogResult.Yes)
{
Solve.Enabled = true;
Graphics g = panelKruskal.CreateGraphics();
g.Clear(panelKruskal.BackColor);
Reset();
}
}
#endregion
#region Methods
#region Drawing
private void DrawEdges(Graphics g)
{
Pen P = new Pen(m_colEdge);
List<Link> lstEdges = m_bSolved ? m_lstEdgesFinal : m_lstEdgesInitial;
foreach (Link e in lstEdges)
{
Point pV1 = new Point(e.V1.pPosition.X + m_nHalfRadius, e.V1.pPosition.Y + m_nHalfRadius);
Point pV2 = new Point(e.V2.pPosition.X + m_nHalfRadius, e.V2.pPosition.Y + m_nHalfRadius);
g.DrawLine(P, pV1, pV2);
DrawString(e.Cost.ToString(), e.StringPosition, g);
}
}
private void DrawString(string strText, Point pDrawPoint, Graphics g)
{
Font drawFont = new Font("Arial", 15);
SolidBrush drawBrush = new SolidBrush(Color.Black);
g.DrawString(strText, drawFont, drawBrush, pDrawPoint);
}
private void DrawVertices(Graphics g)
{
Pen P = new Pen(m_colVertex);
Brush B = new SolidBrush(m_colVertex);
foreach (Node v in m_lstVertices)
{
g.DrawEllipse(P, v.pPosition.X, v.pPosition.Y, m_nRadius, m_nRadius);
g.FillEllipse(B, v.pPosition.X, v.pPosition.Y, m_nRadius, m_nRadius);
DrawString(v.Name.ToString(), v.pPosition, g);
}
}
private Node GetSelectedVertex(Point pClicked)
{
Node vReturn = null;
double dDistance;
foreach (Node v in m_lstVertices)
{
dDistance = GetDistance(v.pPosition, pClicked);
if (dDistance <= m_nRadius)
{
vReturn = v;
break;
}
}
return vReturn;
}
private double GetDistance(Point pStart, Point pFinish)
{
return Math.Sqrt(Math.Pow(pStart.X - pFinish.X, 2) + Math.Pow(pStart.Y - pFinish.Y, 2));
}
private Point GetStringPoint(Point pStart, Point pFinish)
{
int X = (pStart.X + pFinish.X) / 2;
int Y = (pStart.Y + pFinish.Y) / 2;
return new Point(X, Y);
}
#endregion
private void Reset()
{
m_lstVertices = new List<Node>();
m_lstEdgesInitial = new List<Link>();
m_bSolved = false;
m_vFirstVertex = m_vSecondVertex = null;
}
private List<Link> SolveGraph(ref int nTotalCost)
{
Link.QuickSort(m_lstEdgesInitial, 0, m_lstEdgesInitial.Count - 1);
List<Link> lstEdgesRetun = new List<Link>(m_lstEdgesInitial.Count);
foreach (Link ed in m_lstEdgesInitial)
{
Node vRoot1, vRoot2;
vRoot1 = ed.V1.GetRoot();
vRoot2 = ed.V2.GetRoot();
if (vRoot1.Name != vRoot2.Name)
{
nTotalCost += ed.Cost;
Node.Join(vRoot1, vRoot2);
lstEdgesRetun.Add(new Link(ed.V1, ed.V2, ed.Cost, ed.StringPosition));
}
}
return lstEdgesRetun;
}
#endregion
}
}
In the Kruskal.Designer.cs code, or whatever you decided to name it, make sure the paint and mouse click event handlers have been included inside the InitializeComponent() method for the panel control you created:
this.panelKruskal.Location = new System.Drawing.Point(36, 37); this.panelKruskal.Name = "panelKruskal"; this.panelKruskal.Size = new System.Drawing.Size(372, 330); this.panelKruskal.TabIndex = 0; this.panelKruskal.Paint += new System.Windows.Forms.PaintEventHandler(this.panel1_Paint); this.panelKruskal.MouseClick += new System.Windows.Forms.MouseEventHandler(this.panel1_MouseClick);
Try it out!
You should now be in a position to build your program. When running, add nodes using left mouse button clicks:
To set links and link connect weights between node pairs, simply hold down the control button and left-click the two end nodes you are interested in. You will then see the small Cost form you created eariler to enter your values here. Keep repeating until you have added all the links required:
And click the “Solve” button to generate the Minimal Spanning Tree:
Full C# Kruskal Visual Studio project downloadable from here.
