solver.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "medium-264\n",
      "Old Average  pairwise distance: 0.07728654970760233\n",
      "New Average  pairwise distance: 0.09025714285714286\n",
      "medium-263\n",
      "Old Average  pairwise distance: 0.9826666666666667\n",
      "New Average  pairwise distance: 0.918\n",
      "medium-262\n",
      "Old Average  pairwise distance: 435.6190476190476\n",
      "New Average  pairwise distance: 423.3333333333333\n",
      "medium-261\n",
      "Old Average  pairwise distance: 21.555555555555557\n",
      "New Average  pairwise distance: 18.87272727272727\n",
      "medium-260\n",
      "Old Average  pairwise distance: 47.983\n",
      "New Average  pairwise distance: 71.099\n",
      "medium-256\n",
      "Old Average  pairwise distance: 6.487394957983193\n",
      "New Average  pairwise distance: 5.154150197628459\n",
      "medium-255\n",
      "Old Average  pairwise distance: 31.246753246753247\n",
      "New Average  pairwise distance: 30.985507246376812\n",
      "medium-53\n",
      "Old Average  pairwise distance: 0\n",
      "New Average  pairwise distance: 0\n",
      "medium-251\n",
      "Old Average  pairwise distance: 156.55040322580646\n",
      "New Average  pairwise distance: 155.00645161290322\n",
      "medium-247\n",
      "Old Average  pairwise distance: 5.887692307692308\n",
      "New Average  pairwise distance: 6.100985221674877\n",
      "medium-246\n",
      "Old Average  pairwise distance: 58.181045751633995\n",
      "New Average  pairwise distance: 55.75916666666667\n",
      "edium-242\n"
     ]
    },
    {
     "ename": "FileNotFoundError",
     "evalue": "[Errno 2] No such file or directory: 'inputs/edium-242.in'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mFileNotFoundError\u001b[0m                         Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-7-11ed13f072e4>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m\u001b[0m\n\u001b[0;32m    358\u001b[0m         \u001b[0mpath\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;34m'inputs/'\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mfile\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;34m'.in'\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    359\u001b[0m     \u001b[1;31m#path = 'inputs/small-4.in'\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 360\u001b[1;33m         \u001b[0mG\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mread_input_file\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mpath\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    361\u001b[0m         \u001b[0mTree_list\u001b[0m \u001b[1;33m=\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    362\u001b[0m         \u001b[0mtimeout\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mtime\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mtime\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;33m+\u001b[0m \u001b[1;36m60\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\\parse.py\u001b[0m in \u001b[0;36mread_input_file\u001b[1;34m(path, max_size)\u001b[0m\n\u001b[0;32m     26\u001b[0m     \u001b[1;33m:\u001b[0m\u001b[1;32mreturn\u001b[0m\u001b[1;33m:\u001b[0m \u001b[0mnetworkx\u001b[0m \u001b[0mGraph\u001b[0m \u001b[1;32mis\u001b[0m \u001b[0mthe\u001b[0m \u001b[0minput\u001b[0m \u001b[1;32mis\u001b[0m \u001b[0mwell\u001b[0m \u001b[0mformed\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mAssertionError\u001b[0m \u001b[0mthrown\u001b[0m \u001b[0motherwise\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     27\u001b[0m     \"\"\"\n\u001b[1;32m---> 28\u001b[1;33m     \u001b[1;32mwith\u001b[0m \u001b[0mopen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mpath\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m\"r\"\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mas\u001b[0m \u001b[0mfo\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     29\u001b[0m         \u001b[0mn\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mfo\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mreadline\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mstrip\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     30\u001b[0m         \u001b[1;32massert\u001b[0m \u001b[0mn\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0misdigit\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;31mFileNotFoundError\u001b[0m: [Errno 2] No such file or directory: 'inputs/edium-242.in'"
     ]
    }
   ],
   "source": [
    "# below is the method using degree heuristic to let MST pick higher-degree nodes\n",
    "\n",
    "import networkx as nx\n",
    "from parse import read_input_file, write_output_file, read_output_file\n",
    "import utils\n",
    "from utils import is_valid_network, average_pairwise_distance, average_pairwise_distance_fast\n",
    "import os\n",
    "import sys\n",
    "import matplotlib.pyplot as plt\n",
    "import random\n",
    "import numpy as np\n",
    "import itertools\n",
    "import time\n",
    "\n",
    "\n",
    "def bruteforce(G):\n",
    "    list_of_trees = []\n",
    "    min_dist = 1000000\n",
    "    minT = nx.Graph()\n",
    "\n",
    "    # Remove degree 1 nodes and add their neighbors to minT\n",
    "    def traverse(T, G, G_copy):\n",
    "        nonlocal min_dist\n",
    "        nonlocal minT\n",
    "        if G_copy.number_of_edges() == 0:\n",
    "            return\n",
    "        for e in G_copy.edges():\n",
    "            u, v = e[0], e[1]\n",
    "            if e in T.edges():\n",
    "                continue\n",
    "            copy = T.copy()\n",
    "            temp = G_copy.copy()\n",
    "            T.add_node(u)\n",
    "            T.add_node(v)\n",
    "            T.add_edge(v, u, weight=G[v][u]['weight'])\n",
    "            temp.remove_edge(u, v)\n",
    "            if is_valid_network(G, T):\n",
    "                if average_pairwise_distance_fast(T) < min_dist:\n",
    "                    min_dist = average_pairwise_distance_fast(T)\n",
    "                    minT = T.copy()\n",
    "                traverse(T, G, temp)\n",
    "            elif not nx.is_dominating_set(G, T.nodes()) or not nx.is_connected(T):\n",
    "                traverse(T, G, temp)\n",
    "            T = copy.copy()\n",
    "\n",
    "    def findChain(G):\n",
    "        nonlocal confirmed\n",
    "        nonlocal T\n",
    "        nonlocal G_copy\n",
    "        changed = False\n",
    "        nodes = [n for n in G.nodes()]\n",
    "        for v in nodes:\n",
    "            if G.degree(v) == 1:\n",
    "                u = list(G.neighbors(v))[0]\n",
    "                confirmed.append(u)\n",
    "                T.add_node(u)\n",
    "                if u in confirmed and v in confirmed:\n",
    "                    T.add_edge(u, v, weight=G[u][v]['weight'])\n",
    "                    G_copy.remove_edge(u, v)\n",
    "                G.remove_node(v)\n",
    "                changed = True\n",
    "        if changed:\n",
    "            findChain(G)\n",
    "\n",
    "    def remove(copy, G_copy, k):\n",
    "        nonlocal min_dist\n",
    "        nonlocal minT\n",
    "        has_valid = False\n",
    "        for c in itertools.combinations(G_copy.edges(), k):\n",
    "            temp = copy.copy()\n",
    "            for e in c:\n",
    "                u, v = e[0], e[1]\n",
    "                if copy.degree(u) == 1:\n",
    "                    copy.remove_node(u)\n",
    "                elif copy.degree(v) == 1:\n",
    "                    copy.remove_node(v)\n",
    "                else:\n",
    "                    copy.remove_edge(u, v)\n",
    "            if is_valid_network(G, copy):\n",
    "                has_valid = True\n",
    "                if average_pairwise_distance_fast(copy) < min_dist:\n",
    "                    min_dist = average_pairwise_distance_fast(copy)\n",
    "                    minT = copy.copy()\n",
    "            elif nx.is_dominating_set(G, copy.nodes()) and nx.is_connected(copy):\n",
    "                has_valid = True\n",
    "            copy = temp\n",
    "        if not has_valid:\n",
    "            return\n",
    "        remove(copy, G_copy, k + 1)\n",
    "        # if copy.number_of_nodes() == 1:\n",
    "        #     if is_valid_network(G, copy):\n",
    "        #         minT = copy\n",
    "        #     return\n",
    "        # for e in G_copy.edges():\n",
    "        #     if e not in copy.edges():\n",
    "        #         continue\n",
    "        #     u, v = e[0], e[1]\n",
    "        #     if copy.degree(u) == 1:\n",
    "        #         if u in confirmed:\n",
    "        #             continue\n",
    "        #         copy.remove_node(u)\n",
    "        #     elif copy.degree(v) == 1:\n",
    "        #         if v in confirmed:\n",
    "        #             continue\n",
    "        #         copy.remove_node(v)\n",
    "        #     else:\n",
    "        #         copy.remove_edge(u, v)\n",
    "        #     if is_valid_network(G, copy):\n",
    "        #         if average_pairwise_distance_fast(copy) < min_dist:\n",
    "        #             min_dist = average_pairwise_distance_fast(copy)\n",
    "        #             minT = copy.copy()\n",
    "        #         remove(copy, G_copy)\n",
    "        #     elif nx.is_dominating_set(G, copy.nodes) and nx.is_connected(copy):\n",
    "        #         remove(copy, G_copy)\n",
    "        #     if u not in copy.nodes():\n",
    "        #         copy.add_node(u)\n",
    "        #     elif v not in copy.nodes():\n",
    "        #         copy.add_node(v)\n",
    "        #     copy.add_edge(u, v, weight=G[u][v]['weight'])\n",
    "\n",
    "    # minT = min(list_of_trees, key=lambda t: average_pairwise_distance_fast(t))\n",
    "    confirmed = []\n",
    "    T = nx.Graph()\n",
    "    G_copy = G.copy()\n",
    "    findChain(G.copy())\n",
    "    if T.number_of_nodes() != 0 and is_valid_network(G, T):\n",
    "        min_dist = average_pairwise_distance_fast(T)\n",
    "        minT = T.copy()\n",
    "    else:\n",
    "        min_dist = average_pairwise_distance_fast(G)\n",
    "        minT = G.copy()\n",
    "    # for v in G.nodes():\n",
    "    #     if G.degree(v) == 1:\n",
    "    #         confirmed.append(list(G.neighbors(v))[0])\n",
    "    # remove(G.copy())\n",
    "    # T = nx.Graph()\n",
    "    remove(G.copy(), G_copy, 1)\n",
    "    return minT\n",
    "\n",
    "\n",
    "def solve(G):\n",
    "    \"\"\"\n",
    "    Args:\n",
    "        G: networkx.Graph\n",
    "\n",
    "    Returns:\n",
    "        T: networkx.Graph\n",
    "    \"\"\"\n",
    "\n",
    "    def prune(g):\n",
    "        nonlocal min_T\n",
    "        copy = g.copy()\n",
    "        if g.number_of_edges() == 0:\n",
    "            min_T = g\n",
    "            return\n",
    "        e = random.choice(list(g.edges()))\n",
    "        if copy.degree(e[0]) == 1:\n",
    "            copy.remove_node(e[0])\n",
    "        elif copy.degree(e[1]) == 1:\n",
    "            copy.remove_node(e[1])\n",
    "        else:\n",
    "            copy.remove_edge(e[0], e[1])\n",
    "        if is_valid_network(G, copy):\n",
    "#             d = average_pairwise_distance_fast(copy)\n",
    "#             min_dist = average_pairwise_distance_fast(min_T)\n",
    "#             if d < min_dist:\n",
    "#                 min_T = copy.copy()\n",
    "            prune(copy)\n",
    "        elif nx.is_connected(copy) and nx.is_dominating_set(G, copy):\n",
    "            prune(copy)\n",
    "\n",
    "    #     Special case for one central node\n",
    "    for node in G.nodes():\n",
    "        if G.degree(node) == G.number_of_nodes() - 1 and not G.has_edge(node, node):\n",
    "            T = nx.Graph()\n",
    "            T.add_node(node)\n",
    "            return T\n",
    "    # added: weight <- weight - degree, to let MST choose higher-degree nodes\n",
    "    G_copy = G.copy()\n",
    "    for edge in G_copy.edges():\n",
    "        u, v = edge[0], edge[1]\n",
    "        G_copy[u][v]['weight'] /= (G_copy.degree(u) + G_copy.degree(v)) / 2\n",
    "        #G_copy[u][v]['weight'] *= max(nx.eccentricity(G, u), nx.eccentricity(G, v)) / 2\n",
    "        G_copy[u][v]['weight'] /= np.exp(nx.edge_betweenness_centrality(G, k=5, weight='weight')[edge])\n",
    "        G_copy[u][v]['weight'] *= random.uniform(0.2, 5.8)\n",
    "\n",
    "    #     T = nx.Graph()\n",
    "    #     all_shortest_path_lengths = dict(nx.shortest_path_length(G, weight='weight'))\n",
    "    #     all_shortest_paths = nx.shortest_path(G, weight='weight')\n",
    "    #     average_shortest_path_lengths = {}\n",
    "    #     for v in all_shortest_path_lengths.keys():\n",
    "    #         average_shortest_path_lengths[v] = sum([all_shortest_path_lengths[v][u] for u in G.nodes()]) / (\n",
    "    #                 G.number_of_nodes() - 1)\n",
    "    #     root = min(average_shortest_path_lengths, key=lambda x: average_shortest_path_lengths[x])\n",
    "    #     T.add_node(root)\n",
    "    #     G_copy = G.copy()\n",
    "    #     G_copy.remove_node(root)\n",
    "    #     while not is_valid_network(G, T):\n",
    "    #         average_distances = {}\n",
    "    #         corresponding_edge = {}\n",
    "    #         for node in T.nodes():\n",
    "    #             for adj in G.neighbors(node):\n",
    "    #                 if adj in T.nodes(): continue\n",
    "    #                 if adj not in average_distances.keys():\n",
    "    #                     average_distances[adj] = (sum(\n",
    "    #                         [all_shortest_path_lengths[adj][t] for t in T.nodes()]) / T.number_of_nodes() +\n",
    "    #                                               G[node][adj]['weight'])\n",
    "    #                     corresponding_edge[adj] = (node, adj)\n",
    "    #                 else:\n",
    "    #                     temp = (sum(\n",
    "    #                         [all_shortest_path_lengths[adj][t] for t in T.nodes()]) / T.number_of_nodes() +\n",
    "    #                                               G[node][adj]['weight'])\n",
    "    #                     if average_distances[adj] > temp:\n",
    "    #                         average_distances[adj] = temp\n",
    "    #                         corresponding_edge[adj] = (node, adj)\n",
    "    #         next = min(average_distances.keys(), key=lambda x: average_distances[x])\n",
    "    #         T.add_node(next)\n",
    "    #         G_copy.remove_node(next)\n",
    "    #         T.add_edge(corresponding_edge[next][0], corresponding_edge[next][1],\n",
    "    #                    weight=G[corresponding_edge[next][0]][corresponding_edge[next][1]]['weight'])\n",
    "\n",
    "    #     min_T = T.copy()\n",
    "\n",
    "    T = nx.minimum_spanning_tree(G_copy)\n",
    "    for edge in T.edges.data():\n",
    "        u, v = edge[0], edge[1]\n",
    "        edge[2]['weight'] = G[u][v]['weight']\n",
    "\n",
    "    min_T = T.copy()\n",
    "\n",
    "    if T.number_of_nodes() == 1:\n",
    "        return T\n",
    "    elif T.number_of_nodes() == 2:\n",
    "        node = list(T.nodes)[0]\n",
    "        T.remove_node(node)\n",
    "        return T\n",
    "    else:\n",
    "        for i in range(100):\n",
    "            prune(T.copy())\n",
    "\n",
    "            \n",
    "#         for v in G.nodes():\n",
    "#             if nx.eccentricity(G, v, all_shortest_path_lengths) / G.number_of_nodes() < dist:\n",
    "#                 T.add_node(v)\n",
    "#                 edge_list = [(u, v) for u in T.nodes() if G.has_edge(u, v)]\n",
    "#                 r = random.randint(0, len(edge_list))\n",
    "#                 edges_to_add = random.sample(edge_list, r)\n",
    "#                 for e in edge_list:\n",
    "#                     if G[e[0]][e[1]]['weight'] < dist:\n",
    "#                         edges_to_add.append(e)\n",
    "#                 for e in edges_to_add:\n",
    "#                     T.add_edge(e[0], e[1], weight=G[e[0]][e[1]]['weight'])\n",
    "\n",
    "#         # Add some edges with lower weights\n",
    "#         all_shortest_path_lengths = dict(nx.shortest_path_length(G, weight='weight'))\n",
    "#         all_shortest_paths = nx.shortest_path(G, weight='weight')\n",
    "#         dist = average_pairwise_distance_fast(T)\n",
    "#         min_T = T.copy()\n",
    "#         for i in range(100):\n",
    "#             T = min_T.copy()\n",
    "#             edge_list = list(G.edges())\n",
    "#             random.shuffle(edge_list)\n",
    "#             for e in edge_list:\n",
    "#                 if e in T.edges(): continue\n",
    "#                 copy = T.copy()\n",
    "#                 copy.add_edge(e[0], e[1], weight=G[e[0]][e[1]]['weight'])\n",
    "#                 if is_valid_network(G, copy):\n",
    "#                     if average_pairwise_distance_fast(T) > average_pairwise_distance_fast(copy):\n",
    "#                         T = copy.copy()\n",
    "#                 else: break\n",
    "#             if average_pairwise_distance_fast(T) < average_pairwise_distance_fast(min_T):\n",
    "#                 min_T = T.copy()\n",
    "\n",
    "        def findChain(G):\n",
    "            nonlocal confirmed\n",
    "            nonlocal G_copy\n",
    "            changed = False\n",
    "            nodes = [n for n in G.nodes()]\n",
    "            for v in nodes:\n",
    "                if G.degree(v) == 1:\n",
    "                    u = list(G.neighbors(v))[0]\n",
    "                    confirmed.append(u)\n",
    "                    if u in confirmed and v in confirmed:\n",
    "                        T.add_edge(u, v, weight=G[u][v]['weight'])\n",
    "                        G_copy.remove_edge(u, v)\n",
    "                    G.remove_node(v)\n",
    "                    changed = True\n",
    "            if changed:\n",
    "                findChain(G)\n",
    "\n",
    "        confirmed = []\n",
    "        G_copy = G.copy()\n",
    "        findChain(G.copy())\n",
    "\n",
    "        for i in range(100):\n",
    "            copy = min_T.copy()\n",
    "            while is_valid_network(G, copy):\n",
    "                if copy.number_of_edges() == 1:\n",
    "                    if utils.average_pairwise_distance_fast(copy) < utils.average_pairwise_distance_fast(min_T):\n",
    "                        min_T = copy.copy()\n",
    "                    break\n",
    "                T = copy.copy()\n",
    "                edge = random.choices(list(T.edges()))[0]\n",
    "                if T.degree(edge[0]) == 1:\n",
    "                    copy.remove_node(edge[0])\n",
    "                elif T.degree(edge[1]) == 1:\n",
    "                    copy.remove_node(edge[1])\n",
    "                else:\n",
    "                    copy.remove_edge(edge[0], edge[1])\n",
    "                if len(list(copy.nodes)) == 0:\n",
    "                    return T\n",
    "                if is_valid_network(G, copy):\n",
    "                    if utils.average_pairwise_distance_fast(copy) < utils.average_pairwise_distance_fast(min_T):\n",
    "                        min_T = copy.copy()\n",
    "        # prune(T)\n",
    "        # added\n",
    "        #         min_T.remove_edge(20, 21)\n",
    "        #         min_T.add_edge(13, 17)\n",
    "        \n",
    "\n",
    "        return min_T\n",
    "        # TODO: your code here!\n",
    "\n",
    "\n",
    "# Here's an example of how to run your solver.\n",
    "\n",
    "# Usage: python3 solver.py test.in\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",
    "    #             Tree_list = []\n",
    "    #             for i in range(10):\n",
    "    #                 Tree_list.append(solve(G))\n",
    "    #             T = min(Tree_list, key= lambda t: average_pairwise_distance_fast(t))\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",
    "    file_list = \"medium-264, medium-263, medium-262, medium-261, medium-260, medium-256, medium-255, medium-53, medium-251, medium-247, medium-246, edium-242, medium-239, medium-238, medium-237, medium-233, medium-232, medium-230\"\n",
    "    files = file_list.split(', ')\n",
    "    for file in files:\n",
    "        print(file)\n",
    "        path = 'inputs/' + file + '.in'\n",
    "    #path = 'inputs/small-4.in'\n",
    "        G = read_input_file(path)\n",
    "        Tree_list = []\n",
    "        timeout = time.time() + 60\n",
    "        while time.time() < timeout:\n",
    "            Tree_list.append(solve(G))\n",
    "        T = min(Tree_list, key= lambda t: average_pairwise_distance_fast(t))\n",
    "\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",
    "#         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",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "#         fig = plt.figure(figsize=(20, 30))\n",
    "#         fig.add_subplot(211)\n",
    "#         pos = nx.circular_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",
    "        # Compare previous result with new result, update if improvement seen\n",
    "        old = read_output_file('outputs/' + path[7:-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/' + path[7:-2] + 'out')\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"large-117, large-118, large-119, large-120, large-121, large-122, large-124, \" \\\n",
    "                \"large-126, large-127, large-128, large-129, large-130, large-133, large-134, large-135, large-136, large-137, \" \\\n",
    "                \"large-101, large-104, large-105, large-106, large-108, large-112, large-113, large-114, large-139, large-141, \" \\\n",
    "                \"large-143, large-145, large-146, large-147, large-150, large-151, large-152\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"large-301, large-302, large-304, large-305, large-306, large-307, large-308, large-309, large-310, \" \\\n",
    "                \"large-311, large-312, large-313, large-314, large-315, large-316, large-317, large-318, large-319, large-320\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"large-321, large-322, large-323, large-324, large-325, large-326, large-327, large-328, large-329, large-330, \" \\\n",
    "                \"large-331, large-332, large-333, large-334, large-335, large-336, large-337, large-338, large-339, large-340\""
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}