Category: C# Computer Programming Language

namespace HamiltonianCircuit
{
    class Algorithm
    {
        // code from C/C++
        // http://www.geeksforgeeks.org/backtracking-set-7-hamiltonian-cycle/

        // A utility function to check if the vertex v can be added at
        // index 'pos' in the Hamiltonian Cycle constructed so far (stored
        // in 'path[]')

        private bool IsSafe(int v, bool[,] graph, int[] path, int pos)
        {
            /* Check if this vertex is an adjacent vertex of the previously
               added vertex. */
            if (!graph[path[pos - 1], v])
                return false;

            /* Check if the vertex has already been included.
              This step can be optimized by creating an array of size V */
            for (int i = 0; i < pos; i++)
                if (path[i] == v)
                    return false;

            return true;
        }

        /* A recursive utility function to solve hamiltonian cycle problem */
        private bool HamCycleUtil(bool[,] graph, int V, int[] path, int pos)
        {
            /* base case: If all vertices are included in Hamiltonian Cycle */
            if (pos == V)
            {
                // And if there is an edge from the last included vertex to the
                // first vertex
                if (graph[path[pos - 1], path[0]])
                    return true;
                else
                    return false;
            }

            // Try different vertices as a next candidate in Hamiltonian Cycle.
            // We don't try for 0 as we included 0 as starting point in in hamCycle()
            for (int v = 1; v < V; v++)
            {
                // Check if this vertex can be added to Hamiltonian Cycle

                if (IsSafe(v, graph, path, pos))
                {
                    path[pos] = v;

                    // recur to construct rest of the path

                    if (HamCycleUtil(graph, V, path, pos + 1))
                        return true;

                    // If adding vertex v doesn't lead to a solution,
                    // then remove it
                    path[pos] = -1;
                }
            }

            // If no vertex can be added to Hamiltonian Cycle constructed so far,
            // then return false
            return false;
        }

        // This function solves the Hamiltonian Cycle problem using Backtracking.
        // It mainly uses HamCycleUtil() to solve the problem. It returns false
        // if there is no Hamiltonian Cycle possible, otherwise return true and
        // prints the path. Please note that there may be more than one solutions,
        // this function prints one of the feasible solutions.
        public bool HamCycle(bool[,] graph, int V, out int[] path)
        {
            path = new int[V];

            for (int i = 0; i < V; i++)
                path[i] = -1;

           // Let us put vertex 0 as the first vertex in the path. If there is
           // a Hamiltonian Cycle, then the path can be started from any point
           // of the cycle as the graph is undirected

            path[0] = 0;

            if (HamCycleUtil(graph, V, path, 1) == false)
                return false;

            return true;
        }

    }
}

using System;
using System.Collections.Generic;

namespace HamiltonianCircuit
{
    class Edge : IComparable
    {
        public Vertex Lt { get; set; }
        public Vertex Rt { get; set; }
        public int Wt { get; set; }
        public Edge(Vertex lt, Vertex rt, int wt)
        {
            Lt = lt;
            Rt = rt;
            Wt = wt;
        }

        public int CompareTo(object obj)
        {
            Edge other = (Edge)obj;
            int c1 = Lt.CompareTo(other.Lt);
            int c2 = Rt.CompareTo(other.Rt);

            if (c1 != 0)
                return c1;

            if (c2 != 0)
                return c2;

            return Wt - other.Wt;
        }

        public bool InList(List<Edge> elist)
        {
            for (int i = 0; i < elist.Count; i++)
            {
                Edge e = elist[i];

                if (Lt == e.Lt && Rt == e.Rt)
                    return true;
            }

            return false;
        }
    }
}

using System;
using System.Collections.Generic;

namespace HamiltonianCircuit
{
    class Vertex : IComparable
    {
        public int Id { get; set; }
        public List<Edge> Edges { get; set; }
        public Vertex(int id)
        {
            Id = id;
        }

        public Vertex(int id, List<Edge> edges)
        {
            Id = id;
            Edges = edges;
        }

        public int CompareTo(object obj)
        {
            Vertex other = (Vertex)obj;

            return Id - other.Id;
        }
    }
}

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;

namespace HamiltonianCircuit
{
    public partial class MainForm : Form
    {
        private bool generate = true;
        private int n, x, y, x1, y1, x2, y2;
        private Algorithm algo = new Algorithm();
        private Color[] colors =
            {
            Color.Red,
            Color.Blue,
            Color.Green,
            Color.Orange,
            Color.Purple,
            Color.Brown,
            Color.Turquoise,
            Color.Violet,
            Color.Tan,
            Color.Plum,
            Color.Teal,
            Color.Yellow
            };
        private List<Edge> E, F;
        private List<Vertex> V;
        private Random random = new Random();
        private SolidBrush drawBrush;
        private Font drawFont;
        public MainForm()
        {
            InitializeComponent();
            panel1.Paint += new PaintEventHandler(panel1_Paint);
            drawBrush = new SolidBrush(Color.White);
        }

        void panel1_Paint(object sender, PaintEventArgs e)
        {
            if (generate)
                GenerateDraw(e.Graphics);

            else
                PathDraw(e.Graphics);
        }

        private void calculateXY(int id)
        {
            int Width = panel1.Width;
            int Height = panel1.Height;

            x = Width / 2 + (int)(Width * Math.Cos(2 * id * Math.PI / n) / 4.0);
            y = Height / 2 + (int)(Width * Math.Sin(2 * id * Math.PI / n) / 4.0);
        }

        private void PathDraw(Graphics g)
        {
            if (V != null)
            {
                GenerateDraw(g);

                int divisor = 1;
                int Width = panel1.Width;
                int Height = panel1.Height;
                Pen pen = new Pen(Color.Red);

                n = V.Count;

                for (int i = 0; i < F.Count; i++)
                {
                    Vertex u = F[i].Lt, v = F[i].Rt;

                    calculateXY(u.Id);
                    x1 = x + (Width / 2) / n / 2;
                    y1 = y + (Width / 2) / n / 2;
                    calculateXY(v.Id);
                    x2 = x + (Width / 2) / n / 2;
                    y2 = y + (Width / 2) / n / 2;
                    g.DrawLine(pen, x1, y1, x2, y2);
                }

                if (n >= 4 && n <= 5)
                    divisor = 16;
                else if (n >= 6 && n <= 8)
                    divisor = 24;
                else if (n >= 9 && n <= 10)
                    divisor = 32;

                drawFont = new Font("Arial", Width / divisor);

                for (int i = 0; i < n; i++)
                {
                    Vertex u = V[i];
                    SolidBrush brush = new SolidBrush(colors[u.Id]);

                    calculateXY(u.Id);
                    g.FillEllipse(brush, x, y, (Width / 2) / n, (Width / 2) / n);

                    if (n >= 4 && n <= 10)
                        g.DrawString(i.ToString(), drawFont, drawBrush, x + 4, y + 4);
                }
            }
        }

        private void GenerateDraw(Graphics g)
        {
            if (V != null)
            {
                int divisor = 1;
                int Width = panel1.Width;
                int Height = panel1.Height;
                Pen pen = new Pen(Color.Black);

                n = V.Count;

                for (int i = 0; i < n; i++)
                {
                    Vertex u = V[i];

                    calculateXY(u.Id);
                    x1 = x + (Width / 2) / n / 2;
                    y1 = y + (Width / 2) / n / 2;

                    if (u.Edges != null)
                    {
                        for (int j = 0; j < u.Edges.Count; j++)
                        {
                            Vertex v = u.Edges[j].Rt;

                            calculateXY(v.Id);
                            x2 = x + (Width / 2) / n / 2;
                            y2 = y + (Width / 2) / n / 2;
                            g.DrawLine(pen, x1, y1, x2, y2);
                        }
                    }
                }

                if (n >= 4 && n <= 5)
                    divisor = 16;
                else if (n >= 6 && n <= 8)
                    divisor = 24;
                else if (n >= 9 && n <= 10)
                    divisor = 32;

                drawFont = new Font("Arial", Width / divisor);

                for (int i = 0; i < n; i++)
                {
                    Vertex u = V[i];
                    SolidBrush brush = new SolidBrush(colors[u.Id]);

                    calculateXY(u.Id);
                    g.FillEllipse(brush, x, y, (Width / 2) / n, (Width / 2) / n);
                    
                    if (n >= 4 && n <= 10)
                        g.DrawString(i.ToString(), drawFont, drawBrush, x + 4, y + 4);
                }
            }
        }

        private void button1_Click(object sender, EventArgs e)
        {
            generate = true;
            button2.Enabled = true;

            int numVers = (int)numericUpDown1.Value;

            E = new List<Edge>();
            V = new List<Vertex>();

            for (int i = 0; i < numVers; i++)
            {
                Vertex v = new Vertex(i);

                v.Edges = new List<Edge>();
                V.Add(v);
            }

            for (int i = 0; i < numVers; i++)
            {
                int numEdges = random.Next(numVers - 1);

                while (numEdges < 2)
                    numEdges = random.Next(numVers - 1);

                Vertex v = V[i];

                for (int j = 0; j < numEdges; j++)
                {
                    int id = random.Next(numVers);
                    int wt = random.Next(100);
                    Edge edge;

                    while (wt < 10)
                        wt = random.Next(100);

                    while (id == v.Id)
                        id = random.Next(numVers);

                    edge = new Edge(v, V[id], wt);

                    if (!edge.InList(E))
                        E.Add(edge);

                    edge = new Edge(V[id], v, wt);

                    if (!edge.InList(E))
                        E.Add(edge);
                }
            }

            for (int i = 0; i < E.Count; i++)
            {
                Vertex u = E[i].Lt, v = E[i].Rt;

                u.Edges.Add(new Edge(u, v, E[i].Wt));
                v.Edges.Add(new Edge(v, u, E[i].Wt));
            }

            for (int i = 0; i < V.Count; i++)
            {
                if (V[i].Edges.Count == 0)
                {
                    MessageBox.Show("Generate a new graph", "Warning Message",
                        MessageBoxButtons.OK, MessageBoxIcon.Warning);
                    return;
                }
            }

            textBox1.Text = string.Empty;
            textBox1.Text = "Edges(u, v)\r\n";
            textBox1.Text += " u  v wt\r\n";

            for (int i = 0; i < E.Count; i++)
            {
                textBox1.Text += E[i].Lt.Id.ToString().PadLeft(2) + " ";
                textBox1.Text += E[i].Rt.Id.ToString().PadLeft(2) + " ";
                textBox1.Text += E[i].Wt.ToString().PadLeft(2) + "\r\n";
            }

            panel1.Invalidate();
        }

        private void button2_Click(object sender, EventArgs e)
        {
            generate = false;

            Algorithm algo = new Algorithm();

            int n = V.Count;
            bool[,] graph = new bool[n, n];
            int[] ipath;

            for (int i = 0; i < E.Count; i++)
            {
                Edge edge = E[i];
                Vertex u = edge.Lt, v = edge.Rt;

                graph[u.Id, v.Id] = true;
            }

            if (!algo.HamCycle(graph, n, out ipath))
            {
                MessageBox.Show("No Hamilton circuit exists", "Warning Message",
                        MessageBoxButtons.OK, MessageBoxIcon.Warning);
                return;
            }

            textBox1.Text += "\r\n";
            textBox1.Text += "Edges(u, v)\r\n";
            textBox1.Text += " u  v wt\r\n";

            Vertex[] path = new Vertex[n];
            int tcost = 0;

            F = new List<Edge>();

            for (int i = 0; i < n - 1; i++)
            {
                Vertex u = V[ipath[i]], v = V[ipath[i + 1]];
                Edge edge = new Edge(u, v, 0);

                for (int j = 0; j < E.Count; j++)
                {
                    if (edge.Lt == E[j].Lt && edge.Rt == E[j].Rt)
                    {
                        edge.Wt = E[j].Wt;
                        tcost += edge.Wt;
                        break;
                    }
                }

                F.Add(edge);
                textBox1.Text += u.Id.ToString().PadLeft(2) + " ";
                textBox1.Text += v.Id.ToString().PadLeft(2) + " ";
                textBox1.Text += edge.Wt.ToString().PadLeft(2) + "\r\n";
            }

            Vertex up = V[ipath[n - 1]], vp = V[0];

            Edge edgep = new Edge(up, vp, 0);

            for (int j = 0; j < E.Count; j++)
            {
                if (edgep.Lt == E[j].Lt && edgep.Rt == E[j].Rt)
                {
                    edgep.Wt = E[j].Wt;
                    tcost += edgep.Wt;
                    break;
                }
            }

            F.Add(edgep);
            textBox1.Text += up.Id.ToString().PadLeft(2) + " ";
            textBox1.Text += vp.Id.ToString().PadLeft(2) + " ";
            textBox1.Text += edgep.Wt.ToString().PadLeft(2) + "\r\n";

            textBox1.Text += "Cost = " + tcost + "\r\n";
            panel1.Invalidate();
        }
    }
}