Simple attempt to solve the travelling salesman prob

Question

For practicing purposes, I created an application that attempts to find an optimal route between given points.

The algorithm is:

1. Connect two randomly selected points
2. Select a point that's still unconnected (let's call it A)
3. Find it's nearest connected neighbor (let's call it B, where C => B => D)
4. If the distance C => A is smaller than A => D save C => A => B => D, otherwise `C => B => A => D
5. repeat while there're unconnected points

I don't want to discuss the algorithm, I know that it doesn't actually solve the TSP. But I'm interested in hints how to make my code more structured, easier to read and modify or anything else that could be improved.

Interfaces

/Interfaces/IMapCreator.cs

using TravellingSalesmanProblem.Classes;

namespace TravellingSalesmanProblem.Interfaces
{
    public interface IMapCreator
    {
        Map CreateMap(string data);
    }
}

/Interfaces/IMapOptimizer.cs

using TravellingSalesmanProblem.Classes;

namespace TravellingSalesmanProblem.Interfaces
{
    public interface IMapOptimizer
    {
        void Optimize(Map map);
    }
}

Main classes

/Classes/Map.cs

using System.Collections.Generic;
using System.Linq;
using TravellingSalesmanProblem.Interfaces;

namespace TravellingSalesmanProblem.Classes
{
    public class Map
    {
        public IList<Point> Points { get; private set; }

        public Map() : this(new List<Point>()) { }

        public Map(IList<Point> points)
        {
            Points = points;
        }

        public Map AddPoint(Point point) {
            Points.Add(point);
            return this;
        }

        public Point GetPoint(int id)
        {
            return Points.Single(x => x.Id == id);
        }

        public void Optimize(IMapOptimizer optimizer)
        {
            optimizer.Optimize(this);
        }

        public float GetCostOfWholeRoute()
        {
            Point startingPoint = Points.First();
            float cost = startingPoint.OutgoingConnection.Cost;

            Point currentPoint = startingPoint.OutgoingConnection.To;
            while (currentPoint != startingPoint)
            {
                cost += currentPoint.OutgoingConnection.Cost;
                currentPoint = currentPoint.OutgoingConnection.To;
            }

            return cost;
        }
    }
}

/Classes/Connection.cs

namespace TravellingSalesmanProblem.Classes
{
    public class Connection
    {
        public Point From { get; private set; }
        public Point To { get; private set; }
        public float Cost { get; private set; }

        public Connection(Point from, Point to, float cost)
        {
            From = from;
            To = to;
            Cost = cost;
        }
    }
}

/Classes/Point.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace TravellingSalesmanProblem.Classes
{
    public class Point
    {
        public int Id { get; private set; }
        public IList<Connection> PossibleConnections { get; private set; }
        public Connection IncommingConnection { get; private set; }
        public Connection OutgoingConnection { get; private set; }

        public Point(int id) : this(id, new List<Connection>()) { }

        public Point(int id, IList<Connection> possibleConnections)
        {
            Id = id;
            PossibleConnections = possibleConnections;
        }

        public Point AddPossibleConnection(Connection connection)
        {
            PossibleConnections.Add(connection);
            return this;
        }

        /// <summary>
        /// Inserts a new point between an existing connection
        /// this => B becomes this => point > B
        /// </summary>
        public void ConnectTo(Point point)
        {
            //Is this not part of a connection?
            if (this.IncommingConnection == null)
            {
                CreateNewRouteTo(point);
            }
            else
            {
                InsertIntoExistingRoute(point);
            }
        }

        private void CreateNewRouteTo(Point point) {
            this.OutgoingConnection = this.GetConnectionTo(point);
            Console.Write(this.Id + " => " + point.Id + ", ");

            this.IncommingConnection = point.GetConnectionTo(this);
            Console.Write(this.Id + " <= " + point.Id + ", ");


            point.OutgoingConnection = point.GetConnectionTo(this);
            Console.Write(point.Id + " => " + this.Id + ", ");

            point.IncommingConnection = this.GetConnectionTo(point);
            Console.Write(point.Id + " <= " + this.Id);

            Console.WriteLine();
        }

        private void InsertIntoExistingRoute(Point point) {
            //The new point has to be connected to THIS
            //This is possible as an incoming or outgoing connection
            //Is has to be checked, whether it is better to use the incoming or outgoing connection of THIS
            //v-- The incoming connection is better
            if (this.IncommingConnection.From.GetConnectionTo(point).Cost < point.GetConnectionTo(this.OutgoingConnection.To).Cost)
            {
                Console.WriteLine("The incoming connection is used");

                //Use the incoming connection
                point.IncommingConnection = this.IncommingConnection.From.GetConnectionTo(point);
                Console.Write(point.Id + " <= " + this.IncommingConnection.From.Id + ", ");
                point.IncommingConnection.From.OutgoingConnection = point.IncommingConnection;
                Console.Write(point.IncommingConnection.From.Id + " => " + point.Id + ", ");

                //set the outgoing connection to THIS
                point.OutgoingConnection = point.GetConnectionTo(this);
                Console.Write(point.Id + " => " + this.Id + ", ");
                point.OutgoingConnection.To.IncommingConnection = point.OutgoingConnection;
                Console.Write(point.OutgoingConnection.To.Id + " <= " + point.Id);

                Console.WriteLine();
                Console.WriteLine();
            }
            //v-- the outgoing connection is better
            else
            {
                Console.WriteLine("The outgoing connection is used");

                //use the outgoing connection
                point.OutgoingConnection = point.GetConnectionTo(this.OutgoingConnection.To);
                Console.Write(point.Id + " => " + this.OutgoingConnection.To.Id + ", ");
                point.OutgoingConnection.To.IncommingConnection = point.OutgoingConnection;
                Console.Write(point.OutgoingConnection.To.Id + " <= " + point.Id + ", ");

                //set the incoming connection to THIS
                point.IncommingConnection = this.GetConnectionTo(point);
                Console.Write(point.Id + " <= " + this.Id + ", ");
                point.IncommingConnection.From.OutgoingConnection = point.IncommingConnection;
                Console.Write(point.IncommingConnection.From.Id + " => " + point.Id);

                Console.WriteLine();
                Console.WriteLine();
            }
        }

        public Connection GetConnectionTo(Point point)
        {
            return PossibleConnections.Single(x => x.To == point);
        }
    }
}

/Classes/MapOptimizer.cs

using System;
using System.Linq;
using TravellingSalesmanProblem.Interfaces;

namespace TravellingSalesmanProblem.Classes
{
    public class MapOptimizer : IMapOptimizer
    {
        public void Optimize(Map map)
        {
            Random random = new Random();

            {
                //connect two randomly selected points
                Point pointA = map.GetPoint(random.Next(map.Points.Count));
                Point pointB;
                do
                {
                    pointB = map.GetPoint(random.Next(map.Points.Count));
                } while (pointB == pointA);

                pointA.ConnectTo(pointB);

            }

            int connectedPoints = 2;
            while (map.Points.Any(x => x.IncommingConnection == null || x.OutgoingConnection == null))
            {
                connectedPoints++;
                //find a point without a connection
                Point point;
                do
                {
                    point = map.GetPoint(random.Next(map.Points.Count));
                } while (point.IncommingConnection != null);

                //find the nearest point with a connection
                Point nearestPoint = null;
                foreach (Point testPoint in map.Points.Where(x => x.IncommingConnection != null))
                {
                    if (
                        nearestPoint == null
                        || point.GetConnectionTo(testPoint).Cost < point.GetConnectionTo(nearestPoint).Cost
                    )
                    {
                        nearestPoint = testPoint;
                    }
                }

                //insert the point
                nearestPoint.ConnectTo(point);
            }
        }
    }
}

/Classes/StaticMapCreator.cs

using TravellingSalesmanProblem.Interfaces;

namespace TravellingSalesmanProblem.Classes
{
    public class StaticMapCreator : IMapCreator
    {
        public Map CreateMap(string data)
        {
            Map map = new Map();

            Point a = new Point(0);
            Point b = new Point(1);
            Point c = new Point(2);
            Point d = new Point(3);
            Point e = new Point(4);

            Connection ab = new Connection(a, b, 1);
            Connection ac = new Connection(a, c, 1);
            Connection ad = new Connection(a, d, 2);
            Connection ae = new Connection(a, e, 5);
            a.AddPossibleConnection(ab)
                .AddPossibleConnection(ac)
                .AddPossibleConnection(ad)
                .AddPossibleConnection(ae);

            Connection ba = new Connection(b, a, 1);
            Connection bc = new Connection(b, c, 2);
            Connection bd = new Connection(b, d, 1);
            Connection be = new Connection(b, e, 1);
            b.AddPossibleConnection(ba)
                .AddPossibleConnection(bc)
                .AddPossibleConnection(bd)
                .AddPossibleConnection(be);

            Connection ca = new Connection(c, a, 1);
            Connection cb = new Connection(c, b, 2);
            Connection cd = new Connection(c, d, 1);
            Connection ce = new Connection(c, e, 5);
            c.AddPossibleConnection(ca)
                .AddPossibleConnection(cb)
                .AddPossibleConnection(cd)
                .AddPossibleConnection(ce); ;

            Connection da = new Connection(d, a, 2);
            Connection db = new Connection(d, b, 1);
            Connection dc = new Connection(d, c, 1);
            Connection de = new Connection(d, e, 1);
            d.AddPossibleConnection(da)
                .AddPossibleConnection(db)
                .AddPossibleConnection(dc)
                .AddPossibleConnection(de);

            Connection ea = new Connection(e, a, 5);
            Connection eb = new Connection(e, b, 1);
            Connection ec = new Connection(e, c, 5);
            Connection ed = new Connection(e, d, 1);
            e.AddPossibleConnection(ea)
                .AddPossibleConnection(eb)
                .AddPossibleConnection(ec)
                .AddPossibleConnection(ed);

            map.AddPoint(a)
                .AddPoint(b)
                .AddPoint(c)
                .AddPoint(d)
                .AddPoint(e);

            return map;
        }
    }
}

Main programm

using System;
using System.IO;
using TravellingSalesmanProblem.Classes;
using TravellingSalesmanProblem.Interfaces;

namespace TravellingSalesmanProblem
{
    class Program
    {
        static void Main(string[] args)
        {
            IMapCreator mapCreator = new StaticMapCreator();

            Map map = mapCreator.CreateMap(String.Empty); //data is static, no string necessary

            map.Optimize(new MapOptimizer());

            Console.WriteLine("Optimized route has a cost of " + map.GetCostOfWholeRoute());
            Console.ReadLine();
        }
    }
}

Answer 1

I am quite impressed, there's very little I'd change, well done.

I would however prefer to use var in local variable assignments when the right-hand side of the assignment makes the type obvious.

e.g.

Point a = new Point(0);

Should be

var a = new Point(0);

The reason I would prefer this, is that if I were to change the type of a I then only have to change it once.

Secondly, I don't like the single-letter variable names (with the exception of loop indices). They hide the intended purpose behind a cognitive leap. For your points, I'd recommend an array or collection of some kind, and for your connections, it may actually be more readable to omit them entirely and put the constructors into your AddPossibleConnection call.

public class StaticMapCreator : IMapCreator
    {

        private const int PointCount = 5;

        public Map CreateMap(string data)
        {
            var map = new Map();

            var points = new Point[PointCount];
            for(var i=0; i<PointCount; i++)
            {
                points.Add(new Point(i));
            }

            points[0].AddPossibleConnection(new Connection(points[0], points[1], 1))
                .AddPossibleConnection(new Connection(points[0], points[2], 1))
                .AddPossibleConnection(new Connection(points[0], points[3], 2))
                .AddPossibleConnection(new Connection(points[0], points[4], 5));

            //etc...

            foreach(var point in points)
            {
                map.AddPoint(point);
            }

            return map;
        }
    }

Lastly, there may be a simpler way of doing ids, instead of passing them in as parameters. Consider this code:

    public class Point
    {
        private Guid id = Guid.NewGuid();
        public Guid Id
        {
            get
            {
                return id;
            }
        }

        //etc...

    }

Now whenever a new Point instance is created, it has its own unique identifier, without anything passed into a constructor, etc.

Lastly, if you're calling Map.GetPoint(int id) a lot, it might be better to store Points as a Dictionary<int,Point> where the key is the point's id. You can generate this easily by calling points.ToDictionary<int, Point>(x=>x.Id) or by adding the points as key-value pairs in AddPoint. The reason this is better is because a dictionary lookup is an O(1) operation, which means it will take the same time (barring hash collisions) to find a point in a dictionary with 10,000,000 items as it will a dictionary with 1 item. A List cannot promise that efficiency.

Answer 2

You've got an annoying "typo": IncommingConnection should be IncomingConnection.

---

I'm not fond of the calls to Console.Write in the Point class, since it isn't properly testable. Considering that plenty if those calls repeat the same logic I'd at least move these calls to a separate method, e.g.

private void Log(Point point1, Point point2, string comparison, bool displayComma)
{
   Console.Write(point1.Id + comparison + point2.Id + (displayComma ? ", " : string.Empty));
}

But all that output related logic should really move to a separate class. Suppose you don't want to write to the console anymore but instead want to log to a file or to a DB: this should really involve only changing the "Output" class without any need to touch the Point class.

(Quite frankly, at this point the calls to Console look like a quick & dirty debug solution.)

---

I'm also wondering if the repeated logic in InsertIntoExistingRoute couldn't be moved to a separate method.

Answer 3

The method Optimize isn't working fine. It doesn't make sense to connect two randomly selected points and then connect other points by these two's IncommingConnection.

Answer 4

I noticed your StaticMapCreator.CreateMap takes a string argument, but you do nothing with it.

I also think there's opportunity to make the code more readable by using arrays or lists instead of so many variables such as a, b, c, d, e, etc.

ADDED EDIT:

Regarding Points and Connections, I don't see anything that would prevent you from having connections defined starting from 'b' to all others, but then assign the connections collection to another point, such as 'a'. There is a Point.Id that seems to be a unique identifier to a point, but for some reason I am expecting a location property as well. With a location property, the cost between 2 points - that is the cost of a connection - could be calculated from the respective point's location.