map_shortestpath.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "",
       "version_major": 2,
       "version_minor": 0
      },
      "method": "display_data"
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "55ce81ec-3e76-4535-b636-2fec0e4aa593",
       "version_major": 2,
       "version_minor": 0
      },
      "method": "display_data"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%classpath add mvn tech.tablesaw tablesaw-core 0.10.0\n",
    "%import tech.tablesaw.api.Table"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "919d9068-26df-4d4f-8293-206029a5ed43",
       "version_major": 2,
       "version_minor": 0
      },
      "method": "display_data"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "%%java\n",
    "import java.util.Arrays;\n",
    "import java.util.List;\n",
    "String test=\"test\";\n",
    "Plot map = new Plot();\n",
    "Rasters r= new Rasters();\n",
    "r.setFilePath(\"../resources/img/USmapbg.png\");\n",
    "Object[] xs={-132};\n",
    "    Number[] ys={56};\n",
    "        List<Object> x=Arrays.asList(xs);\n",
    "        List<Number> y=Arrays.asList(ys);\n",
    "r.setX(x);\n",
    "r.setY(y);\n",
    "Number[] hs={32};\n",
    "List<Number> h= Arrays.asList(hs);\n",
    "r.setHeight(h);\n",
    "Number[] ws={66};\n",
    "List<Number> w= Arrays.asList(ws);\n",
    "r.setWidth(w);\n",
    "map.add(r);\n",
    "return map;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "ename": "groovy.lang.MissingPropertyException",
     "evalue": " No such property",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31mgroovy.lang.MissingPropertyException: No such property: Table for class: script1535154197606\u001b[0;0m",
      "\u001b[1;31m\tat this cell line 7\u001b[0;0m",
      "\u001b[0;31m\tat com.twosigma.beakerx.groovy.evaluator.GroovyCodeRunner.runScript(GroovyCodeRunner.java:94)\u001b[0;0m",
      "\u001b[0;31m\tat com.twosigma.beakerx.groovy.evaluator.GroovyCodeRunner.call(GroovyCodeRunner.java:59)\u001b[0;0m",
      "\u001b[0;31m\tat com.twosigma.beakerx.groovy.evaluator.GroovyCodeRunner.call(GroovyCodeRunner.java:32)\u001b[0;0m"
     ]
    }
   ],
   "source": [
    "%%groovy\n",
    "// 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": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "0169ea89-911b-409d-8a4d-0deb9513350e",
       "version_major": 2,
       "version_minor": 0
      },
      "method": "display_data"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Brooklyn, Cocolamus, Athens, Baker, Worland, Eden, Carson City]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "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": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "86fa6458-512a-456a-93fb-6add60099544",
       "version_major": 2,
       "version_minor": 0
      },
      "method": "display_data"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "2e13c6f4-d9df-44d5-8c10-8baf67ad14ad",
       "version_major": 2,
       "version_minor": 0
      },
      "method": "display_data"
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "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": []
  },
  "celltoolbar": "Initialization Cell",
  "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"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": false,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": false,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}