Skip to content

Instantly share code, notes, and snippets.

@quommit

quommit/gist:4633786

Last active April 19, 2017 06:04
Download ZIP

Revisions

  1. quommit revised this gist Jan 25, 2013. No changes.
  2. quommit revised this gist Jan 25, 2013. 1 changed file with 9 additions and 8 deletions.
    17 changes: 9 additions & 8 deletions gistfile1.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -121,7 +121,7 @@ public void SaveLoads (string outputFileName) {
    }
    }

    //This is a console application for testing Router class.
    //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
    @@ -138,8 +138,11 @@ public static void Main (string[] args)
    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.
    //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);
    @@ -152,8 +155,7 @@ public static void Main (string[] args)
    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.
    //End node 0 cluster
    router.Go (22, 0, 18);
    router.Go (23, 0, 5);
    router.Go (20, 0, 17);
    @@ -166,15 +168,14 @@ public static void Main (string[] args)
    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.
    //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");

    //Persistimos las cargas acumuladas en cada nodo de destino en un fichero WKT.
    //Store accumulated loads in each end node.
    router.SaveLoads ("loads.wkt");

    Console.WriteLine ("Done!");
  3. quommit revised this gist Jan 25, 2013. 1 changed file with 12 additions and 1 deletion.
    13 changes: 12 additions & 1 deletion gistfile1.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -120,7 +120,18 @@ public void SaveLoads (string outputFileName) {
    }
    }
    }


    //This is a console application for 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 ();
  4. quommit revised this gist Jan 25, 2013. 1 changed file with 5 additions and 6 deletions.
    11 changes: 5 additions & 6 deletions gistfile1.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -67,8 +67,8 @@ public void SetupNetwork (string networkFilePath) {
    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.
    //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);
    @@ -92,8 +92,7 @@ void AddLoad (int destination, int load) {
    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.
    //SavePaths method writes all routes to a plain text file in WKT format.
    public void SavePaths (string outputFileName) {
    SavePaths (outputFileName, true);
    }
    @@ -109,8 +108,8 @@ public void SavePaths (string outputFileName, bool 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.
    //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"));
  5. quommit revised this gist Jan 25, 2013. 1 changed file with 2 additions and 3 deletions.
    5 changes: 2 additions & 3 deletions gistfile1.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -50,9 +50,8 @@ public void SetupPoints (string pointFilePath) {
    }
    }

    //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).
    //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();
  6. quommit revised this gist Jan 25, 2013. 1 changed file with 3 additions and 3 deletions.
    6 changes: 3 additions & 3 deletions gistfile1.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -32,9 +32,9 @@ struct RPath
    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.
    //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();
  7. quommit revised this gist Jan 25, 2013. 1 changed file with 5 additions and 3 deletions.
    8 changes: 5 additions & 3 deletions gistfile1.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -11,13 +11,15 @@ 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.
    //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
    //Destination es el identificador del nodo de destino. Geometry is the
    //LineString geometry of the subgraph
    struct RPath
    {
    public int Source;
  8. quommit revised this gist Jan 25, 2013. 1 changed file with 5 additions and 7 deletions.
    12 changes: 5 additions & 7 deletions gistfile1.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -11,15 +11,13 @@ 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
    //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
    {
    //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
    //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;
  9. quommit revised this gist Jan 25, 2013. No changes.
  10. quommit revised this gist Jan 25, 2013. No changes.
  11. quommit created this gist Jan 25, 2013.
    174 changes: 174 additions & 0 deletions gistfile1.cs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,174 @@
    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!");
    }
    }
    }