DataStructures.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Appendix C. COMPUTATIONAL METHODS\n",
    "\n",
    "# C.1. Data Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A fundamental concept in computer science is the *graph* (aka, network).\n",
    "This is a structure that defines a set of objects and connectivity\n",
    "relations between pairs of objects. The objects are known as *vertices*\n",
    "(or sometimes *nodes*), and the relations are known as *edges* (or\n",
    "sometimes *arcs*).\n",
    "\n",
    "## Graphs\n",
    "\n",
    "A graph $G = (V,E)$ consists of a set of vertices $V$ and a set of edges\n",
    "$E$, in which each edge is a pair $(u,v)$ with $u\\in V$ and $v \\in V$.\n",
    "For every such pair $(u,v)$, $v$ is called a *neighbor* of $u$. We can\n",
    "also define the *neighbors* of a vertex as\n",
    "$N(u) = \\{ v \\in V \\quad |\\quad (u,v)\\in E\\}$.\n",
    "\n",
    "Graphs can either be *directed* in which the existence of an edge\n",
    "$(u,v)$ indicates that a path can move from $u$ to $v$, or *undirected*\n",
    "in which paths can run either direction along an edge. For the\n",
    "undirected case, we shall simply require that if $(u,v) \\in E$ then\n",
    "$(v,u) \\in E$ as well.\n",
    "\n",
    "For each edge $(u,v)$ we say that $u$ is the *tail* of the edge and $v$\n",
    "is its *head*. A sequence of connected edges\n",
    "$(v_0,v_1),(v_1,v_2),\\ldots,(v_{k-1},v_k)$ with each\n",
    "$(v_{i-1},v_i)\\in E$ is known as a *path* in the graph. If a path exists\n",
    "between two vertices in an undirected graph, we say the vertices are\n",
    "*connected*. A path that starts and ends at the same vertex ($v_k=v_0$)\n",
    "is called a *cycle*.\n",
    "\n",
    "## Trees\n",
    "\n",
    "***************\n",
    "![fig:Tree](figures/appendix/tree.svg)\n",
    "\n",
    "<div class=\"figcaption\"><a name=\"fig:Tree\">Figure 1</a>. A tree is a graph with no cycles. (a) A directed tree is drawn with its root at the top, with a node's children drawn on the layer below.\n",
    "Leaf nodes are shaded. (b) A vertex's ancestors (shaded) are the\n",
    "vertices on the path from the root. (c) A vertex's descendants (shaded)\n",
    "forms a subtree of the original tree where $v$ is the\n",
    "root.</div>\n",
    "\n",
    "***************\n",
    "\n",
    "A *tree* is a special kind of undirected graph in which there are no\n",
    "cycles and in which all vertices are connected. A tree can be thought of\n",
    "a directed graph in which each vertex $v$ is the head of at most one\n",
    "edge in $E$. In fact, all vertices are the head of exactly one edge\n",
    "except one special vertex, called the *root* of the tree\n",
    "([Fig. 1](#fig:Tree).a).\n",
    "\n",
    "In a directed tree, we define two concepts for each vertex $v$. The\n",
    "*parent* of $v$, $Parent(v)$ is defined as the unique vertex $u$ for\n",
    "which $(u,v)\\in E$, or *nil* if $v$ is the root. The *children* of $v$\n",
    "are defined as the heads of edges for which $v$ is a tail:\n",
    "$$Children(v) = \\{ w \\in V \\quad |\\quad (v,w) \\in E\\}.$$ If a vertex has\n",
    "no children, then it is called a *leaf*. Trees are usually drawn in\n",
    "downward fashion starting from the root, with all children of a node on\n",
    "the next level down.\n",
    "\n",
    "With this definition, we can also define the *ancestors* of a vertex $v$\n",
    "which is the set of nodes along the path from the root to $v$, inclusive\n",
    "([Fig. 1](#fig:Tree).b). This set includes $v$, $v$'s parent, the\n",
    "parent of $v$'s parent, and so on, until the root is reached. Similarly,\n",
    "the *descendants* of $v$ are the set of nodes $w$ for which either $v=w$\n",
    "or there exists a directed path from $v$ to $w$. In other words, $v$'s\n",
    "descendants are $v$, $v$'s children, $v$'s children's children, and so\n",
    "on. The tree consisting of $v$'s descendants and edges between them is\n",
    "also known as the *subtree* at $v$. In the subtree, $v$ is the root\n",
    "([Fig. 1](#fig:Tree).c).\n",
    "\n",
    "## Representations\n",
    "\n",
    "Representations of trees are simpler than general graphs, so we will\n",
    "describe them first. In most object-oriented programming languages, a\n",
    "tree can be represented as a simple hierarchical data structure. Define\n",
    "a structure `TreeNode` representing a vertex and containing its entire\n",
    "subtree. It has the following members:\n",
    "\n",
    "- `data`: application-specific data to be stored with the vertex.\n",
    "- `children`: array or list of `TreeNode`s.\n",
    "- `parent`: optional, a `TreeNode` reference.\n",
    "\n",
    "Then the entire tree is stored as the root `TreeNode`. With this\n",
    "structure it is possible to search downward from the root for any\n",
    "desired node. If the parent member is present, then it is also possible\n",
    "to search upward from any node.\n",
    "\n",
    "Graph data structures are a bit more complex. The most straightforward\n",
    "representation, which stores $V$ and $E$ as lists of vertices and pairs\n",
    "of vertices, respectively, is not computationally convenient for most\n",
    "purposes. For example, to determine a vertex's neighbors $N(v)$, one\n",
    "would need to loop through *all* of the edges in $E$ to find if $v$ is\n",
    "one of the edge's endpoints. This is an $O(|E|)$ operation, which is\n",
    "$O(|V|^2)$ in the worst case! Since this is a fundamental operation to\n",
    "most interesting operations on graphs (determining connectedness, graph\n",
    "search, etc) the *adjacency list* representation is often preferred.\n",
    "\n",
    "*****************************\n",
    "\n",
    "![fig:abcdGraph](figures/appendix/abcd_graph.svg) \n",
    "\n",
    "<div class=\"figcaption\"><a name=\"fig:AdjacencyList\">Figure 2</a>. A simple graph</div>\n",
    "\n",
    "***************************\n",
    "\n",
    "The adjacency list representation stores for each vertex $v$ the list of\n",
    "its neighbors $N(v)$. Specifically, if we were to number the\n",
    "$n\\equiv |V|$ vertices as $0,1,\\ldots,n-1$ (assuming 0-based indexing in\n",
    "the programming language), the adjacency list representation stores a\n",
    "nested list `edges`$[0], \\ldots,$ `edges`$[n-1]$ where each `edges`$[i]$\n",
    "is a list of vertex indices in $\\{ 0,\\ldots,n-1 \\}$.\n",
    "The code below illustrates this for a simple graph shown in [Fig. 2](#fig:AdjacencyList).\n",
    "\n",
    "```python\n",
    "data = ['A','B','C','D'] #vertex names\n",
    "edges = [[1,2],#indices of neighbors of 'A'\n",
    "         [3],  #indices of neighbors of 'B'\n",
    "         [3],  #indices of neighbors of 'C'\n",
    "         []]   #indices of neighbors of 'D'\n",
    "``` \n",
    "\n",
    "Any application-specific data associated with vertices is stored as an\n",
    "auxiliary array `data`$[0], \\ldots,$ `data`$[n-1]$. The main\n",
    "disadvantage of this representation is that identifying whether an edge\n",
    "exists requires iterating through the adjacency list of the edge's tail.\n",
    "\n",
    "The alternative *adjacency matrix* representation is useful for a number\n",
    "of operations, such as determining whether an edge exists in the graph\n",
    "and various graph-theoretic operations. This represents the edges of a\n",
    "graph as an $n \\times n$ array such that `edges`$[i,j]$ is 1 if there is\n",
    "an edge in $E$ from the vertex indexed by $i$ to the vertex indexed by\n",
    "$j$, and 0 otherwise. Again we are assuming 0-based indexing.\n",
    "the matrix\n",
    "$$\\begin{bmatrix}\n",
    "0 & 1 & 1 & 0 \\\\\n",
    "0 & 0 & 0 & 1 \\\\\n",
    "0 & 0 & 0 & 1 \\\\\n",
    "0 & 0 & 0 & 0 \n",
    "\\end{bmatrix}$$\n",
    "gives the adjacency list for the graph shown in [Fig. 2](#fig:AdjacencyList). The main\n",
    "disadvantages of this representation are that 1) it takes $n^2$ space to\n",
    "store, and 2) determining neighbors of a vertex requires checking $n$\n",
    "entries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.7.5"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "autoclose": false,
   "autocomplete": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 1,
   "hotkeys": {
    "equation": "Ctrl-E",
    "itemize": "Ctrl-I"
   },
   "labels_anchors": false,
   "latex_user_defs": true,
   "report_style_numbering": false,
   "user_envs_cfg": false
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "303.833px"
   },
   "toc_section_display": true,
   "toc_window_display": true
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}