two-step model for lower-bounding and computing the frustration index.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Linear programming (continuous) and binary linear (discrete) programming models for lower-bounding and computing the frustration index of relatively dense signed graphs\n",
    "\n",
    "Jupyter code written by Samin Aref in 2018\n",
    "\n",
    " Creative common licence: \n",
    " Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)\n",
    "\n",
    "Using this code for non-commercial purposes is permitted to all given that the three following publications are cited:\n",
    "\n",
    "1. Aref, S, Mason, AJ, Wilson, MC. A modeling and computational study of the frustration index in signed networks. Networks. 2020; 75: 95– 110. url: https://doi.org/10.1002/net.21907\n",
    "\n",
    "\n",
    "2. Aref, S., Mason, A. J., and Wilson, M. C., Computing the line index of balance using integer programming optimisation. In Optimization Problems in Graph Theory, B. Goldengorin, Ed. Springer, 2018, pp. 65-84. url: https://doi.org/10.1007/978-3-319-94830-0_3\n",
    "\n",
    "\n",
    "3. Aref, S., and Neal, Z., Detecting Coalitions by Optimally Partitioning Signed Networks of Political Collaboration. Scientific Reports (2020). url: http://arxiv.org/pdf/1906.01696.\n",
    "        "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Related dataset: \n",
    "    \n",
    "    Neal, Z., A Sign of the Times: Dataset of US Congress signed network backbones from co-sponsorship data, 1973-2016. Figshare research data repository (2019). http://doi.org/10.6084/m9.figshare.8096429.v3. \n",
    "        \n",
    "Suggested articles and other relevant datasets:\n",
    "\n",
    "    Aref, S., and Wilson, M. C. Balance and frustration in signed networks. Journal of Complex Networks 7, 2 (2019), 163–189. doi: 10.1093/comnet/cny015.\n",
    "    \n",
    "    Aref, S., and Wilson, M. C. Measuring partial balance in signed networks. Journal of Complex Networks 6, 4 (2018), 566-595. doi: 10.1093/comnet/cnx044. \n",
    "    \n",
    "    Aref, S. Signed networks from sociology and political science, systems biology, international relations, finance, and computational chemistry. Figshare research data repository (2017). doi: 10.6084/m9.figshare.5700832.v2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "House or Senate? (H/S)s\n",
      "start session (inclusive)? (96,97,98,...,114)96\n",
      "end session (exclusive)? (97,98,99,...,115)98\n",
      "instance S 96 generated\n",
      "instance S 97 generated\n"
     ]
    }
   ],
   "source": [
    "# Constructing SEVERAL signed graphs from data file in excel format\n",
    "\n",
    "# This is coded for the ease of users to load the data exactly from\n",
    "# the file provided in the FigShare repository. However, loading networks\n",
    "# from .csv format is much faster (code is provided in the end). \n",
    "\n",
    "import networkx as nx\n",
    "import csv\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "signedMatrix=[]\n",
    "unsignedMatrix=[]\n",
    "Graph=[]\n",
    "sorted_weighted_edges=[]\n",
    "\n",
    "chamber=input(\"House or Senate? (H/S)\")\n",
    "\n",
    "start_year=int(input(\"start session (inclusive)? (96,97,98,...,114)\"))\n",
    "end_year=int(input(\"end session (exclusive)? (97,98,99,...,115)\"))\n",
    "\n",
    "n=end_year-start_year\n",
    "\n",
    "for index in range(n):\n",
    "    \n",
    "    line=pd.read_excel('datasets\\\\a_sign_of_the_times.xlsx',\\\n",
    "                       sheet_name=str(chamber.upper()+str(index+start_year)), header=None, nrows = 1)\n",
    "    cols=range(1,len(line.columns))\n",
    "    adjacency=pd.read_excel('datasets\\\\a_sign_of_the_times.xlsx',\\\n",
    "                            sheet_name=str(chamber.upper()+str(index+start_year)), header=None, usecols=cols)\n",
    "    matrix= adjacency.rename_axis('ID').values\n",
    "    order=len(np.matrix(matrix))\n",
    "    \n",
    "    signedMatrix.append(np.matrix(matrix))\n",
    "    unsignedMatrix.append(abs(np.matrix(matrix)))\n",
    "    \n",
    "    Graph.append(nx.from_numpy_matrix(signedMatrix[index]))\n",
    "    sorted_weighted_edges.append(nx.get_edge_attributes(Graph[index], 'weight'))\n",
    "    \n",
    "    print(\"instance\",chamber.upper(),index+start_year,\"generated\")\n",
    "    \n",
    "run=len(Graph)    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Democrats\n",
      "59\n",
      "47\n",
      "Republicans\n",
      "41\n",
      "53\n",
      "Others\n",
      "1\n",
      "1\n"
     ]
    }
   ],
   "source": [
    "# Using the party affiliation of legislators to create a feasible solution (upper bound on frustration index)\n",
    "# to \"warm-start\" the algorithm\n",
    "# This step is optional, but if you skip this, you should comment out five lines of the code for continuous model\n",
    "\n",
    "import pandas as pd\n",
    "\n",
    "party=[]\n",
    "dataframes=[]\n",
    "control=[]\n",
    "for index in range(n):\n",
    "    cols=range(1)\n",
    "    df=pd.read_excel('datasets\\\\a_sign_of_the_times.xlsx',\\\n",
    "                            sheet_name=str(chamber.upper()+str(index+start_year)), header=None, usecols=cols)\n",
    "    dataframes.append(df)\n",
    "    control.append([len(df[df[0].str.contains(\"-D\")]),\\\n",
    "                    len(df[df[0].str.contains(\"-R\")]),\\\n",
    "                   len(df)-len(df[df[0].str.contains(\"-D\")])-len(df[df[0].str.contains(\"-R\")])])\n",
    "\n",
    "#print('Democrats')\n",
    "#for index in range(n):\n",
    "#    print((control[index])[0])\n",
    "    \n",
    "#print('Republicans')\n",
    "#for index in range(n):\n",
    "#    print((control[index])[1])\n",
    "        \n",
    "#print('Others')\n",
    "#for index in range(n):\n",
    "#    print((control[index])[2])\n",
    "    \n",
    "for index in range(n):\n",
    "    party.append(list((dataframes[index])[0].str.contains(\"-D\")))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Academic license - for non-commercial use only\n",
      "Changed value of parameter Method to 2\n",
      "   Prev: -1  Min: -1  Max: 5  Default: -1\n",
      "Changed value of parameter Crossover to 0\n",
      "   Prev: -1  Min: -1  Max: 5  Default: -1\n",
      "Changed value of parameter TimeLimit to 36000.0\n",
      "   Prev: 1e+100  Min: 0.0  Max: 1e+100  Default: 1e+100\n",
      "Parameter OutputFlag unchanged\n",
      "   Value: 1  Min: 0  Max: 1  Default: 1\n",
      "Changed value of parameter Threads to 4\n",
      "   Prev: 0  Min: 0  Max: 1024  Default: 0\n",
      "Optimize a model with 88036 rows, 2376 columns and 392746 nonzeros\n",
      "Coefficient statistics:\n",
      "  Matrix range     [5e-01, 1e+00]\n",
      "  Objective range  [2e+00, 1e+02]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 1e+00]\n",
      "Presolve removed 1 rows and 2 columns\n",
      "Presolve time: 0.18s\n",
      "Presolved: 2375 rows, 90410 columns, 390751 nonzeros\n",
      "Ordering time: 0.00s\n",
      "\n",
      "Barrier statistics:\n",
      " AA' NZ     : 1.331e+05\n",
      " Factor NZ  : 1.544e+06 (roughly 50 MBytes of memory)\n",
      " Factor Ops : 1.461e+09 (less than 1 second per iteration)\n",
      " Threads    : 4\n",
      "\n",
      "                  Objective                Residual\n",
      "Iter       Primal          Dual         Primal    Dual     Compl     Time\n",
      "   0  -1.62021865e+05  1.77100000e+03  2.10e-03 0.00e+00  3.55e+00     1s\n",
      "   1  -5.05227614e+04  1.35386901e+03  4.49e-12 2.85e-02  6.08e-01     1s\n",
      "   2  -1.33215534e+03  1.29835552e+03  4.80e-13 5.55e-16  2.84e-02     1s\n",
      "   3   2.29860818e+02  1.01651664e+03  2.34e-13 4.44e-16  8.49e-03     1s\n",
      "   4   4.38084622e+02  7.63615502e+02  9.44e-14 5.55e-16  3.51e-03     1s\n",
      "   5   5.01414248e+02  6.76860373e+02  4.45e-13 5.55e-16  1.89e-03     1s\n",
      "   6   5.33195530e+02  5.62709275e+02  1.37e-12 8.88e-16  3.18e-04     1s\n",
      "   7   5.39264764e+02  5.41975082e+02  9.30e-13 7.77e-16  2.92e-05     1s\n",
      "   8   5.40994918e+02  5.41019598e+02  6.75e-12 7.77e-16  2.66e-07     1s\n",
      "   9   5.41000000e+02  5.41000000e+02  7.76e-12 8.88e-16  4.40e-13     1s\n",
      "\n",
      "Barrier solved model in 9 iterations and 1.20 seconds\n",
      "Optimal objective 5.41000000e+02\n",
      "\n",
      "Instance 0  solution equals 541.0\n",
      "--------------------------------------------------------------------------------------------\n",
      "Changed value of parameter Method to 2\n",
      "   Prev: -1  Min: -1  Max: 5  Default: -1\n",
      "Changed value of parameter Crossover to 0\n",
      "   Prev: -1  Min: -1  Max: 5  Default: -1\n",
      "Changed value of parameter TimeLimit to 36000.0\n",
      "   Prev: 1e+100  Min: 0.0  Max: 1e+100  Default: 1e+100\n",
      "Parameter OutputFlag unchanged\n",
      "   Value: 1  Min: 0  Max: 1  Default: 1\n",
      "Changed value of parameter Threads to 4\n",
      "   Prev: 0  Min: 0  Max: 1024  Default: 0\n",
      "Optimize a model with 62522 rows, 2174 columns and 278236 nonzeros\n",
      "Coefficient statistics:\n",
      "  Matrix range     [5e-01, 1e+00]\n",
      "  Objective range  [1e+00, 1e+02]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 1e+00]\n",
      "Presolve removed 1 rows and 2 columns\n",
      "Presolve time: 0.15s\n",
      "Presolved: 2173 rows, 64694 columns, 276403 nonzeros\n",
      "Ordering time: 0.00s\n",
      "\n",
      "Barrier statistics:\n",
      " AA' NZ     : 9.474e+04\n",
      " Factor NZ  : 1.109e+06 (roughly 36 MBytes of memory)\n",
      " Factor Ops : 8.587e+08 (less than 1 second per iteration)\n",
      " Threads    : 4\n",
      "\n",
      "                  Objective                Residual\n",
      "Iter       Primal          Dual         Primal    Dual     Compl     Time\n",
      "   0  -1.20896502e+05  1.54000000e+03  7.12e+01 0.00e+00  3.64e+00     0s\n",
      "   1  -3.66158038e+04  1.22900476e+03  4.27e-01 5.05e-02  6.51e-01     1s\n",
      "   2  -2.12119166e+03  1.15281145e+03  4.11e-13 5.00e-16  4.90e-02     1s\n",
      "   3   5.67602923e+01  9.29106577e+02  2.20e-13 4.44e-16  1.31e-02     1s\n",
      "   4   3.03007765e+02  7.25696843e+02  5.42e-14 4.16e-16  6.33e-03     1s\n",
      "   5   3.80786356e+02  5.72433481e+02  4.40e-14 5.00e-16  2.87e-03     1s\n",
      "   6   4.13278577e+02  4.92556399e+02  4.57e-14 4.86e-16  1.19e-03     1s\n",
      "   7   4.22467384e+02  4.56317985e+02  1.13e-13 4.51e-16  5.07e-04     1s\n",
      "   8   4.32301011e+02  4.40452771e+02  1.29e-12 6.66e-16  1.22e-04     1s\n",
      "   9   4.34837363e+02  4.35269587e+02  1.39e-06 6.66e-16  6.46e-06     1s\n",
      "  10   4.34999776e+02  4.35000531e+02  1.34e-10 7.77e-16  1.13e-08     1s\n",
      "  11   4.35000000e+02  4.35000001e+02  8.32e-10 6.66e-16  1.13e-11     1s\n",
      "\n",
      "Barrier solved model in 11 iterations and 1.42 seconds\n",
      "Optimal objective 4.35000000e+02\n",
      "\n",
      "Instance 1  solution equals 435.0\n",
      "--------------------------------------------------------------------------------------------\n",
      "-------------------------------- ***  EXPERIMENT STATS  *** --------------------------------\n",
      "--------------------------------------------------------------------------------------------\n",
      "Lower bounds on frustration index: [541. 435.]\n",
      "\n",
      "Solve times: [1.22 1.44]\n",
      "Average solve time 1.3312972784042358\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# Continuous model to obtain a lower bound for L(G) as the optimal objective function\n",
    "# Based on the linear programming model (Eq. 7) discussed in the following publication\n",
    "#  Aref, S., and Neal, Z., Detecting Coalitions by Optimally Partitioning Signed Networks \n",
    "#  of Political Collaboration. Scientific Reports (2020). url: http://arxiv.org/pdf/1906.01696.\n",
    "\n",
    "\n",
    "# This code solves graph optimization model(s) using \"Gurobi solver\"\n",
    "# to compute a lower-bound of frustration index for the input signed graph(s)\n",
    "\n",
    "# Note that you must have installed Gurobi into Jupyter and registered a Gurobi license\n",
    "# in order to run this code\n",
    "\n",
    "\n",
    "import time\n",
    "import numpy as np\n",
    "import multiprocessing\n",
    "from gurobipy import *\n",
    "objectivevalue=[]\n",
    "solveTime=[]\n",
    "\n",
    "for index in range(run):\n",
    "    \n",
    "    order=len(signedMatrix[index])\n",
    "    NumberOfNegative=((-1 == signedMatrix[index])).sum()/2\n",
    "    size=int(np.count_nonzero(signedMatrix[index])/2)\n",
    "\n",
    "    neighbors={}\n",
    "    Degree=[]\n",
    "    for u in sorted((Graph[index]).nodes()):\n",
    "        neighbors[u] = list((Graph[index])[u])\n",
    "        Degree.append(len(neighbors[u]))\n",
    "    unsignedDegree=Degree\n",
    "    \n",
    "    #Finding the node with the highest unsigned degree\n",
    "    maximum_degree = max(unsignedDegree)\n",
    "    [node_to_fix]=[([i for i, j in enumerate(unsignedDegree) if j == maximum_degree]).pop()]\n",
    "\n",
    "    # Model parameters\n",
    "    model = Model(\"Continuous model for lower-bounding frustration index\")\n",
    "    \n",
    "    # There are different methods for solving optimization models:\n",
    "    # (-1=automatic, 0=primal simplex, 1=dual simplex, 2=barrier, 3=concurrent, 4=deterministic concurrent)\n",
    "    # For problems with a large number of contstraints, barrier method is more suitable\n",
    "    model.setParam(GRB.param.Method, 2)\n",
    "\n",
    "    # Solving the problems without crossover takes a substantially shorter time\n",
    "    # in cases where there are a large number of constraints. (0=without, 1=with)\n",
    "    model.setParam(GRB.Param.Crossover, 0)\n",
    "    \n",
    "    # What is the time limit in second?\n",
    "    # Here, it is set to 10 hours\n",
    "    model.setParam('TimeLimit', 10*3600)\n",
    "    \n",
    "    # Do you want details of branching to be reported? (0=No, 1=Yes)\n",
    "    model.setParam(GRB.param.OutputFlag, 1) \n",
    "    \n",
    "    # How many threads to be used for exploring the feasible space in parallel?\n",
    "    # Here, the minimum of 32 and the availbale CPUs is used\n",
    "    model.setParam(GRB.Param.Threads, min(32,multiprocessing.cpu_count()))\n",
    "   \n",
    "    #This chunk of code lists the graph triangles\n",
    "    GraphTriangles=[]\n",
    "    for n1 in sorted((Graph[index]).nodes()):\n",
    "        neighbors1 = set((Graph[index])[n1])\n",
    "        for n2 in filter(lambda x: x>n1, neighbors1):\n",
    "            neighbors2 = set((Graph[index])[n2])\n",
    "            common = neighbors1 & neighbors2\n",
    "            for n3 in filter(lambda x: x>n2, common):\n",
    "                GraphTriangles.append([n1,n2,n3])\n",
    "    len(GraphTriangles)\n",
    "    #print(\"--- %Listed\",len(GraphTriangles),\"triangles for the graph\")\n",
    "    \n",
    "\n",
    "    # Create decision variables and update model to integrate new variables\n",
    "    # Note that the variables are defined as CONTINUOUS within the unit interval\n",
    "    x=[]\n",
    "    for i in range(0,order):\n",
    "        x.append(model.addVar(lb=0.0, ub=1, vtype=GRB.CONTINUOUS, name='x'+str(i)))\n",
    "\n",
    "    z={}    \n",
    "    for (i,j) in (sorted_weighted_edges[index]):\n",
    "        z[(i,j)]=model.addVar(lb=0.0, ub=1, vtype=GRB.CONTINUOUS, name='z'+str(i)+','+str(j))    \n",
    "\n",
    "    model.update()\n",
    "    \n",
    "    # Set the objective function\n",
    "    OFV=0\n",
    "    for (i,j) in (sorted_weighted_edges[index]):\n",
    "        OFV = OFV + (1-(sorted_weighted_edges[index])[(i,j)])/2 + ((sorted_weighted_edges[index])[(i,j)])*(x[i]+x[j]-2*z[(i,j)])          \n",
    "    model.setObjective(OFV, GRB.MINIMIZE)\n",
    "\n",
    "    # Add constraints to the model and update model to integrate new constraints\n",
    "    \n",
    "    ## ADD CORE CONSTRAINTS ##\n",
    "\n",
    "    for (i,j) in (sorted_weighted_edges[index]):\n",
    "            if (sorted_weighted_edges[index])[(i,j)]==1:\n",
    "                model.addConstr(z[(i,j)] <= (x[i]+x[j])/2 , 'Edge positive'+str(i)+','+str(j))\n",
    "            if (sorted_weighted_edges[index])[(i,j)]==-1:\n",
    "                model.addConstr(z[(i,j)] >= x[i] + x[j] -1 , 'Edge negative'+str(i)+','+str(j))            \n",
    "\n",
    "    for triangle in GraphTriangles:\n",
    "            [i,j,k]=triangle\n",
    "            model.addConstr(x[j] + z[(i,k)] >= z[(i,j)] + z[(j,k)] , 'triangle1'+','+str(i)+','+str(j)+','+str(k))\n",
    "            model.addConstr(x[i] + z[(j,k)] >= z[(i,j)] + z[(i,k)] , 'triangle2'+','+str(i)+','+str(j)+','+str(k))       \n",
    "            model.addConstr(x[k] + z[(i,j)] >= z[(i,k)] + z[(j,k)] , 'triangle3'+','+str(i)+','+str(j)+','+str(k))\n",
    "            model.addConstr( 1 + z[(i,j)] + z[(i,k)] + z[(j,k)] >= x[i] + x[j] + x[k] , 'triangle4'+','+str(i)+','+str(j)+','+str(k))           \n",
    "    model.update()\n",
    "\n",
    "    ## ADD ADDITIONAL CONSTRAINTS (speed-ups) ##\n",
    "    \n",
    "    # Colour the node with the highest degree as 1\n",
    "    model.addConstr(x[node_to_fix]==1 , '1stnodecolour')   \n",
    "    model.update()\n",
    "  \n",
    "\n",
    "    # Solve\n",
    "    start_time = time.time()\n",
    "    model.optimize()\n",
    "    solveTime.append(time.time() - start_time) \n",
    "    \n",
    "    # Save optimal objective function values\n",
    "    obj = model.getObjective()\n",
    "    objectivevalue.append((obj.getValue()))\n",
    "        \n",
    "    # Report the optimal objective function value for each instance\n",
    "    print('Instance', index,' solution equals',np.around(objectivevalue[index])) \n",
    "    print(\"-\"*92)\n",
    "    \n",
    "    # Printing the solution (optional)\n",
    "    #print(\"Optimal values of the decision variables\")\n",
    "    #for v in model.getVars():\n",
    "    #    print (v.varName, v.x)\n",
    "    #print()    \n",
    "\n",
    "# Save the lower bounds as a list for the next step (computing the frutsration index)\n",
    "LowerBounds=np.around(objectivevalue)  \n",
    "\n",
    "print(\"-\"*32,\"***  EXPERIMENT STATS  ***\",\"-\"*32)\n",
    "print(\"-\"*92)\n",
    "print(\"Lower bounds on frustration index:\",LowerBounds)\n",
    "print()\n",
    "print(\"Solve times:\",np.around(solveTime, decimals=2))\n",
    "print(\"Average solve time\",np.mean(solveTime))\n",
    "#print(\"Solve time Standard Deviation\",np.std(solveTime))\n",
    "print()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Parameter OutputFlag unchanged\n",
      "   Value: 1  Min: 0  Max: 1  Default: 1\n",
      "Changed value of parameter Threads to 4\n",
      "   Prev: 0  Min: 0  Max: 1024  Default: 0\n",
      "Optimize a model with 16982 rows, 2376 columns and 53218 nonzeros\n",
      "Variable types: 2275 continuous, 101 integer (101 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [1e+00, 1e+00]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 5e+02]\n",
      "\n",
      "Loaded MIP start with objective 882\n",
      "\n",
      "Presolve time: 0.07s\n",
      "Presolved: 16982 rows, 2376 columns, 53218 nonzeros\n",
      "Extracted 12431 lazy constraints\n",
      "Variable types: 2275 continuous, 101 integer (101 binary)\n",
      "\n",
      "Root relaxation: objective 1.000000e+00, 106 iterations, 0.01 seconds\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "     0     0    1.00000    0  101  882.00000    1.00000   100%     -    0s\n",
      "H    0     0                     658.0000000    1.00000   100%     -    0s\n",
      "H    0     0                     650.0000000    1.00000   100%     -    0s\n",
      "H    0     0                     649.0000000    1.00000   100%     -    0s\n",
      "     0     0  541.00000    0   91  649.00000  541.00000  16.6%     -    0s\n",
      "     0     0  541.00000    0   92  649.00000  541.00000  16.6%     -    0s\n",
      "     0     0  541.00000    0   93  649.00000  541.00000  16.6%     -    1s\n",
      "     0     0  541.00000    0   93  649.00000  541.00000  16.6%     -    3s\n",
      "     0     2  541.00000    0   93  649.00000  541.00000  16.6%     -    6s\n",
      "   121   126     cutoff   21       649.00000  541.00000  16.6%   483   10s\n",
      "*  304   236              20     607.0000000  541.00000  10.9%   451   13s\n",
      "   394   291     cutoff   21       607.00000  541.00000  10.9%   427   15s\n",
      "H  404    27                     541.0000000  541.00000  0.00%   429   15s\n",
      "\n",
      "Cutting planes:\n",
      "  Gomory: 7\n",
      "  MIR: 163\n",
      "  Lazy constraints: 3\n",
      "\n",
      "Explored 492 nodes (217253 simplex iterations) in 15.34 seconds\n",
      "Thread count was 4 (of 4 available processors)\n",
      "\n",
      "Solution count 6: 541 607 649 ... 882\n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 5.410000000000e+02, best bound 5.410000000000e+02, gap 0.0000%\n",
      "Instance 0  solution equals 541.0000000000043\n",
      "--------------------------------------------------------------------------------------------\n",
      "Parameter OutputFlag unchanged\n",
      "   Value: 1  Min: 0  Max: 1  Default: 1\n",
      "Changed value of parameter Threads to 4\n",
      "   Prev: 0  Min: 0  Max: 1024  Default: 0\n",
      "Optimize a model with 11997 rows, 2174 columns and 38061 nonzeros\n",
      "Variable types: 2073 continuous, 101 integer (101 binary)\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [1e+00, 1e+00]\n",
      "  Bounds range     [1e+00, 1e+00]\n",
      "  RHS range        [1e+00, 4e+02]\n",
      "\n",
      "Loaded MIP start with objective 583\n",
      "\n",
      "Presolve time: 0.06s\n",
      "Presolved: 11997 rows, 2174 columns, 38061 nonzeros\n",
      "Extracted 7850 lazy constraints\n",
      "Variable types: 2073 continuous, 101 integer (101 binary)\n",
      "\n",
      "Root relaxation: objective 1.000000e+00, 103 iterations, 0.01 seconds\n",
      "\n",
      "    Nodes    |    Current Node    |     Objective Bounds      |     Work\n",
      " Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time\n",
      "\n",
      "     0     0    1.00000    0  101  583.00000    1.00000   100%     -    0s\n",
      "     0     0  435.00000    0   91  583.00000  435.00000  25.4%     -    0s\n",
      "     0     0  435.00000    0   91  583.00000  435.00000  25.4%     -    0s\n",
      "     0     0  435.00000    0   91  583.00000  435.00000  25.4%     -    1s\n",
      "     0     0  435.00000    0   91  583.00000  435.00000  25.4%     -    2s\n",
      "     0     2  435.00000    0   91  583.00000  435.00000  25.4%     -    4s\n",
      "    11    16  435.00000    3   95  583.00000  435.00000  25.4%   720    5s\n",
      "   193   167  435.00000    7   94  583.00000  435.00000  25.4%   429   10s\n",
      "*  343   312              20     578.0000000  435.00000  24.7%   408   12s\n",
      "*  345   308              19     571.0000000  435.00000  23.8%   407   12s\n",
      "*  346   300              19     553.0000000  435.00000  21.3%   406   12s\n",
      "*  483   292              18     494.0000000  435.00000  11.9%   380   13s\n",
      "   512   340  435.00000   10   91  494.00000  435.00000  11.9%   384   15s\n",
      "   832   502  435.00000   12   89  494.00000  435.00000  11.9%   391   20s\n",
      "* 1039   517              16     461.0000000  435.00000  5.64%   382   21s\n",
      "  1079   552  435.00000    7   92  461.00000  435.00000  5.64%   382   25s\n",
      "  1083   555  460.25000   16   97  461.00000  435.00000  5.64%   381   30s\n",
      "  1087   558  435.00000    9   97  461.00000  435.00000  5.64%   380   37s\n",
      "  1089   559  435.00000   13   99  461.00000  435.00000  5.64%   379   41s\n",
      "H 1090   531                     460.0000000  435.00000  5.43%   378   42s\n",
      "  1095   534  435.00000   12  101  460.00000  435.00000  5.43%   377   45s\n",
      "  1100   540  435.00000   10  100  460.00000  435.00000  5.43%   427   50s\n",
      "  1114   552  435.00000   13   97  460.00000  435.00000  5.43%   431   56s\n",
      "  1152   566  435.00000   17   93  460.00000  435.00000  5.43%   447   60s\n",
      "* 1270   468              23     435.0000000  435.00000  0.00%   445   62s\n",
      "\n",
      "Cutting planes:\n",
      "  Gomory: 41\n",
      "  MIR: 17\n",
      "  Flow cover: 404\n",
      "  Lazy constraints: 22\n",
      "\n",
      "Explored 1311 nodes (587237 simplex iterations) in 62.49 seconds\n",
      "Thread count was 4 (of 4 available processors)\n",
      "\n",
      "Solution count 8: 435 460 461 ... 583\n",
      "\n",
      "Optimal solution found (tolerance 1.00e-04)\n",
      "Best objective 4.350000000000e+02, best bound 4.350000000000e+02, gap 0.0000%\n",
      "Instance 1  solution equals 435.0\n",
      "--------------------------------------------------------------------------------------------\n",
      "-------------------------------- ***  EXPERIMENT STATS  *** --------------------------------\n",
      "--------------------------------------------------------------------------------------------\n",
      "Frustration indices: [541. 435.]\n",
      "\n",
      "Solve times: [15.37 62.5 ]\n",
      "Average solve time 38.93592429161072\n",
      "\n",
      "Effective branching factors (EBFs) [1.0025055473430644, 1.003160388137674]\n",
      "Average EBF 1.0028329677403693\n"
     ]
    }
   ],
   "source": [
    "# Discrete model to be given lower bounds and compute L(G) as the optimal objective function\n",
    "# Based on the binary linear programming model (Eq. 8) discussed in the following publication\n",
    "#  Aref, S., and Neal, Z., Detecting Coalitions by Optimally Partitioning Signed Networks \n",
    "#  of Political Collaboration. Scientific Reports (2020). url: http://arxiv.org/pdf/1906.01696.\n",
    "\n",
    "# This code solves graph optimization model(s) using \"Gurobi solver\"\n",
    "# to compute the measure called, frustration index, for the input signed graph(s)\n",
    "\n",
    "# Note that you must have installed Gurobi into Jupyter and registered a Gurobi license\n",
    "# in order to run this code\n",
    "\n",
    "\n",
    "#Setting parameters\n",
    "#lazyParam=int(input(\"What is the lazy parameter for unbalanced triangle lazy cuts? (0/1/2/3)\"))\n",
    "# See \"lazy\" as a tunable parameter in linear constraint attributes in Gurobi optimizer reference manual below:\n",
    "# https://www.gurobi.com/documentation/8.1/refman/lazy.html\n",
    "lazyParam=int(2)\n",
    "\n",
    "#speedupParam=int(input(\"Do you want to use the speedups? (0=No, 1=Yes)\"))\n",
    "speedupParam=int(1)\n",
    "\n",
    "import time\n",
    "import numpy as np\n",
    "import multiprocessing\n",
    "from gurobipy import *\n",
    "objectivevalue=[]\n",
    "solveTime=[]\n",
    "effectiveBranchingFactors=[]\n",
    "\n",
    "for index in range(run):\n",
    "    \n",
    "    order=len(signedMatrix[index])\n",
    "    NumberOfNegative=((-1 == signedMatrix[index])).sum()/2\n",
    "    size=int(np.count_nonzero(signedMatrix[index])/2)\n",
    "\n",
    "    neighbors={}\n",
    "    Degree=[]\n",
    "    for u in sorted((Graph[index]).nodes()):\n",
    "        neighbors[u] = list((Graph[index])[u])\n",
    "        Degree.append(len(neighbors[u]))\n",
    "    unsignedDegree=Degree\n",
    "    \n",
    "    #Finding the node with the highest unsigned degree\n",
    "    maximum_degree = max(unsignedDegree)\n",
    "    [node_to_fix]=[([i for i, j in enumerate(unsignedDegree) if j == maximum_degree]).pop()]\n",
    "\n",
    "    # Model parameters\n",
    "    model = Model(\"Continuous model for computing the frustration index (a lower bound is needed)\")\n",
    "\n",
    "    # There are different methods for solving optimization models:\n",
    "    # (-1=automatic, 0=primal simplex, 1=dual simplex, 2=barrier, 3=concurrent, 4=deterministic concurrent)\n",
    "    # model.setParam(GRB.param.Method, -1)\n",
    "    \n",
    "    # What is the time limit in second?\n",
    "    # model.setParam('TimeLimit', 10*3600)\n",
    "    \n",
    "    # Do you want details of branching to be reported? (0=No, 1=Yes)\n",
    "    model.setParam(GRB.param.OutputFlag, 1) \n",
    "    \n",
    "    # Do you want a non-zero Mixed integer programming tolerance (MIP Gap)?\n",
    "    # Note that a non-zero MIP gap may prevent the model from computing the exact value of frustration index\n",
    "    # model.setParam('MIPGap', 0.0001)  \n",
    "    \n",
    "    # How many threads to be used for exploring the feasible space in parallel?\n",
    "    # Here, the minimum of 32 and the availbale CPUs is used\n",
    "    model.setParam(GRB.Param.Threads, min(32,multiprocessing.cpu_count()))\n",
    "    \n",
    "    #This chunk of code lists the graph triangles\n",
    "    GraphTriangles=[]\n",
    "    for n1 in sorted((Graph[index]).nodes()):\n",
    "        neighbors1 = set((Graph[index])[n1])\n",
    "        for n2 in filter(lambda x: x>n1, neighbors1):\n",
    "            neighbors2 = set((Graph[index])[n2])\n",
    "            common = neighbors1 & neighbors2\n",
    "            for n3 in filter(lambda x: x>n2, common):\n",
    "                GraphTriangles.append([n1,n2,n3])\n",
    "    len(GraphTriangles)\n",
    "    #print(\"--- %Listed\",len(GraphTriangles),\"triangles for the graph\")\n",
    "\n",
    "    #This chunk of code lists the balanced and unbalanced triangles\n",
    "    w=nx.get_edge_attributes(Graph[index], 'weight')  \n",
    "    unbalanced_triangles = []\n",
    "    balanced_triangles = []\n",
    "    for triad in GraphTriangles: \n",
    "        if  (sorted_weighted_edges[index])[(triad[0],triad[1])]*\\\n",
    "        (sorted_weighted_edges[index])[(triad[0],triad[2])]*(sorted_weighted_edges[index])[(triad[1],triad[2])] == -1:\n",
    "            unbalanced_triangles.append(triad)\n",
    "        elif (sorted_weighted_edges[index])[(triad[0],triad[1])]*\\\n",
    "        (sorted_weighted_edges[index])[(triad[0],triad[2])]*(sorted_weighted_edges[index])[(triad[1],triad[2])] == 1:\n",
    "            balanced_triangles.append(triad)  \n",
    "    \n",
    "\n",
    "    # Create decision variables and update model to integrate new variables\n",
    "    x=[]\n",
    "    for i in range(0,order):\n",
    "        x.append(model.addVar(vtype=GRB.BINARY, name='x'+str(i))) # arguments by name\n",
    "    model.update()\n",
    "    \n",
    "    f={}\n",
    "    for (i,j) in (sorted_weighted_edges[index]):\n",
    "        f[(i,j)]=model.addVar(lb=0.0, ub=1, vtype=GRB.CONTINUOUS, name='f'+str(i)+','+str(j))\n",
    "    model.update()\n",
    "\n",
    "    # Set the objective function\n",
    "    OFV=0\n",
    "    for (i,j) in (sorted_weighted_edges[index]):\n",
    "        OFV = OFV + f[(i,j)]                 \n",
    "    model.setObjective(OFV, GRB.MINIMIZE)\n",
    "\n",
    "    # Add constraints to the model and update model to integrate new constraints\n",
    "    \n",
    "    ## ADD CORE CONSTRAINTS ##\n",
    "\n",
    "    for (i,j) in (sorted_weighted_edges[index]):\n",
    "        model.addConstr( f[(i,j)] >= x[i] - ((sorted_weighted_edges[index])[(i,j)])*x[j] -\\\n",
    "                        (1-(sorted_weighted_edges[index])[(i,j)])/2\n",
    "                             , '1st Edge'+','+str(i)+','+str(j))\n",
    "        model.addConstr( f[(i,j)] >= -x[i] + ((sorted_weighted_edges[index])[(i,j)])*x[j] +\\\n",
    "                        (1-(sorted_weighted_edges[index])[(i,j)])/2\n",
    "                             , '2nd Edge'+','+str(i)+','+str(j))                  \n",
    "    model.update()  \n",
    "    \n",
    "    model.addConstr(OFV >= int(LowerBounds[index]), 'LP lower bound')\n",
    "    model.update()\n",
    "            \n",
    "    ## ADD ADDITIONAL CONSTRAINTS (speed-ups) ##\n",
    "    \n",
    "    if speedupParam==1:\n",
    "\n",
    "        # Triangle valid inequalities            \n",
    "\n",
    "        triangleInequalityCount=len(unbalanced_triangles)\n",
    "        for triangle in unbalanced_triangles:\n",
    "            [i,j,k]=triangle\n",
    "            model.addConstr(f[(i,j)] + f[(i,k)] + f[(j,k)] >= 1 ,'UnbalancedTriangle'+','+str(i)+','+str(j)+','+str(k))    \n",
    "\n",
    "        model.update()\n",
    "        model.setAttr('Lazy',model.getConstrs()[2*size:2*size+triangleInequalityCount],[lazyParam]*triangleInequalityCount)\n",
    "        model.update() \n",
    "\n",
    "        #branching priority is based on unsigned degree \n",
    "        model.setAttr('BranchPriority',model.getVars()[:order],unsignedDegree)\n",
    "        model.update()\n",
    "        \n",
    "    # Using a warm start\n",
    "    # If a specific partitioning is known which can be used as a starting point to \"warm-start\" the algorithm,\n",
    "    # it can be provided to the model here by giving start values to the node variables:\n",
    "    # If the optional step above is skipped, you should comment out these five lines\n",
    "    for i in range(0,order):\n",
    "        if (party[index])[i]==True:\n",
    "            x[i].start = 1.0\n",
    "        else:\n",
    "            x[i].start = 0    \n",
    "    \n",
    "\n",
    "    # Solve\n",
    "    start_time = time.time()\n",
    "    model.optimize()\n",
    "    solveTime.append(time.time() - start_time) \n",
    "    \n",
    "    \n",
    "    # Save optimal objective function values\n",
    "    obj = model.getObjective()\n",
    "    objectivevalue.append((obj.getValue()))\n",
    "    \n",
    "    # Compute the effective branching factors\n",
    "    if (model.NodeCount)**(1/(size+2*order)) >= 1:\n",
    "        effectiveBranchingFactors.append((model.NodeCount)**(1/(size+2*order)))\n",
    "        \n",
    "    # Report the optimal objective function value for each instance\n",
    "    print('Instance', index,' solution equals',objectivevalue[index]) \n",
    "    print(\"-\"*92)\n",
    "    \n",
    "    # Printing the solution (optional)\n",
    "    #print(\"Optimal values of the decision variables\")\n",
    "    #for v in model.getVars():\n",
    "    #    print (v.varName, v.x)\n",
    "    #print()    \n",
    "\n",
    "  \n",
    "    \n",
    "print(\"-\"*32,\"***  EXPERIMENT STATS  ***\",\"-\"*32)\n",
    "print(\"-\"*92)\n",
    "print(\"Frustration indices:\",np.around(objectivevalue))\n",
    "#print(\"Average frustrarion index\",np.mean(objectivevalue))\n",
    "#print(\"Frustration index Standard Deviation\",np.std(objectivevalue))\n",
    "print()\n",
    "print(\"Solve times:\",np.around(solveTime, decimals=2))\n",
    "print(\"Average solve time\",np.mean(solveTime))\n",
    "#print(\"Solve time Standard Deviation\",np.std(solveTime))\n",
    "print()\n",
    "if (model.NodeCount)**(1/(size+2*order)) >= 1:\n",
    "    print(\"Effective branching factors (EBFs)\",effectiveBranchingFactors)\n",
    "    print(\"Average EBF\",np.mean(effectiveBranchingFactors))\n",
    "    #print(\"EBF Standard Deviation\",np.std(effectiveBranchingFactors))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Two extra chunks of code are provided below for:\n",
    "\n",
    " (1) generating synthetic data using random graph models,\n",
    " \n",
    " (2) loading networks of US Congress legislators from .csv files."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "How many random graphs do you want to create?(1/2/...)2\n",
      "\n",
      " 1.  Erdős-Rényi binomial graph G_{n,p} \n",
      " 2.  Random graph of n nodes and m total edges G_{n,m} \n",
      " 3.  Newman-Watts-Strogatz small world graph (adding new edges to the ring) G_{n,k,p} \n",
      " 4.  Watts-Strogatz small world graph (rewiring the ring) G_{n,k,p} \n",
      " 5.  Random regular graph of n nodes each with degree d G_{d,n} \n",
      " 6.  Barabási-Albert preferential attachment model graph G_{n,m} \n",
      " 7.  Growing graph with powerlaw degree distribution and approximate average clustering G_{n,m,p}\n",
      " 8.  Two-dimensional grid n*n \n",
      "What type of random graph(s) do you want to create from the list above? (1/2/...)1\n",
      "What is the number of nodes?50\n",
      "What is the probability of having an edge for each two nodes? (0.1, 0.5, ...)0.5\n",
      "What is the number of negative edges for this instance? (0/1/2/.../m)10\n",
      "What is the number of nodes?50\n",
      "What is the probability of having an edge for each two nodes? (0.1, 0.5, ...)0.5\n",
      "What is the number of negative edges for this instance? (0/1/2/.../m)20\n"
     ]
    }
   ],
   "source": [
    "# This code is for producing synthetic data (generating random \"signed graphs\")\n",
    "# \"Signed graphs\" are graphs in which edges are postive or negative (signed)\n",
    "# This code asks you for type of random graph, several parameters for generating them such as size and order\n",
    "# and then it asks for \"number of negative edges\" so that it randomly makes some edges negative and produce \n",
    "# a signed graph out of an unsigned graph\n",
    "\n",
    "import networkx as nx\n",
    "import numpy as np\n",
    "import random\n",
    "\n",
    "\n",
    "listOfGraphs=[]\n",
    "NumberOfNegative=[]\n",
    "run=int(input(\"How many random graphs do you want to create?(1/2/...)\"))\n",
    "\n",
    "print(\"\\n 1.  Erdős-Rényi binomial graph G_{n,p} \"\n",
    "      \"\\n 2.  Random graph of n nodes and m total edges G_{n,m} \"\n",
    "      \"\\n 3.  Newman-Watts-Strogatz small world graph (adding new edges to the ring) G_{n,k,p} \"\n",
    "      \"\\n 4.  Watts-Strogatz small world graph (rewiring the ring) G_{n,k,p} \"\n",
    "      \"\\n 5.  Random regular graph of n nodes each with degree d G_{d,n} \"\n",
    "      \"\\n 6.  Barabási-Albert preferential attachment model graph G_{n,m} \"\n",
    "      \"\\n 7.  Growing graph with powerlaw degree distribution and approximate average clustering G_{n,m,p}\"\n",
    "      \"\\n 8.  Two-dimensional grid n*n \")\n",
    "\n",
    "graph_type=int(input(\"What type of random graph(s) do you want to create from the list above? (1/2/...)\"))\n",
    "\n",
    "for i in range(run):\n",
    "\n",
    "    if graph_type == 1:\n",
    "        n=int(input(\"What is the number of nodes?\"))\n",
    "        p=float(input(\"What is the probability of having an edge for each two nodes? (0.1, 0.5, ...)\"))\n",
    "        NumberOfNegative.append(int(input(\"What is the number of negative edges for this instance? (0/1/2/.../m)\")))\n",
    "        G=nx.fast_gnp_random_graph(n,p)\n",
    "        listOfGraphs.append(G) \n",
    "    elif graph_type == 2:\n",
    "        n=int(input(\"What is the number of nodes?\"))\n",
    "        m=int(input(\"What is the total number of edges?\"))  \n",
    "        NumberOfNegative.append(int(input(\"What is the number of negative edges for this instance? (0/1/2/.../m)\")))\n",
    "        G=nx.gnm_random_graph(n,m)\n",
    "        listOfGraphs.append(G)\n",
    "    elif graph_type == 3:\n",
    "        n=int(input(\"What is the number of nodes?\"))\n",
    "        k=int(input(\"What is the number of nearest neighbors in ring topology?\"))\n",
    "        p=float(input(\"What is the probability of adding a new edge?\"))\n",
    "        NumberOfNegative.append(int(input(\"What is the number of negative edges for this instance? (0/1/2/.../m)\")))\n",
    "        G=nx.newman_watts_strogatz_graph(n,k,p)\n",
    "        listOfGraphs.append(G)\n",
    "    elif graph_type == 4:\n",
    "        n=int(input(\"What is the number of nodes?\"))\n",
    "        k=int(input(\"What is the number of nearest neighbors in ring topology?\"))\n",
    "        p=float(input(\"What is the probability of rewiring each edge?\"))\n",
    "        NumberOfNegative.append(int(input(\"What is the number of negative edges for this instance? (0/1/2/.../m)\")))\n",
    "        G=nx.watts_strogatz_graph(n,k,p)\n",
    "        listOfGraphs.append(G)\n",
    "    elif graph_type == 5:\n",
    "        n=int(input(\"What is the number of nodes?(n>d)\"))\n",
    "        d=int(input(\"What is the degree?(The value of n*d must be even)\"))\n",
    "        NumberOfNegative.append(int(input(\"What is the number of negative edges for this instance? (0/1/2/.../m)\")))\n",
    "        G=nx.random_regular_graph(d,n)\n",
    "        listOfGraphs.append(G)\n",
    "    elif graph_type == 6:\n",
    "        n=int(input(\"What is the number of nodes?\"))\n",
    "        m=int(input(\"What is the number of edges to attach from a new node to existing nodes?\"))\n",
    "        NumberOfNegative.append(int(input(\"What is the number of negative edges for this instance? (0/1/2/.../m)\")))\n",
    "        G=nx.barabasi_albert_graph(n,m)   \n",
    "        listOfGraphs.append(G)\n",
    "    elif graph_type == 7:\n",
    "        n=int(input(\"What is the number of nodes?\"))\n",
    "        m=int(input(\"What is the number of random edges to add for each new node?\"))\n",
    "        p=float(input(\"What is the probability of adding a triangle after adding a random edge?\"))\n",
    "        NumberOfNegative.append(int(input(\"What is the number of negative edges for this instance? (0/1/2/.../m)\")))\n",
    "        G=nx.powerlaw_cluster_graph(n,m,p)    \n",
    "        listOfGraphs.append(G)\n",
    "    elif graph_type == 8:\n",
    "        n=int(input(\"What is the size of the grid?(sqrt(n))\"))\n",
    "        NumberOfNegative.append(int(input(\"What is the number of negative edges for this instance? (0/1/2/.../m)\")))\n",
    "        G=nx.grid_2d_graph(n,n)\n",
    "        mapping=dict(zip(G.nodes(),range(len(G.nodes()))))\n",
    "        G=nx.relabel_nodes(G,mapping)\n",
    "        listOfGraphs.append(G)\n",
    "    else:\n",
    "        print(\"Try again and choose a graph type from the selection above!\")\n",
    "\n",
    "                    \n",
    "Graph=[]\n",
    "signedMatrix=[]\n",
    "unsignedMatrix=[]\n",
    "ShuffledEdges=[]\n",
    "sorted_weighted_edges=[]\n",
    "\n",
    "\n",
    "for i in range(run):\n",
    "        ShuffledEdges = list(listOfGraphs[i].edges())\n",
    "        random.shuffle(ShuffledEdges)\n",
    "        Graph.append(nx.Graph())\n",
    "        for u in listOfGraphs[i].nodes():\n",
    "            Graph[i].add_node(u)\n",
    "        for ind in range(0,NumberOfNegative[i]):\n",
    "            (u,v) = ShuffledEdges[ind]\n",
    "            Graph[i].add_edge(u,v,weight=-1)\n",
    "        for ind in range(NumberOfNegative[i],len(listOfGraphs[i].edges())):\n",
    "            (u,v) = ShuffledEdges[ind]\n",
    "            Graph[i].add_edge(u,v,weight=1)\n",
    "        signedMatrix.append(nx.to_numpy_matrix(Graph[i]))\n",
    "        unsignedMatrix.append(abs(signedMatrix[i]))\n",
    "        ShuffledEdges=[]\n",
    "\n",
    "        weighted_edges=nx.get_edge_attributes(Graph[i], 'weight') \n",
    "        sorted_weighted_edges.append({})\n",
    "        for (u,v) in weighted_edges:\n",
    "            if u<v:\n",
    "                (sorted_weighted_edges[i])[(u,v)] = weighted_edges[(u,v)]\n",
    "            if u>v:\n",
    "                (sorted_weighted_edges[i])[(v,u)] = weighted_edges[(u,v)]          \n",
    "          "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "House or Senate? (H/S)h\n",
      "start session (inclusive)? (96,97,98,...,114)96\n",
      "end session (exclusive)? (97,98,99,...,115)115\n",
      "instance H 96 generated\n",
      "instance H 97 generated\n",
      "instance H 98 generated\n",
      "instance H 99 generated\n",
      "instance H 100 generated\n",
      "instance H 101 generated\n",
      "instance H 102 generated\n",
      "instance H 103 generated\n",
      "instance H 104 generated\n",
      "instance H 105 generated\n",
      "instance H 106 generated\n",
      "instance H 107 generated\n",
      "instance H 108 generated\n",
      "instance H 109 generated\n",
      "instance H 110 generated\n",
      "instance H 111 generated\n",
      "instance H 112 generated\n",
      "instance H 113 generated\n",
      "instance H 114 generated\n",
      "Total elapsed time: 12.554391145706177 seconds\n"
     ]
    }
   ],
   "source": [
    "# Constructing SEVERAL signed graphs from matrices in CSV format\n",
    "# Loading networks from .csv format is much faster\n",
    "\n",
    "import networkx as nx\n",
    "import csv\n",
    "import numpy as np\n",
    "\n",
    "signedMatrix=[]\n",
    "unsignedMatrix=[]\n",
    "Graph=[]\n",
    "sorted_weighted_edges=[]\n",
    "\n",
    "chamber=input(\"House or Senate? (H/S)\")\n",
    "\n",
    "start_year=int(input(\"start session (inclusive)? (96,97,98,...,114)\"))\n",
    "end_year=int(input(\"end session (exclusive)? (97,98,99,...,115)\"))\n",
    "\n",
    "start_time = time.time()\n",
    "\n",
    "n=end_year-start_year\n",
    "\n",
    "for index in range(n):\n",
    "    \n",
    "    matrix=np.loadtxt(open('csv_datasets\\\\'+chamber.upper()+str(index+start_year)+'.csv', \"rb\"), delimiter=\",\")\n",
    "    order=len(np.matrix(matrix))\n",
    "    \n",
    "    signedMatrix.append(np.matrix(matrix))\n",
    "    unsignedMatrix.append(abs(np.matrix(matrix)))\n",
    "    \n",
    "    Graph.append(nx.from_numpy_matrix(signedMatrix[index]))\n",
    "    sorted_weighted_edges.append(nx.get_edge_attributes(Graph[index], 'weight'))\n",
    "    \n",
    "    print(\"instance\",chamber.upper(),index+start_year,\"generated\")\n",
    "\n",
    "print(\"Total elapsed time:\",(time.time() - start_time),\"seconds\")\n",
    "    \n",
    "run=len(Graph)    "
   ]
  }
 ],
 "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}