experimental.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Experimental"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 107,
   "metadata": {
    "scrolled": false
   },
   "outputs": [],
   "source": [
    "df = pd.DataFrame(clusters_points)\n",
    "df['new_conn'] = df['connected']\n",
    "nodes = df[['X', 'Y', 'area_m2', 'pop_sum', 'connected', 'new_conn']].reset_index().values.astype(int).tolist()\n",
    "for node in nodes:\n",
    "    node.extend([0, [], []])  # add default 0's for off_grid_cost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 108,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_hash_table(clusters, distance_limit):\n",
    "    hash_table = defaultdict(lambda: defaultdict(list))\n",
    "    for node in clusters:\n",
    "        hash_x = int(node[1] / distance_limit)\n",
    "        hash_y = int(node[2] / distance_limit)\n",
    "        hash_table[hash_x][hash_y].append(node[0])\n",
    "    return hash_table       \n",
    "\n",
    "def get_near(hash_table, unelec_cluster, distance_limit):\n",
    "\n",
    "    near = []\n",
    "    hash_x = int(unelec_cluster[1] / distance_limit)\n",
    "    hash_y = int(unelec_cluster[2] / distance_limit)\n",
    "\n",
    "    near.extend(hash_table.get(hash_x, {}).get(hash_y, []))\n",
    "    near.extend(hash_table.get(hash_x, {}).get(hash_y - 1, []))\n",
    "    near.extend(hash_table.get(hash_x, {}).get(hash_y + 1, []))\n",
    "\n",
    "    near.extend(hash_table.get(hash_x + 1, {}).get(hash_y, []))\n",
    "    near.extend(hash_table.get(hash_x + 1, {}).get(hash_y - 1, []))\n",
    "    near.extend(hash_table.get(hash_x + 1, {}).get(hash_y + 1, []))\n",
    "\n",
    "    near.extend(hash_table.get(hash_x - 1, {}).get(hash_y, []))\n",
    "    near.extend(hash_table.get(hash_x - 1, {}).get(hash_y - 1, []))\n",
    "    near.extend(hash_table.get(hash_x - 1, {}).get(hash_y + 1, []))\n",
    "\n",
    "    return near"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 109,
   "metadata": {},
   "outputs": [],
   "source": [
    "search_radii = [1000, 2000, 5000, 10000, 20000, 50000, 150000]\n",
    "hash_tables = {}\n",
    "\n",
    "for radius in search_radii:\n",
    "    hash_tables[radius] = get_hash_table(nodes, radius)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 110,
   "metadata": {},
   "outputs": [],
   "source": [
    "network = []\n",
    "counter = 0\n",
    "for node in nodes:\n",
    "    if node[5] == 0:\n",
    "        xs = node[1]\n",
    "        ys = node[2]\n",
    "        \n",
    "        for radius, table in hash_tables.items():\n",
    "            near = get_near(table, node, radius)\n",
    "            \n",
    "            if len(near) >= 5 or radius == search_radii[-1]:  # also check if any near are connected?\n",
    "                for n in near:\n",
    "                   \n",
    "                    if n != node[0] and node[0] not in nodes[n][9]:\n",
    "                        xe = nodes[n][1]\n",
    "                        ye = nodes[n][2]\n",
    "                        length = sqrt((xe - xs)**2 + (ye - ys)**2)\n",
    "                        network.append([counter, xs, ys, xe, ye, node[0], n, length, 0])\n",
    "                        \n",
    "                        nodes[n][8].append(counter)\n",
    "                        nodes[n][9].append(node[0])\n",
    "                        \n",
    "                        node[8].append(counter)\n",
    "                        node[9].append(n)\n",
    "                        \n",
    "                        counter += 1\n",
    "                        \n",
    "                break\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 111,
   "metadata": {},
   "outputs": [],
   "source": [
    "# off-grid costs\n",
    "demand_per_person_kwh_month = 2 # 6kWh/month = MTF Tier 2\n",
    "demand_per_person_kw_peak = demand_per_person_kwh_month / (4*30)  # 130 4hours/day*30days/month based on MTF numbers, should use a real demand curve\n",
    "mg_gen_cost_per_kw = 9e99\n",
    "mg_cost_per_m2 = 2\n",
    "\n",
    "for node in nodes:\n",
    "    if node[5] == 0:\n",
    "        node[7] = node[4]*demand_per_person_kw_peak*mg_gen_cost_per_kw + node[3]*mg_cost_per_m2\n",
    "\n",
    "# grid costs\n",
    "cost_wire_per_m = 39\n",
    "grid_cost_per_m2 = 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# METHOD 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_best(nodes, network, index, prev_arc, b_pop, b_length, b_nodes, b_arcs, c_pop, c_length, c_nodes, c_arcs, tbc):\n",
    "    if nodes[index][6] == 0:        \n",
    "        c_pop += nodes[index][4]\n",
    "        c_length += network[prev_arc][7]\n",
    "        c_nodes.append(index)\n",
    "        c_arcs.append(prev_arc)\n",
    "              \n",
    "        if c_pop/c_length > b_pop/b_length:\n",
    "            b_pop = c_pop\n",
    "            b_length = c_length\n",
    "            b_nodes[:] = c_nodes[:]\n",
    "            b_arcs[:] = c_arcs[:]\n",
    "    \n",
    "        connected_arcs = [network[arc_index] for arc_index in nodes[index][8]]\n",
    "        for arc in connected_arcs:\n",
    "            if arc[8] == 0 and arc[0] != prev_arc and arc[0] not in c_arcs and arc[0] not in [j for sub in [item[2] for item in tbc] for j in sub]:\n",
    "\n",
    "                goto = 6 if arc[5] == index else 5\n",
    "                if arc[goto] not in c_nodes:\n",
    "                    nodes, network, b_pop, b_length, best_nodes, best_arcs = find_best(\n",
    "                        nodes, network, arc[goto], arc[0],\n",
    "                        b_pop, b_length, b_nodes, b_arcs,\n",
    "                        c_pop, c_length, c_nodes, c_arcs, tbc)\n",
    "                \n",
    "    return nodes, network, b_pop, b_length, b_nodes, b_arcs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def alt_best(nodes, network, index, prev_arc, b_pop, b_length, b_nodes, b_arcs, c_pop, c_length, c_nodes, c_arcs, tbc):\n",
    "    if nodes[index][6] == 0 and index not in [j for sub in [item[1] for item in tbc] for j in sub]:        \n",
    "        c_pop += nodes[index][4]\n",
    "        c_length += network[prev_arc][7]\n",
    "        c_nodes.append(index)\n",
    "        c_arcs.append(prev_arc)\n",
    "              \n",
    "        if c_pop/c_length > b_pop/b_length:\n",
    "            b_pop = c_pop\n",
    "            b_length = c_length\n",
    "            b_nodes[:] = c_nodes[:]\n",
    "            b_arcs[:] = c_arcs[:]\n",
    "    \n",
    "        connected_arcs = [network[arc_index] for arc_index in nodes[index][8]]\n",
    "        for arc in connected_arcs:\n",
    "            if arc[8] == 0 and arc[0] != prev_arc and arc[0] not in c_arcs and arc[0] not in [j for sub in [item[2] for item in tbc] for j in sub]:\n",
    "\n",
    "                goto = 6 if arc[5] == index else 5\n",
    "                if arc[goto] not in c_nodes and arc[goto] not in [j for sub in [item[1] for item in tbc] for j in sub]:\n",
    "                    nodes, network, b_pop, b_length, best_nodes, best_arcs = alt_best(\n",
    "                        nodes, network, arc[goto], arc[0],\n",
    "                        b_pop, b_length, b_nodes, b_arcs,\n",
    "                        c_pop, c_length, c_nodes, c_arcs, tbc)\n",
    "    \n",
    "    return nodes, network, b_pop, b_length, b_nodes, b_arcs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "tbc = []\n",
    "found = True\n",
    "while found:\n",
    "    found = False\n",
    "    for node in nodes:\n",
    "        \n",
    "        if node[6] == 1 or node[0] in [j for sub in [item[1] for item in tbc] for j in sub]:\n",
    "            print()\n",
    "            print()\n",
    "            print(' -------NODE ', node[0], '------')\n",
    "            \n",
    "            connected_arcs = [network[arc_index] for arc_index in node[8]]\n",
    "            for arc in connected_arcs:\n",
    "                print('--ARC ', arc[0])\n",
    "                if arc[8] == 0 and arc[0] not in [j for sub in [item[2] for item in tbc] for j in sub]:\n",
    "                    \n",
    "                    goto = 6 if arc[5] == node[0] else 5\n",
    "                    nodes, network, b_length, b_pop, b_nodes, b_arcs = find_best(\n",
    "                        nodes, network, arc[goto], arc[0], 0, 1e-9, [], [], 0, 1e-9, [], [], tbc)                \n",
    "\n",
    "                    best_nodes = [nodes[i] for i in b_nodes]\n",
    "                    best_arcs = [network[i] for i in b_arcs]\n",
    "                    mg_cost = sum([node[7] for node in best_nodes])\n",
    "                    grid_cost = (cost_wire_per_m * sum(arc[7] for arc in best_arcs) + \n",
    "                                 grid_cost_per_m2 * sum([node[3] for node in best_nodes]))\n",
    "\n",
    "                    if grid_cost < mg_cost:\n",
    "                        # check if any have marked as tbc\n",
    "                        found_worse = False\n",
    "                        found_better = False\n",
    "                        for index, item in enumerate(tbc):\n",
    "                            if set(b_nodes).intersection(item[1]):\n",
    "                                if b_pop/b_length < item[0]:\n",
    "                                    found_worse = True\n",
    "                                    remove_from_tbc = index\n",
    "                                else:\n",
    "                                    found_better = True\n",
    "                                break                             \n",
    "                                \n",
    "                        if found_worse:\n",
    "                            print('found worse so removing', tbc[remove_from_tbc])\n",
    "                            del tbc[remove_from_tbc]\n",
    "                        elif found_better:\n",
    "                            nodes, network, b_length, b_pop, b_nodes, b_arcs = alt_best(\n",
    "                                nodes, network, arc[goto], arc[0], 0, 1e-9, [], [], 0, 1e-9, [], [], tbc)                \n",
    "\n",
    "                            best_nodes = [nodes[i] for i in b_nodes]\n",
    "                            best_arcs = [network[i] for i in b_arcs]\n",
    "                            mg_cost = sum([node[7] for node in best_nodes])\n",
    "                            grid_cost = (cost_wire_per_m * sum(arc[7] for arc in best_arcs) + \n",
    "                                         grid_cost_per_m2 * sum([node[3] for node in best_nodes]))\n",
    "\n",
    "                            if grid_cost < mg_cost:\n",
    "                                #print()\n",
    "                                #print(tbc)\n",
    "                                print('found better but adding', b_nodes, 'arcs', b_arcs)\n",
    "                                tbc.append((b_pop/b_length, b_nodes, b_arcs))\n",
    "                            \n",
    "                            continue\n",
    "\n",
    "                        # mark as to be connected\n",
    "                        print('adding ', b_nodes, 'arcs', b_arcs)\n",
    "                        print()\n",
    "                        tbc.append((b_pop/b_length, b_nodes, b_arcs))\n",
    "                        found = True\n",
    "            print('tbc', tbc)\n",
    "            print()\n",
    "        \n",
    "    print('TBC ', tbc)\n",
    "    print('####')\n",
    "    print('####')\n",
    "    print('####')\n",
    "        \n",
    "for item in tbc:\n",
    "    for node in item[1]:\n",
    "        nodes[node][6] = 1\n",
    "    for arc in item[2]:\n",
    "        network[arc][8] = 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# METHOD 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 112,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_best(nodes, network, index, prev_arc, br, bs, cr, cs, tbc):\n",
    "    if nodes[index][6] == 0 and index not in [c[0] for c in cs]:\n",
    "        #print('cs', [c[0] for c in cs])\n",
    "        #print('idx', index)\n",
    "        pop = cr[0] + nodes[index][4]\n",
    "        length = cr[1] + network[prev_arc][7]\n",
    "        \n",
    "        cont = True\n",
    "        tentatives = [n[0] for n in tbc]\n",
    "        if index in tentatives:\n",
    "            cont = False\n",
    "            if pop/length > tbc[tentatives.index(index)][2]:\n",
    "                print('removing', tbc[tentatives.index(index)])\n",
    "                del tbc[tentatives.index(index)]\n",
    "                cont = True\n",
    "        \n",
    "        cr = [pop, length]\n",
    "        cs = cs[:] + [(index, prev_arc, pop/length)]\n",
    "        \n",
    "        if cont:\n",
    "            if len(br) == 0 or cr[0]/cr[1] > br[0]/br[1]:\n",
    "                br[:] = cr[:]\n",
    "                bs[:] = cs[:]\n",
    "            \n",
    "            connected_arcs = [network[arc_index] for arc_index in nodes[index][8]]\n",
    "            for arc in connected_arcs:\n",
    "                if arc[8] == 0 and arc[0] != prev_arc and arc[0] not in [c[1] for c in cs]:# and arc[0] not in [n[2] for n in tbc]:\n",
    "\n",
    "                    goto = 6 if arc[5] == index else 5\n",
    "                    if arc[goto] not in [c[0] for c in cs]:\n",
    "                        nodes, network, br, bs = find_best(\n",
    "                            nodes, network, arc[goto], arc[0], br, bs, cr, cs, tbc)\n",
    "        else:\n",
    "            goto_arc = tbc[tentatives.index(index)][1]\n",
    "            node = network[goto_arc][5] if network[goto_arc][5] != index else network[goto_arc][6]\n",
    "\n",
    "            if node not in [c[0] for c in cs]:\n",
    "                nodes, network, br, bs = find_best(\n",
    "                    nodes, network, node, goto_arc, br, bs, cr, cs, tbc)\n",
    "                \n",
    "    return nodes, network, br, bs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 113,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      " -------NODE  2 ------\n",
      "--ARC  1\n",
      "adding  [(0, 1, 0.7756358109962858)]\n",
      "--ARC  6\n",
      "adding  [(1, 6, 0.01177840052747079)]\n",
      "--ARC  11\n",
      "removing (0, 1, 0.7756358109962858)\n",
      "removing (1, 6, 0.01177840052747079)\n",
      "adding  [(3, 11, 0.011537134449123543), (0, 2, 0.7816606141452157)]\n",
      "--ARC  15\n",
      "removing (3, 11, 0.011537134449123543)\n",
      "adding  [(5, 15, 0.00031040111162922656), (0, 3, 0.7756399723639926), (3, 2, 0.5575758670112337)]\n",
      "--ARC  18\n",
      "removing (5, 15, 0.00031040111162922656)\n",
      "adding  [(6, 18, 5.620494589928472e-05), (1, 10, 0.005913267245088932)]\n",
      "TBC  [(0, 2, 0.7816606141452157), (0, 3, 0.7756399723639926), (3, 2, 0.5575758670112337), (6, 18, 5.620494589928472e-05), (1, 10, 0.005913267245088932)]\n",
      "\n",
      "\n",
      " -------NODE  4 ------\n",
      "--ARC  4\n",
      "--ARC  9\n",
      "removing (1, 10, 0.005913267245088932)\n",
      "removing (6, 18, 5.620494589928472e-05)\n",
      "adding  [(1, 9, 0.040032967303875414)]\n",
      "--ARC  13\n",
      "--ARC  16\n",
      "adding  [(5, 16, 8.405093144184302e-05)]\n",
      "--ARC  19\n",
      "adding  [(6, 19, 4.725937634817695e-05)]\n",
      "TBC  [(0, 2, 0.7816606141452157), (0, 3, 0.7756399723639926), (3, 2, 0.5575758670112337), (1, 9, 0.040032967303875414), (5, 16, 8.405093144184302e-05), (6, 19, 4.725937634817695e-05)]\n",
      "####\n",
      "####\n",
      "####\n"
     ]
    }
   ],
   "source": [
    "tbc = []\n",
    "found = True\n",
    "while found:\n",
    "    \n",
    "    found = False\n",
    "    for node in nodes:\n",
    "        \n",
    "        if node[6] == 1:# or node[0] in [n[0] for n in tbc]:\n",
    "            print()\n",
    "            print()\n",
    "            print(' -------NODE ', node[0], '------')\n",
    "            \n",
    "            connected_arcs = [network[arc_index] for arc_index in node[8]]\n",
    "            for arc in connected_arcs:\n",
    "                print('--ARC ', arc[0])\n",
    "                if arc[8] == 0 and arc[0] not in [n[2] for n in tbc]:\n",
    "                    \n",
    "                    goto = 6 if arc[5] == node[0] else 5\n",
    "                    nodes, network, br, bs = find_best(\n",
    "                        nodes, network, arc[goto], arc[0], [], [], [0,0], [], tbc)\n",
    "                    \n",
    "                    best_nodes = [nodes[i] for i in [n[0] for n in bs]]\n",
    "                    best_arcs = [network[i] for i in [n[1] for n in bs]]\n",
    "                    mg_cost = sum([node[7] for node in best_nodes])\n",
    "                    grid_cost = (cost_wire_per_m * sum(arc[7] for arc in best_arcs) + \n",
    "                                 grid_cost_per_m2 * sum([node[3] for node in best_nodes]))\n",
    "\n",
    "                    if grid_cost < mg_cost:\n",
    "                        print('adding ', bs)\n",
    "                        tbc.extend(bs)\n",
    "                        #found = True\n",
    "        \n",
    "            print('TBC ', tbc)\n",
    "    print('####')\n",
    "    print('####')\n",
    "    print('####')\n",
    "    #if len(tbc) > 0:\n",
    "    #    found = True\n",
    "for item in tbc:\n",
    "    nodes[item[0]][6] = 1\n",
    "    network[item[1]][8] = 1"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}