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
  {
    //Router class allows calculating and storing shortest paths between 
    //predefined start and end nodes on a network. It also accumulates on
    //the end point an integer value carried by the start point.
    class Router
    {
      //RPath structure represents routes as network subgraphs.
      //Source and Destination are start and end node identifiers respectively.
      //Destination es el identificador del nodo de destino. Geometry is the 
      //LineString geometry of the subgraph
      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!");
    }
  }
}