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

      //SetupPoints method stores in memory all predefined start and end nodes from
      //a point shapefile. An identifier is assigned to each node according to its
      //record position.
      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);
            }
          }
        }
      }

      //SetupNetwork method initializes a network structure organized as a simple 
      //non directed graph. A shapefile with connected linear elements is needed as input.
      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 ();
      }

      //Go method stores shortest path between source and destination
      //and accumulates load in destination.
      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;
      }

      //SavePaths method writes all routes to a plain text file in WKT format.
      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 ();
      }

      //SaveLoads method writes all end nodes and their accumulated loads
      //to a plain text file in WKT format.
      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));
          }
        }
      }
    }
    
    //This is a console application for ad hoc testing Router class.
    //You can download data for testing at: 
    //https://docs.google.com/file/d/0Bzcu8L-HEdBqaTdaWmlxTVJUcmc/edit
    //You should get a ShortestPathTestData.zip file. To make things 
    //easier unpack zip file in your executable file's path. Assuming
    //your executable name is ShortestPath.exe, invoke it this way:
    //ShortestPath.exe Nodes.shp Network.shp
    //or this way if you're using Mono:
    //mono ShortestPath.exe Nodes.shp Network.shp
    //Arguments refer to point shapefile and network shapefile locations,
    //in that order.
    public static void Main (string[] args)
    {
      var router = new Router ();
      router.SetupPoints (args[0]);
      router.SetupNetwork (args[1]);
  
      //We are testing 3 node clusters. All start nodes 
      //in a cluster share the same end node. For each cluster
      //we calculate and store all shortest paths.
      
      //End node 1 cluster
      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");
  
      //End node 0 cluster
      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");
  
      //End node 4 cluster
      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");
  
      //Store accumulated loads in each end node.
      router.SaveLoads ("loads.wkt");
  
      Console.WriteLine ("Done!");
    }
  }
}