collab_lab2.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyOiDTjcapZYYBscmyGwgKgB",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/nrflynn2/swe-molecular-sciences/blob/main/collab_lab2.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "# Lab 2: Traversals on Drug Metabolism Networks\n",
        "\n",
        "Review the lab material and go through the entire notebook. The lab contains 5 exercises for you to solve. The entire lab is worth 2.5% of your final grade and each exercise is worth 0.4% of your final grade. Going through the full notebook is worth 0.5% of your final grade. Any extra credit or bonus exercises are worth an additional 0.4%.\n",
        "\n",
        "Labs are due by Friday at 11:59 PM PST and can be submitted on BCourses assignment page for the corresponding lab."
      ],
      "metadata": {
        "id": "F5icexU1Z58I"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Graph Concepts\n",
        "\n",
        "In week 4, we introduced graphs as a fundamental data structure.\n",
        "We reintroduce key graph concepts through a programmatic perspective by using the networkx library. Graph data not only contain intrinsic value, via nodes or\n",
        "vertices, but they also contain relationship value, via edges or links.\n",
        "Graphs can be used to represent a wide range of data including social\n",
        "relationships, physical networks, and business operations. Graphs can be\n",
        "undirected when the relationships between entities has no preferred\n",
        "direction or they can be directed, when a relationship is directed, such\n",
        "as parent to child or in social media when one person may follow another\n",
        "but not the other way around. Graphs can also allow or exclude\n",
        "multiple-connections  (or edges) between nodes.\n",
        "\n",
        "With the networkx library, we have the following [four types][ngt] of\n",
        "graphs:\n",
        "\n",
        "- `Graph`: a basic undirected graph,\n",
        "- `DiGraph`: a basic directed graph,\n",
        "- `MultiGraph`: an undirected graph that supports multiple edges (or\n",
        "links) between nodes, and\n",
        "- `MultiDiGraph`: a directed graph that supports multiple edges (or\n",
        "links) between nodes.\n",
        "\n",
        "In this Notebook, we will focus on the basic components of a graph:\n",
        "nodes, edges, and attributes, before moving on to the different types of\n",
        "graphs. First, we set up the basic environment of this notebook before\n",
        "introducing creating a graph and adding nodes.\n",
        "\n",
        "-----\n",
        "\n",
        "[ngt]: https://networkx.readthedocs.org/en/stable/reference/classes.html"
      ],
      "metadata": {
        "id": "hE574pb4ap6T"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Set up Notebook\n",
        "\n",
        "%matplotlib inline\n",
        "\n",
        "# Standard imports\n",
        "import numpy as np\n",
        "import pandas as pd\n",
        "import pprint\n",
        "import matplotlib.pyplot as plt\n",
        "import seaborn as sns\n",
        "\n",
        "# We do this to ignore several specific Pandas warnings\n",
        "import warnings\n",
        "warnings.filterwarnings(\"ignore\")"
      ],
      "metadata": {
        "id": "FY5xqKikaiKd"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Nodes\n",
        "\n",
        "The basic components in a graph are the nodes. Once we have created a\n",
        "graph, for example, by `nx.Graph` as shown below, we can begin to add\n",
        "nodes. A node can represent a number of different components, including\n",
        "a token, a document, a single person, a physical entity such as a\n",
        "computer or house, or a business. When using netowrkx, a node can be any\n",
        "Python object that is _hashable_, which essentially means nearly any\n",
        "Python object can be used as a node. While we often use simple constructs\n",
        "for nodes (since they often represent some physical construct), in some\n",
        "cases this capability can be very important.\n",
        "\n",
        "In the following code cells, we first create and draw different types of\n",
        "graphs (all of which contain no edges). First, we create a single node\n",
        "graph, whose node is the integer one. Next, we add tow more nodes, with\n",
        "the integers two and three, before expanding the graph to fourteen\n",
        "nodes, that span the integers one through fourteen. Finally, we display\n",
        "the list of nodes by calling the `nodes()` method on the graph object\n",
        "itself."
      ],
      "metadata": {
        "id": "zsJBOmsNbTMi"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import networkx as nx\n",
        "\n",
        "# Create and draw a single node graph\n",
        "g = nx.Graph()\n",
        "g.add_node(1)\n",
        "\n",
        "plt.figure(figsize=(2,2))\n",
        "nx.draw(g)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "jXcXyn-pbJfs"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Create and draw a three node graph\n",
        "\n",
        "g.add_nodes_from([2, 3])\n",
        "\n",
        "plt.figure(figsize=(3,3))\n",
        "nx.draw(g)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "-SN9173WbePV"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Create and draw a fourteen node graph\n",
        "\n",
        "g.add_nodes_from(range(4, 15))\n",
        "\n",
        "plt.figure(figsize=(3, 3))\n",
        "nx.draw(g)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "08nCndSzbhNu"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# List nodes\n",
        "\n",
        "print(g.nodes())"
      ],
      "metadata": {
        "id": "LZRW4ZqRbnRJ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "In the next cell, we add several nodes that demonstrate using\n",
        "non-standard types. First, we add several functions to the graph, before\n",
        "adding an open file handle. We next display the list of nodes in the\n",
        "graph (showing the functions and open file handle). Following this, we\n",
        "demonstrate how to remove nodes, first by removing the non-integer nodes\n",
        "one at a time, before we remove several integer nodes in bulk."
      ],
      "metadata": {
        "id": "3oKAbI6vb-uq"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Build graph of mixed nodes, integers and functions\n",
        "\n",
        "import math\n",
        "\n",
        "g.add_node(math.pi)\n",
        "g.add_node(math.exp)\n",
        "\n",
        "fout = open('tmp.dat','w')\n",
        "\n",
        "g.add_node(fout)\n",
        "\n",
        "print(g.nodes())"
      ],
      "metadata": {
        "id": "eQskmg_Ob3nS"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Remove single node\n",
        "g.remove_node(14)\n",
        "\n",
        "# Remove non integer nodes\n",
        "g.remove_node(math.pi)\n",
        "g.remove_node(math.exp)\n",
        "g.remove_node(fout)\n",
        "\n",
        "#remove list of nodes\n",
        "g.remove_nodes_from([11, 12, 13])\n",
        "\n",
        "#show results\n",
        "print(g.nodes())"
      ],
      "metadata": {
        "id": "B5agfvmNb7sq"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Edges\n",
        "\n",
        "On their own, nodes aren't very different than other data we have\n",
        "analyzed. The major change with graph (or networkx) data is the\n",
        "relationships between nodes. These relationships are modeled by using\n",
        "edges. An edge can be undirected, meaning each node is the same in the\n",
        "relationship, or the edge can be directed, which means there is a\n",
        "preferred direction, of course the edge could be bi-directional. The\n",
        "former is handled with an undirected graph, while the latter is handled\n",
        "with a directed graph. As an example, when using Facebook, two\n",
        "individuals are friends with each other (via a request), thus the edge\n",
        "is undirected, whereas in Twitter one individual might follow another\n",
        "individual, leading to a directed edge. Of course if two Twitter users\n",
        "follow each other, we have a bi-directional edge (it is still\n",
        "directional since other edge will all be directed, just possibly in one\n",
        "direction.\n",
        "\n",
        "In the following code cells, we demonstrate adding edges to a graph. We\n",
        "first add a single edge, by listing the starting and ending nodes,\n",
        "before adding multiple edges by supplying a list of tuples, where each\n",
        "tuple provides the initial and ending node. Following this, we\n",
        "demonstrate several different methods for drawing the same graph. These\n",
        "techniques differ based on the mechanism by which nodes are laid out,\n",
        "which can be affected by the edges in the graph."
      ],
      "metadata": {
        "id": "Ud7CeOjOcWV8"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Add single edge\n",
        "\n",
        "g.add_edge(0, 1)\n",
        "\n",
        "edgs = (3, 6)\n",
        "g.add_edge(*edgs)\n",
        "\n",
        "nx.draw(g)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "BgJ7znaqcTnj"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Remove edge\n",
        "g.remove_edge(0, 1)\n",
        "\n",
        "# now add new edges en masse.\n",
        "edgs = [(idx, idx + 1) for idx in range(g.order())]\n",
        "g.add_edges_from(edgs)\n",
        "\n",
        "# Draw graph\n",
        "plt.figure(figsize=(4, 4))\n",
        "nx.draw(g)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "6A44_S7_cgZC"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "plt.figure(figsize=(4, 4))\n",
        "nx.draw_circular(g)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "-Nd62jc5c2oq"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Shortcut to make this graph\n",
        "h = nx.path_graph(11)\n",
        "print(h.nodes())\n",
        "\n",
        "# Draw graph in circular format\n",
        "plt.figure(figsize=(4, 4))\n",
        "nx.draw_circular(h, with_labels=True)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "QMSoGOnIc51x"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "plt.figure(figsize=(5, 5))\n",
        "\n",
        "# Draw graph in networkx format\n",
        "nx.draw_networkx(g)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "AKIpSfVJc8sR"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Plot and specify node positions\n",
        "\n",
        "plt.figure(figsize=(5, 5))\n",
        "pos=nx.circular_layout(g)\n",
        "nx.draw_networkx(g, pos)\n",
        "nx.draw_networkx_labels(g, pos)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "-_QUCuhyc_IK"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "We also can create nodes by using string values. In the following cells,\n",
        "we create an undirected graph and add five nodes with string values for\n",
        "one through five, before adding different edges between these nodes,\n",
        "creating a kite like graph. We next display basic graph properties, such\n",
        "as the number of nodes and edges, the list of nodes and edges, and the\n",
        "number of neighbors (via the edge connections) to several different\n",
        "nodes."
      ],
      "metadata": {
        "id": "cC-eOhd0dIa8"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create a new arbitrary graph by hand, with string labels\n",
        "\n",
        "g = nx.Graph()\n",
        "g.add_node('1')\n",
        "g.add_node('2')\n",
        "g.add_node('3')\n",
        "g.add_node('4')\n",
        "g.add_node('5')\n",
        "g.add_edge('1', '2')\n",
        "g.add_edge('2', '3')\n",
        "g.add_edge('3', '4')\n",
        "g.add_edge('4', '1')\n",
        "g.add_edge('4', '5')\n",
        "\n",
        "# plot graph\n",
        "nx.draw_networkx(g)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "MBU7AY4CdIt4"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "n_nds = g.order() # or g.number_of_nodes()\n",
        "n_edgs = g.size() # or g.number_of_edges()\n",
        "print('Graph has {0} nodes and {1} edges'.format(n_nds, n_edgs))\n",
        "\n",
        "print('\\nNodes in the Graph:')\n",
        "print(g.nodes())\n",
        "\n",
        "print('\\nEdges in the Graph:')\n",
        "print(g.edges())\n",
        "\n",
        "nd = '4'\n",
        "\n",
        "# The node degree is the number of edges adjacent to that node.\n",
        "print('\\nNeighbors to node #{0}'.format(nd))\n",
        "print(g.degree(nd))\n",
        "\n",
        "# List neihgbors\n",
        "print('\\nNeighbors to node #{0}'.format(nd))\n",
        "print(g.neighbors(nd))"
      ],
      "metadata": {
        "id": "6lIGmfKMd2Ts"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Attributes\n",
        "\n",
        "Each entity in the graph, including the graph itself, can possess\n",
        "individual attributes. For example, a node can have a `name` attribute,\n",
        "while a different node can have the `name` attribute and a `type`\n",
        "attribute. Attributes can be defined at creation time or at later times,\n",
        "and some entities have _special_ attributes, such as the `weight`\n",
        "attribute for an edge. The attributes of the graph, node, or edge are\n",
        "maintained in a dictionary, and are thus accessed by using dictionary\n",
        "access methods. In the following cells, we demonstrate how to create or\n",
        "add attributes to the graph, to nodes, and to edges."
      ],
      "metadata": {
        "id": "g2791j_3d67U"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Graph Attributes\n",
        "\n",
        "# Specify an attribute at graph creation\n",
        "g = nx.Graph(my_name = 'Test')\n",
        "g.add_nodes_from(range(6))\n",
        "\n",
        "# Add an attribute by using dictionary\n",
        "g.graph['type'] = 'Demo'\n",
        "print(g.graph)\n",
        "\n",
        "# Set a default attribute\n",
        "g.name = 'Noah\\'s Graph!'\n",
        "\n",
        "plt.figure(figsize=(5, 5))\n",
        "nx.draw_networkx(g)\n",
        "plt.title(g.name)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "RjLKYfHVd_Ja"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Node attributes\n",
        "\n",
        "nd = 6\n",
        "g.add_node(nd, name='Robert')\n",
        "print(nd, g.nodes[nd])\n",
        "print('Node {0} name = {1}'.format(nd, g.nodes[nd]['name']))\n",
        "\n",
        "nd = 5\n",
        "g.nodes[nd]['name'] = 'Edward'\n",
        "print(nd, g.nodes[nd])\n",
        "print('Node {0} name = {1}'.format(nd, g.nodes[nd]['name']))"
      ],
      "metadata": {
        "id": "Y1stONU8eJf0"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Edge attributes\n",
        "\n",
        "# Specify attribute at edge creation\n",
        "g.add_edge('1', 6, rltn='friends')\n",
        "print(g['1'][6])\n",
        "\n",
        "# Special edge attribute is weight\n",
        "g.add_edge('1', '3', weight=10.0)\n",
        "print(g['1']['3'])\n",
        "\n",
        "# Add multuple weight attribtues\n",
        "g.add_edges_from([(idx, idx + 1, {'weight': (idx + 1) * 10})\n",
        "                  for idx in range(g.order())])"
      ],
      "metadata": {
        "id": "ETOIKxZaekAj"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Now list the nodes and draw the graph\n",
        "\n",
        "print(g.nodes())\n",
        "\n",
        "nx.draw_networkx(g)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "G8kdVHACengq"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Matrix Representations\n",
        "\n",
        "The relationships between nodes in a graph can be [represented\n",
        "numerically][nla] as matrices. The two most used matrix representations\n",
        "are the [adjacency matrix][wam] and the [incidence matrix][wim]. We\n",
        "demonstrate these two matrices for the graph created in the previous few\n",
        "code cells below. The adjacency matrix contains edges connecting node\n",
        "`i` to node `j` with an entry in position `i`, `j` in the matrix, and\n",
        "the value in the matrix can be the weight of the edge connecting the\n",
        "two nodes. The incidence matrix, on the other hand, represents each node\n",
        "as a row in the matrix and each edge as a column. Thus a value of one,\n",
        "in a standard incidence matrix, shows where an edge connects to a node.\n",
        "Note, how the adjacency matrix includes the weights of the edges\n",
        "connecting different nodes.\n",
        "\n",
        "[nla]: https://networkx.readthedocs.org/en/stable/reference/linalg.html\n",
        "[wam]: https://en.wikipedia.org/wiki/Adjacency_matrix\n",
        "[wim]: https://en.wikipedia.org/wiki/Incidence_matrix"
      ],
      "metadata": {
        "id": "ruspxM0fe_oC"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Adjacency Matrix\n",
        "adj_mat = nx.adjacency_matrix(g)\n",
        "\n",
        "print(adj_mat.todense())"
      ],
      "metadata": {
        "id": "rdmmKV4VfCab"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Incidence Matrix\n",
        "\n",
        "inc_mat = nx.incidence_matrix(g)\n",
        "print(inc_mat.todense())"
      ],
      "metadata": {
        "id": "kKaTeAO5fGdd"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Exercise 1: Graph Representations & Memory\n",
        "\n",
        "Consider an unweighted graph that has n = 156317 vertices and m = 1059331 edges. Assume that in your computer each boolean is 1 byte, each integer is 4 bytes, and each pointer also 4 bytes. Calculate the amount of memory that is necessary to store this graph using an adjacency matrix representation and an adjacency lists representation. Which takes up more memory?\n"
      ],
      "metadata": {
        "id": "aGMH8vca4t8u"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Directed Graphs\n",
        "\n",
        "To this point, we have simply demonstrated undirected graphs. We now\n",
        "introduce using directed graphs. The first change is the graph creation,\n",
        "where we now use `nx.DiGraph()` to create a simple, directed graph.\n",
        "Otherwise, we add edges in the same manner, albeit the direction is\n",
        "assumed to be from the starting node to the ending node. If we need to\n",
        "have directed edges going both ways, we simply add an edge with the\n",
        "nodes reversed in order. These concepts are demonstrated in the\n",
        "following cells, where we create and operate on directed graphs."
      ],
      "metadata": {
        "id": "quXI0s4UfNGc"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create a directed graph, add nodes and edges.\n",
        "dg = nx.DiGraph()\n",
        "dg.add_nodes_from(['1', '2', '3', '4', '5'])\n",
        "dg.add_edge('1', '2')\n",
        "dg.add_edge('2', '3')\n",
        "dg.add_edge('3', '4')\n",
        "dg.add_edge('4', '1')\n",
        "dg.add_edge('4', '5')\n",
        "dg.add_edge('5', '4')\n",
        "\n",
        "# Display nodes, edges, and the graph.\n",
        "print('Nodes:', dg.nodes())\n",
        "print('Edges:', dg.edges())\n",
        "\n",
        "nx.draw_spectral(dg, with_labels=True)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "tzzC-GeLfMT7"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Create directed graph, and add edges\n",
        "# (which adds the corresponding nodes automatically).\n",
        "\n",
        "dg = nx.DiGraph()\n",
        "dg.add_edge(1, 2)\n",
        "dg.add_edge(2, 3)\n",
        "dg.add_edge(3, 4)\n",
        "dg.add_edge(3, 1)\n",
        "dg.add_edge(3, 5)\n",
        "\n",
        "# Display nodes, edges, and directions.\n",
        "print('Nodes:', dg.nodes())\n",
        "print('Edges:', dg.edges())\n",
        "\n",
        "print('\\nNumber of edges entering a node:')\n",
        "print(dg.in_degree())\n",
        "\n",
        "print('\\nNumber of edges leaving a node:')\n",
        "print(dg.out_degree())\n",
        "\n",
        "# Draw graph.\n",
        "nx.draw(dg, with_labels=True)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "gbbGG0NWfT9z"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Create directed graph, and display directed edges,\n",
        "# and the weights of directed edges.\n",
        "\n",
        "dg = nx.DiGraph()\n",
        "dg.add_nodes_from(range(8))\n",
        "\n",
        "dg.add_weighted_edges_from([(idx, idx + 1, (idx + 1) * 10)\n",
        "                           for idx in range(dg.order())])\n",
        "\n",
        "print('\\nNumber of edges entering a node:')\n",
        "print(dg.in_degree())\n",
        "\n",
        "print('\\nNumber of edges leaving a node:')\n",
        "print(dg.out_degree())\n",
        "\n",
        "print('\\nWeighted Number of edges entering a node:')\n",
        "print(dg.in_degree(weight='weight'))\n",
        "\n",
        "print('\\nWeighted Number of edges leaving a node:')\n",
        "print(dg.out_degree(weight='weight'))\n",
        "\n",
        "nx.draw_circular(dg, with_labels=True)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "dO9-hXAXfYQz"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Multigraphs\n",
        "\n",
        "All graphs we have created and used within this notebook have been\n",
        "simple, which simply means two nodes can be connected by at most one\n",
        "edge. In some cases, however it makes sense to have multiple edges\n",
        "connecting two nodes. The networkx library provides two graph types,\n",
        "`MultiGraph` and `MultiDiGraph` for complex undirected or directed\n",
        "graphs, respectively. Below we demonstrate using a multi-graph, however,\n",
        "note that the multiple edges are not drawn by networkx. To visualize\n",
        "large or more complex graphs, other tools, such as [Graphviz][gv], are\n",
        "recommended.\n",
        "\n",
        "[gv]: http://www.graphviz.org"
      ],
      "metadata": {
        "id": "g1RgX_Mrfc-4"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Create directed multigraph and add nodes\n",
        "mdg = nx.MultiDiGraph()\n",
        "mdg.add_nodes_from(range(8))\n",
        "\n",
        "# Now add edges, including repeat edges.\n",
        "mdg.add_weighted_edges_from([(idx, idx + 1, (idx + 1) * 10)\n",
        "                            for idx in range(mdg.order())])\n",
        "\n",
        "mdg.add_weighted_edges_from([(1, 3, 0.5), (3, 5, 0.25), (5, 7, 0.125)])\n",
        "mdg.add_weighted_edges_from([(1, 3, 1.5), (3, 5, 2.25), (5, 7, 3.125)])\n",
        "\n",
        "# Display graph edges and the graph.\n",
        "print(mdg.edges())\n",
        "nx.draw_circular(mdg, with_labels=True)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "9I_FLOyKfcZ0"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Exercise 2: Directed Graph Construction\n",
        "\n",
        "- Make a directed graph with 20 integer nodes, and edges connecting every even integer node to the next odd integer node. Start from zero (Zero is an even number).\n",
        "  - Node 0 has an edge pointing to node 1\n",
        "  - Node 2 has an edge pointing to node 3\n",
        "  - ...\n",
        "  - Node 18 has an edge pointing to node 19"
      ],
      "metadata": {
        "id": "gxv7uCPjoM2Q"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "![UN01](https://github.com/nrflynn2/swe-molecular-sciences/blob/main/figures/L02_digraph_ex1.png?raw=1)"
      ],
      "metadata": {
        "id": "YC9csYyc5UYV"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def get_circular_dg():\n",
        "    '''\n",
        "    Creates a directed graph with 20 integer nodes.\n",
        "    Every even interger node is connected to the next odd integer node.\n",
        "\n",
        "    Paramters\n",
        "    ---------\n",
        "    None\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    A networkx.Digraph instance.\n",
        "    '''\n",
        "\n",
        "    # YOUR CODE HERE\n",
        "\n",
        "    return dg"
      ],
      "metadata": {
        "id": "klQ_vJnKoMTX"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "dg = get_circular_dg()"
      ],
      "metadata": {
        "id": "vQoSUqGJoz2Z"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Display graph edges and the graph to visually validate correct behavior.\n",
        "print(dg.edges())\n",
        "nx.draw_circular(dg, with_labels=True)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "EQcNFnp8pP1S"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Graph Analysis\n",
        "\n",
        "Graphs can be large and\n",
        "complex since they will are not simply data but also the relationships\n",
        "between the data. As a result, the subject of graph or [network\n",
        "analysis][wna] is quite complex and we will only skim the surface. In\n",
        "this notebook we demonstrate basic graph traversal, computing properties\n",
        "of nodes and edges, quickly building graphs by using generators, and\n",
        "combining graphs. Finally, we will perform basic graph analysis before\n",
        "exploring a sample graph that is included with the networkx library.\n",
        "\n",
        "[wna]: https://en.wikipedia.org/wiki/Network_science"
      ],
      "metadata": {
        "id": "ho7JUyP9dNxB"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "To demonstrate analyzing a graph, we first construct a simple path graph\n",
        "of ten nodes, with the nodes connected sequentially. Afterwards, we\n",
        "display the number of edges per node, the degree of each node, and the\n",
        "weight of each edge.\n"
      ],
      "metadata": {
        "id": "80OFZijmgalE"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Make a directed graph to traverse\n",
        "\n",
        "dg = nx.DiGraph()\n",
        "dg.add_nodes_from(range(10))\n",
        "\n",
        "dg.add_weighted_edges_from([(idx, idx + 1, (idx + 1) * 10)\n",
        "                           for idx in range(dg.order())])\n",
        "\n",
        "nx.draw(dg)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "mWE8F9n3dQ-I"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Display number of edges for each node\n",
        "\n",
        "fmt_str = 'Node {0} has {1} edge(s)'\n",
        "for node in dg.nodes():\n",
        "    print(fmt_str.format(node, dg.degree(node)))"
      ],
      "metadata": {
        "id": "MFQOLeViggVs"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Display node degrees (connections)\n",
        "\n",
        "fmt_str = 'Node {0} has degree {1}'\n",
        "for node in dg.nodes():\n",
        "    print(fmt_str.format(node, dg.degree(node)))"
      ],
      "metadata": {
        "id": "hHdCAWe0gjO2"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Display node connections with weights\n",
        "\n",
        "fmt_str = 'Node {0} connected to Node {1} with Weight {2}'\n",
        "for n, m, attr in dg.edges(data=True):\n",
        "    print(fmt_str.format(n, m, attr['weight']))"
      ],
      "metadata": {
        "id": "idWF9X8bgq9s"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Graph Operations\n",
        "\n",
        "Given one or more graphs, there are [different operations][nop] that can\n",
        "be performed as supported by the networkx library. For example,\n",
        "multiple graphs can be easily joined when there are no nodes in common\n",
        "(`union`). If there are overlaps, they can be ignored  (`compose`) or\n",
        "new nodes made to account for each duplicate (`disjoint_union`). The\n",
        "complement (an inverse) of a graph can be constructed (`complement`),\n",
        "subgraphs can be constructed by specifying nodes to extract from a\n",
        "graph, and cartesian products of two graphs (`cartesian_product`).\n",
        "\n",
        "[nop]: https://networkx.github.io/documentation/latest/reference/algorithms.operators.html"
      ],
      "metadata": {
        "id": "4cD2fRy8gs9X"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "g1 = nx.Graph()\n",
        "g1.add_nodes_from(range(6))\n",
        "\n",
        "g2 = nx.Graph()\n",
        "g2.add_nodes_from(range(6, 12))\n",
        "\n",
        "g3 = nx.Graph()\n",
        "g3.add_nodes_from(range(3, 11))\n",
        "\n",
        "print('Nodes in Graph 1:', g1.nodes())\n",
        "print('Nodes in Graph 2:', g2.nodes())\n",
        "print('Nodes in Graph 3:', g3.nodes())\n",
        "\n",
        "# Combine graphs with no overlaps\n",
        "gu = nx.union(g1, g2)\n",
        "print('\\nNodes in Union of Graphs 1 and 2:', gu.nodes())\n",
        "\n",
        "# Combine graphs with possible overlaps\n",
        "gcm = nx.compose(g1, g3)\n",
        "print('\\nNodes in Composition of Graphs 1 and 3:', gcm.nodes())\n",
        "\n",
        "# Make a subgraph, of specific nodes\n",
        "gsg = nx.subgraph(gu, g3)\n",
        "print('\\nSubgraph (g3 nodes) from Union of Graphs 1 and 2:', gsg.nodes())\n",
        "\n",
        "# Disjoint union treats each node as distinct.\n",
        "gdu = nx.disjoint_union(g1, g3)\n",
        "print('\\nNodes in Disjoint Union of Graphs 1 and 3:', gdu.nodes())\n",
        "\n",
        "print('\\nCaretsian Product of Graphs 1 and 2')\n",
        "gcp = nx.cartesian_product(g1, g2)\n",
        "\n",
        "pp = pprint.PrettyPrinter(indent=2, depth=2, width=54, compact=True)\n",
        "\n",
        "pp.pprint(list(gcp.nodes()))"
      ],
      "metadata": {
        "id": "vEE_dRC_g29z"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Make a siomple path graph\n",
        "h = nx.path_graph(6)\n",
        "print('Edges in Graph h:', h.edges())\n",
        "\n",
        "plt.figure(figsize=(3, 3))\n",
        "nx.draw_circular(h, with_labels=True)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "9nSIgGfihzRU"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Compute and display the graph complement\n",
        "hc = nx.complement(h)\n",
        "print('Edges in Complement of Graph h:', hc.edges())\n",
        "\n",
        "plt.figure(figsize=(3, 3))\n",
        "nx.draw_circular(hc, with_labels=True)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "jRHbnoLvh2kk"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Graph Generators\n",
        "\n",
        "In some cases, we simply need to create a graph for specific analyses or\n",
        "simple demonstrations. The networkx library provides _generators_ for a\n",
        "number of different types of graphs. These generators can be classified\n",
        "as _simple_, _classic_, or _stochastic_. The classic graphs are\n",
        "frequently used as they include the _complete_ and _complete bipartite_\n",
        "graphs, as well as the _barbell_ and _lollipop_ graphs. In the following\n",
        "code cells, we use several of these different generators to quickly make\n",
        "and display different types of graphs."
      ],
      "metadata": {
        "id": "2DrdqOo1h9E0"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Make a simple graph and display\n",
        "\n",
        "pg = nx.petersen_graph()\n",
        "print('Peterson Graph Edges:\\n')\n",
        "pp.pprint(pg.edges())\n",
        "\n",
        "plt.figure(figsize=(4, 4))\n",
        "nx.draw(pg, with_labels=True)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "m51UxH32iAVe"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Make a complete graph and display\n",
        "\n",
        "cg = nx.complete_graph(6)\n",
        "print('CG Edges:', cg.edges())\n",
        "\n",
        "plt.figure(figsize=(4, 4))\n",
        "nx.draw(cg, with_labels=True)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "ZtYqvCgqiEcF"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Make a complete bipartite graph and display\n",
        "\n",
        "cbg = nx.complete_bipartite_graph(3, 2)\n",
        "print('CBG Edges:', cbg.edges())\n",
        "\n",
        "plt.figure(figsize=(4, 4))\n",
        "nx.draw(cbg, with_labels=True)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "2gLVZTQBiHKs"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Make a barbell graph and display\n",
        "\n",
        "barbell = nx.barbell_graph(8, 2)\n",
        "nx.draw(barbell)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "HODPi8dDiJaU"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Make a lollipop graph and display (changing the node and edge colors)\n",
        "\n",
        "lg = nx.lollipop_graph(8, 3)\n",
        "\n",
        "nx.draw(lg, with_labels=True, node_color='g', node_size=750, edge_color='b')\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "Gc3aCyAPiMW5"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Make a Barabási–Albert graph and display\n",
        "\n",
        "ba = nx.barabasi_albert_graph(36, 12)\n",
        "nx.draw(ba)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "kZr06RBZiOhc"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Graph IO\n",
        "\n",
        "When working with graphs, it is often important to save the data to\n",
        "share or use later in another application. For example, when  working\n",
        "with twitter data (social network analysis) or chembl data (chemical / biological network analysis), we often will want to cache the data to avoid rate limits. The networkx library [supports reading and\n",
        "writing][nrw] graph data (or a subset of the graph data such as the\n",
        "nodes or edges) to a number of different formats, including\n",
        "\n",
        "- GML, or graph markup language\n",
        "- GEXF, or Graph Exchange XML Format\n",
        "- GraphML\n",
        "- JSON\n",
        "- GIS Shapefile\n",
        "\n",
        "and of course, you can also pickle graphs. Below we demonstrate this\n",
        "capability, by first creating a simple graph and writing it to a\n",
        "temporary file. We demonstrate this file exists by using the Unix list\n",
        "files command (`ls -la`), before reading the graph into a new variable\n",
        "and displaying the recovered graph.\n",
        "\n",
        "[nrw]: https://networkx.github.io/documentation/latest/reference/readwrite.html"
      ],
      "metadata": {
        "id": "xP3xK-zPidO_"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "tcg = nx.complete_graph(12)\n",
        "nx.write_gml(tcg, 'tmp-cg.dat')"
      ],
      "metadata": {
        "id": "2ABLxB36iwpl"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "!ls -la tmp-cg.dat"
      ],
      "metadata": {
        "id": "Xa3I0L2DiyQ-"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "ncg = nx.read_gml('tmp-cg.dat')\n",
        "\n",
        "print('CG Edges:', tcg.edges())\n",
        "\n",
        "clrs = sns.color_palette(\"Paired\")\n",
        "\n",
        "plt.figure(figsize=(5, 5))\n",
        "nx.draw(tcg, with_labels=True, node_color=clrs[0])\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "1rv8RXfHi1XG"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Graph Analysis\n",
        "\n",
        "So far, we have only created graphs. The power of network analysis,\n",
        "however, is in analyzing the properties of graphs to gain insight into\n",
        "the underlying data. This can include finding clusters of nodes,\n",
        "computing path distances between nodes, and finding properties of the\n",
        "entire graph or of collections of nodes. The networkx library provides a\n",
        "wide range of basic graph analysis methodology, which is demonstrated in\n",
        "the rest of this notebook. First, we analyze the lollipop graph to\n",
        "identify clusters. In this case, there is one cluster and points are\n",
        "inside it (value of 1), outside (value of 0), or on the border\n",
        "(fractional value). Next, we create a special graph and identify the\n",
        "connected components."
      ],
      "metadata": {
        "id": "TRxKB3z5i4VG"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Apply clustering to lollipop graph\n",
        "print(nx.clustering(lg))\n",
        "\n",
        "nx.draw(lg, with_labels=True, node_color=clrs[2], node_size=750)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "jibMBq2OjMRl"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "g = nx.Graph()\n",
        "g.add_nodes_from(range(8))\n",
        "g.add_edges_from([(1, 2), (2, 3), (4, 5), (5, 6), (7, 8)])\n",
        "\n",
        "plt.figure(figsize=(5, 5))\n",
        "nx.draw(g, with_labels=True, node_color=clrs[2], node_size=750)\n",
        "plt.show()\n",
        "\n",
        "for idx, nds in enumerate(nx.connected_components(g)):\n",
        "    print('Connected Group {0} has {1} nodes: {2}'.format(idx, len(nds), nds))"
      ],
      "metadata": {
        "id": "ehKKwBlpjSBn"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "The networkx library has a number of build-in graph analysis methods,\n",
        "which can be used to find properties of the graph, such as the `center`\n",
        "or `radius`, but also to compute paths between nodes. For example, one\n",
        "commonly required task is to compute the shortest path between nodes,\n",
        "which can include weights from the edges (which might be miles between\n",
        "cities). In the following cll, we modify the previous graph to make a\n",
        "special graph that has nodes with varying path lengths. In the following\n",
        "cells, we compute and display several graph properties before computing\n",
        "the shortest paths between each pair of nodes. Finally, we compute the\n",
        "number of paths of a given length that connect all pairs of nodes.\n"
      ],
      "metadata": {
        "id": "IHcNexlFjWyX"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# Compute Shortest Paths\n",
        "\n",
        "g.add_edges_from([(0, 3), (2, 7), (1, 5)])\n",
        "\n",
        "plt.figure(figsize=(5, 5))\n",
        "nx.draw(g, with_labels=True, node_color=clrs[2], node_size=750)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "sLZnTz-3jYqb"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "print(\"Graph Radius: {0:3.1f}\".format(nx.radius(g)))\n",
        "print(\"Graph Diameter: {0:3.1f}\".format(nx.diameter(g)))\n",
        "print(\"Graph Eccentricity: {0}\".format(nx.eccentricity(g)))\n",
        "print(\"Graph Center: {0}\".format(nx.center(g)))\n",
        "print(\"Graph Periphery: {0}\".format(nx.periphery(g)))\n",
        "print(\"Graph Density: {0:4.3f}\".format(nx.density(g)))"
      ],
      "metadata": {
        "id": "T1vki4BpjdS4"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "path_lengths=[]\n",
        "\n",
        "print(\"Starting Node {End Node : Length, ... }\")\n",
        "for node in g.nodes():\n",
        "    spl= nx.single_source_shortest_path_length(g, node)\n",
        "    print('{0} {1}'.format(node, spl))\n",
        "    for path in spl.values():\n",
        "        path_lengths.append(path)\n",
        "\n",
        "print(\"\\nAverage shortest Path Length = {0:4.3f}\".format(sum(path_lengths)/len(path_lengths)))"
      ],
      "metadata": {
        "id": "vf8XyTiJjf9m"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Accumulate number of paths in graph of given length\n",
        "\n",
        "lengths = {}\n",
        "for path in path_lengths:\n",
        "    if path in lengths:\n",
        "        lengths[path] += 1\n",
        "    else:\n",
        "        lengths[path] = 1\n",
        "\n",
        "print(\"Length : Number of Paths\")\n",
        "for length in sorted(lengths.keys()):\n",
        "    print('  {0}    :    {1:2d}'.format(length, lengths[length]))"
      ],
      "metadata": {
        "id": "URvk120ejjSG"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "\n",
        "Another important concept in graphs is natural groupings, which are\n",
        "known as _cliques_. The networkx library provides methods to find\n",
        "cliques, which may or may not be useful for a particular analysis (in\n",
        "other words, you may need have to provide specific functionality  if\n",
        "the networkx methods are not sufficient). Below we compute the number of\n",
        "_maximal_ cliques and then display the different cliques."
      ],
      "metadata": {
        "id": "OwFmOPAxjl5i"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "print('Total number of maximal cliques = {0}'.format(nx.number_of_cliques(g)))\n",
        "\n",
        "for clique in nx.find_cliques(g):\n",
        "    print(clique)"
      ],
      "metadata": {
        "id": "Ppq5yJWEjnwy"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Demo Graph\n",
        "\n",
        "The networkx library comes with several data sets, which can be used to\n",
        "demonstrate basic graph analysis. Below we use one of these data sets,\n",
        "the _Davis Women's club_ data. This data has relationships between the\n",
        "different women, and also who attended which club event. Below we first\n",
        "display a histogram of the number of connections between the women\n",
        "before computing the number of friends for each woman (we use a\n",
        "bipartite graph to simplify this calculation). Finally, we conclude this\n",
        "demo by displaying the graph and computing the number of shard\n",
        "connections, via the number of meetings each woman attended and the\n",
        "number of other women at those meetings.\n"
      ],
      "metadata": {
        "id": "qIqbwmnqnRSu"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "sample_graph = nx.davis_southern_women_graph()\n",
        "\n",
        "edges = [v for k, v in nx.degree(sample_graph)]\n",
        "\n",
        "plt.figure(figsize=(6, 6))\n",
        "sns.set(style='white')\n",
        "sns.distplot(edges, kde=False)\n",
        "sns.despine(offset=5)"
      ],
      "metadata": {
        "id": "Nb0i7_COnUQZ"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "import networkx.algorithms.bipartite as bipartite\n",
        "\n",
        "women = sample_graph.graph['top']\n",
        "\n",
        "# We make a bipartite graph linking each individual woman to the other women\n",
        "bpg = bipartite.projected_graph(sample_graph, women)\n",
        "print('{0:25s} : # Friends'.format('Member'))\n",
        "print(40*'-')\n",
        "\n",
        "for woman in women:\n",
        "    print('{0:25s} : {1:2d}'.format(woman, bpg.degree(woman)))"
      ],
      "metadata": {
        "id": "vCRkc6gCn5K4"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Plot the connections between the women.\n",
        "\n",
        "plt.figure(figsize=(8, 8))\n",
        "\n",
        "pos = nx.spring_layout(bpg)\n",
        "nx.draw(bpg, node_size=500, node_color=clrs[1], node_shape='H')\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "izuyeHOfn7zx"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# Make bipartite graph that weights connections between an individual\n",
        "# woman and the other women by the number of shared contacts\n",
        "\n",
        "bpwg = bipartite.weighted_projected_graph(sample_graph, women)\n",
        "\n",
        "print('{0:25s} : # Friend Meetings'.format('Member'))\n",
        "print(40*'-')\n",
        "\n",
        "for woman in women:\n",
        "    print('{0:25s} : {1:2d}'.format(woman, bpwg.degree(woman, weight='weight')))"
      ],
      "metadata": {
        "id": "zhwuQCiAoEUM"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Exercise 2: Zachary's Karate Club\n",
        "\n"
      ],
      "metadata": {
        "id": "ScEvwoPjpjfm"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "We use [Zachary's Karete Club](https://networkx.github.io/documentation/latest/reference/generated/networkx.generators.social.karate_club_graph.html) data set. You can read more about it on [Wikipedia](https://en.wikipedia.org/wiki/Zachary%27s_karate_club) or refer to the original paper [Zachary (1997)].\n",
        "\n",
        "According to Wikipedia:\n",
        "\n",
        "<blockquote>\n",
        "A social network of a karate club was studied by Wayne W. Zachary for a period of three years from 1970 to 1972. The network captures 34 members of a karate club, documenting 78 pairwise links between members who interacted outside the club. During the study a conflict arose between the administrator \"John A\" and instructor \"Mr. Hi\" (pseudonyms), which led to the split of the club into two. Half of the members formed a new club around Mr. Hi, members from the other part found a new instructor or gave up karate. Basing on collected data Zachary assigned correctly all but one member of the club to the groups they actually joined after the split.\n",
        "</blockquote>"
      ],
      "metadata": {
        "id": "YVPGaHWtWSlK"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "g = nx.karate_club_graph()"
      ],
      "metadata": {
        "id": "Og5sXxMcWW1w"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "fig, ax = plt.subplots()\n",
        "nx.draw(g, ax=ax, with_labels = True)\n",
        "plt.show()"
      ],
      "metadata": {
        "id": "SjczAthdWa6Q"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Exercise 3: Compute the Degree of each Node\n",
        "\n",
        "Compute the degree of each node in the graph. To do this, implement the get_degree function. A working implementation will pass the assertion statements a few cells down."
      ],
      "metadata": {
        "id": "UB2dMNNjWw2p"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def get_degree(graph):\n",
        "    '''\n",
        "    Computes the degree of each node.\n",
        "\n",
        "    Paramters\n",
        "    ---------\n",
        "    graph: A networkx.Graph instance.\n",
        "\n",
        "    Returns\n",
        "    -------\n",
        "    A dict of foramt {node: degree}\n",
        "    '''\n",
        "\n",
        "    # YOUR CODE HERE\n",
        "    result = {}\n",
        "\n",
        "    #TODO: Iterate over each node in the graph, compute the degree of the node, and store it in the dictionary at the index of the node\n",
        "\n",
        "    return result"
      ],
      "metadata": {
        "id": "PK1ZGCjmW0hp"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "degree = get_degree(g)\n",
        "print('Node  Degree')\n",
        "for node in degree:\n",
        "    print('{0:4d} {1:7d}'.format(node, degree[node]))"
      ],
      "metadata": {
        "id": "1NWH-Xy-XG-8"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# For full points on exercise 3, your computation should pass the following assertion\n",
        "assert list(degree.keys()) == list(range(34))\n",
        "assert degree[0] == 16\n",
        "assert degree[1] == 9\n",
        "assert degree[32] == 12\n",
        "assert degree[33] == 17"
      ],
      "metadata": {
        "id": "DrBFzWndXJUi"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "source": [
        "We see that two people (Nodes 0 and 33) have well above the average number of degrees. Node 0 corresponds to Mr. Hi, and node 33 corresponds to John A (or \"officer\"). Node 32 has many friends but not as many as those two. To visualize this, we color each node according to whether it is a friend of node 0 or node 33.\n",
        "\n",
        "If someone is a friend of both 0 and 33, classify the node as a friend of node 33.\n",
        "\n",
        "By coloring the friends of node 0 and node 33, we can see that the club has two subgroups based on social relationships!\n",
        "\n",
        "![UN02](https://github.com/nrflynn2/swe-molecular-sciences/blob/main/figures/L02_karate_ex2.png?raw=1)"
      ],
      "metadata": {
        "id": "MzocmXgeXajc"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Exercise 4: Fun with Graphs\n",
        "\n",
        "In the preceding cells, we introduced several basic graph analysis\n",
        "techniques.\n",
        "\n",
        "Make a new graph with 12 nodes. Add edges between all pairs of even nodes. Add edges between all pairs of odd nodes. Next add edges between nodes that are evenly divisible by three.\n",
        "\n",
        "1. Plot your new graph.\n",
        "2. Compute the clustering on this new graph. Describe the results and if it makes sense.\n",
        "3. Compute graph statistics such as `radius` and `density`. What were the computed values?"
      ],
      "metadata": {
        "id": "yWUjB8Zfalwx"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## War Story: Traversals on Drug Metabolism Networks"
      ],
      "metadata": {
        "id": "yIgJxfK0dSUM"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Idiosyncratic Adverse Drug Reactions\n",
        "\n",
        "Adverse drug reactions (ADRs) are a core limiting factor in the development of drugs and their distribution. ADRs account for 4.9--7.7\\% of hospital admissions and are a leading cause of death in the U.S. Moreover, vulnerable populations face high risks -- 39\\% of ADRs in pediatric patients end up being life--threatening or fatal and 11.4--35.5\\% of geriatric hospital admissions are due to drug--related incidences. Incidence of ADRs in the USA are estimated to cost up to 30.1 billion dollars annually due to  increased hospitalization, prolongation of hospital stay, and visits to emergency departments.\n",
        "\n",
        "Approximately 10--15\\% of ADRs are dose-independent and idiosyncratic (IADRS), which makes them notoriously difficult to plan for and unable to be evaded by simple dose adjustments. IADRs occur at very low frequencies of 1 in 10,000 to 1 in 100,000, allowing them to evade detection until the drug has gained increased exposure at large population levels that are not tractable in clinical trials. IADRs commonly affect the skin, blood cells, and especially the liver. At least 17\\% of liver transplant cases and 50\\% of acute liver failure cases can be traced to IADRs. Consequently, IADRs are a major reason for drug clinical trial termination and drug-induced liver injury, which is the leading cause of drug withdrawal from the market. Partly due to a poor ability to screen early on for IADRs, one in five drugs that has been on the market for at least two years ends up being withdrawn or tagged with a black box warning. Metabolic activation of an extraneous drug, or xenobiotic, into a reactive metabolite, is a common precursor of ADRs."
      ],
      "metadata": {
        "id": "Dz5hQCwZp6dw"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Understanding Reactive Metabolite Formation\n",
        "\n",
        "In silico prediction of reactive metabolites is an important cheminformatics problem.\n",
        "Reactive metabolite formation is an unfortunate consequence of drug-clearing defense mechanisms, i.e., metabolism.\n",
        "Metabolism is generally beneficial, making drugs more hydrophilic and easier to excrete.\n",
        "However, metabolism can transform drugs into pernicious reactive metabolites that may conjugate to DNA or off-target proteins and result in adverse events.\n",
        "In particular, P450 enzymes are highly relevant to bioactivation processes surrounding drugs, as they collectively have more substrates than any other enzymes and several of their reaction products have strong electrophilic properties.\n",
        "Reactive metabolites are significant drivers of drug candidate attrition and market withdrawal -- 65% of drugs associated with IADRs have been shown to produce reactive metabolites, primarily resulting in adverse outcomes in conditions that affect the blood, liver, and skin.\n",
        "Detection of reactive metabolite formation during metabolism of a drug to known structural end points could be leveraged to engineer rational modifications that bypass formation of the reactive metabolite in favor of benign metabolic pathways.\n",
        "\n",
        "![UN03](https://github.com/nrflynn2/swe-molecular-sciences/blob/main/figures/L02_RMs_Adverse_Outcomes.png?raw=1)\n",
        "\n",
        "Computational methods are high-throughput and cheap to perform to screen thousands to millions of compounds for potentially toxic molecules during the early stages of the drug development pipeline.\n",
        "Commonly used computational methods focus on detecting and structurally characterizing reactive metabolite-biomolecule adducts or predicting sites on a drug molecule that are liable to form reactive metabolites.\n",
        "However, such methods are often only concerned with the structure of the initial drug molecule (i.e., the starting state) or of the adduct formed when a biomolecule conjugates to a reactive metabolite (i.e., the ending state).\n",
        "This is problematic because the majority of drug molecules require more than one metabolic transformation to form a reactive metabolite.\n",
        "Thus, these methods are likely to miss intermediate metabolites that may lead to subsequent reactive metabolite formation.\n",
        "To address these shortcomings, we will consider XenoNet, which was a metabolic network predictor that receives an input substrate molecule and optional target metabolite(s) and generates a metabolic network.\n",
        "In the metabolic network, molecules are nodes and directional edges convey metabolic transformations.\n",
        "The metabolic network is generated by enumerating pathways, or sequences of intermediate metabolites, between the substrate and targets and predicting the probability of each metabolic transformation."
      ],
      "metadata": {
        "id": "GzxIjxPAqhqJ"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "XenoNet works by iteratively chaining together two types of models: Site of metabolism (SOM) models, which identify atoms, or bonds, that are liable to be metabolized, and metabolite structure inference models, which can infer the structures of potential metabolites formed during metabolism of a given molecule.\n",
        "\n",
        "![UN04](https://github.com/nrflynn2/swe-molecular-sciences/blob/main/figures/L02_SOM_models.png?raw=1)\n",
        "\n",
        "![UN05](https://github.com/nrflynn2/swe-molecular-sciences/blob/main/figures/L02_structure_inference_models.png?raw=1)\n",
        "\n",
        "XenoNet uses a deep learning phase I and phase II metabolism model to predict sites of metabolism. It uses a rule-based structure inference model (reliant on various path-finding graph algorithms) to infer possible metabolite structures that are one metabolic step away, as well as the specific SOMs and the corresponding metabolic transformations that act on those SOMs to produce the inferred metabolite.\n",
        "\n",
        "Metabolic pathways are explored in a depth-first manner, where the structure inference algorithm is applied iteratively to generate a tree of potential pathways that span multiple metabolic pathways, eventually resulting in a final graph structure where inferred pathways are saved if they meet user-defined criteria (as visualized below).\n",
        "\n",
        "![UN06](https://github.com/nrflynn2/swe-molecular-sciences/blob/main/figures/L02_DFS_build_network.png?raw=1)\n",
        "\n",
        "With respect to inferring intermediate, reactive metabolite structures, all pathways that link a user-defined starting molecule and user-defined target molecule(s) are saved. Through the application of the SOM model, the likelihood of each step in a pathway can then be computed.\n",
        "XenoNet's weighted metabolic pathways are stored using a custom graph-based data structure where each molecule is a node, and each metabolic transformation is an edge.\n",
        "This network object supports additional functionality, such as the ability to compute the likelihoods of paths and metabolites in the network, output a subnetwork of most important metabolites by some metric, compute network centrality measures, etc. In addition, the network object readily supports conversion to a NetworkX MultiDiGraph class object for further utility.\n",
        "\n",
        "![UN07](https://github.com/nrflynn2/swe-molecular-sciences/blob/main/figures/xenonet_high_level.png?raw=1)\n",
        "\n",
        "![UN08](https://github.com/nrflynn2/swe-molecular-sciences/blob/main/figures/xenonet_high_level_2.png?raw=1)\n"
      ],
      "metadata": {
        "id": "dGz0xj3U8Qd_"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### Problem from an Algorithmic Perspective\n",
        "\n",
        "Consider the example network output provided by XenoNet.\n",
        "\n",
        "![UN09](https://github.com/nrflynn2/swe-molecular-sciences/blob/main/figures/L02_xenonet_example_1.png?raw=1)\n",
        "\n",
        "Now consider the following network.\n",
        "\n",
        "![UN10](https://github.com/nrflynn2/swe-molecular-sciences/blob/main/figures/L02_xenonet_example.png?raw=1)\n",
        "\n",
        "These networks can get quite large, much larger and complex than what it shown here. From an algorithmic perspective, traversing the whole tree has time complexity $O(n^d)$ -- intractable to search the whole tree.\n",
        "- n = number of metabolites per molecules\n",
        "- d = depth of search\n",
        "\n",
        "In practice, conducting full network construction is not tractable for $d \\geq 3$\n"
      ],
      "metadata": {
        "id": "7Els8X14rmwt"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "How can algorithms (and other methods) help us? Some ideas:\n",
        "1. Algorithmic variants\n",
        "  - Bidirectional search. For network inputs that have a defined target, search from the start while, in parallel, searching in reverse from the target(s). Requires implement retrosynthetic algorithms to enact the structure inference process in reverse + some tricky adaptations to consolidate overlaps.\n",
        "  - Greedy search. Use the SOM model predictinos and limit future searches to only the top $n$ metabolites at a given depth in the tree. If don't want this to be deterministic, then stochastically sample from possible next metabolites to conduct the search from by using their associated SOM model prediction (normalized) as a proxy for a probability.\n",
        "  - Beam search. A greedy approach selects the most probable metabolites at each search step, but is problematic because it is impossible to know a priori which chosen metabolite will lead to the more promising future. The effect of choosing a metabolite may not be obvious until several search steps later and early choice of the wrong metabolite may cumulatively lead to a poorer overall path probability over time. Performing an exhaustive search, retaining all choices, and forking the network with every possible molecule under consideration at a given step rapidly blows up. Instead, retain only the top $N$ scoring forks at each search step. We choose the top $N$ based on the product of probabilities of all metabolites along the path constructed so far.\n",
        "\n",
        "![UN11](https://github.com/nrflynn2/swe-molecular-sciences/blob/main/figures/L02_beam_search.png?raw=1)\n",
        "\n",
        "2. Heuristics to reduce search space (e.g., reduce $n$)\n",
        "  - Substructure search. If you know the start structure and the target structure(s), then you can narrow down sites of metabolism to consider from all sites in a molecule to only those sites that are different between the start and target structures.\n",
        "\n",
        "![UN12](https://github.com/nrflynn2/swe-molecular-sciences/blob/main/figures/L02_search_heuristics.png?raw=1)\n",
        "\n",
        "3. Iterative construction.\n",
        "  - Machine learning based. We can build out an initial version of the network, say at a depth limit of 2, then extract an \"important\" (where important can mean whatever we want it to mean) subnetwork via a deep learning model. Then, resume the network construction process on the subnetwork. Idea is build out initial network, prune irrelevant elements, then continue building out.\n",
        "  - Graph theory based. Do similar as above, but use classic centrality measures to score \"important\" metabolites and links.\n",
        "\n",
        "![UN13](https://github.com/nrflynn2/swe-molecular-sciences/blob/main/figures/L02_subnet_extraction_main_idea.png?raw=1)"
      ],
      "metadata": {
        "id": "uQSQTZq6Akm2"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Exercise 5: Trade-offs\n",
        "\n",
        "Several of the proposed solutions enact a trade-off that reduces the search time but might result in an output network that captures less of the full picture. Which method do you think reduces the search time the most? Which method do you think would result in greatest reduction in the quality of the network output? Why for both? Feel free to make any additional assumptions, but do state them. There is not one right answer and this question is graded primarily on your ability to justify a choice."
      ],
      "metadata": {
        "id": "pJMW9fapGSMJ"
      }
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "vlqgttcxF9Cl"
      },
      "execution_count": null,
      "outputs": []
    }
  ]
}