Dijkstra.java

  1. package org.drip.sample.graph;

  3. import java.util.Set;

  5. import org.drip.numerical.common.FormatUtil;
  6. import org.drip.service.env.EnvManager;
  7. import org.drip.spaces.graph.DijkstraScheme;
  8. import org.drip.spaces.graph.Edge;
  9. import org.drip.spaces.graph.Topography;
  10. import org.drip.spaces.graph.ShortestPathVertex;
  11. import org.drip.spaces.graph.ShortestPathTree;

  13. /*
  14.  * -*- mode: java; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
  15.  */

  17. /*!
  18.  * Copyright (C) 2019 Lakshmi Krishnamurthy
  19.  * Copyright (C) 2018 Lakshmi Krishnamurthy
  20.  * 
  21.  *  This file is part of DROP, an open-source library targeting risk, transaction costs, exposure, margin
  22.  *      calculations, valuation adjustment, and portfolio construction within and across fixed income,
  23.  *      credit, commodity, equity, FX, and structured products.
  24.  *  
  25.  *      https://lakshmidrip.github.io/DROP/
  26.  *  
  27.  *  DROP is composed of three modules:
  28.  *  
  29.  *  - DROP Analytics Core - https://lakshmidrip.github.io/DROP-Analytics-Core/
  30.  *  - DROP Portfolio Core - https://lakshmidrip.github.io/DROP-Portfolio-Core/
  31.  *  - DROP Numerical Core - https://lakshmidrip.github.io/DROP-Numerical-Core/
  32.  * 
  33.  *  DROP Analytics Core implements libraries for the following:
  34.  *  - Fixed Income Analytics
  35.  *  - Asset Backed Analytics
  36.  *  - XVA Analytics
  37.  *  - Exposure and Margin Analytics
  38.  * 
  39.  *  DROP Portfolio Core implements libraries for the following:
  40.  *  - Asset Allocation Analytics
  41.  *  - Transaction Cost Analytics
  42.  * 
  43.  *  DROP Numerical Core implements libraries for the following:
  44.  *  - Statistical Learning
  45.  *  - Numerical Optimizer
  46.  *  - Spline Builder
  47.  *  - Algorithm Support
  48.  * 
  49.  *  Documentation for DROP is Spread Over:
  50.  * 
  51.  *  - Main                     => https://lakshmidrip.github.io/DROP/
  52.  *  - Wiki                     => https://github.com/lakshmiDRIP/DROP/wiki
  53.  *  - GitHub                   => https://github.com/lakshmiDRIP/DROP
  54.  *  - Repo Layout Taxonomy     => https://github.com/lakshmiDRIP/DROP/blob/master/Taxonomy.md
  55.  *  - Javadoc                  => https://lakshmidrip.github.io/DROP/Javadoc/index.html
  56.  *  - Technical Specifications => https://github.com/lakshmiDRIP/DROP/tree/master/Docs/Internal
  57.  *  - Release Versions         => https://lakshmidrip.github.io/DROP/version.html
  58.  *  - Community Credits        => https://lakshmidrip.github.io/DROP/credits.html
  59.  *  - Issues Catalog           => https://github.com/lakshmiDRIP/DROP/issues
  60.  *  - JUnit                    => https://lakshmidrip.github.io/DROP/junit/index.html
  61.  *  - Jacoco                   => https://lakshmidrip.github.io/DROP/jacoco/index.html
  62.  * 
  63.  *  Licensed under the Apache License, Version 2.0 (the "License");
  64.  *      you may not use this file except in compliance with the License.
  65.  *   
  66.  *  You may obtain a copy of the License at
  67.  *      http://www.apache.org/licenses/LICENSE-2.0
  68.  *  
  69.  *  Unless required by applicable law or agreed to in writing, software
  70.  *      distributed under the License is distributed on an "AS IS" BASIS,
  71.  *      WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  72.  *  
  73.  *  See the License for the specific language governing permissions and
  74.  *      limitations under the License.
  75.  */

  77. /**
  78.  * <i>Dijkstra</i> illustrates the Execution of the Dijkstra Algorithm. The References are:
  79.  *  
  80.  * <br><br>
  81.  *  <ul>
  82.  *      <li>
  83.  *          Wikipedia (2018a): Graph (Abstract Data Type)
  84.  *              https://en.wikipedia.org/wiki/Graph_(abstract_data_type)
  85.  *      </li>
  86.  *      <li>
  87.  *          Wikipedia (2018b): Graph Theory https://en.wikipedia.org/wiki/Graph_theory
  88.  *      </li>
  89.  *      <li>
  90.  *          Wikipedia (2018c): Graph (Discrete Mathematics)
  91.  *              https://en.wikipedia.org/wiki/Graph_(discrete_mathematics)
  92.  *      </li>
  93.  *      <li>
  94.  *          Wikipedia (2018d): Dijkstra's Algorithm https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
  95.  *      </li>
  96.  *      <li>
  97.  *          Wikipedia (2018e): Bellman-Ford Algorithm
  98.  *              https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
  99.  *      </li>
  100.  *  </ul>
  101.  * <br><br>
  102.  *  <ul>
  103.  *      <li><b>Module </b> = <a href = "https://github.com/lakshmiDRIP/DROP/tree/master/NumericalCore.md">Numerical Core Module</a></li>
  104.  *      <li><b>Library</b> = <a href = "https://github.com/lakshmiDRIP/DROP/tree/master/AlgorithmSupportLibrary.md">Algorithm Support Library</a></li>
  105.  *      <li><b>Project</b> = <a href = "https://github.com/lakshmiDRIP/DROP/tree/master/src/main/java/org/drip/sample/README.md">Sample</a></li>
  106.  *      <li><b>Package</b> = <a href = "https://github.com/lakshmiDRIP/DROP/tree/master/src/main/java/org/drip/sample/graph/README.md">Graph Builder and Navigator</a></li>
  107.  *  </ul>
  108.  * <br><br>
  109.  *
  110.  * @author Lakshmi Krishnamurthy
  111.  */

  113. public class Dijkstra
  114. {

  116.     private static final Topography SetTopography()
  117.         throws Exception
  118.     {
  119.         String[] vertexArray = new String[]
  120.         {
  121.             "Delhi     ",
  122.             "Bombay    ",
  123.             "Madras    ",
  124.             "Calcutta  ",
  125.             "Bangalore ",
  126.             "Hyderabad ",
  127.             "Cochin    ",
  128.             "Pune      ",
  129.             "Ahmedabad ",
  130.             "Jaipur    "
  131.         };

  133.         Topography topography = new Topography();

  135.         for (String vertexName : vertexArray)
  136.         {
  137.             topography.addVertex (vertexName);
  138.         }

  140.         topography.addEdge (
  141.             new Edge (
  142.                 vertexArray[0], // Delhi
  143.                 vertexArray[1], // Bombay
  144.                 1388.
  145.             )
  146.         );

  148.         topography.addEdge (
  149.             new Edge (
  150.                 vertexArray[0], // Delhi
  151.                 vertexArray[2], // Madras
  152.                 2191.
  153.             )
  154.         );

  156.         topography.addEdge (
  157.             new Edge (
  158.                 vertexArray[1], // Bombay
  159.                 vertexArray[2], // Madras
  160.                 1279.
  161.             )
  162.         );

  164.         topography.addEdge (
  165.             new Edge (
  166.                 vertexArray[0], // Delhi
  167.                 vertexArray[3], // Calcutta
  168.                 1341.
  169.             )
  170.         );

  172.         topography.addEdge (
  173.             new Edge (
  174.                 vertexArray[1], // Bombay
  175.                 vertexArray[3], // Calcutta
  176.                 1968.
  177.             )
  178.         );

  180.         topography.addEdge (
  181.             new Edge (
  182.                 vertexArray[2], // Madras
  183.                 vertexArray[3], // Calcutta
  184.                 1663.
  185.             )
  186.         );

  188.         topography.addEdge (
  189.             new Edge (
  190.                 vertexArray[2], // Madras
  191.                 vertexArray[4], // Bangalore
  192.                 361.
  193.             )
  194.         );

  196.         topography.addEdge (
  197.             new Edge (
  198.                 vertexArray[2], // Madras
  199.                 vertexArray[5], // Hyderabad
  200.                 784.
  201.             )
  202.         );

  204.         topography.addEdge (
  205.             new Edge (
  206.                 vertexArray[2], // Madras
  207.                 vertexArray[6], // Cochin
  208.                 697.
  209.             )
  210.         );

  212.         topography.addEdge (
  213.             new Edge (
  214.                 vertexArray[1], // Bombay
  215.                 vertexArray[7], // Pune
  216.                 192.
  217.             )
  218.         );

  220.         topography.addEdge (
  221.             new Edge (
  222.                 vertexArray[1], // Bombay
  223.                 vertexArray[8], // Ahmedabad
  224.                 492.
  225.             )
  226.         );

  228.         topography.addEdge (
  229.             new Edge (
  230.                 vertexArray[0], // Delhi
  231.                 vertexArray[9], // Jaipur
  232.                 308.
  233.             )
  234.         );

  236.         return topography;
  237.     }

  239.     private static final String PathVertexes (
  240.         final String source,
  241.         final String destination,
  242.         final ShortestPathTree vertexPeripheryMap)
  243.         throws Exception
  244.     {
  245.         String path = "";
  246.         String vertex = destination;

  248.         ShortestPathVertex vertexPeriphery = vertexPeripheryMap.shortestPathVertex (vertex);

  250.         while (!source.equalsIgnoreCase (vertexPeriphery.current()))
  251.         {
  252.             path = path + vertexPeriphery.current() + " <- ";

  254.             vertexPeriphery = vertexPeripheryMap.shortestPathVertex (vertexPeriphery.preceeding());
  255.         }

  257.         path = path + source;
  258.         return path;
  259.     }

  261.     public static void main (
  262.         final String[] inputArray)
  263.         throws Exception
  264.     {
  265.         EnvManager.InitEnv ("");

  267.         Topography topography = SetTopography();

  269.         DijkstraScheme dijkstraScheme = new DijkstraScheme (topography);

  271.         Set<String> vertexNameSet = topography.vertexNameSet();

  273.         for (String source : vertexNameSet)
  274.         {
  275.             ShortestPathTree vertexPeripheryMap = dijkstraScheme.spf (source).vertexPeripheryMap();

  277.             System.out.println ("\t||------------------------------------------------------------||");

  279.             for (String vertex : vertexNameSet)
  280.             {
  281.                 if (!vertex.equalsIgnoreCase(source))
  282.                 {
  283.                     ShortestPathVertex vertexPeriphery = vertexPeripheryMap.shortestPathVertex (vertex);

  285.                     System.out.println (
  286.                         "\t|| " + source + " to " + vertex + " is " +
  287.                         FormatUtil.FormatDouble (vertexPeriphery.weightFromSource(), 4, 0, 1.) +
  288.                         " | Previous is " + vertexPeriphery.preceeding() + " || " + PathVertexes (
  289.                             source,
  290.                             vertex,
  291.                             vertexPeripheryMap
  292.                         )
  293.                     );
  294.                 }
  295.             }

  297.             System.out.println ("\t||------------------------------------------------------------||\n");
  298.         }

  300.         EnvManager.TerminateEnv();
  301.     }
  302. }
Created with JaCoCo 0.7.9.201702052155