C# routing application for calculating a set of shortest paths from a series of predefined start and end locations. Each start node can be assigned an integer load value which accumulates on its corresponding end node. In order to compile this code, download and reference NetTopologySuite, an open source spatial analysis library, and QuickGraph,…

gistfile1.cs

using System;
using System.Collections.Generic;
using System.IO;
using GeoAPI.Geometries;
using NetTopologySuite.Features;
using NetTopologySuite.Geometries;
using NetTopologySuite.IO;
using System.Globalization;

namespace ShortestPath
{
  class MainClass
  {
    //La clase Router implementa una mﾃ｡quina de estados extremadamente simple
    //que permite calcular y almacenar rutas entre puntos de origen y destino
    //de una red y acumular en destino el valor transferido por cada origen
    class Router
    {
      //La estructura RPath permite representar una ruta como un subgrafo de la red:
      //Source es el identificador del nodo de origen
      //Destination es el identificador del nodo de destino
      //Geometry es la geometría (LineString) del subgrafo o recorrido a través de la red
      struct RPath
      {
        public int Source;
        public int Destination;
        public IGeometry Geometry;
      }

      IDictionary<int, Coordinate> nodes = new Dictionary<int, Coordinate> ();
      PathFinder network = new PathFinder (true);
      IList<RPath> paths = new List<RPath> ();
      IDictionary<int, IGeometry> loads = new Dictionary<int, IGeometry> ();

      //La función SetupPoints almacena en memoria los nodos de origen o destino de la red a
      //partir de un fichero en formato Shape de puntos. El identificador de cada nodo
      // coincide con su índice o posición en la lista.
      public void SetupPoints (string pointFilePath) {
        var reader = new ShapefileReader(pointFilePath);
        var points = reader.ReadAll();
        int i = 0;
        using (var file = File.CreateText ("points.wkt")) {
          file.WriteLine (string.Format ("{0}|{1}", "wkt", "id"));
          foreach (IGeometry g in points) {
            if (g is IPoint) {
              file.WriteLine (string.Format ("{0}|{1}", g.AsText (), i));
              nodes.Add (i++, g.Coordinate);
            }
          }
        }
      }

      //La función SetupNetwork genera en memoria una red estructurada como un grafo simple
      //no dirigido a partir de un fichero en formato Shape de elementos lineales conectados
      // (por ejemplo el conjunto de ejes medios extraido de un Diagrama de Voronoi).
      public void SetupNetwork (string networkFilePath) {
        var reader = new ShapefileReader(networkFilePath);
        var edges = reader.ReadAll();
        foreach (IGeometry edge in edges) {
          ILineString ls = null;
          if (edge is IMultiLineString)
            ls = (ILineString) edge.GetGeometryN (0);
          else if (edge is ILineString)
            ls = (ILineString) edge;
          if (ls != null)
            network.Add (ls);
        }
        network.Initialize ();
      }

      //La función Go calcula una ruta entre un nodo de origen y otro de destino, la almacena
      //en la lista de recorridos y acumula en el punto de destino un valor de carga.
      public void Go (int source, int destination, int load) {
        AddPath (source, destination);
        AddLoad (destination, load);
      }

      void AddPath (int source, int destination) {
        Coordinate start = nodes[source];
        Coordinate end = nodes[destination];
        paths.Add (new RPath () {Source = source, Destination = destination, Geometry = network.Find (start, end)});
      }

      void AddLoad (int destination, int load) {
        if (!loads.ContainsKey (destination)) {
          IGeometryFactory f = new GeometryFactory (new PrecisionModel(PrecisionModels.Fixed));
          IGeometry point = f.CreatePoint (nodes[destination]);
          loads.Add (destination, point);
        }
        if (loads[destination].UserData == null)
          loads[destination].UserData = load;
        else
          loads[destination].UserData = (int) loads[destination].UserData + load;
      }

      //La función SavePaths persiste la lista de recorridos en un fichero
      //de texto en formato WKT del Open Geospatial Consortium.
      public void SavePaths (string outputFileName) {
        SavePaths (outputFileName, true);
      }

      public void SavePaths (string outputFileName, bool flushPaths) {
        using (var file = File.CreateText (outputFileName)) {
          file.WriteLine (string.Format ("{0}|{1}|{2}|{3}", "wkt", "source", "destination", "length"));
          foreach (var path in paths) {
            file.WriteLine (string.Format ("{0}|{1}|{2}|{3}", path.Geometry.AsText (), path.Source, path.Destination, path.Geometry.Length.ToString ("##.#")));
          }
        }
        if (flushPaths)
          paths.Clear ();
      }

      //La función SavePaths persiste la lista de cargas acumuladas en cada
      //nodo de destino en un fichero de texto en formato WKT del Open Geospatial Consortium.
      public void SaveLoads (string outputFileName) {
        using (var file = File.CreateText (outputFileName)) {
          file.WriteLine (string.Format ("{0}|{1}|{2}", "wkt", "id", "load"));
          foreach (var load in loads) {
            var exitPoint = load.Value;
            file.WriteLine (string.Format ("{0}|{1}|{2}", exitPoint.AsText (), load.Key, exitPoint.UserData));
          }
        }
      }
    }

    public static void Main (string[] args)
    {
      var router = new Router ();
      router.SetupPoints (args[0]);
      router.SetupNetwork (args[1]);
  
      //Calculamos los recorridos para el cluster de la salida 1 y los persistimos en un
      //fichero WKT.
      router.Go (12, 1, 25);
      router.Go (13, 1, 25);
      router.Go (14, 1, 17);
      router.Go (16, 1, 6);
      router.Go (15, 1, 17);
      router.Go (17, 1, 6);
      router.Go (7, 1, 2);
      router.Go (6, 1, 2);
      router.Go (8, 1, 3);
      router.Go (24, 1, 19);
      router.SavePaths ("cluster1_paths.wkt");
  
      //Calculamos los recorridos para el cluster de la salida 0 y los persistimos en un
      //fichero WKT.
      router.Go (22, 0, 18);
      router.Go (23, 0, 5);
      router.Go (20, 0, 17);
      router.Go (21, 0, 6);
      router.Go (18, 0, 17);
      router.Go (19, 0, 6);
      router.Go (10, 0, 3);
      router.Go (9, 0, 4);
      router.Go (11, 0, 3);
      router.Go (29, 0, 33);
      router.SavePaths ("cluster0_paths.wkt");
  
      //Calculamos los recorridos para el cluster de la salida 4 y los persistimos en un
      //fichero WKT.
      router.Go (25, 4, 48);
      router.Go (26, 4, 32);
      router.Go (27, 4, 48);
      router.Go (28, 4, 31);
      router.SavePaths ("cluster4_paths.wkt");
  
      //Persistimos las cargas acumuladas en cada nodo de destino en un fichero WKT.
      router.SaveLoads ("loads.wkt");
  
      Console.WriteLine ("Done!");
    }
  }
}