A_Star.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# A*\n",
    "\n",
    "I accidentally ended up with an implementation of a_star in javascript. Some ES6 features have made it possible to write this code legibly. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Function]"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"use strict\";\n",
    "\n",
    "var vertex_id = 0;\n",
    "class Vertex{\n",
    "    constructor(){\n",
    "        this.id = vertex_id++;\n",
    "        this.neighbors = new Set();\n",
    "        this.edges = new Set();\n",
    "    }\n",
    "\n",
    "    release(){\n",
    "        for(var v of this.neighbors){\n",
    "            v.neighbors.delete(this);\n",
    "        }\n",
    "        delete this.id;\n",
    "    }\n",
    "}\n",
    "\n",
    "var edge_id = 0;\n",
    "class Edge{\n",
    "    constructor(src, tgt){\n",
    "        this.id = edge_id++;\n",
    "        this.src = src;\n",
    "        this.tgt = tgt;\n",
    "        \n",
    "        src.neighbors.add(tgt);\n",
    "        tgt.neighbors.add(src);\n",
    "\n",
    "        src.edges.add(this);\n",
    "        tgt.edges.add(this);\n",
    "    }\n",
    "    \n",
    "    release(){\n",
    "        this.src.release();\n",
    "        this.src.edges.delete(this);\n",
    "        delete this.src;\n",
    "\n",
    "        this.tgt.release();\n",
    "        this.tgt.edges.delete(this);\n",
    "        delete this.tgt;\n",
    "    }\n",
    "}\n",
    "\n",
    "var graph_id = 0;\n",
    "class Graph {\n",
    "    constructor(){\n",
    "        this.id = graph_id++;\n",
    "        this.V = new Map();\n",
    "        this.E = new Map();\n",
    "    }\n",
    "    \n",
    "    add_vertex(vertex){\n",
    "        this.V.set(vertex.id, vertex);\n",
    "        return vertex;\n",
    "    }\n",
    "    \n",
    "    remove_vertex(id){\n",
    "        this.V.delete(id);\n",
    "    }\n",
    "    \n",
    "    add_edge(src_vertex, tgt_vertex){\n",
    "        var edge = new Edge(src_vertex, tgt_vertex);\n",
    "        this.E.set(edge.id, edge);\n",
    "        return edge;\n",
    "    }\n",
    "    \n",
    "    remove_edge(id){\n",
    "        this.E.delete(id);\n",
    "    }\n",
    "    \n",
    "    /*\n",
    "      Lists a random vertex.\n",
    "    */\n",
    "    random_vertex(){\n",
    "        var items = Array.from(this.V.values());\n",
    "        return items[Math.round(Math.random() * items.length)];\n",
    "    }\n",
    "    \n",
    "    /*\n",
    "      Creates an edge between two random vertices. \n",
    "    */\n",
    "    random_edge(){\n",
    "        \n",
    "        var v1 \n",
    "        while((v1 = this.random_vertex()) == undefined);\n",
    "\n",
    "        var v2;\n",
    "        while((v2 = this.random_vertex()) == v1 || (v2 == undefined));\n",
    "        \n",
    "        return this.add_edge(v1, v2);\n",
    "    }\n",
    "    \n",
    "    clear(){\n",
    "        this.E.clear();\n",
    "        this.V.clear();\n",
    "    }\n",
    "\n",
    "    connected(){\n",
    "        var source = this.random_vertex();\n",
    "        for(var goal of this.V){\n",
    "            var path = this.a_star(source, goal);\n",
    "            if(path.length >= 2){\n",
    "                return true;\n",
    "            }else{\n",
    "                return false; \n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}\n",
    "\n",
    "\n",
    "Graph.prototype.a_star = function(start, goal){\n",
    "    // The set of nodes already evaluated. \n",
    "    var closed_set = new Set();\n",
    "    \n",
    "    // The set of currently discovered nodes that are not evaluated yet.\n",
    "    // Initially, only the start node is known. \n",
    "    var open_set = new Set([start]);\n",
    "    \n",
    "    // For each node, which node it can most efficiently be reached from. \n",
    "    // If a node can be reached from manny nodes, came_from will eventually\n",
    "    // contain the most efficient step. \n",
    "    var came_from = new Map();\n",
    "    \n",
    "    // For each node, the cost of getting from the start node to that node.\n",
    "    var g_score = new Map()\n",
    "    this.V.forEach(function(vertex){\n",
    "        g_score.set(vertex, Infinity);\n",
    "    });\n",
    "    \n",
    "    // For the first node, that value is completely heuristic. \n",
    "    g_score.set(start, 0.0);\n",
    "    \n",
    "    // For each node, the total cost of getting from the start node to the \n",
    "    // goal by passing by that node. That value is partly known, partly\n",
    "    // heuristic. \n",
    "    var f_score = new Map();\n",
    "    this.V.forEach(function(vertex){\n",
    "        f_score.set(vertex, Infinity);\n",
    "    });\n",
    "    \n",
    "    // For the first node, that value is completely heuristic. \n",
    "    f_score.set(start, heuristic_cost_estimate(start, goal));\n",
    "    \n",
    "    while(open_set.size){\n",
    "        var entries_it = open_set.entries();\n",
    "        var entries = [];\n",
    "        for(var entry of entries_it){\n",
    "            entries.push(entry[0]);\n",
    "        }\n",
    "        entries.sort((a, b) => f_score.get(a) - f_score.get(b));\n",
    "        var current = entries[0];\n",
    "        // why keep it in a set if we're just gonna sort it anyway? \n",
    "        \n",
    "        if(current === goal){\n",
    "            return reconstruct_path(came_from, current);\n",
    "        }\n",
    "        \n",
    "        open_set.delete(current);\n",
    "        closed_set.add(current);\n",
    "        \n",
    "        var neighbors = current.neighbors.values();\n",
    "        for(var neighbor of neighbors){\n",
    "            if(closed_set.has(neighbor)){\n",
    "                continue;\n",
    "            }\n",
    "            \n",
    "            if(!open_set.has(neighbor)){\n",
    "                open_set.add(neighbor);\n",
    "            }\n",
    "            \n",
    "            var tentative_g_score = g_score.get(current) + 1.0;\n",
    "            if(tentative_g_score >= g_score.get(neighbor)){\n",
    "                continue;\n",
    "            }\n",
    "            \n",
    "            came_from.set(neighbor, current);\n",
    "            g_score.set(neighbor, tentative_g_score);\n",
    "            f_score.set(neighbor, g_score.get(neighbor) + heuristic_cost_estimate(neighbor, goal));\n",
    "        }\n",
    "    }\n",
    "    \n",
    "    return [];\n",
    "}\n",
    "\n",
    "function reconstruct_path(came_from, current){\n",
    "    var total_path = [current];\n",
    "    while(came_from.has(current)){\n",
    "        current = came_from.get(current);\n",
    "        total_path.push(current);\n",
    "    }\n",
    "    \n",
    "    return total_path.reverse();\n",
    "}\n",
    "\n",
    "function heuristic_cost_estimate(start, goal){\n",
    "    return 1.0 - (1.0/start.neighbors.size > 0 ? start.neighbors.size : 1);\n",
    "}\n",
    "\n",
    "function dist_between(start, goal){\n",
    "    return 1.0;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here's an example..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Path:\n",
      "[ Vertex { id: 0, neighbors: Set { [Object] }, edges: Set { [Object] } },\n",
      "  Vertex {\n",
      "    id: 1,\n",
      "    neighbors: Set { [Object], [Object] },\n",
      "    edges: Set { [Object], [Object] } },\n",
      "  Vertex { id: 2, neighbors: Set { [Object] }, edges: Set { [Object] } } ]\n"
     ]
    }
   ],
   "source": [
    "var graph = new Graph();\n",
    "\n",
    "var v0 = graph.add_vertex(new Vertex());\n",
    "var v1 = graph.add_vertex(new Vertex());\n",
    "var v2 = graph.add_vertex(new Vertex());\n",
    "\n",
    "var e0 = graph.add_edge(v0, v1);\n",
    "var e1 = graph.add_edge(v1, v2);\n",
    "\n",
    "console.log('Path:');\n",
    "console.log(graph.a_star(v0, v2));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It bugs me that the graph api isn't consistent. Just remember to add a `new Vertex()` to the `add_vertex(...)` function. The `add_edge` function takes two vertices. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "100 100 0\n",
      "100 200 6\n",
      "100 500 3\n",
      "100 1000 4\n",
      "100 5000 2\n",
      "100 10000 2\n",
      "100 100000 2\n"
     ]
    }
   ],
   "source": [
    "var path_length = function(v, e){\n",
    "    var vertices = [];\n",
    "    var graph = new Graph();\n",
    "    \n",
    "    // add vertices\n",
    "    for(var i=0; i<v; i++){\n",
    "        vertices.push(graph.add_vertex(new Vertex()));\n",
    "    }\n",
    "\n",
    "    /*\n",
    "        It might not finish, but if it does, it will return something defined. \n",
    "    */\n",
    "    var choice = function(vertices){\n",
    "        console.assert(vertices.length);\n",
    "        var random_vertex = undefined;\n",
    "        do{\n",
    "            random_vertex = vertices[Math.round(Math.random()*vertices.length)];\n",
    "        }while(random_vertex === undefined);\n",
    "        return random_vertex;\n",
    "    }\n",
    "    \n",
    "    // add edges\n",
    "    for(var i=0; i<e; i++){\n",
    "        graph.add_edge(choice(vertices), choice(vertices));\n",
    "    }\n",
    "\n",
    "    var start = vertices[0];\n",
    "    var end = vertices[vertices.length-1];\n",
    "    \n",
    "    console.assert(start);\n",
    "    console.assert(end);\n",
    "    \n",
    "    var distance = graph.a_star(start, end).length;\n",
    "    return distance;\n",
    "}\n",
    "\n",
    "var average = function(list){\n",
    "    var sum = 0.0;\n",
    "    for(var i=0; i<list.length; i++){\n",
    "        sum += list[i];\n",
    "    }\n",
    "\n",
    "    return sum / list.length; \n",
    "}\n",
    "\n",
    "var V = [100, 100, 100, 100, 100, 100, 100];\n",
    "var E = [100, 200, 500, 1000, 5000, 10000, 100000];\n",
    "\n",
    "// not sure what the original zip function does....\n",
    "var zip = function(arr0, arr1){\n",
    "    console.assert(arr0.length == arr1.length);\n",
    "    var combo = [];\n",
    "    for(var i=0; i<arr0.length; i++){\n",
    "        combo.push([arr0[i], arr1[i]]);\n",
    "    }\n",
    "    \n",
    "    return combo;\n",
    "}\n",
    "\n",
    "var args = zip(V, E);\n",
    "\n",
    "console.log(path_length(100, 2000));\n",
    "\n",
    "for(var i=0; i<args.length; i++){\n",
    "    console.log(args[i][0], args[i][1], path_length(args[i][0], args[i][1]));\n",
    "}\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Intuitive, right? As the edge count increases relative to the vertex count, the minimal distance between the two decreases. There's more ways to travel. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Javascript (Node.js)",
   "language": "javascript",
   "name": "javascript"
  },
  "language_info": {
   "file_extension": ".js",
   "mimetype": "application/javascript",
   "name": "javascript",
   "version": "8.9.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}