doc/old/map_shortestpath.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%classpath add mvn tech.tablesaw tablesaw-core 0.10.0\n",
    "%import tech.tablesaw.api.Table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// Basic setups\n",
    "fileName = \"../resources/data/UScity.csv\";\n",
    "startCity = \"Brooklyn\";\n",
    "endCity = \"Carson City\";\n",
    "\n",
    "// show data in table\n",
    "table = Table.read().csv(fileName);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// simple ploting by city coordinates\n",
    "import com.twosigma.beakerx.fileloader.CSV;\n",
    "\n",
    "def cities = new CSV().read(fileName)\n",
    "map = new Plot(title: \"US City Map\", yLabel: \"Latitude\", xLabel: \"Longitude\");\n",
    "map << new Rasters(x: [-132], y: [56], width: [66], height: [32], opacity:[0.8], filePath: \"../resources/img/USmapbg.png\");\n",
    "map << new Points(y: cities.latitude, x: cities.longitude);\n",
    "map"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// calculate shortest path\n",
    "\n",
    "import com.twosigma.beakerx.fileloader.CSV;\n",
    "\n",
    "class ShortestPathAlgoritm {\n",
    "    def graph, start, destination    \n",
    "    def unsettledNodes = new PriorityQueue<String>(500, new Comparator<String>() {\n",
    "       public int compare(String node1, String node2) {\n",
    "            shortestDistance(node1).compareTo(shortestDistance(node2))\n",
    "        }\n",
    "    });\n",
    "    def shortestDistances = [:]\n",
    "    def predecessors = [:]\n",
    "    def settledNodes = [] as Set\n",
    "\n",
    "    ShortestPathAlgoritm(graph, start, destination) {\n",
    "        this.graph = graph\n",
    "        this.start = start\n",
    "        this.destination = destination\n",
    "\n",
    "        unsettledNodes.add(start)\n",
    "        shortestDistances[(start)] = 0\n",
    "    }\n",
    "\n",
    "    double shortestDistance(node) {\n",
    "        shortestDistances.containsKey(node) ? shortestDistances[node] : Integer.MAX_VALUE\n",
    "    }\n",
    "\n",
    "    def extractMin() {\n",
    "        unsettledNodes.poll()\n",
    "    }\n",
    "\n",
    "    def unsettledNeighbours(node) {\n",
    "        graph.findAll { edge ->\n",
    "            edge.node1 == node && !settledNodes.contains(edge.node2)\n",
    "        }\n",
    "    }\n",
    "\n",
    "    def relaxNeighbours(node) {\n",
    "        unsettledNeighbours(node).each { edge ->\n",
    "            if (shortestDistance(edge.node2) > shortestDistance(edge.node1) + edge.distance) {\n",
    "                shortestDistances[edge.node2] = shortestDistance(edge.node1) + edge.distance\n",
    "                predecessors[edge.node2] = edge.node1\n",
    "                if (!unsettledNodes.contains(edge.node2)) {\n",
    "                    unsettledNodes.add(edge.node2)\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "\n",
    "    def calculateShortestPath() {\n",
    "        while (!unsettledNodes.isEmpty()) {\n",
    "            String node = extractMin()\n",
    "            if (node == destination) {\n",
    "                break\n",
    "            }\n",
    "            settledNodes += node\n",
    "            relaxNeighbours(node)\n",
    "        }\n",
    "        shortestDistances[destination]\n",
    "    }\n",
    "\n",
    "    def getShortestPath(node, path) {\n",
    "        node == start ? [node]+path : getShortestPath(predecessors[node], [node]+path)\n",
    "    }\n",
    "    \n",
    "    def getShortestPath() {\n",
    "        getShortestPath(destination, []) \n",
    "    }\n",
    "}\n",
    "\n",
    "class Edge {\n",
    "    String node1, node2\n",
    "    double distance\n",
    "}\n",
    "\n",
    "double getDistance(double x1,double y1, double x2, double y2){\n",
    "    return Math.sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1))\n",
    "}\n",
    "\n",
    "cities = new CSV().read(fileName)\n",
    "n = cities.size;\n",
    "def graph = new Edge[n * n];\n",
    "def graphidx = 0;\n",
    "\n",
    "// build a graph\n",
    "for (int i = 0; i < n; i++){\n",
    "    for (int j = 0; j < n; j++){\n",
    "        def dist = getDistance(cities.longitude[i], cities.latitude[i], cities.longitude[j], cities.latitude[j]);\n",
    "        if (dist > 7){\n",
    "            dist = Integer.MAX_VALUE \n",
    "            // view as unreachable because they are too far away from each other\n",
    "            // there should be shorter ways in between\n",
    "        }\n",
    "        graph[graphidx++] = new Edge(node1: cities.city[i], node2: cities.city[j], distance: dist);\n",
    "    }\n",
    "}\n",
    "\n",
    "// calculate shortest path\n",
    "dijkstra = new ShortestPathAlgoritm(graph, startCity, endCity)\n",
    "dist = dijkstra.calculateShortestPath();\n",
    "dijkstra.shortestPath"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// plot path on the graph\n",
    "import com.twosigma.beakerx.fileloader.CSV;\n",
    "\n",
    "newmap = new Plot(title: \"Shortest Path\", yLabel: \"Latitude\", xLabel: \"Longitude\");\n",
    "// all cities\n",
    "newmap << new Points(y: cities.latitude, x: cities.longitude);\n",
    "\n",
    "def ps = dijkstra.shortestPath.size();\n",
    "def pathy = new double[ps];\n",
    "def pathx = new double[ps];\n",
    "def pathc = new String[ps];\n",
    "for (int i = 0; i < ps; i++){\n",
    "    for (int j = 0 ; j < n; j++){\n",
    "        if (cities.city[j] == dijkstra.shortestPath[i]){\n",
    "            pathx[i] = cities.longitude[j];\n",
    "            pathy[i] = cities.latitude[j];\n",
    "            pathc[i] = cities.city[j];\n",
    "        }\n",
    "    }\n",
    "}\n",
    "newmap << new Rasters(x: [-132], y: [56], width: [66], height: [32], opacity:[0.8], filePath: \"../resources/img/USmapbg.png\");\n",
    "\n",
    "// start and end points\n",
    "newmap << new Points(y: [pathy[0]], x:[pathx[0]], shape: ShapeType.CIRCLE, color: Color.orange, outlineColor: Color.red)\n",
    "newmap << new Points(y: [pathy[ps - 1]], x:[pathx[ps - 1]], shape: ShapeType.DIAMOND, color: Color.green, outlineColor: Color.red)\n",
    "for (int i = 0; i < ps; i ++){\n",
    "  newmap << new Text(y: pathy[i], x:pathx[i], text: pathc[i],  pointerAngle: -i/1.5)\n",
    "}\n",
    "\n",
    "// path\n",
    "newmap << new Line(y: pathy, x:pathx); \n",
    "newmap"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// final visualization of everything \n",
    "\n",
    "import com.twosigma.beakerx.jvm.object.TabbedOutputContainerLayoutManager;\n",
    "import com.twosigma.beakerx.jvm.object.OutputContainer;\n",
    "\n",
    "def layout = new TabbedOutputContainerLayoutManager()\n",
    "layout.setBorderDisplayed(false)\n",
    "def o = new OutputContainer()\n",
    "o.setLayoutManager(layout)\n",
    "o.addItem(table, \"City info\")\n",
    "o.addItem(map, \"US City Map\")\n",
    "o.addItem(newmap, \"Shortest Path\")\n",
    "o.addItem(dijkstra.shortestPath, \"Path Detail\")\n",
    "o\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "beakerx_kernel_parameters": {
   "classpath": [],
   "imports": []
  },
  "kernelspec": {
   "display_name": "Groovy",
   "language": "groovy",
   "name": "groovy"
  },
  "language_info": {
   "codemirror_mode": "groovy",
   "file_extension": ".groovy",
   "mimetype": "",
   "name": "Groovy",
   "nbconverter_exporter": "",
   "version": "2.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}