Click here to Skip to main content
12,702,455 members (35,889 online)
Click here to Skip to main content

Tagged as

Stats

105.9K views
9.2K downloads
68 bookmarked
Posted

Kruskal Algorithm

, 5 Jul 2012 CPOL
Implementation of Kruskal Algorithm in C#
KruskalAlgorithm
Client
bin
Debug
Client.exe
Client.pdb
Client.vshost.exe
Client.vshost.exe.manifest
Kruskal.dll
Kruskal.pdb
KruskalAlgorithm.exe
KruskalAlgorithm.vshost.exe.manifest
Release
obj
x86
Debug
Client.exe
Client.pdb
Client.Properties.Resources.resources
DesignTimeResolveAssemblyReferencesInput.cache
GenerateResource.read.1.tlog
GenerateResource.write.1.tlog
Kruskal.frmCost.resources
Kruskal.frmMain.resources
TempPE
Properties.Resources.Designer.cs.dll
Properties
Kruskal
bin
Debug
Kruskal.dll
Kruskal.pdb
Release
Contracts
Entities
Implementation
obj
Debug
DesignTimeResolveAssemblyReferencesInput.cache
Kruskal.dll
Kruskal.pdb
TempPE
Properties
KruskalAlgorithm.sln.docstates.suo
KruskalAlgorithm.suo
KruskalAlgorithm.vsmdi
Local.testsettings
TestResults
Omar_OMAR-PC 2012-07-02 14_38_22.trx
Omar_OMAR-PC 2012-07-02 18_16_57.trx
Omar_OMAR-PC 2012-07-02 18_20_20.trx
Omar_OMAR-PC 2012-07-02 18_20_27.trx
Omar_OMAR-PC 2012-07-02 18_23_20.trx
Omar_OMAR-PC 2012-07-02 18_23_20
In
OMAR-PC
Out
AgentRestart.dat
Omar_OMAR-PC 2012-07-02 18_24_35.trx
Omar_OMAR-PC 2012-07-02 18_24_35
In
OMAR-PC
Out
AgentRestart.dat
Omar_OMAR-PC 2012-07-02 18_27_14.trx
Omar_OMAR-PC 2012-07-02 18_27_14
In
OMAR-PC
Out
AgentRestart.dat
Omar_OMAR-PC 2012-07-02 18_29_28.trx
Omar_OMAR-PC 2012-07-02 18_29_28
In
OMAR-PC
Out
AgentRestart.dat
Omar_OMAR-PC 2012-07-03 15_36_58.trx
Omar_OMAR-PC 2012-07-03 15_38_50.trx
Omar_OMAR-PC 2012-07-03 15_38_50
In
OMAR-PC
Out
AgentRestart.dat
Omar_OMAR-PC 2012-07-03 15_43_17.trx
Omar_OMAR-PC 2012-07-03 15_43_17
In
OMAR-PC
Out
AgentRestart.dat
Omar_OMAR-PC 2012-07-03 15_45_42.trx
Omar_OMAR-PC 2012-07-03 15_46_25.trx
Omar_OMAR-PC 2012-07-03 15_46_25
In
OMAR-PC
Out
AgentRestart.dat
Omar_OMAR-PC 2012-07-03 16_06_02.trx
Omar_OMAR-PC 2012-07-03 16_06_05.trx
Omar_OMAR-PC 2012-07-03 16_06_05
In
OMAR-PC
Out
AgentRestart.dat
Omar_OMAR-PC 2012-07-03 16_08_00.trx
Omar_OMAR-PC 2012-07-03 16_08_00
In
OMAR-PC
Out
AgentRestart.dat
Omar_OMAR-PC 2012-07-03 16_08_16.trx
Omar_OMAR-PC 2012-07-03 16_08_16
In
OMAR-PC
Out
AgentRestart.dat
Omar_OMAR-PC 2012-07-03 16_10_25.trx
Omar_OMAR-PC 2012-07-03 16_10_25
In
OMAR-PC
Out
AgentRestart.dat
Omar_OMAR-PC 2012-07-03 16_11_27.trx
Omar_OMAR-PC 2012-07-03 16_11_27
In
OMAR-PC
Out
AgentRestart.dat
Omar_OMAR-PC 2012-07-03 16_13_46.trx
Omar_OMAR-PC 2012-07-03 16_16_19.trx
Omar_OMAR-PC 2012-07-03 16_16_46.trx
Omar_OMAR-PC 2012-07-05 20_04_47.trx
Omar_OMAR-PC 2012-07-05 20_08_10.trx
Omar_OMAR-PC 2012-07-05 20_08_33.trx
TraceAndTestImpact.testsettings
UnitTests
AlgorithmTest
bin
Debug
Kruskal.dll
Kruskal.pdb
Kruskal_Accessor.dll
Kruskal_Accessor.pdb
UnitTests.dll
UnitTests.pdb
Release
EntitiesTest
obj
Debug
DesignTimeResolveAssemblyReferencesInput.cache
Kruskal_Accessor.dll
Kruskal_Accessor.pdb
ResolveAssemblyReference.cache
TempPE
UnitTests.dll
UnitTests.pdb
Properties
Test References
Kruskal.accessor
KruskalDemo
KruskalAlgorithm.exe
KruskalAlgorithm.pdb
KruskalAlgorithm.vshost.exe
KruskalAlgorithm.vshost.exe.manifest
KruskalAlgorithm.suo
KruskalAlgorithm
bin
Debug
KruskalAlgorithm.exe
KruskalAlgorithm.vshost.exe
KruskalAlgorithm.vshost.exe.manifest
Release
Properties
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 KruskalAlgorithm
{
    public partial class frmMain : Form
    {
        public frmMain()
        {
            InitializeComponent();
            Clear();
        }

        #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<Vertex> m_lstVertices;
        List<Edge> m_lstEdgesInitial, m_lstEdgesFinal;

        Vertex 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)
                    {
                        frmCost formCost = new frmCost();
                        formCost.ShowDialog();

                        Point pStringPoint = GetStringPoint(m_vFirstVertex.pPosition, m_vSecondVertex.pPosition);
                        m_lstEdgesInitial.Add(new Edge(m_vFirstVertex, m_vSecondVertex, formCost.m_nCost, pStringPoint));
                        panel1.Invalidate();
                    }
                }
            }
            else
            {
                m_lstVertices.Add(new Vertex(m_lstVertices.Count, pClicked));
                panel1.Invalidate();
            }
        }

        private void panel1_Paint(object sender, PaintEventArgs e)
        {
            Graphics g = e.Graphics;
            DrawVertices(g);
            DrawEdges(g);
            g.Dispose();
        }

        private void btnSolve_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
                {
                    btnSolve.Enabled = false;
                    int nTotalCost = 0;
                    m_lstEdgesFinal = SolveGraph(ref nTotalCost);
                    m_bSolved = true;
                    panel1.Invalidate();
                    MessageBox.Show("Total Cost:" + nTotalCost.ToString(), "Solution", MessageBoxButtons.OK, MessageBoxIcon.Information);
                }
            }
        }

        private void btnClear_Click(object sender, EventArgs e)
        {
            DialogResult dr = MessageBox.Show("Clear form ?", "Alert", MessageBoxButtons.YesNo, MessageBoxIcon.Exclamation);
            if (dr == DialogResult.Yes)
            {
                btnSolve.Enabled = true;
                Graphics g = panel1.CreateGraphics();
                g.Clear(panel1.BackColor);
                Clear();
            }
        }
        #endregion

        #region Methods

        #region Drawing

        private void DrawEdges(Graphics g)
        {
            Pen P = new Pen(m_colEdge);
            List<Edge> lstEdges = m_bSolved ? m_lstEdgesFinal : m_lstEdgesInitial;
            foreach (Edge 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 (Vertex 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 Vertex GetSelectedVertex(Point pClicked)
        {
            Vertex vReturn = null;
            double dDistance;
            foreach (Vertex 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 Clear()
        {
            m_lstVertices = new List<Vertex>();
            m_lstEdgesInitial = new List<Edge>();
            m_bSolved = false;
            m_vFirstVertex = m_vSecondVertex = null;
        }

        private List<Edge> SolveGraph(ref int nTotalCost)
        {
            Edge.QuickSort(m_lstEdgesInitial, 0, m_lstEdgesInitial.Count - 1);
            List<Edge> lstEdgesRetun = new List<Edge>(m_lstEdgesInitial.Count);
            foreach (Edge ed in m_lstEdgesInitial)
            {
                Vertex vRoot1, vRoot2;
                vRoot1 = ed.V1.GetRoot();
                vRoot2 = ed.V2.GetRoot();
                if (vRoot1.Name != vRoot2.Name)
                {
                    nTotalCost += ed.Cost;
                    Vertex.Join(vRoot1, vRoot2);
                    lstEdgesRetun.Add(new Edge(ed.V1, ed.V2, ed.Cost, ed.StringPosition));
                }
            }
            return lstEdgesRetun;
        }
        #endregion
    }
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Omar Gameel Salem
Software Developer
Australia Australia
Enthusiastic programmer/researcher, passionate to learn new technologies, interested in problem solving, data structures, algorithms, AI, machine learning and nlp.

Amateur guitarist/ keyboardist, squash player.

You may also be interested in...

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.170118.1 | Last Updated 5 Jul 2012
Article Copyright 2011 by Omar Gameel Salem
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid