GraphsImplementations.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graph Implementation\n",
    "https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/GraphImpl.html\n",
    "\n",
    "### Table of Contents\n",
    "- **[Graph Representations](#represent)**<br>\n",
    "- **[Graph ADT using Adjacency Matrix](#matrix)**<br>\n",
    "- **[Graph ADT using Adjacency List](#list)**<br>\n",
    "- **[Graph Traversals](#traversals)**<br>\n",
    "    - **[Depth First Search (DFS)](#dfs)**<br>\n",
    "    - **[Breadth First Search (BFS)](#bfs)**<br>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph Representations\n",
    "- two traditional approaches to representing graphs:\n",
    "    1. adjacency matrix\n",
    "    - adjacency list\n",
    "- this notebook demonstrates both approaches\n",
    "\n",
    "<img src=\"./resources/directedGraphRepresentation.png\">\n",
    "<center> Representing Directed Graph using Adjacency Matrix and List</center>\n",
    "\n",
    "<img src=\"./resources/undirectedGraphRep.png\">\n",
    "<center> Representing Undirected Graph using Adjacency Matrix and List</center>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph ADT using Adjacency Matrix\n",
    "\n",
    "- graph implementation presented here do not address the issue of how the graph is actually created\n",
    "- graph can be built e.g., by reading the graph description from a file\n",
    "- the graph can be built-up by using the addEdge method provided by the ADT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <algorithm>\n",
    "#include <vector>\n",
    "#include <unordered_set>\n",
    "#include <list>\n",
    "\n",
    "using namespace std;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "code_folding": []
   },
   "outputs": [],
   "source": [
    "class GraphM {\n",
    "    private:\n",
    "        vector<vector<int> > matrix;\n",
    "        size_t numEdge;\n",
    "        unordered_set<int> nodes;\n",
    "    \n",
    "    public:\n",
    "        GraphM(size_t n) {\n",
    "            this->numEdge = 0;\n",
    "            // initializes matrix with 0s\n",
    "            this->matrix.assign(n, vector<int>(n, 0));\n",
    "            /*\n",
    "            for (int i=0; i<n; i++) {\n",
    "                vector<int> v(n, 0); // create an array of n elements initialized with 0s\n",
    "                matrix.push_back(v);\n",
    "            }\n",
    "            */\n",
    "        }\n",
    "        // returns the number of vertices/nodes\n",
    "        size_t nodeCount() {\n",
    "            return nodes.size();\n",
    "        }\n",
    "    \n",
    "        // returns the number of edges\n",
    "        size_t edgeCount() {\n",
    "            return numEdge;\n",
    "        }\n",
    "        \n",
    "        // adds a new edge from node u to node v, with weight w\n",
    "        void addEdge(int u, int v, int w=1) {\n",
    "            if (w == 0) return;\n",
    "            matrix[u][v] = w;\n",
    "            ++numEdge;\n",
    "            nodes.insert(u);\n",
    "            nodes.insert(v);\n",
    "        }\n",
    "    \n",
    "        // get the weight value for an edge, u->v\n",
    "        int weight(int u, int v) {\n",
    "            return matrix[u][v];\n",
    "        }\n",
    "    \n",
    "        // removes an edge from the graph\n",
    "        void removeEdge(int u, int v) {\n",
    "            matrix[u][v] = 0;\n",
    "            --numEdge;\n",
    "        }\n",
    "    \n",
    "        // checks if there's an edge between u and v\n",
    "        bool hasEdge(int u, int v) {\n",
    "            return matrix[u][v] != 0;\n",
    "        }\n",
    "        \n",
    "        // returns vector containing neighbors of u\n",
    "        vector<int> neighbors(int u) {\n",
    "            vector<int> neighs;\n",
    "            for(int v = 0; v<matrix[u].size(); v++) {\n",
    "                if (matrix[u][v] != 0) neighs.push_back(v);\n",
    "            }\n",
    "            return neighs;\n",
    "        }\n",
    "    \n",
    "        // prints graph\n",
    "        void print() {\n",
    "            for(auto u: matrix) {\n",
    "                for (auto v: u)\n",
    "                    cout << v << \" \";\n",
    "                cout << endl;\n",
    "            }\n",
    "        }\n",
    "        \n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's test GraphM ADT using the following directed graph\n",
    "<img src=\"resources/DirectedGraphImp.png\" />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "// test GraphM with some data\n",
    "GraphM graph(5); // graph with 5 nodes; see directed graph above"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph.addEdge(0, 1, 1); // let's say all weights are 1\n",
    "graph.addEdge(0, 4, 1);\n",
    "graph.addEdge(1, 3); // default weight is 1\n",
    "graph.addEdge(2, 4);\n",
    "graph.addEdge(3, 2);\n",
    "graph.addEdge(4, 1);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# of nodes = 5\n",
      "# of edges = 6\n"
     ]
    }
   ],
   "source": [
    "cout << \"# of nodes = \" << graph.nodeCount() << endl;\n",
    "cout << \"# of edges = \" << graph.edgeCount() << endl;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 1 0 0 1 \n",
      "0 0 0 1 0 \n",
      "0 0 0 0 1 \n",
      "0 0 1 0 0 \n",
      "0 1 0 0 0 \n"
     ]
    }
   ],
   "source": [
    "graph.print();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# of nodes = 5\n",
      "# of edges = 5\n",
      "0 1 0 0 0 \n",
      "0 0 0 1 0 \n",
      "0 0 0 0 1 \n",
      "0 0 1 0 0 \n",
      "0 1 0 0 0 \n"
     ]
    }
   ],
   "source": [
    "graph.removeEdge(0, 4);\n",
    "cout << \"# of nodes = \" << graph.nodeCount() << endl;\n",
    "cout << \"# of edges = \" << graph.edgeCount() << endl;\n",
    "graph.print();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "neighbors of 0 are: 1, "
     ]
    }
   ],
   "source": [
    "cout << \"neighbors of 0 are: \";\n",
    "for (auto n: graph.neighbors(0))\n",
    "    cout << n << \", \";"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " has edge 0->4? false\n"
     ]
    }
   ],
   "source": [
    "cout << boolalpha << \" has edge 0->4? \" << graph.hasEdge(0, 4) << endl;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph ADT using Adjacency List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <algorithm>\n",
    "#include <vector>\n",
    "#include <unordered_set>\n",
    "#include <list>\n",
    "\n",
    "using namespace std;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "code_folding": []
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "\u001b[1minput_line_24:1:7: \u001b[0m\u001b[0;1;31merror: \u001b[0m\u001b[1mredefinition of 'GraphL'\u001b[0m\n",
      "class GraphL {\n",
      "\u001b[0;1;32m      ^\n",
      "\u001b[0m\u001b[1minput_line_9:1:7: \u001b[0m\u001b[0;1;30mnote: \u001b[0mprevious definition is here\u001b[0m\n",
      "class GraphL {\n",
      "\u001b[0;1;32m      ^\n",
      "\u001b[0m"
     ]
    },
    {
     "ename": "Interpreter Error",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "Interpreter Error: "
     ]
    }
   ],
   "source": [
    "class GraphL {\n",
    "    private:\n",
    "        vector<list<pair<int, int> > > graph; // list stores pair of neighbor id and weight\n",
    "        // can also use unorderd_map<int, vector<int> >\n",
    "        size_t numEdge;\n",
    "        unordered_set<int> nodes;\n",
    "    \n",
    "    public:\n",
    "        GraphL(size_t n) {\n",
    "            this->numEdge = 0;\n",
    "            // initialize vector with empty list\n",
    "            for (int i=0; i<n; i++) {\n",
    "                list<pair<int, int> > v; // create an empty list of <int, int> pair type\n",
    "                graph.push_back(v);\n",
    "            }\n",
    "        }\n",
    "        // returns number of vertices/nodes\n",
    "        size_t nodeCount() {\n",
    "            return nodes.size();\n",
    "        }\n",
    "    \n",
    "        // returns the current number of edges\n",
    "        size_t edgeCount() {\n",
    "            return numEdge;\n",
    "        }\n",
    "        \n",
    "        // adds a new edge from node u to node v, with weight w\n",
    "        void addEdge(int u, int v, int w=1) {\n",
    "            if (w == 0) return;\n",
    "            graph[u].push_back({v, w});\n",
    "            ++numEdge;\n",
    "            nodes.insert(u);\n",
    "            nodes.insert(v);\n",
    "        }\n",
    "    \n",
    "        // returns the weight of an edge, u->v\n",
    "        int weight(int u, int v) {\n",
    "            for(auto p: graph[u]) {\n",
    "                if (p.first == v)\n",
    "                    return p.second;\n",
    "            }\n",
    "            return 0;\n",
    "        }\n",
    "    \n",
    "        // removes an edge from the graph\n",
    "        void removeEdge(int u, int v) {\n",
    "            // p.first is neibhbor id and p.second is weight\n",
    "            for(auto p: graph[u]) {\n",
    "                if (p.first == v) {\n",
    "                    graph[u].remove(p);\n",
    "                    --numEdge;\n",
    "                    break;\n",
    "                }\n",
    "            }\n",
    "        }\n",
    "    \n",
    "        // checks if there's an edge between u and v\n",
    "        bool hasEdge(int u, int v) {\n",
    "            for(auto p: graph[u]) {\n",
    "                if (p.first == v)\n",
    "                    return true;\n",
    "            }\n",
    "            return false;\n",
    "        }\n",
    "        \n",
    "        // returns vector containing neighbors of u\n",
    "        vector<int> neighbors(int u) {\n",
    "            vector<int> neighs;\n",
    "            for(auto p: graph[u]) {\n",
    "                neighs.push_back(p.first);\n",
    "            }\n",
    "            return neighs;\n",
    "        }\n",
    "    \n",
    "        // print graph\n",
    "        void print() {\n",
    "            for(int i=0; i<graph.size(); i++) {\n",
    "                cout << i << \" -> \";\n",
    "                for (auto p: graph[i])\n",
    "                    cout << p.first << \" \";\n",
    "                cout << endl;\n",
    "            }\n",
    "        }\n",
    "};"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's test GraphL ADT using the following undirected graph\n",
    "\n",
    "<img src=\"resources/undirectedGraphImp.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "// represent undirected graph shown in above diagram\n",
    "GraphL graph1(5);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph1.addEdge(0, 1);\n",
    "graph1.addEdge(0, 4);\n",
    "graph1.addEdge(1, 0);\n",
    "graph1.addEdge(1, 4);\n",
    "graph1.addEdge(1, 3);\n",
    "graph1.addEdge(2, 4);\n",
    "graph1.addEdge(2, 3);\n",
    "graph1.addEdge(3, 1);\n",
    "graph1.addEdge(3, 2);\n",
    "graph1.addEdge(4, 0);\n",
    "graph1.addEdge(4, 1);\n",
    "graph1.addEdge(4, 2);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0 -> 1 4 \n",
      "1 -> 0 4 3 \n",
      "2 -> 4 3 \n",
      "3 -> 1 2 \n",
      "4 -> 0 1 2 \n"
     ]
    }
   ],
   "source": [
    "graph1.print();"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "neighbors of 4 are: 0 1 2 "
     ]
    }
   ],
   "source": [
    "cout << \"neighbors of 4 are: \";\n",
    "for(auto n : graph1.neighbors(4))\n",
    "    cout << n << \" \";"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "is 1 connected to 3? true"
     ]
    }
   ],
   "source": [
    "cout << boolalpha << \"is 1 connected to 3? \" << graph1.hasEdge(1, 3);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " weight of edge between 1 and 3 = 1"
     ]
    }
   ],
   "source": [
    "cout << \" weight of edge between 1 and 3 = \" << graph1.weight(1, 3);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "is 1 connected to 3? false"
     ]
    }
   ],
   "source": [
    "// remove edge 1->3\n",
    "graph1.removeEdge(1, 3);\n",
    "cout << boolalpha << \"is 1 connected to 3? \" << graph1.hasEdge(1, 3);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph Traversals\n",
    "https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/GraphTraversal.html\n",
    "- many graph applications need to visit the vertices of a graph in some specific order\n",
    "- graph traversal algorithms begin with a start vertex and attempt to visit the remaining vertices from there at least (at most) once\n",
    "- must deal with two main troublesome cases:\n",
    "    1. all the vertices may not be reachable from given start vertex\n",
    "        - occurs when graph is not fully connected\n",
    "    2. graph might contain cycles (avoid infinite loop)\n",
    "- a simple solution to avoid these cases is using a VISITED flag for each vertex that is visited"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Depth-First Search (DFS)\n",
    "- whenever a vertex, $v$ is visited, DFS will recursively visit all of $v$'s unvisited neighbors\n",
    "- use stack to push all the neighbors (leading out of $v$) (iterative version)\n",
    "    - effectively follow one branch through the graph to its conclusion\n",
    "    - back up and follow another branch, and so on...\n",
    "- can be applied to both directed and undirected graphs\n",
    "\n",
    "### visualize DFS: https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/GraphTraversal.html#depth-first-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DFS Implementation (iterative version using stack)\n",
    "- implemented as a function\n",
    "- can also be a method in Graph ADT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <stack>\n",
    "#include <vector>\n",
    "#include <algorithm>\n",
    "\n",
    "using namespace std;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "// iterative version using stack\n",
    "template<class T>\n",
    "void DFS(T &G, int start) {\n",
    "    vector<bool> visited(G.nodeCount(), false); // boolean vector to keep track of visited nodes\n",
    "    stack<int> vertices;\n",
    "    vertices.push(start);\n",
    "    while(!vertices.empty()) {\n",
    "        int u = vertices.top(); // get the top of the stack\n",
    "        // pop the stack\n",
    "        vertices.pop();\n",
    "        // mark node as visited\n",
    "        // do something with the data if not already visited\n",
    "        // stack may contain same vertex twice; print the item if it's not already visited\n",
    "        if (!visited[u]) {\n",
    "            cout << \" \" << u;\n",
    "            visited[u] = true;\n",
    "        }\n",
    "        // add all the unvisited neighbors (adjacent vertices) of u to the stack\n",
    "        for(auto v: G.neighbors(u)) {\n",
    "            if (!visited[v])\n",
    "                vertices.push(v);\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "// recusive version\n",
    "template<class T>\n",
    "void DFSRec(T &G, vector<bool> & visited, int start) {\n",
    "    visited[start] = true;\n",
    "    cout << start << \" \";\n",
    "    vector<int> neighbors = G.neighbors(start);\n",
    "    for (int i=0; i<neighbors.size(); i++) {\n",
    "        int v = neighbors[i];\n",
    "        if (!visited[v])\n",
    "            DFSRec(G, visited, v);\n",
    "    }\n",
    "    // post visit\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's test DFS with the following directed graph\n",
    "\n",
    "<img src=\"resources/DirectedGraphImp.png\" />"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "// Work with directed graph shown in above figure\n",
    "GraphM graph2(5);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph2.addEdge(0, 4);\n",
    "graph2.addEdge(0, 1);\n",
    "graph2.addEdge(1, 3);\n",
    "graph2.addEdge(2, 4);\n",
    "graph2.addEdge(3, 2);\n",
    "graph2.addEdge(4, 1);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 4 1 3 2"
     ]
    }
   ],
   "source": [
    "// depth first search on graph2\n",
    "DFS<GraphM>(graph2, 4);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's test DFS and DFSRec functions with the following undirected graph\n",
    "\n",
    "<img src=\"resources/undirectedGraphImp.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "// represent undirected graph shown in above diagram\n",
    "GraphL graph3(5);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph3.addEdge(0, 1);\n",
    "graph3.addEdge(0, 4);\n",
    "graph3.addEdge(1, 0);\n",
    "graph3.addEdge(1, 4);\n",
    "graph3.addEdge(1, 3);\n",
    "graph3.addEdge(2, 4);\n",
    "graph3.addEdge(2, 3);\n",
    "graph3.addEdge(3, 1);\n",
    "graph3.addEdge(3, 2);\n",
    "graph3.addEdge(4, 0);\n",
    "graph3.addEdge(4, 1);\n",
    "graph3.addEdge(4, 2);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0 4 2 3 1"
     ]
    }
   ],
   "source": [
    "// Depth first search on graph3\n",
    "DFS<GraphL>(graph3, 0);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "// previsit if necessary\n",
    "// boolean vector to keep track of visited nodes\n",
    "vector<bool> visited1(graph3.nodeCount(), false); \n",
    "// Depth-first search recursive\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "vistited."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "4 0 1 3 2 "
     ]
    }
   ],
   "source": [
    "DFSRec<GraphL>(graph3, visited1, 4);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Breadth-First Search (BFS)\n",
    "- BFS visits all the neighbors connected to current (start) vertex before visiting vertices further away\n",
    "- similar to DFS implementation wise, but uses **queue** instead of stack\n",
    "- NOTE: if the graph is a tree and the start vertex is the root, BFS is equivalent to visiting vertices level by level from top to bottom\n",
    "\n",
    "### visualize BFS: https://opendsa-server.cs.vt.edu/ODSA/Books/CS3/html/GraphTraversal.html#breadth-first-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# BFS Implementation using queue\n",
    "- implemented as a function\n",
    "- can also be a method in Graph ADT"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <queue>\n",
    "#include <vector>\n",
    "#include <algorithm>\n",
    "\n",
    "using namespace std;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "// BFS can also be a method in Graph ADT\n",
    "// Also, keep track of parent node of each node to print the edges in BFS Tree\n",
    "template<class T>\n",
    "void BFS(T &G, int start, vector<int> &parent) {\n",
    "    vector<bool> visited(G.nodeCount(), false);\n",
    "    queue<int> q;\n",
    "    q.push(start); // push start vertex into the queue\n",
    "\n",
    "    while(!q.empty()) {\n",
    "        // get the front of the queue\n",
    "        int u = q.front();\n",
    "        // remove the front element\n",
    "        q.pop();\n",
    "        // visit and mark the node visited\n",
    "        cout << \" \" << u;\n",
    "        visited[u] = true;\n",
    "        \n",
    "        // add neighbors of u to the queue\n",
    "        for(auto v: G.neighbors(u)) {\n",
    "            if (!visited[v]) {\n",
    "                q.push(v);\n",
    "                // prevent from duplicate nodes being pushed to the queue\n",
    "                visited[v] = true;\n",
    "                // v is visited from u\n",
    "                parent[v] = u;\n",
    "            }\n",
    "        }\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's test BFS on the following directed graph\n",
    "<img src=\"resources/DirectedGraphImp.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0 1 4 3 2"
     ]
    }
   ],
   "source": [
    "// Work with directed graph shown in above figure\n",
    "// parent vector to keep track of parent for each node\n",
    "// initialized with -1\n",
    "vector<int> parent(graph2.nodeCount(), -1);\n",
    "BFS<GraphM>(graph2, 0, parent); // prints the node as they're visited using BFS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{ -1, 0, 3, 1, 0 }"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "// let's check the content of parent vector\n",
    "parent"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0->1\n",
      "3->2\n",
      "1->3\n",
      "0->4\n"
     ]
    }
   ],
   "source": [
    "// print the edges in BFS tree using parent vector\n",
    "for (int v=0; v<parent.size(); v++) {\n",
    "    if (parent[v] == -1) continue;\n",
    "    cout << parent[v] << \"->\" << v << endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's test BFS on the following undirected graph\n",
    "<img src=\"resources/undirectedGraphImp.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      " 0 1 4 3 2"
     ]
    }
   ],
   "source": [
    "// Work with undirected graph shown in above figure\n",
    "vector<int> parent_g3(graph3.nodeCount(), -1);\n",
    "BFS(graph3, 0, parent_g3);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0->1\n",
      "4->2\n",
      "1->3\n",
      "0->4\n"
     ]
    }
   ],
   "source": [
    "// print the eddges in BFS tree using parent vector\n",
    "for (int v=0; v<parent_g3.size(); v++) {\n",
    "    if (parent_g3[v] == -1) continue;\n",
    "    cout << parent_g3[v] << \"->\" << v << endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Exercises\n",
    "1. Where's My Internet?? - https://open.kattis.com/problems/wheresmyinternet\n",
    "    - DFS on undirected graph\n",
    "    - check graph connectedness\n",
    "- Erdos Numbers - https://open.kattis.com/problems/erdosnumbers\n",
    "    - BFS on undirected graph\n",
    "- Running MoM - https://open.kattis.com/problems/runningmom\n",
    "    - finding cycle in a DAG"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++14",
   "language": "C++14",
   "name": "xcpp14"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}