Lab00.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Setting Up Your Environment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook contains some guidelines to prepare programming environments for the upcomming labs. During our labs we will mostly work in Jupyter Notebook. \n",
    "\n",
    "(We are using Python 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Step 1: Install Jupyter Notebook"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I suggest you to install free [Anaconda](https://docs.anaconda.com/anaconda/install/) Python distribution which already includes all necessary Python packages and modules - NumPy, SciPy, Matplotlib and **NetworkX**. Simply download appropriate installer for your OS and follow the proposed steps."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<!-- -*- coding: utf-8 -*- -->\n",
    "# Introduction to NetworkX\n",
    "*Credits: This tutorial was created by the NetworkX Developers and modified by Laura Arditti.*\n",
    "\n",
    "This guide can help you start working with NetworkX."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph Types\n",
    "\n",
    "NetworkX provides data structures and methods for storing graphs. The choice of graph class depends on the structure of the graph you want to represent.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Graph—Undirected graphs\n",
    "Base class for undirected graphs.\n",
    "A Graph stores nodes and edges with optional data, or attributes.\n",
    "Graphs hold undirected edges. Self loops are allowed but multiple (parallel) edges are not.\n",
    "Edges are represented as links between nodes with optional key/value attributes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Creating a Graph\n",
    "\n",
    "Create an empty graph with no nodes and no edges."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import networkx as nx\n",
    "G = nx.Graph()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By definition, a `Graph` is a collection of nodes (vertices) along with\n",
    "identified pairs of nodes (called edges, links, etc).  In NetworkX, nodes can\n",
    "be any hashable object e.g., a text string, an image, another\n",
    "Graph, etc.\n",
    "\n",
    "## Nodes\n",
    "\n",
    "The graph `G` can be grown in several ways.  You can add one node\n",
    "at a time,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.add_node(1)\n",
    "print(G.nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or you can add the nodes from any container (a list, dict, set or the nodes from another graph)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.add_nodes_from([2, 3])\n",
    "G.add_nodes_from(range(100, 110))\n",
    "H = nx.path_graph(10)\n",
    "G.add_nodes_from(H)\n",
    "print(G.nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# What to use as nodes and edges\n",
    "Any Python hashable object (except `None`) can represent a node, even another Graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.add_node(H)\n",
    "print(G.nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The graph `G` now contains `H` as a node. This flexibility is very powerful as\n",
    "it allows graphs of graphs, graphs of files, and much more.\n",
    "\n",
    "Similarily, an edge can be associated\n",
    "with any object `x` using `G.add_edge(n1, n2, object=x)`.\n",
    "\n",
    "Nodes and edges are not specified as NetworkX\n",
    "objects.  This leaves you free to use meaningful items as nodes and\n",
    "edges. The most common choices are numbers or strings."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Edges\n",
    "\n",
    "`G` can also be grown by adding one edge at a time,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.add_edge(1, 2)\n",
    "e = (2, 3)\n",
    "G.add_edge(*e)  # unpack edge tuple*\n",
    "print(G.edges)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "by adding a list of edges,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.add_edges_from([(1, 2), (1, 3)])\n",
    "print(G.edges)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or by adding any ebunch of edges.  An *ebunch* is any iterable\n",
    "container of edge-tuples.  An edge-tuple can be a 2-tuple of nodes or a 3-tuple\n",
    "with 2 nodes followed by an edge attribute dictionary, e.g.,\n",
    "`(2, 3, {'weight': 3.1415})`.\n",
    "For example, an instance of ebunch containing all the edges of the graph H is obtained with `H.edges`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.add_edges_from(H.edges)\n",
    "print(G.edges)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If some edges connect nodes not yet in the graph, the nodes are added automatically. There are no errors when adding nodes or edges that already exist.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For example, after removing all nodes and edges,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.clear()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "we add new nodes/edges and NetworkX quietly ignores any that are\n",
    "already present."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.add_edges_from([(1, 2), (1, 3)])\n",
    "G.add_node(1)\n",
    "G.add_edge(1, 2)\n",
    "G.add_node(\"spam\")        # adds node \"spam\"\n",
    "G.add_nodes_from(\"spam\")  # adds 4 nodes: 's', 'p', 'a', 'm'\n",
    "G.add_edge(3, 'm')\n",
    "print(\"Nodes:\", G.nodes)\n",
    "print(\"Edges:\", G.edges)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "At this stage the graph `G` consists of 8 nodes and 3 edges, as can be seen by:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Number of nodes:\", G.number_of_nodes())\n",
    "print(\"Number of edges:\", G.number_of_edges())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Examining elements of a graph\n",
    "\n",
    "\n",
    "We can examine the nodes and edges. Four basic graph properties facilitate\n",
    "reporting: `G.nodes`, `G.edges`, `G.adj` and `G.degree`.  These\n",
    "are views of the nodes, edges, neighbors (adjacencies), and degrees\n",
    "of nodes in a graph. They offer a continually updated read-only view into\n",
    "the graph structure.\n",
    "\n",
    "They are also dict-like in that you can look up node\n",
    "and edge data attributes via the views and iterate with data attributes\n",
    "using methods `.items()`, `.data('attribute')`.\n",
    "\n",
    "\n",
    "If you want a specific container type instead of a view, you can specify one.\n",
    "Here we use lists, though sets, dicts, tuples and other containers may be\n",
    "better in other contexts."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"List of nodes:\", list(G.nodes))\n",
    "print(\"List of edges:\", list(G.edges))\n",
    "print(\"List of neighbors of node 1:\", list(G.adj[1]))  # or list(G.neighbors(1))\n",
    "print(\"Degree of node 1:\", G.degree[1])  # the number of edges incident to 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One can specify to report the edges and degree from a subset of all nodes\n",
    "using an *nbunch*. An *nbunch* is any of: None (meaning all nodes), a node,\n",
    "or an iterable container of nodes that is not itself a node in the graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.degree([2, 3])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Removing elements from a graph\n",
    "\n",
    "One can remove nodes and edges from the graph in a similar fashion to adding.\n",
    "Use methods\n",
    "`Graph.remove_node()`,\n",
    "`Graph.remove_nodes_from()`,\n",
    "`Graph.remove_edge()`\n",
    "and\n",
    "`Graph.remove_edges_from()`, e.g."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.remove_node(2)\n",
    "G.remove_nodes_from(\"spam\")\n",
    "G.remove_edge(1, 3)\n",
    "list(G.nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "# Accessing edges and neighbors\n",
    "\n",
    "In addition to the views `Graph.edges`, and `Graph.adj`,\n",
    "access to edges and neighbors is possible using subscript notation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.Graph([(1, 2, {\"color\": \"yellow\"})])\n",
    "print(\"Neighborhood of node 1:\", G[1])\n",
    "# same as \n",
    "print(G.adj[1])\n",
    "print(\"Edge attributes of edge between 1 and 2:\", G[1][2])\n",
    "# same as \n",
    "print(G.edges[(1, 2)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can get/set the attributes of an edge using subscript notation\n",
    "if the edge already exists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.add_edge(1, 3)\n",
    "G[1][3]['color'] = \"blue\"\n",
    "G.edges[(1, 2)]['color'] = \"red\"\n",
    "print(\"Edges with attributes:\", dict(G.edges))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Fast examination of all (node, adjacency) pairs is achieved using\n",
    "`G.adjacency()`, or `G.adj.items()`.\n",
    "Note that for undirected graphs, adjacency iteration sees each edge twice."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "FG = nx.Graph()\n",
    "FG.add_weighted_edges_from([(1, 2, 0.125), (1, 3, 0.75), (2, 4, 1.2), (3, 4, 0.375)])\n",
    "for n, nbrs in FG.adj.items():\n",
    "    for nbr, eattr in nbrs.items():\n",
    "        wt = eattr['weight']\n",
    "        if wt < 0.5: print('(%d, %d, %.3f)' % (n, nbr, wt))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Convenient access to all edges is achieved with the edges property."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for (u, v, wt) in FG.edges.data('weight'):\n",
    "    if wt < 0.5: print('(%d, %d, %.3f)' % (u, v, wt))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Adding attributes\n",
    "\n",
    "Attributes such as weights, labels, colors, or whatever Python object you like,\n",
    "can be attached to graphs, nodes, or edges.\n",
    "\n",
    "Each edge can hold key/value attribute pairs in an associated\n",
    "attribute dictionary (the keys must be hashable).  By default these are empty,\n",
    "but attributes can be added or changed using `add_edge`or by direct\n",
    "manipulation of the attribute dictionary named\n",
    "`G.edges` for a graph `G`.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Edge Attributes\n",
    "\n",
    "Add/change edge attributes using `add_edge()`, `add_edges_from()`,\n",
    "or subscript notation."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G.add_edge(1, 2, weight=4.7 )\n",
    "G.add_edges_from([(3, 4), (4, 5)], color='red')\n",
    "G.add_edges_from([(1, 2, {'color': 'blue'}), (2, 3, {'weight': 8})])\n",
    "G[1][2]['weight'] = 4.7\n",
    "G.edges[(3, 4)]['weight'] = 4.2\n",
    "print(\"All edges with their attributes:\", dict(G.edges))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The special attribute `weight` should be numeric as it is used by\n",
    "algorithms requiring weighted edges.\n",
    "\n",
    "# Directed graphs\n",
    "\n",
    "The `DiGraph` class provides additional properties specific to\n",
    "directed edges, e.g.,\n",
    "`DiGraph.out_edges()`, `DiGraph.in_degree()`,\n",
    "`DiGraph.predecessors()`, `DiGraph.successors()` etc.\n",
    "To allow algorithms to work with both classes easily, the directed versions of\n",
    "`neighbors()` is equivalent to `successors()` while `degree` reports\n",
    "the sum of `in_degree` and `out_degree` even though that may feel\n",
    "inconsistent at times."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "DG = nx.DiGraph()\n",
    "DG.add_weighted_edges_from([(1, 2, 0.5), (3, 1, 0.75)])\n",
    "# argument weight specifies which edge attribute to be used \n",
    "# as weight in computing the degree\n",
    "print(\"Out degree of node 1:\",DG.out_degree(1, weight='weight')) \n",
    "print(\"Sum of in-degree and out-degree of node 1:\", DG.degree(1, weight='weight'))\n",
    "print(\"Successors of node 1:\", list(DG.successors(1)))\n",
    "print(\"All neighbors of node 1:\", list(DG.neighbors(1)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Some algorithms work only for directed graphs and others are not well\n",
    "defined for directed graphs. If you want to treat\n",
    "a directed graph as undirected for some measurement you should probably\n",
    "convert it using `Graph.to_undirected()` or with"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "H = nx.Graph(DG)  # convert G to undirected graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Multigraphs\n",
    "\n",
    "NetworkX provides classes for graphs which allow multiple edges\n",
    "between any pair of nodes.  The `MultiGraph` and\n",
    "`MultiDiGraph`\n",
    "classes allow you to add the same edge twice, possibly with different\n",
    "edge data.  This can be powerful for some applications, but many\n",
    "algorithms are not well defined on such graphs.\n",
    "\n",
    "In some cases results are well defined,\n",
    "e.g., `MultiGraph.degree()`.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "MG = nx.MultiGraph()\n",
    "MG.add_weighted_edges_from([(1, 2, 0.5), (1, 2, 0.75), (2, 3, 0.5)])\n",
    "print(\"All nodes with their degree:\", dict(MG.degree(weight='weight')))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Otherwise you should convert to a standard graph in a way that makes the measurement\n",
    "well defined."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Example: to compute the shortest path in a Multigraph, we construct a standard graph where \n",
    "# multiple links are replaced by a single link with the sum of all weights\n",
    "GG = nx.Graph()\n",
    "for n, nbrs in MG.adjacency():\n",
    "    for nbr, edict in nbrs.items():\n",
    "        minvalue = min([d['weight'] for d in edict.values()])\n",
    "        GG.add_edge(n, nbr, weight = minvalue)\n",
    "\n",
    "nx.shortest_path(GG, 1, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graph generators and graph operations\n",
    "\n",
    "In addition to constructing graphs node-by-node or edge-by-edge, they\n",
    "can also be generated by\n",
    "\n",
    "1. Applying classic graph operations, such as:\n",
    "\n",
    "   ```\n",
    "   subgraph(G, nbunch)      - induced subgraph view of G on nodes in nbunch\n",
    "   union(G1,G2)             - graph union\n",
    "   disjoint_union(G1,G2)    - graph union assuming all nodes are different\n",
    "   cartesian_product(G1,G2) - return Cartesian product graph\n",
    "   compose(G1,G2)           - combine graphs identifying nodes common to both\n",
    "   complement(G)            - graph complement\n",
    "   create_empty_copy(G)     - return an empty copy of the same graph class\n",
    "   to_undirected(G) - return an undirected representation of G\n",
    "   to_directed(G)   - return a directed representation of G\n",
    "   ```\n",
    "\n",
    "1. Using a call to one of the classic small graphs, e.g.,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "petersen = nx.petersen_graph()\n",
    "tutte = nx.tutte_graph()\n",
    "maze = nx.sedgewick_maze_graph()\n",
    "tet = nx.tetrahedral_graph()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Using a (constructive) generator for a classic graph, e.g.,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "K_5 = nx.complete_graph(5)\n",
    "K_3_5 = nx.complete_bipartite_graph(3, 5)\n",
    "barbell = nx.barbell_graph(10, 10)\n",
    "lollipop = nx.lollipop_graph(10, 20)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. Using a stochastic graph generator, e.g.,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "er = nx.erdos_renyi_graph(100, 0.15)\n",
    "ws = nx.watts_strogatz_graph(30, 3, 0.1)\n",
    "ba = nx.barabasi_albert_graph(100, 5)\n",
    "red = nx.random_lobster(100, 0.9, 0.9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "5. Reading a graph stored in a file using common graph formats,\n",
    "   such as edge lists, adjacency lists, GML and others."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.write_gml(red, \"path.to.file\")\n",
    "mygraph = nx.read_gml(\"path.to.file\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For details on graph formats see section Reading and writing graphs of Networkx documentation\n",
    "and for graph generator functions see section Graph generators."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Drawing graphs\n",
    "\n",
    "NetworkX is not primarily a graph drawing package but basic drawing with\n",
    "Matplotlib is included.  \n",
    "\n",
    "First import Matplotlib’s plot interface "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As an example, draw `G` using one of"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.petersen_graph()\n",
    "plt.subplot(121)\n",
    "nx.draw(G, with_labels=True, font_weight='bold')\n",
    "plt.subplot(122)\n",
    "nx.draw_shell(G, nlist=[range(5, 10), range(5)], with_labels=True, font_weight='bold')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can specify drawing options separately using an `options` dictionary.\n",
    "You can find additional options via `draw_networkx()` and\n",
    "layouts via `layout`. For example, the shell layout `draw_shell()` places different gropus of nodes in concentric circles (\"shells\")."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "options = {\n",
    "    'node_color': 'black',\n",
    "    'node_size': 100,\n",
    "    'width': 3,\n",
    "}\n",
    "plt.subplot(221)\n",
    "nx.draw_random(G, **options)\n",
    "plt.subplot(222)\n",
    "nx.draw_circular(G, **options)\n",
    "plt.subplot(223)\n",
    "nx.draw_spectral(G, **options)\n",
    "plt.subplot(224)\n",
    "nx.draw_shell(G, nlist=[range(5,10), range(5)], **options)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "G = nx.dodecahedral_graph()\n",
    "shells = [[2, 3, 4, 5, 6], [8, 1, 0, 19, 18, 17, 16, 15, 14, 7], [9, 10, 11, 12, 13]]\n",
    "nx.draw_shell(G, nlist=shells, **options)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To save drawings to a file, use, for example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "nx.draw(G)\n",
    "plt.savefig(\"path.png\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "writes to the file `path.png` in the local directory."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "See Drawing for additional details."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Algorithms\n",
    "NetworkX offers the implementation of a lot of network-related algorithms, which allow performing complex graph analysis in a simple way.\n",
    "As an overview we present the following functions contained in the modules `networkx.algorithms.components` and `networkx.algorithms.cycles`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Strong connectivity\n",
    "A directed graph is strongly connected if and only if every vertex in the graph is reachable from every other vertex.\n",
    "`networkx.algorithms.components.is_strongly_connected` test directed graph for strong connectivity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "DG = nx.DiGraph()\n",
    "DG.add_edges_from([(1, 2), (2, 3), (3, 1)])\n",
    "DG.add_edges_from([(4,5), (5,6), (6,7), (7,4)])\n",
    "DG.add_edge(4,1)\n",
    "nx.draw(DG)\n",
    "print(\"Is strongly connected:\", nx.algorithms.components.is_strongly_connected(DG))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "You can further analyze connectivity of a directed graph by computing the number of strongly connected components and the condensation graph, which is the graph with each of the strongly connected components contracted into a single node."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Number of connected components:\", nx.algorithms.components.number_strongly_connected_components(DG))\n",
    "CG = nx.algorithms.components.condensation(DG)\n",
    "nx.draw(CG, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "CG is the condensation graph of DG. The node labels are integers corresponding to the index of the component in the list of strongly connected components of DG. \n",
    "\n",
    "CG has a graph attribute named ‘mapping’ with a dictionary mapping the original nodes of DG to the nodes in CG to which they belong. Each node in CG also has a node attribute ‘members’ with the set of original nodes in DG that form the strongly connected component that the node in CG represents."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mapping = CG.graph['mapping']\n",
    "print(mapping)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dict(CG.nodes)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Note**: all previous functions related to strong connectivity can only be applied to directed graphs. Counterparts are provided for undirected graphs."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sinks\n",
    "In networkxX, an attracting component in a directed graph DG is a strongly connected component with the property that a random walker on the graph will never leave the component, once it enters the component. This is equivalent to requiring that the strongly connected component is a trapping set.\n",
    "Attracting components in DG consitute sinks of its condensation graph CG.\n",
    "\n",
    "`networkx.algorithms.components.number_attracting_components` returns the number of attracting components in DG.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Number of attracting components:\", nx.algorithms.components.number_attracting_components(DG))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`networkx.algorithms.components.attracting_components` generates the attracting components of DG.\n",
    "You can directly list nodes of DG belonging to each attracting component:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for c in nx.algorithms.components.attracting_components(DG):\n",
    "    print(c)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or you can obtain the subgraphs of DG induced on each attracting component and visualize them:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "components = list(DG.subgraph(c).copy() for c in nx.algorithms.components.attracting_components(DG))\n",
    "for c in components:\n",
    "    nx.draw(c, with_labels=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Cycles\n",
    "A simple cycle is a closed path where no node appears twice. Two elementary circuits are considered distinct if they are not cyclic permutations of each other.\n",
    "\n",
    "NetworkX provides cycle finding algorithms, that can be exploited to compute the periodicity of nodes and graphs.\n",
    "For example, `networkx.algorithms.cycles.simple_cycles` find simple cycles of a directed graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "cycles = list(nx.simple_cycles(DG))\n",
    "for cycle in cycles:\n",
    "    print(\"Cycle:\", cycle, \"Lenght:\", len(cycle))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Period of a node\n",
    "The period of a node is the Greatest Common Divisior of all cycles containing such node.\n",
    "\n",
    "#### Exercise\n",
    "Try to compute the period of each node in DG. \n",
    "\n",
    "**Hint**: exploit `networkx.algorithms.cycles.simple_cycles` and `math.gcd()`, which computes the GCD of two given numbers.\n",
    "Remember that you can compute the GCD of a list of numbers sequentially:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from math import gcd\n",
    "\n",
    "numbers = [9,6,21]\n",
    "GCD = numbers[0] # First initialize GCD with the first number of the list\n",
    "for n in numbers:\n",
    "    GCD = gcd(GCD,n)\n",
    "GCD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TO DO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "Consider the following directed graph."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "DG = nx.DiGraph()\n",
    "n_nodes = 10\n",
    "nx.add_cycle(DG, range(n_nodes))\n",
    "for n in range(n_nodes):\n",
    "    other = n+3\n",
    "    if other>=n_nodes:\n",
    "        other-=n_nodes\n",
    "    DG.add_edge(other,n)\n",
    "nx.draw_circular(DG, with_labels=True)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can check that DG is strongly connected and not aperiodic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Is strongly connected:\",nx.is_strongly_connected(DG))\n",
    "print(\"Is aperiodic:\",nx.is_aperiodic(DG))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In view of these facts, compute the period of the graph DG.\n",
    "\n",
    "**Hint:** Exploit the results from previous exercise and the fact that all nodes of a strongly connected graph have the same period."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TO DO"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Spanning subgraphs\n",
    "A spanning subgraph is a subgraph that contains all the vertices of the original graph. Of particular interest are spanning trees, i.e., spanning subgraphs that are trees.\n",
    "\n",
    "We can generate all the spanning subgraphs of a given graph as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# As an example, construct a graph\n",
    "G = nx.Graph()\n",
    "nx.add_cycle(G, range(4))\n",
    "G.add_edges_from([(0,2), (1,3)]) \n",
    "nx.draw_circular(G, with_labels=True)\n",
    "\n",
    "# Define a function for computing the power set of a given set\n",
    "from itertools import chain, combinations\n",
    "\n",
    "def powerset(iterable):\n",
    "    \"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)\"\n",
    "    s = list(iterable)\n",
    "    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))\n",
    "\n",
    "# Use 'powerset' to compute all subgraphs of G\n",
    "\n",
    "subgraphs = list()\n",
    "for edge_set in powerset(G.edges):\n",
    "    H = G.edge_subgraph(edge_set)\n",
    "    subgraphs.append(H)\n",
    "print(\"Number of subgraphs:\", len(subgraphs))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise \n",
    "Compute all spanning subtrees of G. \n",
    "\n",
    "**Hint:** use the previous code and exploit the following characterization of trees:\n",
    "> An undirected graph T is a tree if and only if T is connected and the number of edges of T is one less that the number of its nodes."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# TO DO"
   ]
  }
 ],
 "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.8.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}