0_quick-start.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4th European Conference On Social Networks\n",
    "## Workshop: Introduction to Python's Graph-Tool\n",
    "# 0. Quick-Start Using Graph-Tool\n",
    "**Source**: <a href='https://graph-tool.skewed.de/static/doc/quickstart.html'>graph-tool documentation</a>\n",
    "\n",
    "**Description**: This notebook is an almost exact copy of the section <a href='https://graph-tool.skewed.de/static/doc/quickstart.html#creating-and-manipulating-graphs'>Creating and manipulating graphs</a> from the graph-tool <a href='https://graph-tool.skewed.de/'>project homepage</a>.\n",
    "\n",
    "**License**: <a href='https://www.gnu.org/licenses/gpl-3.0.en.html'>GNU General Public License 3.0</a>\n",
    "\n",
    "***\n",
    "\n",
    "The <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#module-graph_tool'>graph_tool</a> module provides a <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph'>Graph</a> class and several algorithms that operate on it. The internals of this class, and of most algorithms, are written in C++ for performance, using the <a href='http://www.boost.org/'>Boost Graph Library</a>.\n",
    "\n",
    "The module must be of course imported before it can be used. The package is subdivided into several sub-modules. To import everything from all of them, one can do:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from graph_tool.all import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To run efficiently on a multi-core server, the numbger of threads to be used must be set manually:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "openmp_set_num_threads(2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 0.1. Creating and Manipulating Graphs\n",
    "An empty graph can be created by instantiating a <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph'>Graph</a> class:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g = Graph()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By default, newly created graphs are always directed. To construct undirected graphs, one must pass a value to the ``directed`` parameter:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ug = Graph(directed=False)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A graph can always be switched *on-the-fly* from directed to undirected (and vice versa), with the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.set_directed'>set_directed()</a> method. The \"directedness\" of the graph can be queried with the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.is_directed'>is_directed()</a> method,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ug = Graph()\n",
    "ug.set_directed(False)\n",
    "assert ug.is_directed() == False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A graph can also be created by providing another graph, in which case the entire graph (and its internal property maps, see <a href='https://graph-tool.skewed.de/static/doc/quickstart.html#sec-property-maps'>Property maps</a>) is copied:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g1 = Graph()\n",
    "# ... construct g1 ...\n",
    "g2 = Graph(g1) # g1 and g2 are copies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Above, ``g2`` is a \"deep\" copy of ``g1``, i.e. any modification of ``g2`` will not affect ``g1``.\n",
    "\n",
    "Once a graph is created, it can be populated with vertices and edges. A vertex can be added with the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.add_vertex'>add_vertex()</a> method, which returns an instance of a <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Vertex'>Vertex</a> class, also called a *vertex descriptor*. For instance, the following code creates two vertices, and returns vertex descriptors stored in the variables ``v1`` and ``v2``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v1 = g.add_vertex()\n",
    "v2 = g.add_vertex()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Edges can be added in an analogous manner, by calling the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.add_edge'>add_edge()</a> method, which returns an edge descriptor (an instance of the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Edge'>Edge</A> class):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "e = g.add_edge(v1, v2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The above code creates a directed edge from ``v1`` to ``v2``. We can visualize the graph we created so far with the <a href='https://graph-tool.skewed.de/static/doc/draw.html#graph_tool.draw.graph_draw'>graph_draw()</a> function."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph_draw(g, vertex_text=g.vertex_index, vertex_font_size=18, output_size=(200, 200)) # add output='two-nodes.png' to save the plot to a file"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With vertex and edge descriptors, one can examine and manipulate the graph in an arbitrary manner. For instance, in order to obtain the out-degree of a vertex, we can simply call the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Vertex.out_degree'>out_degree()</a> method:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(v1.out_degree())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Analogously, we could have used the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Vertex.in_degree'>in_degree()</a> method to query the in-degree."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-info\">\n",
    "<big><b>Note</b></big>\n",
    "\n",
    "For undirected graphs, the \"out-degree\" is synonym for degree, and in this case the in-degree of a vertex is always zero.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Edge descriptors have two useful methods, <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Edge.source'>source()</a> and <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Edge.target'>target()</a>, which return the source and target vertex of an edge, respectively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(e.source(), e.target())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.add_vertex'>add_vertex()</a> method also accepts an optional parameter which specifies the number of vertices to create. If this value is greater than 1, it returns an iterator on the added vertex descriptors:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vlist = g.add_vertex(10)\n",
    "print(len(list(vlist)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Each vertex in a graph has an unique index, which is *always* between $0$ and $N−1$, where $N$ is the number of vertices. This index can be obtained by using the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.vertex_index'>vertex_index</a> attribute of the graph (which is a *property map*, see <a href='https://graph-tool.skewed.de/static/doc/quickstart.html#sec-property-maps'>Property maps</a>), or by converting the vertex descriptor to an ``int``."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v = g.add_vertex()\n",
    "print(g.vertex_index[v])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(int(v))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Edges and vertices can also be removed at any time with the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.remove_vertex'>remove_vertex()</a> and <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.remove_edge'>remove_edge()</a> methods,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g.remove_edge(e) # e no longer exists"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g.remove_vertex(v2) # the second vertex is also gone"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-info\">\n",
    "<big><b>Note</b></big>\n",
    "\n",
    "Removing a vertex is typically an $O(N)$ operation. The vertices are internally stored in a STL vector, so removing an element somewhere in the middle of the list requires the shifting of the rest of the list. Thus, fast $O(1)$ removals are only possible either if one can guarantee that only vertices in the end of the list are removed (the ones last added to the graph), or if the relative vertex ordering is invalidated. The latter behavior can be achieved by passing the option ``fast == True``, to <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.remove_vertex'>remove_vertex()</a>, which causes the vertex being deleted to be ‘swapped’ with the last vertex (i.e. with the largest index), which will in turn inherit the index of the vertex being deleted.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-warning\">\n",
    "<big><b>Warning</b></big>\n",
    "\n",
    "Because of the above, removing a vertex with an index smaller than $N−1$ will **invalidate either the last** (``fast = True``) **or all** (``fast = False``) **descriptors pointing to vertices with higher index**.\n",
    "\n",
    "As a consequence, if more than one vertex is to be removed at a given time, they should **always** be removed in decreasing index order:\n",
    "\n",
    "``# 'del_list' is a list of vertex descriptors\n",
    "for v in reversed(sorted(del_list)):\n",
    "    g.remove_vertex(v)``\n",
    "\n",
    "Alternatively (and preferably), a list (or any iterable) may be passed directly as the ``vertex`` parameter of the < a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.remove_vertex'>remove_vertex()</a> function, and the above is performed internally (in C++).\n",
    "\n",
    "Note that property map values (see <a href='https://graph-tool.skewed.de/static/doc/quickstart.html#sec-property-maps'>Property maps</a>) are unaffected by the index changes due to vertex removal, as they are modified accordingly by the library.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-info\">\n",
    "<big><b>Note</b></big>\n",
    "\n",
    "Removing an edge is an $O(k_s+k_t)$ operation, where $k_s$ is the out-degree of the source vertex, and $k_t$ is the in-degree of the target vertex. This can be made faster by setting <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.set_fast_edge_removal'>set_fast_edge_removal()</a> to *True*, in which case it becomes $O(1)$, at the expense of additional data of size $O(E)$.\n",
    "\n",
    "No edge descriptors are ever invalidated after edge removal, with the exception of the edge being removed.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Since vertices are uniquely identifiable by their indexes, there is no need to keep the vertex descriptor lying around to access them at a later point. If we know its index, we can obtain the descriptor of a vertex with a given index using the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.vertex'>vertex()</a> method,"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "v = g.vertex(8)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "which takes an index, and returns a vertex descriptor. Edges cannot be directly obtained by its index, but if the source and target vertices of a given edge are known, it can be retrieved with the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.edge'>edge()</a> method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "g.add_edge(g.vertex(2), g.vertex(3))\n",
    "e = g.edge(2, 3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Another way to obtain edge or vertex descriptors is to *iterate* through them, as described in section <a href='https://graph-tool.skewed.de/static/doc/quickstart.html#sec-iteration'>Iterating over vertices and edges</a>. This is in fact the most useful way of obtaining vertex and edge descriptors.\n",
    "\n",
    "Like vertices, edges also have unique indexes, which are given by the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.edge_index'>edge_index</a> property:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "e = g.add_edge(g.vertex(0), g.vertex(1))\n",
    "print(g.edge_index[e])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Differently from vertices, edge indexes do not necessarily conform to any specific range. If no edges are ever removed, the indexes will be in the range $[0,E−1]$, where $E$ is the number of edges, and edges added earlier have lower indexes. However if an edge is removed, its index will be \"vacant\", and the remaining indexes will be left unmodified, and thus will not all lie in the range $[0,E−1]$. If a new edge is added, it will reuse old indexes, in an increasing order."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 0.1.1. Iterating Over Vertices and Edges\n",
    "Algorithms must often iterate through vertices, edges, out-edges of a vertex, etc. The <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph'>Graph</a> and <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Vertex'>Vertex</a> classes provide different types of iterators for doing so. The iterators always point to edge or vertex descriptors.\n",
    "#### 0.1.1.1. Iterating Over All Vertices or Edges\n",
    "In order to iterate through all the vertices or edges of a graph, the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.vertices'>vertices()</a> and <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.edges'>edges()</a> methods should be used:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for v in g.vertices():\n",
    "    print(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for e in g.edges():\n",
    "    print(e)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code above will print the vertices and edges of the graph in the order they are found.\n",
    "#### 0.1.1.2. Iterating Over the Neighborhood af a Vertex\n",
    "The out- and in-edges of a vertex, as well as the out- and in-neighbors can be iterated through with the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Vertex.out_edges'>out_edges()</a>, <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Vertex.in_edges'>in_edges()</a>, <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Vertex.out_neighbors'>out_neighbors()</a> and <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Vertex.in_neighbors'>in_neighbors()</a> methods, respectively."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for v in g.vertices():\n",
    "   for e in v.out_edges():\n",
    "       print(e)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for v in g.vertices():\n",
    "   for w in v.out_neighbors():\n",
    "       print(w)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "for v in g.vertices():\n",
    "   # the edge and neighbors order always match\n",
    "   for e, w in zip(v.out_edges(), v.out_neighbors()):\n",
    "       assert e.target() == w"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The code above will print the out-edges and out-neighbors of all vertices in the graph."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div class=\"alert alert-warning\">\n",
    "<big><b>Warning</b></big>\n",
    "\n",
    "You should never remove vertex or edge descriptors when iterating over them, since this invalidates the iterators. If you plan to remove vertices or edges during iteration, you must first store them somewhere (such as in a list) and remove them only after no iterator is being used. Removal during iteration will cause bad things to happen.\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 0.1.1.3. Fast Iteration Over Vertices and Edges\n",
    "While convenient, looping over the graph as described in the previous section is not the most efficient approach. This is because the loops are performed in pure Python, and hence it undermines the main feature of the library, which is the offloading of loops from Python to C++. Following the <a href='https://docs.scipy.org/doc/numpy/reference/index.html#module-numpy'>numpy</a> philosophy, <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#module-graph_tool'>graph_tool</a> also provides an array-based interface that avoids loops in Python. This is done with the <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.get_vertices'>get_vertices()</a>, <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.get_edges'>get_edges()</a>, <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.get_out_edges'>get_out_edges()</a>, <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.get_in_edges'>get_in_edges()</a>, <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.get_all_edges'>get_all_edges()</a>, <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.get_out_neighbors'>get_out_neighbors()</a>, <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.get_in_neighbors'>get_in_neighbors()</a>, <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.get_all_neighbors'>get_all_neighbors()</a>, <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.get_out_degrees'>get_out_degrees()</a>, <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.get_in_degrees'>get_in_degrees()</a> and <a href='https://graph-tool.skewed.de/static/doc/graph_tool.html#graph_tool.Graph.get_total_degrees'>get_total_degrees()</a> methods, which return <a href='https://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.html#numpy.ndarray'>numpy.ndarray</a></a> instances instead of iterators.\n",
    "\n",
    "For example, using this interface we can get the out-degree of each node via:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(g.get_out_degrees(g.get_vertices()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "or the sum of the product of the in and out-degrees of the endpoints of each edge with:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "edges = g.get_edges()\n",
    "in_degs = g.get_in_degrees(g.get_vertices())\n",
    "out_degs = g.get_out_degrees(g.get_vertices())\n",
    "print((out_degs[edges[:,0]] * in_degs[edges[:,1]]).sum())"
   ]
  }
 ],
 "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.6.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}