new_solve.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "ename": "NetworkXNoCycle",
     "evalue": "No cycle found.",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mNetworkXNoCycle\u001b[0m                           Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-15-0c517cadce88>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m    267\u001b[0m \u001b[1;31m#     else:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    268\u001b[0m \u001b[1;31m#         T = solve(G)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 269\u001b[1;33m     \u001b[0mT\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mdominate\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mG\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    270\u001b[0m     \u001b[0mfig\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mplt\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mfigure\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mfigsize\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m20\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;36m30\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    271\u001b[0m     \u001b[0mfig\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0madd_subplot\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m211\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mD:\\UCB\\Spring 2020\\CS 170\\project\\graph_algorithm\\dominating_set.py\u001b[0m in \u001b[0;36mdominate\u001b[1;34m(G)\u001b[0m\n\u001b[0;32m     30\u001b[0m                     \u001b[0mminT\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mcopy\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mcopy\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     31\u001b[0m                 \u001b[0mprune\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mcopy\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 32\u001b[1;33m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     33\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     34\u001b[0m     \u001b[0mS\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mnx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mdominating_set\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mG\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mD:\\UCB\\Spring 2020\\CS 170\\project\\graph_algorithm\\dominating_set.py\u001b[0m in \u001b[0;36mprune\u001b[1;34m(g)\u001b[0m\n\u001b[0;32m      9\u001b[0m         \u001b[1;32mnonlocal\u001b[0m \u001b[0mmin_dist\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mminT\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     10\u001b[0m         \u001b[0mcopy\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mg\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mcopy\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 11\u001b[1;33m         \u001b[0mno_cycles\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;32mFalse\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     12\u001b[0m         \u001b[1;32mtry\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     13\u001b[0m             \u001b[0mcycles\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mnx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mfind_cycle\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mg\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mD:\\anaconda\\envs\\170proj\\lib\\site-packages\\networkx\\algorithms\\cycles.py\u001b[0m in \u001b[0;36mfind_cycle\u001b[1;34m(G, source, orientation)\u001b[0m\n\u001b[0;32m    489\u001b[0m     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    490\u001b[0m         \u001b[1;32massert\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mcycle\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m==\u001b[0m \u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 491\u001b[1;33m         \u001b[1;32mraise\u001b[0m \u001b[0mnx\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mexception\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mNetworkXNoCycle\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'No cycle found.'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    492\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    493\u001b[0m     \u001b[1;31m# We now have a list of edges which ends on a cycle.\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mNetworkXNoCycle\u001b[0m: No cycle found."
     ]
    }
   ],
   "source": [
    "from utils import is_valid_network, average_pairwise_distance, average_pairwise_distance_fast\n",
    "import sys\n",
    "import copy\n",
    "from parse import *\n",
    "import networkx as nx\n",
    "import os\n",
    "import matplotlib.pyplot as plt\n",
    "import random\n",
    "from bruteforce import *\n",
    "from dominating_set import *\n",
    "\n",
    "\n",
    "def solve(G):\n",
    "    \"\"\"\n",
    "    Args:\n",
    "        G: networkx.Graph\n",
    "\n",
    "    Returns:\n",
    "        T: networkx.Graph\n",
    "    \"\"\"\n",
    "    # TODO: your code here!\n",
    "    degree = G.degree()\n",
    "    degree_list = [degree[i] for i in range(0, len(degree))]\n",
    "    d = G.number_of_nodes() - 1\n",
    "    if d in degree_list: # if some nodes connect to all the other nodes\n",
    "        node = degree_list.index(d)\n",
    "        if not G.has_edge(node, node):\n",
    "            res = nx.Graph()\n",
    "            res.add_node(node)\n",
    "            return res\n",
    "    val = heuristics(G)\n",
    "    improve_val = improve_heuristics(G)\n",
    "    temp = add_edge(G, val)\n",
    "    return improve(G, temp, improve_val)\n",
    "    # pass\n",
    "\n",
    "\n",
    "def heuristics(G):\n",
    "    \"\"\"\n",
    "    :param G: Given a graph G\n",
    "    :return: the estimated cost of choosing each vertex.\n",
    "    \"\"\"\n",
    "    res = []\n",
    "    degree = G.degree()\n",
    "    deg_para = 10000/G.number_of_edges()\n",
    "    wei_para = -1000/average_pairwise_distance_fast(G)\n",
    "    for i in range(0, G.number_of_nodes()):\n",
    "        total_weight = 0\n",
    "        for neighbour in G.neighbors(i):\n",
    "            total_weight += G.get_edge_data(i, neighbour).get('weight')\n",
    "        res.append(deg_para * degree[i] + wei_para * total_weight)\n",
    "    return res\n",
    "\n",
    "\n",
    "def improve_heuristics(G):\n",
    "    \"\"\"\n",
    "    :param G: Given a graph G\n",
    "    :return: the estimated cost of choosing each vertex.\n",
    "    Used in the improve method\n",
    "    \"\"\"\n",
    "    res = []\n",
    "    degree = G.degree()\n",
    "    deg_para = 0.0\n",
    "    wei_para = 1.0\n",
    "    for i in range(0, G.number_of_nodes()):\n",
    "        total_weight = 0\n",
    "        for neighbour in G.neighbors(i):\n",
    "            total_weight += G.get_edge_data(i, neighbour).get('weight')\n",
    "        res.append(deg_para * degree[i] + wei_para * total_weight)\n",
    "    return res\n",
    "\n",
    "\n",
    "def add_edge(G, val):\n",
    "    \"\"\"\n",
    "    :param G: The original graph, used to check whether the new graph is a valid network.\n",
    "    :param val: estimated cost of choosing each vertex.\n",
    "    :return: possible best result\n",
    "    \"\"\"\n",
    "    best_graph = nx.Graph()\n",
    "    edge_list = []\n",
    "    new_edge = \"\"\n",
    "    node = val.index(max(val))\n",
    "    new_edge += str(node)\n",
    "    max_val = -float(\"inf\")\n",
    "    max_neighbour = 0\n",
    "    for neighbour in G.neighbors(node):\n",
    "        if val[neighbour] > max_val and neighbour != node:\n",
    "            max_val = val[neighbour]\n",
    "            max_neighbour = neighbour\n",
    "    new_edge += \" \" + str(max_neighbour)\n",
    "    new_edge += \" \" + str(G.get_edge_data(node, max_neighbour).get(\"weight\"))\n",
    "    edge_list.append(new_edge)\n",
    "    new_graph = nx.parse_edgelist(edge_list, nodetype=int, data=(('weight', float),))\n",
    "    val[node], val[max_neighbour] = -float(\"inf\"), -float(\"inf\")\n",
    "    if is_valid_network(G, new_graph):\n",
    "        # if average_pairwise_distance_fast(new_graph) < best_so_far:\n",
    "        #     best_so_far = average_pairwise_distance_fast(new_graph)\n",
    "        best_graph = copy.deepcopy(new_graph)\n",
    "        return best_graph\n",
    "\n",
    "    while True:\n",
    "        new_edge = \"\"\n",
    "        max_val = -float(\"inf\")\n",
    "        max_neighbour = 0\n",
    "        max_node = 0\n",
    "        check = False\n",
    "        for node in new_graph.nodes():\n",
    "            for neighbour in G.neighbors(node):\n",
    "                if val[neighbour] > max_val:\n",
    "                    max_val = val[neighbour]\n",
    "                    max_neighbour = neighbour\n",
    "                    max_node = node\n",
    "                    check = True\n",
    "        if not check:\n",
    "            break\n",
    "        new_edge += str(max_node)\n",
    "        new_edge += \" \" + str(max_neighbour)\n",
    "        new_edge += \" \" + str(G.get_edge_data(max_node, max_neighbour).get(\"weight\"))\n",
    "        edge_list.append(new_edge)\n",
    "        new_graph = nx.parse_edgelist(edge_list, nodetype=int, data=(('weight', float),))\n",
    "        val[max_node], val[max_neighbour] = -float(\"inf\"), -float(\"inf\")\n",
    "        if is_valid_network(G, new_graph):\n",
    "            best_graph = copy.deepcopy(new_graph)\n",
    "            break\n",
    "    return best_graph\n",
    "\n",
    "\n",
    "def improve(G, temp, val):\n",
    "    \"\"\"\n",
    "    :param G: The original graph\n",
    "    :param temp: Best graph we get so far. It's already a valid network, but in some cases add a new vertex can\n",
    "    reduce the cost\n",
    "    :param val: Heurisitics\n",
    "    :return: new Best graph\n",
    "    \"\"\"\n",
    "    best_so_far = average_pairwise_distance_fast(temp)\n",
    "    new_graph = copy.deepcopy(temp)\n",
    "    while True:\n",
    "        min_val = float(\"inf\")\n",
    "        min_neighbour = 0\n",
    "        min_node = 0\n",
    "        check = False\n",
    "        for node in temp.nodes():\n",
    "            for neighbour in G.neighbors(node):\n",
    "                if val[neighbour] < min_val:\n",
    "                    min_val = val[neighbour]\n",
    "                    min_neighbour = neighbour\n",
    "                    min_node = node\n",
    "        min_weight = G.get_edge_data(min_node, min_neighbour).get(\"weight\")\n",
    "        new_graph.add_edge(min_node, min_neighbour, weight=min_weight)\n",
    "        val[min_node], val[min_neighbour] = -1, -1\n",
    "        if is_valid_network(G, new_graph):\n",
    "            if average_pairwise_distance_fast(new_graph) < best_so_far:\n",
    "                best_so_far = average_pairwise_distance_fast(new_graph)\n",
    "                check = True\n",
    "        if not check:\n",
    "            return temp\n",
    "    return new_graph\n",
    "\n",
    "\n",
    "# def solve(G):\n",
    "#     \"\"\"\n",
    "#     Args:\n",
    "#         G: networkx.Graph\n",
    "#     Returns:\n",
    "#         T: networkx.Graph\n",
    "#     \"\"\"\n",
    "#     # TODO: your code here!\n",
    "#     mst_g = nx.minimum_spanning_tree(G)\n",
    "#     best_graph = copy.deepcopy(G)\n",
    "#     cost_so_far = average_pairwise_distance_fast(mst_g)\n",
    "#     assert mst_g.number_of_edges() == mst_g.number_of_nodes() - 1\n",
    "#     memo = []\n",
    "#     for i in range(1, 4):\n",
    "#         res = delete_edge(G, mst_g, i, memo)\n",
    "#         if res[0] < cost_so_far:\n",
    "#             cost_so_far = res[0]\n",
    "#             print(cost_so_far)\n",
    "#             best_graph = copy.deepcopy(res[1])\n",
    "#         else:\n",
    "#             break\n",
    "#     return best_graph\n",
    "#\n",
    "# def delete_edge(G, mst, k, memo):\n",
    "#     \"\"\"\n",
    "#     Given a graph mst, delete k edges randomly. Check all possible deletions whether they are valid networks.\n",
    "#     Always delete the edges that connects to the leaf node.\n",
    "#\n",
    "#     G is the original graph. Used to check whether the new graph is a valid network.\n",
    "#\n",
    "#     memo is a list storing all possible graphs that delete k - 1 edges(k > 1).\n",
    "#     \"\"\"\n",
    "#     best_so_far = float(\"inf\")\n",
    "#     new_graph = copy.deepcopy(mst)\n",
    "#     if k == 0:\n",
    "#         return [average_pairwise_distance_fast(mst), mst]\n",
    "#     elif k == 1:\n",
    "#         degree = mst.degree()\n",
    "#         for i in mst.nodes():\n",
    "#             if degree[i] == 1:  # degree(leaf node) = 1\n",
    "#                 temp_g = copy.deepcopy(mst)\n",
    "#                 neighbour_node = next(temp_g.neighbors(i))\n",
    "#                 temp_g.remove_edge(i, neighbour_node)\n",
    "#                 temp_g.remove_node(i)\n",
    "#                 if is_valid_network(G, temp_g):\n",
    "#                     memo.append(temp_g)\n",
    "#                     # print(len(memo))\n",
    "#                     temp = delete_edge(G, temp_g, 0, memo)\n",
    "#                     if temp[0] < best_so_far:\n",
    "#                         best_so_far = temp[0]\n",
    "#                         new_graph = copy.deepcopy(temp[1])\n",
    "#         if mst in memo:\n",
    "#             memo.remove(mst)\n",
    "#     else:\n",
    "#         length = len(memo)\n",
    "#         for i in range(0, length):\n",
    "#             temp = delete_edge(G, memo[0], 1, memo)\n",
    "#             if temp[0] < best_so_far:\n",
    "#                 best_so_far = temp[0]\n",
    "#                 new_graph = copy.deepcopy(temp[1])\n",
    "#     return [best_so_far, new_graph]\n",
    "\n",
    "\n",
    "# Here's an example of how to run your solver.\n",
    "# Usage: python3 solver.py test.in\n",
    "# if __name__ == '__main__':\n",
    "#     assert len(sys.argv) == 2\n",
    "#     path = sys.argv[1]\n",
    "#     G = read_input_file(path)\n",
    "#     T = solve(G)\n",
    "#     assert is_valid_network(G, T)\n",
    "#     print(*T.nodes())\n",
    "#     for i in T.edges():\n",
    "#         print(i[0], i[1])\n",
    "#     print(\"cost:\", average_pairwise_distance_fast(T))\n",
    "    # print(\"Average  pairwise distance: {}\".format(average_pairwise_distance(T)))\n",
    "    # write_output_file(T, 'out/test.out')\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "#         input_folder_path = 'inputs'\n",
    "#         for input_file in os.listdir(input_folder_path):\n",
    "#             print(input_file)\n",
    "#             full_path = os.path.join(input_folder_path, input_file)\n",
    "#             G = read_input_file(full_path)\n",
    "#             total = sum([1 for n in G.nodes() if G.degree(n) <= 2])\n",
    "#             leaves = sum([1 for n in G.nodes() if G.degree(n) < 2])\n",
    "#             if total >= 15 and G.number_of_nodes() <= 25 and leaves <= 12:\n",
    "#                 T = bruteforce(G)\n",
    "#             else:\n",
    "#                 T = solve(G)\n",
    "#             assert is_valid_network(G, T), \"T is not a valid network of G.\"\n",
    "#             # Compare previous result with new result, update if improvement seen\n",
    "#             old = read_output_file('outputs/' + input_file[:-2] + 'out', G)\n",
    "#             dist_old = average_pairwise_distance_fast(old)\n",
    "#             dist_new = average_pairwise_distance_fast(T)\n",
    "#             print(\"Old Average  pairwise distance: {}\".format(dist_old))\n",
    "#             print(\"New Average  pairwise distance: {}\".format(dist_new))\n",
    "#             if dist_old > dist_new:\n",
    "#                 write_output_file(T, 'outputs/' + input_file[:-2] + 'out')\n",
    "\n",
    "    path = 'inputs/small-4.in'\n",
    "    G = read_input_file(path)\n",
    "    # Added: if more than 15 nodes with degree <= 2\n",
    "#     total = sum([1 for n in G.nodes() if G.degree(n) <= 2])\n",
    "#     if total >= 15:\n",
    "#         T = bruteforce(G)\n",
    "#     else:\n",
    "#         T = solve(G)\n",
    "    T = dominate(G)\n",
    "    fig = plt.figure(figsize=(20, 30))\n",
    "    fig.add_subplot(211)\n",
    "    pos = nx.spring_layout(G)\n",
    "\n",
    "    labels = nx.get_edge_attributes(G, 'weight')\n",
    "\n",
    "    nx.draw_networkx(G, pos=pos, node_color='yellow')\n",
    "    nx.draw_networkx(G.edge_subgraph(T.edges()), pos=pos, node_color='red', edge_color='red')\n",
    "    #nx.draw_networkx(T, pos=pos, node_color='blue')\n",
    "    nx.draw_networkx_edge_labels(G, pos, edge_labels=labels)\n",
    "    assert is_valid_network(G, T), \"T is not a valid network of G.\"\n",
    "\n",
    "    print(\"Average  pairwise distance: {}\".format(average_pairwise_distance(T)))\n",
    "    write_output_file(T, 'outputs/' + path[-10:-2] + 'out')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}