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

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("PathToXmlFile");

            map.Optimize(new MapOptimizer());

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