{ "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(500, new Comparator() {\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 }