polymake-common 3.2r2-3 / usr / share / polymake / demo / apps_graph.ipynb

{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dealing with Graphs\n",
    "\n",
    "Graphs are ubiquitous in geometric combinatorics.  Hence they occur a lot throughout the `polymake` system, explicitly and implicitly.  It is important to understand that the user encounters graphs on two distinct layers in the object hierarchy.  It is the purpose of this tutorial to explore the various features.  For the sake of simplicity here we restrict our attention to undirected graphs.\n",
    "\n",
    "## Graphs of Polytopes\n",
    "\n",
    "Coming from polytopes the first situation in which a graph occurs is the vertex-edge graph of such a polytope.\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20\n",
       "\n"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "$p=rand_sphere(3,20);\n",
    "print $p->GRAPH->N_NODES;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Here `GRAPH` is a property of the polytope object `$p` which happens to be of the object type `Graph`.  The following is a fragment of the file `apps/polytopes/rules/polytope_properties.rules`.  This is where all the standard properties of polytopes are declared.\n",
    "\n",
    "    \n",
    "    property GRAPH : objects::Graph {\n",
    "    \n",
    "       # Difference of the vertices for each edge (only defined up to signs).\n",
    "       property EDGE_DIRECTIONS : EdgeMap<Undirected, Vector<Scalar>>;\n",
    "    }\n",
    "\n",
    "\n",
    "In fact, this `objects::Graph` is the main object class of another application, called `graph`.  This application `graph` is defined in `apps/graph` and its subdirectories.  Although the application `graph` has much fewer features than the application `polytope` the overall mechanism of interaction is the same.  In particular, there are properties, rules, clients, and such.  Non-trivial features include the algorithm for computing the diameter and the visualization of graphs based on a pseudo-physical model (described in [this paper](http://front.math.ucdavis.edu/0711.2397)).\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4\n"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $p->DIAMETER;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "$p->VISUAL;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "As polytopes and all other objects in `polymake`'s object hierarchy the graphs from the application `graph` are immutable objects.  It is not possible to add a node or to delete an edge.  It is instructive to look at the beginning of the file `apps/graph/graph_properties.rules` which reads like this.\n",
    "\n",
    "    \n",
    "    declare object Graph<Dir=Undirected> {\n",
    "    \n",
    "    # combinatorial description of the Graph in the form of adjacency matrix\n",
    "    property ADJACENCY : props::Graph<Dir>;\n",
    "    \n",
    "    ...\n",
    "\n",
    "\n",
    "The key property of a graph object is its `ADJACENCY`.  For each node all neighbors are listed.  Here we want to focus on the type `props::Graph` of this property.  This refers to C++ class from the Polymake Template Library named `Graph`, and this is where the data structure and most algorithms reside.  It is possible to directly manipulate objects of this type, and these are *not* immutable, they can be changed.  The following shows how one can create a 5-cycle.  Calling the method `edge` creates an edge if it did not exist before.  The output is the ordered list of neighbors per node.\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1 4}               \n",
       "{0 2}               \n",
       "{1 3}               \n",
       "{2 4}               \n",
       "{0 3}               \n",
       "\n"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "$g=new props::Graph(5);                      \n",
    "for (my $i=0; $i<5; ++$i) { $g->edge($i,($i+1)%5) };\n",
    "print $g;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "If a graph has many nodes it is convenient to know which line of the output refers to which node.  If an array of labels is given this could also be used instead of the numbers which are the default.\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0:1 4                             \n",
       "1:0 2                             \n",
       "2:1 3                             \n",
       "3:2 4                             \n",
       "4:0 3                             \n",
       "\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print rows_labeled($g);"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "There are other ways to change such a graph. Contracting the edge *(x,y)* where *x* is smaller than *y* implies that the node *y* is destroyed. \n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "$g->delete_edge(0,1);\n",
    "$g->contract_edge(2,3);\n",
    "$g->squeeze();"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "However, most of our graph algorithms expect a graph with consecutively numbered nodes.  The function `squeeze` takes care of a proper renumbering, but this takes linear time in the number of nodes.\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0:4\n",
       "1:2\n",
       "2:1 4\n",
       "3:0 2\n",
       "\n"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print rows_labeled($g);"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "How do I iterate over the adjacent nodes to a given node?\n",
    "\n",
    "    \n",
    "    foreach (@{$g->adjacent_nodes(0)}) {\n",
    "       print \"node number $_ is adjacent to node number 0\\n\";\n",
    "    }\n",
    "\n",
    "\n",
    "It is also legal to copy all adjacent nodes to an array as in:\n",
    "\n",
    "    \n",
    "    @x = @{$g->adjacent_nodes(0)};\n",
    "\n",
    "\n",
    "Subsequently, the individial neighbors can be accessed at random, for instance, as `$x[1]`.  However, for technical reasons too difficult to explain here, it is *not* legal to write `$g->adjacent_nodes(0)->[1]`!\n",
    "Usually it is preferred to avoid copying; so use constructions like `foreach` and `map` if possible.\n",
    "\n",
    "\n",
    "\n",
    "## Defining a Graph from Scratch\n",
    "\n",
    "You can also work with graphs independent of their connection to polytopes. We will switch to `application \"graph\"` for the following commands, but this is not strictly necessary. We want to define a new object of type `Graph` in `polymake`.\n",
    "\n",
    "The key property of a graph is its adjacency matrix, which is stored in the property `ADJACENCY`. It lists the neighbors of each node. We use again the above example of a 5-cycle C<sub>5</sub> with consecutively numbered nodes. Then one can define C<sub>5</sub> by\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "application \"graph\";"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "$g=new objects::Graph(ADJACENCY=>[[1,4],[0,2],[1,3],[2,4],[0,3]]);"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Note the `objects::` in front of the key word `Graph`, which is not needed when you define any of the other `polymake` objects, like `Polytope<Rational> or `Matroid`.  This is necessary here to distinguish the `polymake` object `Graph` from the `C++` class `Graph` that we have used above, and that is accessed with the additional qualification `props::`.\n",
    "\n",
    "The list of edges of the graph is induced by the adjacency matrix (please note that in a undirected graph each edge appears twice). You can get an explicit list of the edges with the user function `EDGES`.\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{0 1}\n",
       "{1 2}\n",
       "{2 3}\n",
       "{0 4}\n",
       "{3 4}\n",
       "\n"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $g->EDGES;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note however, that this list is not stored in the object, as it is just a different view on the adjacency matrix. \n",
    "\n",
    "Most often when you define a graph you would not write it down as a list of adjacencies, but as a list of edges. For convenience, `polymake` provides a way to create a graph from a list of edges. The same 5-cycle as above could also be defined via\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    " $g=graph_from_edges([[0,1],[1,2],[2,3],[0,4],[3,4]]);"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "The order of the edges, and the order of the nodes for each edge in a undirected case, is not important. We can check the adjacency matrix,\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{1 4}\n",
       "{0 2}\n",
       "{1 3}\n",
       "{2 4}\n",
       "{0 3}\n",
       "\n"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $g->ADJACENCY;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "and continue to work with the graph by e.g. checking its `DIAMETER`, `BIPARTITE`-ness or other properties:\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2\n"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $g->DIAMETER;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0\n"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $g->BIPARTITE;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{{0 1} {0 4} {1 2} {2 3} {3 4}}\n",
       "\n"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print $g->MAX_CLIQUES;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "## Directed Graphs\n",
    "\n",
    "By specifying the template parameter `Directed` a graph is born as a directed graph.  Properties which make sense for directed graphs work as expected.  A directed graph may have two arcs between any two nodes with opposite orientations.\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4\n",
       "\n"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "$g=new objects::Graph<Directed>(ADJACENCY=>[[1],[2],[3],[2,4],[0]]);\n",
    "print $g->DIAMETER;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Here is an example of an undirected graph property which does not make sense for directed graphs.\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#print $g->MAX_CLIQUES;"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    \n",
    "    polymake:  ERROR: Object Graph<Directed> does not have a property or method MAX_CLIQUES\n",
    "\n",
    "\n",
    "Graphs with multiple edges/arcs are currently not supported.\n",
    " \n",
    "\n",
    "## Visualizing Graphs\n",
    "\n",
    "Like other \"big\" `polymake` objects the `Graph` class has a member (function) `VISUAL` which returns an abstract visualization object.  Depending on the configuration it typically uses `JReality` or `JavaView`.  Particularly interesting for graph drawing is the visualization via `Graphviz`.\n",
    "\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "graphviz($g->VISUAL);"
   ]
  },
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "\n",
    "Note that the latter starts a postscript viewer with the `Graphviz` output.  Make sure that the custom variable `$Postscript::viewer` is set to something reasonable (like, e.g., `/usr/bin/evince`).\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "polymake",
   "language": "polymake",
   "name": "polymake"
  },
  "language_info": {
   "codemirror_mode": "perl",
   "file_extension": ".pm",
   "mimetype": "text/x-polymake",
   "name": "polymake"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}