DFS_SSP.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "DFS_SSP.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {
        "id": "hu6NL8c_sPXl"
      },
      "outputs": [],
      "source": [
        "import networkx as nx\n",
        "import random\n",
        "import numpy as np\n",
        "import matplotlib.pyplot as plt\n",
        "import math"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def card(g,**kwargs):\n",
        "  weight=kwargs.get(\"weight\",\"weight\")\n",
        "  epsilon=kwargs.get(\"epsilon\",0.0000001)\n",
        "  t=nx.get_node_attributes(g,name=weight)\n",
        "  nodelist=list(t)\n",
        "  start_weights=np.array(list(t.values()))\n",
        "  adj=nx.convert_matrix.to_numpy_array(g,nodelist)\n",
        "  adj=adj.T\n",
        "\n",
        "  weights=start_weights\n",
        "  finished=False\n",
        "  adjsum=np.sum(adj,axis=1)\n",
        "  while not finished:\n",
        "    new_weights=start_weights/(1+adjsum+np.divide(np.matmul(adj,weights),adjsum,out=np.zeros_like(weights), where=adjsum!=0))\n",
        "    if np.linalg.norm(abs(new_weights-weights)/new_weights)<epsilon:\n",
        "      finished=True\n",
        "    weights=new_weights\n",
        "  return weights\n",
        "\n",
        "def h_cat(g,**kwargs):\n",
        "  \"\"\"takes an argumentation graph as input. Each node must have a weight parameter, default \"weight\". Epsilon tells us when to stop iterating\"\"\"\n",
        "  weight=kwargs.get(\"weight\",\"weight\")\n",
        "  epsilon=kwargs.get(\"epsilon\",0.0000001)\n",
        "  t=nx.get_node_attributes(g,name=weight)\n",
        "  nodelist=list(t)\n",
        "  start_weights=np.array(list(t.values()))\n",
        "  adj=nx.convert_matrix.to_numpy_array(g,nodelist)\n",
        "  adj=adj.T\n",
        "\n",
        "  weights=start_weights\n",
        "  finished=False\n",
        "  while not finished:\n",
        "    new_weights=start_weights/(np.matmul(adj,weights)+1)\n",
        "    if np.linalg.norm(abs(new_weights-weights)/new_weights)<epsilon:\n",
        "      finished=True\n",
        "    weights=new_weights\n",
        "  return weights"
      ],
      "metadata": {
        "id": "T46sOOZ6sV0k"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "cache={frozenset([0]):0}\n",
        "\n",
        "def init_ssp():\n",
        "  global cache\n",
        "  cache={frozenset([0]):0}\n",
        "\n",
        "def ssp_dfs(t,s,candidate,**kwargs):\n",
        "  \"\"\"should return the subset of s used to add up to t, within a tolerance tol (default 0.00001).\n",
        "     Does a DFS storing the results in the cache for use later until we exceed the target t.\n",
        "  \"\"\"\n",
        "  global cache\n",
        "  ans=None\n",
        "  tol=kwargs.get(\"tolerance\",0.0000001)\n",
        "  k=kwargs.get(\"k\",-1)\n",
        "  #print(t)\n",
        "  for a in s:\n",
        "    #print(candidate,a)\n",
        "    if a in candidate:\n",
        "      continue\n",
        "\n",
        "    new_candidate=frozenset(candidate.union([a]))\n",
        "    if k!=-1 and len(new_candidate)>k: #don't bother exploring if we have more than k elements in our set\n",
        "        continue\n",
        "\n",
        "    if cache.get(new_candidate,None)==None:\n",
        "        cache[new_candidate]=cache[candidate]+a\n",
        "    #if cache[new_candidate]==t:  #commented out as this is the precise solution\n",
        "    if abs(cache[new_candidate]-t)<tol: #found a solution within tolerance\n",
        "        return new_candidate\n",
        "    if cache[new_candidate]<t: \n",
        "        ans=ssp_dfs(t,s,new_candidate)\n",
        "        if ans!=None:\n",
        "          return ans\n",
        "    else: #we are bigger than t so can just end this branch\n",
        "          continue\n",
        "  return None\n"
      ],
      "metadata": {
        "id": "Gs__rk4ksWEn"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def SSP_Solve_hc(g):\n",
        "  my_graph=nx.DiGraph() #my_graph is a graph with just the nodes, containing associated data from g (weight and FAD)\n",
        "  my_graph.add_nodes_from(g.nodes(data=True))\n",
        "\n",
        "  s=[] #the set of FAD numbers used for SSP\n",
        "  for n in g.nodes:\n",
        "    s.append(g.nodes[n][\"FAD\"])\n",
        "\n",
        "  for n in g.nodes: #for each node, compute the target sum based for h-cat\n",
        "    t=(g.nodes[n][\"weight\"]-g.nodes[n][\"FAD\"])/g.nodes[n][\"FAD\"]\n",
        "    \n",
        "    if t==0:\n",
        "      continue #no need to add an edge for this node as its not attacked\n",
        "\n",
        "    init_ssp()\n",
        "    ans=ssp_dfs(t,s,frozenset([0]))  #now try to find the SSP that sums up to the target sum for that node \n",
        "  \n",
        "    if ans==None: #we couldn't find the sum\n",
        "        return False\n",
        "    \n",
        "    for a in ans: #if we find the solution, for node n we create an edge from the attacker (via its index in s) to the current node\n",
        "      if a!=0:\n",
        "        my_graph.add_edge(s.index(a),n)\n",
        "  return my_graph"
      ],
      "metadata": {
        "id": "phbW1AXZtKFm"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def SSP_Solve_cb(g):\n",
        "  my_graph=nx.DiGraph() #my_graph is a graph with just the nodes, containing associated data from g (weight and FAD)\n",
        "  my_graph.add_nodes_from(g.nodes(data=True))\n",
        "\n",
        "  s=[] #the set of FAD numbers used for SSP\n",
        "  sums=0\n",
        "  for n in g.nodes:\n",
        "    s.append(g.nodes[n][\"FAD\"])\n",
        "    sums+=s[-1]\n",
        "\n",
        "  for n in g.nodes: #for each node, compute the target sum based for card\n",
        "    \n",
        "    ans=None #ans will be the answer to the ssp\n",
        "    sigma=g.nodes[n][\"FAD\"]\n",
        "    w=g.nodes[n][\"weight\"]\n",
        "\n",
        "    if sigma==w: #an unattacked argument\n",
        "      continue\n",
        "    \n",
        "    #we have that k must be the integer between \n",
        "    #k=(w-f)/f as the upper bound\n",
        "    #k=(w-2f)/f as the lower bound\n",
        "    upper=(w-sigma)/sigma\n",
        "    lower=(w-2*sigma)/sigma\n",
        "\n",
        "    if math.floor(upper)!=math.ceil(lower):\n",
        "      print(\"error\",upper,lower)\n",
        "    k=math.floor(upper)\n",
        "\n",
        "    #for k in range(1,len(g.nodes)):\n",
        "      \n",
        "    t=-k*(sigma*k + sigma - w)/sigma \n",
        "      \n",
        "    if t<0 or sums<t: #invalid t value so can't be this k. Should never happen\n",
        "        continue\n",
        "      \n",
        "    init_ssp()\n",
        "    ans=ssp_dfs(t,s,frozenset([0]),k=k)  #now try to find the SSP that sums up to the target sum for that node \n",
        "  \n",
        "    if ans==None: #we couldn't find the sum, try next k\n",
        "        continue\n",
        "      \n",
        "    for a in ans: #if we find the solution, for node n we create an edge from the attacker (via its index in s) to the current node\n",
        "        if a!=0:\n",
        "          my_graph.add_edge(s.index(a),n)\n",
        "      #break #we've found an answer so go out of the k loop\n",
        "\n",
        "    if ans==None: #we've tried all k values and stil lcan't find a solution\n",
        "      return False \n",
        "  return my_graph"
      ],
      "metadata": {
        "id": "ZTEwxmbixJZb"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#TEST HCAT; set parameters for reproducibility\n",
        "seed=1\n",
        "random.seed(seed)\n",
        "np.random.seed(seed)\n",
        "\n",
        "num_args=13\n",
        "erdos_p=0.3\n",
        "g=nx.erdos_renyi_graph(num_args,p=erdos_p,seed=seed,directed=True)\n",
        "\n",
        "for n in g.nodes:\n",
        "    g.nodes[n][\"weight\"]=random.random()\n",
        "\n",
        "w=h_cat(g)\n",
        "for n in g.nodes:\n",
        "    g.nodes[n][\"FAD\"]=w[n]\n",
        "\n",
        "mg=SSP_Solve_hc(g)\n",
        "\n",
        "if mg!=False:\n",
        "  w2=h_cat(mg)\n",
        "  print(len(mg.edges()),\"\\n\",len(g.edges())) #these should be equal, and we should be able to dig into them\n",
        "  #let's compare the two FADs, should be close to 0\n",
        "  for n in g.nodes:\n",
        "    print(abs(w2[n]-g.nodes[n][\"FAD\"]))"
      ],
      "metadata": {
        "id": "kgvpOJk2tw4O"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "#TEST CB; set parameters for reproducibility\n",
        "seed=1\n",
        "random.seed(seed)\n",
        "np.random.seed(seed)\n",
        "\n",
        "num_args=13\n",
        "erdos_p=0.3\n",
        "g=nx.erdos_renyi_graph(num_args,p=erdos_p,seed=seed,directed=True)\n",
        "\n",
        "for n in g.nodes:\n",
        "    g.nodes[n][\"weight\"]=random.random()\n",
        "\n",
        "w=card(g)\n",
        "for n in g.nodes:\n",
        "    g.nodes[n][\"FAD\"]=w[n]\n",
        "  \n",
        "mg=SSP_Solve_cb(g)\n",
        "\n",
        "if mg!=False:\n",
        "  w2=card(mg)\n",
        "  print(len(mg.edges()),\"\\n\",len(g.edges())) #these should be equal, and we should be able to dig into them\n",
        "  #let's compare the two FADs, should be close to 0\n",
        "  for n in g.nodes:\n",
        "    print(abs(w2[n]-g.nodes[n][\"FAD\"]))"
      ],
      "metadata": {
        "id": "wLy7UEs6ykN7"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        ""
      ],
      "metadata": {
        "id": "iJ2YgNgNCIRB"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}