{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Module 2, Practical 9\n", "\n", "In this practical we will keep working with graphs. \n", "\n", "## Graphs recap\n", "\n", "Graphs are mathematical structures made of two key elements: **nodes** (or **vertices**) and **edges**. Nodes are things that we want to represent and edges are relationships among the objects. Mathematically, a graph is an entity $G = (N,E)$ where $N$ is a set of nodes and $E = N \\times N$ is the set of edges.\n", "\n", "Nodes are normally represented as circles, while edges (relationships) are represented by lines/arrows connecting nodes. An example follows:\n", "\n", "![](images/graph_1.png)\n", "\n", "\n", "Relations represented by edges can be transitive (e.g. sibling_of: if $X$ is sibling of $Y$ then $Y$ is sibling of $X$) and in this case the edges are just lines rather than arrows. In this case the graph is **directed**. In case relationships are not transitive (i.e. $X \\rightarrow Y$ does not imply $Y \\rightarrow X$) we put an arrow to indicate the direction of the relationship among the nodes and in this case we say the graph is **undirected**.\n", "\n", "Some terminology (from the lecture):\n", "\n", "![](images/graphTerms.png)\n", "\n", "The **degree** of a node is the number of connection it has with other nodes. In directed graphs the **in-degree** is the number of **incoming** edges, while the **out-degree** is the number of **outgoing** edges. \n", "\n", "![](images/degree.png)\n", "\n", "A **path** in the graph is a sequence of nodes connected by edges. \n", "\n", "![](images/path.png)\n", "\n", "Up to now, we have seen two different strategies for implementing graphs: **adjacency matrices** and **linked lists**. In the remainder, we will work with the **DiGraphLL** and **DiGraphLLAnalyzer** class implemented in the previous practical.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Visits\n", "\n", "Visiting graphs means traversing through its edges and nodes following the connections that make up the graph. Graphs can have cycles and this makes it quite tricky to visit the graph. Differently from what seen in the case of trees, **we need to keep a data structure of visited nodes** to avoid getting stuck in loops like the following (or you can pretty much end up in an infinite while loop):\n", "\n", "![](images/circle.png)\n", "\n", "\n", "Traversing a graph $G = (V,E)$ in mathematical terms can be described as, given a node $r$, visit all the nodes reachable from $r$ going through the nodes exactly once. \n", "\n", "As in the case of Trees, two ways exist to perform a visit of a graph: **depth-first** and **breadth-first** search. \n", "\n", "As said above, the base class that we will extend is ```DiGraphLL```, whose code is reported below as a reminder:" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "\n", "class DiGraphLL:\n", " def __init__(self):\n", " \"\"\"Every node is an element in the dictionary. \n", " The key is the node id and the value is a dictionary\n", " with second node as key and the weight as value\n", " \"\"\"\n", " self.__nodes = dict()\n", " \n", " def insertNode(self, node):\n", " test = self.__nodes.get(node, None)\n", " \n", " if test == None:\n", " self.__nodes[node] = {}\n", " #print(\"Node {} added\".format(node))\n", " \n", " def insertEdge(self, node1, node2, weight):\n", " test = self.__nodes.get(node1, None)\n", " test1 = self.__nodes.get(node2, None)\n", " if test != None and test1 != None:\n", " #if both nodes exist othewise don't do anything\n", " test = self.__nodes[node1].get(node2, None)\n", " if test != None:\n", " exStr = \"Edge {} --> {} already existing.\".format(node1,node2)\n", " raise Exception(exStr)\n", " else: \n", " #print(\"Inserted {}-->{} ({})\".format(node1,node2,weight))\n", " self.__nodes[node1][node2] = weight\n", " \n", " def deleteNode(self, node):\n", " test = self.__nodes.get(node, None)\n", " if test != None:\n", " self.__nodes.pop(node)\n", " # need to loop through all the nodes!!!\n", " for n in self.__nodes:\n", " test = self.__nodes[n].get(node, None)\n", " if test != None:\n", " self.__nodes[n].pop(node)\n", " \n", " def deleteEdge(self, node1,node2):\n", " test = self.__nodes.get(node1, None)\n", " if test != None:\n", " test = self.__nodes[node1].get(node2, None)\n", " if test != None:\n", " self.__nodes[node1].pop(node2)\n", " \n", " def __len__(self):\n", " return len(self.__nodes)\n", " \n", " def nodes(self):\n", " return list(self.__nodes.keys())\n", " \n", " def graph(self):\n", " return self.__nodes\n", " \n", " def __str__(self):\n", " ret = \"\"\n", " for n in self.__nodes:\n", " for edge in self.__nodes[n]: \n", " ret += \"{} -- {} --> {}\\n\".format(str(n),\n", " str(self.__nodes[n][edge]),\n", " str(edge))\n", " return ret\n", " \n", " def adjacent(self, node):\n", " \"\"\"returns a list of nodes connected to node\"\"\"\n", " ret = []\n", " test = self.__nodes.get(node, None)\n", " if test != None:\n", " for n in self.__nodes:\n", " if n == node:\n", " #all outgoing edges\n", " for edge in self.__nodes[node]:\n", " ret.append(edge)\n", " else:\n", " #all incoming edges\n", " for edge in self.__nodes[n]:\n", " if edge == node:\n", " ret.append(n)\n", " return ret\n", "\n", " def adjacentEdge(self, node, incoming = True):\n", " \"\"\"\n", " If incoming == False\n", " we look at the edges of the node\n", " else we need to loop through all the nodes. \n", " An edge is present if there is a \n", " corresponding entry in the dictionary.\n", " If no such nodes exist returns None\n", " \"\"\"\n", " ret = []\n", " if incoming == False:\n", " edges = self.__nodes.get(node,None)\n", " if edges != None:\n", " for e in edges:\n", " w = self.__nodes[node][e]\n", " ret.append((node, e, w))\n", " return ret\n", " else:\n", " for n in self.__nodes:\n", " edge = self.__nodes[n].get(node,None)\n", " if edge != None:\n", " ret.append((n,node, edge))\n", " return ret\n", " \n", " def edges(self):\n", " \"\"\"Returns all the edges in a list of triplets\"\"\"\n", " ret = []\n", " for node in self.__nodes:\n", " for edge in self.__nodes[node]:\n", " w = self.__nodes[node][edge]\n", " ret.append((node,edge, w))\n", " return ret\n", " \n", " def edgeIn(self,node1,node2):\n", " \"\"\"Checks if edge node1 --> node2 is present\"\"\"\n", " n1 = self.__nodes.get(node1, None)\n", " if n1 != None:\n", " n2 = self.__nodes[node1].get(node2, None)\n", " if n2 != None:\n", " return True\n", " else:\n", " return False\n", " else: \n", " return False " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [DiGraphLL2.py](data_structures/DiGraphLL2.py)\n", "\n", "### Depth First Search (DFS)\n", "\n", "Depth-first search visits nodes of the graph going as deep as possible along each path. \n", "This procedure is normally used to travel through **all the nodes** of the graph, and so it might have to be repeated several times (starting each time from a different node) as the output is, in general, a **forest of DFS trees**. \n", "\n", "We have two possible versions of this algorithm: **pre-order** and **post-order** DFS. \n", "This algorithm makes use of a stack (rather *implicit*, as done below by using recursion) or *explicitly*. \n", "\n", "Difference between the two ways:\n", "\n", "**Pre-order DFS**\n", "\n", "You process the node before exploring its neighbors. In code, this means the “visit action” (print, store, compute, etc.) happens right after the node is discovered and before recursively visiting adjacent nodes.\n", "\n", "**Post-order DFS**\n", "\n", "You process the node after exploring all its neighbors. The visit action happens when recursion is returning, meaning after all reachable nodes from this node have been fully explored.\n", "\n", "**Example:** Let's implement DFS in the ```DiGraphLLAnalyzer``` class we implemented in the previous lab." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Preorder:\n", "Node_1\n", "\tfrom Node_1 --> Node_2\n", "Node_2\n", "\tfrom Node_2 --> Node_3\n", "Node_3\n", "\tfrom Node_3 --> Node_4\n", "Node_4\n", "\tfrom Node_3 --> Node_6\n", "Node_6\n", "\tfrom Node_2 --> Node_5\n", "Node_5\n", "\tfrom Node_5 --> Node_8\n", "Node_8\n", "\tfrom Node_8 --> Node_7\n", "Node_7\n", "\n", "Postorder:\n", "\tfrom Node_1 --> Node_2\n", "\tfrom Node_2 --> Node_3\n", "\tfrom Node_3 --> Node_4\n", "Node_4\n", "\tfrom Node_3 --> Node_6\n", "Node_6\n", "Node_3\n", "\tfrom Node_2 --> Node_5\n", "\tfrom Node_5 --> Node_8\n", "\tfrom Node_8 --> Node_7\n", "Node_7\n", "Node_8\n", "Node_5\n", "Node_2\n", "Node_1\n", "\n", "Preorder from Node_9\n", "Node_9\n", "\tfrom Node_9 --> Node_2\n", "Node_2\n", "\tfrom Node_2 --> Node_1\n", "Node_1\n", "\tfrom Node_1 --> Node_3\n", "Node_3\n", "\tfrom Node_3 --> Node_4\n", "Node_4\n", "\tfrom Node_3 --> Node_6\n", "Node_6\n", "\tfrom Node_1 --> Node_5\n", "Node_5\n", "\tfrom Node_5 --> Node_8\n", "Node_8\n", "\tfrom Node_8 --> Node_7\n", "Node_7\n" ] } ], "source": [ "from collections import deque\n", "\n", "\n", "class DiGraphLLAnalyzer(DiGraphLL):\n", " \"\"\"Every node is an element in the dictionary. \n", " The key is the node id and the value is a dictionary\n", " with key second node and value the weight\n", " \"\"\"\n", "\n", " def getTopConnected_incoming(self):\n", " \n", " topN = \"\"\n", " #accumulator to count connections\n", " conn = [0]*len(self.nodes())\n", " for node in self.nodes():\n", " for el in self.graph()[node]:\n", " elInd = self.nodes().index(el)\n", " conn[elInd] +=1\n", " M = max(conn)\n", " ind = [x for x in range(len(conn)) if conn[x] == M]\n", " return [self.nodes()[x] for x in ind]\n", " \n", " def getTopConnected_outgoing(self):\n", " \"\"\"Returns the node(s)\"\"\"\n", " topN = []\n", " conn = -1\n", "\n", " for node in self.nodes():\n", " n = len(self.graph()[node])\n", " if n > conn:\n", " topN = [node]\n", " conn = n\n", " else:\n", " if n == conn:\n", " topN.append(node) \n", " \n", " return topN\n", " \n", " def hasPathAux(self, node1,node2):\n", " if node1 not in self.nodes() or node2 not in self.nodes():\n", " return False\n", " else:\n", " Q = deque()\n", " Q.append(node1)\n", " visited = set()\n", " while len(Q) > 0:\n", " curN = Q.popleft()\n", " #do not travel on already visited nodes\n", " if curN not in visited:\n", " visited.add(curN)\n", " #get all outgoing nodes of Q\n", " for edge in self.graph()[curN]:\n", " if edge == node2:\n", " return True\n", " else:\n", " Q.append(edge)\n", " \n", " return False\n", " \n", " def hasPath(self, node1, node2):\n", " #checks both paths and returns True or false\n", " res = self.hasPathAux(node1,node2)\n", " if res:\n", " return True\n", " else:\n", " return self.hasPathAux(node2,node1)\n", " \n", " \n", " def DFSvisit(self, root, preorder = True, visited = set()):\n", " visited.add(root)\n", " if preorder:\n", " print(\"{}\".format(root))\n", " #remember that the self.adjacentEdge method returns:\n", " #[('node1','node2', weight1), ...('node1', 'nodeX', weightX)]\n", " outGoingEdges = self.adjacentEdge(root, incoming = False)\n", " nextNodes = []\n", " if len(outGoingEdges) > 0:\n", " nextNodes = [x[1] for x in outGoingEdges]\n", " #print(nextNodes)\n", " for nextN in nextNodes:\n", " if nextN not in visited:\n", " print(\"\\tfrom {} --> {}\".format(root, nextN))\n", " self.DFSvisit(nextN, preorder, visited)\n", " if not preorder:\n", " print(\"{}\".format(root))\n", " \n", "if __name__ == \"__main__\":\n", " G = DiGraphLLAnalyzer()\n", " for i in range(1,10):\n", " G.insertNode(\"Node_\" + str(i))\n", " \n", " G.insertEdge(\"Node_1\", \"Node_2\",1)\n", " G.insertEdge(\"Node_2\", \"Node_1\",1)\n", " G.insertEdge(\"Node_1\", \"Node_3\",1)\n", " G.insertEdge(\"Node_1\", \"Node_5\",1)\n", " G.insertEdge(\"Node_2\", \"Node_3\",1)\n", " G.insertEdge(\"Node_2\", \"Node_5\",1)\n", " G.insertEdge(\"Node_3\", \"Node_4\",1)\n", " G.insertEdge(\"Node_3\", \"Node_6\",1)\n", " G.insertEdge(\"Node_5\", \"Node_3\",1)\n", " G.insertEdge(\"Node_5\", \"Node_5\",1)\n", " G.insertEdge(\"Node_6\", \"Node_4\",1)\n", " G.insertEdge(\"Node_6\", \"Node_6\",1)\n", " G.insertEdge(\"Node_7\", \"Node_5\",1)\n", " G.insertEdge(\"Node_5\", \"Node_8\",1)\n", " G.insertEdge(\"Node_8\", \"Node_7\",1)\n", " G.insertEdge(\"Node_9\", \"Node_2\",1)\n", " \n", " print(\"Preorder:\")\n", " G.DFSvisit(\"Node_1\", preorder = True, visited = set())\n", " print(\"\\nPostorder:\")\n", " G.DFSvisit(\"Node_1\", preorder = False, visited = set())\n", " \n", " print(\"\\nPreorder from Node_9\")\n", " G.DFSvisit(\"Node_9\", preorder = True, visited = set())" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [DiGraphLLAnalyzer2.py](data_structures/DiGraphLLAnalyzer2.py)\n", "\n", "**If you look at the output of preorder visit from Node_1 you'll notice that we are are not visiting Node_9.**\n", "\n", "To make sure we visit all nodes we need to modify the code in the following way:" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Preorder:\n", "Starting from Node_1\n", "Node_1\n", "\tfrom Node_1 --> Node_2\n", "Node_2\n", "\tfrom Node_2 --> Node_3\n", "Node_3\n", "\tfrom Node_3 --> Node_4\n", "Node_4\n", "\tfrom Node_3 --> Node_6\n", "Node_6\n", "\tfrom Node_2 --> Node_5\n", "Node_5\n", "\tfrom Node_5 --> Node_8\n", "Node_8\n", "\tfrom Node_8 --> Node_7\n", "Node_7\n", "Starting from Node_9\n", "Node_9\n", "\n", "Postorder:\n", "Starting from Node_1\n", "\tfrom Node_1 --> Node_2\n", "\tfrom Node_2 --> Node_3\n", "\tfrom Node_3 --> Node_4\n", "Node_4\n", "\tfrom Node_3 --> Node_6\n", "Node_6\n", "Node_3\n", "\tfrom Node_2 --> Node_5\n", "\tfrom Node_5 --> Node_8\n", "\tfrom Node_8 --> Node_7\n", "Node_7\n", "Node_8\n", "Node_5\n", "Node_2\n", "Node_1\n", "Starting from Node_9\n", "Node_9\n", "\n", "Postorder:\n", "Starting from Node_5\n", "\tfrom Node_5 --> Node_3\n", "\tfrom Node_3 --> Node_4\n", "Node_4\n", "\tfrom Node_3 --> Node_6\n", "Node_6\n", "Node_3\n", "\tfrom Node_5 --> Node_8\n", "\tfrom Node_8 --> Node_7\n", "Node_7\n", "Node_8\n", "Node_5\n", "Starting from Node_1\n", "\tfrom Node_1 --> Node_2\n", "Node_2\n", "Node_1\n", "Starting from Node_9\n", "Node_9\n" ] } ], "source": [ "from collections import deque\n", "\n", "\n", "\n", "class DiGraphLLAnalyzer(DiGraphLL):\n", "\n", " # ... missing code ... same as above\n", " \n", " def DFSvisit(self, root, preorder = True, visited = set()):\n", " visited.add(root)\n", " if preorder:\n", " print(\"{}\".format(root))\n", " #remember that the self.adjacentEdge method returns:\n", " #[('node1','node2', weight1), ...('node1', 'nodeX', weightX)]\n", " outGoingEdges = self.adjacentEdge(root, incoming = False)\n", " nextNodes = []\n", " if len(outGoingEdges) > 0:\n", " nextNodes = [x[1] for x in outGoingEdges]\n", " #print(nextNodes)\n", " for nextN in nextNodes:\n", " if nextN not in visited:\n", " print(\"\\tfrom {} --> {}\".format(root, nextN))\n", " self.DFSvisit(nextN, preorder, visited)\n", " if not preorder:\n", " print(\"{}\".format(root))\n", " \n", " def DFS(self, root, preorder = True):\n", " visited = set()\n", " #first visit from specified node then check all other nodes\n", " #set is mutable so the set is going to change!\n", " print(\"Starting from {}\".format(root))\n", " self.DFSvisit(root, preorder, visited)\n", " \n", " for node in self.nodes():\n", " if node not in visited:\n", " print(\"Starting from {}\".format(node))\n", " self.DFSvisit(node, preorder, visited)\n", " \n", " \n", "if __name__ == \"__main__\":\n", " G = DiGraphLLAnalyzer()\n", " for i in range(1,10):\n", " G.insertNode(\"Node_\" + str(i))\n", " \n", " G.insertEdge(\"Node_1\", \"Node_2\",1)\n", " G.insertEdge(\"Node_2\", \"Node_1\",1)\n", " G.insertEdge(\"Node_1\", \"Node_3\",1)\n", " G.insertEdge(\"Node_1\", \"Node_5\",1)\n", " G.insertEdge(\"Node_2\", \"Node_3\",1)\n", " G.insertEdge(\"Node_2\", \"Node_5\",1)\n", " G.insertEdge(\"Node_3\", \"Node_4\",1)\n", " G.insertEdge(\"Node_3\", \"Node_6\",1)\n", " G.insertEdge(\"Node_5\", \"Node_3\",1)\n", " G.insertEdge(\"Node_5\", \"Node_5\",1)\n", " G.insertEdge(\"Node_6\", \"Node_4\",1)\n", " G.insertEdge(\"Node_6\", \"Node_6\",1)\n", " G.insertEdge(\"Node_7\", \"Node_5\",1)\n", " G.insertEdge(\"Node_5\", \"Node_8\",1)\n", " G.insertEdge(\"Node_8\", \"Node_7\",1)\n", " G.insertEdge(\"Node_9\", \"Node_2\",1)\n", " \n", " print(\"Preorder:\")\n", " G.DFS(\"Node_1\", preorder = True)\n", " print(\"\\nPostorder:\")\n", " G.DFS(\"Node_1\", preorder = False)\n", " print(\"\\nPostorder:\")\n", " G.DFS(\"Node_5\", preorder = False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [DiGraphLLAnalyzer3.py](data_structures/DiGraphLLAnalyzer3.py)\n", "\n", "The graph created above (except for the weights of the edges) is:\n", "\n", "![](images/testgraph.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercises\n", "\n", "1. Implement depth first search for the class ```DiGraphLLAnalyzer``` using an **explicit stack** and a **pre-order** visit of the nodes (to keep things simple). Remember that you can simulate a stack (FILO -- first in last out queue) by using a list with ```append(elem)``` and ```pop(-1)``` (or ```collections.deque``` and the methods ```append(elem)``` and ```pop()```. Use the pseudocode below (I suggest to use a set rather than a boolean list for the visited structure):\n", "\n", "![](images/dfs_pseudocode.png)\n", "\n", "You can test your methods with the following code:\n", "\n", "```python\n", "G = DiGraphLLAnalyzer()\n", " G1 = DiGraphLLAnalyzer()\n", " for i in range(1,10):\n", " G.insertNode(\"Node_\" + str(i))\n", " G1.insertNode(\"Node_\" + str(i))\n", " \n", " G.insertEdge(\"Node_1\", \"Node_2\",1)\n", " G.insertEdge(\"Node_2\", \"Node_1\",1)\n", " G.insertEdge(\"Node_1\", \"Node_3\",1)\n", " G.insertEdge(\"Node_1\", \"Node_5\",1)\n", " G.insertEdge(\"Node_2\", \"Node_3\",1)\n", " G.insertEdge(\"Node_2\", \"Node_5\",1)\n", " G.insertEdge(\"Node_3\", \"Node_4\",1)\n", " G.insertEdge(\"Node_3\", \"Node_6\",1)\n", " G.insertEdge(\"Node_5\", \"Node_3\",1)\n", " G.insertEdge(\"Node_5\", \"Node_5\",1)\n", " G.insertEdge(\"Node_6\", \"Node_4\",1)\n", " G.insertEdge(\"Node_6\", \"Node_6\",1)\n", " G.insertEdge(\"Node_7\", \"Node_5\",1)\n", " G.insertEdge(\"Node_5\", \"Node_8\",1)\n", " G.insertEdge(\"Node_8\", \"Node_7\",1)\n", " G.insertEdge(\"Node_9\", \"Node_2\",1)\n", " #Graph G1\n", " G1.insertEdge(\"Node_1\" ,\"Node_2\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_6\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_7\", 1)\n", " G1.insertEdge(\"Node_2\" ,\"Node_7\", 1)\n", " G1.insertEdge(\"Node_3\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_5\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_6\" ,\"Node_5\", 1)\n", " G1.insertEdge(\"Node_6\" ,\"Node_8\", 1)\n", " G1.insertEdge(\"Node_7\" ,\"Node_9\", 1)\n", " G1.insertEdge(\"Node_8\" ,\"Node_9\", 1)\n", " \n", " G.DFS(\"Node_1\")\n", " G.DFS(\"Node_5\")\n", " \n", " G1.DFS(\"Node_1\")\n", " G1.DFS(\"Node_4\")\n", " G1.DFS(\"Node_6\")\n", "```\n", "\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "G from Node_1:\n", "Starting from Node_1\n", "Node_1 (visit order: 1)\n", "\tfrom Node_1 --> Node_2\n", "\tfrom Node_1 --> Node_3\n", "\tfrom Node_1 --> Node_5\n", "Node_5 (visit order: 2)\n", "\tfrom Node_5 --> Node_3\n", "\tfrom Node_5 --> Node_5\n", "\tfrom Node_5 --> Node_8\n", "Node_8 (visit order: 3)\n", "\tfrom Node_8 --> Node_7\n", "Node_7 (visit order: 4)\n", "\tfrom Node_7 --> Node_5\n", "Node_3 (visit order: 5)\n", "\tfrom Node_3 --> Node_4\n", "\tfrom Node_3 --> Node_6\n", "Node_6 (visit order: 6)\n", "\tfrom Node_6 --> Node_4\n", "\tfrom Node_6 --> Node_6\n", "Node_4 (visit order: 7)\n", "Node_2 (visit order: 8)\n", "\tfrom Node_2 --> Node_1\n", "\tfrom Node_2 --> Node_3\n", "\tfrom Node_2 --> Node_5\n", "Starting from Node_9\n", "Node_9 (visit order: 1)\n", "\tfrom Node_9 --> Node_2\n", "\n", "\n", "G from Node_5:\n", "Starting from Node_5\n", "Node_5 (visit order: 1)\n", "\tfrom Node_5 --> Node_3\n", "\tfrom Node_5 --> Node_5\n", "\tfrom Node_5 --> Node_8\n", "Node_8 (visit order: 2)\n", "\tfrom Node_8 --> Node_7\n", "Node_7 (visit order: 3)\n", "\tfrom Node_7 --> Node_5\n", "Node_3 (visit order: 4)\n", "\tfrom Node_3 --> Node_4\n", "\tfrom Node_3 --> Node_6\n", "Node_6 (visit order: 5)\n", "\tfrom Node_6 --> Node_4\n", "\tfrom Node_6 --> Node_6\n", "Node_4 (visit order: 6)\n", "Starting from Node_1\n", "Node_1 (visit order: 1)\n", "\tfrom Node_1 --> Node_2\n", "\tfrom Node_1 --> Node_3\n", "\tfrom Node_1 --> Node_5\n", "Node_2 (visit order: 2)\n", "\tfrom Node_2 --> Node_1\n", "\tfrom Node_2 --> Node_3\n", "\tfrom Node_2 --> Node_5\n", "Starting from Node_9\n", "Node_9 (visit order: 1)\n", "\tfrom Node_9 --> Node_2\n", "\n", "\n", "G1:\n", "G1 from Node_1:\n", "Starting from Node_1\n", "Node_1 (visit order: 1)\n", "\tfrom Node_1 --> Node_2\n", "\tfrom Node_1 --> Node_4\n", "\tfrom Node_1 --> Node_6\n", "\tfrom Node_1 --> Node_7\n", "Node_7 (visit order: 2)\n", "\tfrom Node_7 --> Node_9\n", "Node_9 (visit order: 3)\n", "Node_6 (visit order: 4)\n", "\tfrom Node_6 --> Node_5\n", "\tfrom Node_6 --> Node_8\n", "Node_8 (visit order: 5)\n", "\tfrom Node_8 --> Node_9\n", "Node_5 (visit order: 6)\n", "\tfrom Node_5 --> Node_4\n", "Node_4 (visit order: 7)\n", "Node_2 (visit order: 8)\n", "\tfrom Node_2 --> Node_7\n", "Starting from Node_3\n", "Node_3 (visit order: 1)\n", "\tfrom Node_3 --> Node_4\n", "\n", "G1 from Node_4:\n", "Starting from Node_4\n", "Node_4 (visit order: 1)\n", "Starting from Node_1\n", "Node_1 (visit order: 1)\n", "\tfrom Node_1 --> Node_2\n", "\tfrom Node_1 --> Node_4\n", "\tfrom Node_1 --> Node_6\n", "\tfrom Node_1 --> Node_7\n", "Node_7 (visit order: 2)\n", "\tfrom Node_7 --> Node_9\n", "Node_9 (visit order: 3)\n", "Node_6 (visit order: 4)\n", "\tfrom Node_6 --> Node_5\n", "\tfrom Node_6 --> Node_8\n", "Node_8 (visit order: 5)\n", "\tfrom Node_8 --> Node_9\n", "Node_5 (visit order: 6)\n", "\tfrom Node_5 --> Node_4\n", "Node_2 (visit order: 7)\n", "\tfrom Node_2 --> Node_7\n", "Starting from Node_3\n", "Node_3 (visit order: 1)\n", "\tfrom Node_3 --> Node_4\n", "\n", "G1 from Node_6:\n", "Starting from Node_6\n", "Node_6 (visit order: 1)\n", "\tfrom Node_6 --> Node_5\n", "\tfrom Node_6 --> Node_8\n", "Node_8 (visit order: 2)\n", "\tfrom Node_8 --> Node_9\n", "Node_9 (visit order: 3)\n", "Node_5 (visit order: 4)\n", "\tfrom Node_5 --> Node_4\n", "Node_4 (visit order: 5)\n", "Starting from Node_1\n", "Node_1 (visit order: 1)\n", "\tfrom Node_1 --> Node_2\n", "\tfrom Node_1 --> Node_4\n", "\tfrom Node_1 --> Node_6\n", "\tfrom Node_1 --> Node_7\n", "Node_7 (visit order: 2)\n", "\tfrom Node_7 --> Node_9\n", "Node_2 (visit order: 3)\n", "\tfrom Node_2 --> Node_7\n", "Starting from Node_3\n", "Node_3 (visit order: 1)\n", "\tfrom Node_3 --> Node_4\n" ] } ], "source": [ "from collections import deque\n", "\n", "\n", "\n", "class DiGraphLLAnalyzer(DiGraphLL):\n", "\n", " # ... missing code ...\n", " \n", " def DFSvisit(self, root, visited = set()):\n", " S = deque() # the stack\n", " S.append(root)\n", " order = 1\n", " while len(S) > 0:\n", " curNode = S.pop()\n", " if curNode not in visited:\n", " #pre-order visit\n", " print(\"{} (visit order: {})\".format(curNode,order))\n", " order += 1\n", " visited.add(curNode)\n", " #remember that self.adjacentEdge returns:\n", " #[('node1','node2', weight1), ...('node1', 'nodeX', weightX)]\n", " outGoingEdges = self.adjacentEdge(curNode, incoming = False)\n", " nextNodes = []\n", " if len(outGoingEdges) > 0:\n", " nextNodes = [x[1] for x in outGoingEdges]\n", " #print(nextNodes)\n", " for nextN in nextNodes:\n", " print(\"\\tfrom {} --> {}\".format(curNode, nextN))\n", " S.append(nextN)\n", " \n", " def DFS(self, root):\n", " visited = set()\n", " #first visit from specified node then check all other nodes\n", " #set is mutable so the set is going to change!\n", " print(\"Starting from {}\".format(root))\n", " self.DFSvisit(root, visited)\n", " \n", " for node in self.nodes():\n", " if node not in visited:\n", " print(\"Starting from {}\".format(node))\n", " self.DFSvisit(node, visited)\n", " \n", "if __name__ == \"__main__\":\n", " G = DiGraphLLAnalyzer()\n", " G1 = DiGraphLLAnalyzer()\n", " for i in range(1,10):\n", " G.insertNode(\"Node_\" + str(i))\n", " G1.insertNode(\"Node_\" + str(i))\n", " \n", " G.insertEdge(\"Node_1\", \"Node_2\",1)\n", " G.insertEdge(\"Node_2\", \"Node_1\",1)\n", " G.insertEdge(\"Node_1\", \"Node_3\",1)\n", " G.insertEdge(\"Node_1\", \"Node_5\",1)\n", " G.insertEdge(\"Node_2\", \"Node_3\",1)\n", " G.insertEdge(\"Node_2\", \"Node_5\",1)\n", " G.insertEdge(\"Node_3\", \"Node_4\",1)\n", " G.insertEdge(\"Node_3\", \"Node_6\",1)\n", " G.insertEdge(\"Node_5\", \"Node_3\",1)\n", " G.insertEdge(\"Node_5\", \"Node_5\",1)\n", " G.insertEdge(\"Node_6\", \"Node_4\",1)\n", " G.insertEdge(\"Node_6\", \"Node_6\",1)\n", " G.insertEdge(\"Node_7\", \"Node_5\",1)\n", " G.insertEdge(\"Node_5\", \"Node_8\",1)\n", " G.insertEdge(\"Node_8\", \"Node_7\",1)\n", " G.insertEdge(\"Node_9\", \"Node_2\",1)\n", " #Graph G1\n", " G1.insertEdge(\"Node_1\" ,\"Node_2\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_6\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_7\", 1)\n", " G1.insertEdge(\"Node_2\" ,\"Node_7\", 1)\n", " G1.insertEdge(\"Node_3\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_5\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_6\" ,\"Node_5\", 1)\n", " G1.insertEdge(\"Node_6\" ,\"Node_8\", 1)\n", " G1.insertEdge(\"Node_7\" ,\"Node_9\", 1)\n", " G1.insertEdge(\"Node_8\" ,\"Node_9\", 1)\n", " \n", " print(\"G from Node_1:\")\n", " G.DFS(\"Node_1\")\n", " print(\"\\n\\nG from Node_5:\")\n", " G.DFS(\"Node_5\")\n", " print(\"\\n\\nG1:\")\n", " print(\"G1 from Node_1:\")\n", " G1.DFS(\"Node_1\")\n", " print(\"\\nG1 from Node_4:\")\n", " G1.DFS(\"Node_4\")\n", " print(\"\\nG1 from Node_6:\")\n", " G1.DFS(\"Node_6\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [DiGraphLLAnalyzerEx1.py](data_structures/DiGraphLLAnalyzerEx1.py)\n", "
\n", "\n", "2. Write a method ```getDFStime(self,start_sort = True)``` that for each node of a ```DiGraphLLAnalyzer```, returns its start and end time in a DFS visit. Time is just a counter that counts the visiting operations. Start time is when a node has first been encountered, and end time is when all its subgraph has been visited and the algorithm moved to another part of the graph. Sort the results by start time or by end time depending on the value of ```start_sort``` that can be True or False (Hint: use lambda functions with sort!). \n", "\n", "Hint: implement another function (```dfsTime(self, root, visited, times, time)```) that performs a dfs of the graph updating a structure of start and end times (```times```) and keeping a counter (```time```) that increases step by step by one.\n", "\n", "Test the code with the following two graphs G and G1 (checking them with the pictures below):\n", "\n", "![](images/g1_g2.png)\n", "\n", "that can be generated by the following code:\n", "\n", "```python\n", " G = DiGraphLLAnalyzer()\n", " G1 = DiGraphLLAnalyzer()\n", " for i in range(1,10):\n", " G.insertNode(\"Node_\" + str(i))\n", " G1.insertNode(\"Node_\" + str(i))\n", " \n", " G.insertEdge(\"Node_1\", \"Node_2\",1)\n", " G.insertEdge(\"Node_2\", \"Node_1\",1)\n", " G.insertEdge(\"Node_1\", \"Node_3\",1)\n", " G.insertEdge(\"Node_1\", \"Node_5\",1)\n", " G.insertEdge(\"Node_2\", \"Node_3\",1)\n", " G.insertEdge(\"Node_2\", \"Node_5\",1)\n", " G.insertEdge(\"Node_3\", \"Node_4\",1)\n", " G.insertEdge(\"Node_3\", \"Node_6\",1)\n", " G.insertEdge(\"Node_5\", \"Node_3\",1)\n", " G.insertEdge(\"Node_5\", \"Node_5\",1)\n", " G.insertEdge(\"Node_6\", \"Node_4\",1)\n", " G.insertEdge(\"Node_6\", \"Node_6\",1)\n", " G.insertEdge(\"Node_7\", \"Node_5\",1)\n", " G.insertEdge(\"Node_5\", \"Node_8\",1)\n", " G.insertEdge(\"Node_8\", \"Node_7\",1)\n", " G.insertEdge(\"Node_9\", \"Node_2\",1)\n", " #Graph G1\n", " G1.insertEdge(\"Node_1\" ,\"Node_2\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_6\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_7\", 1)\n", " G1.insertEdge(\"Node_2\" ,\"Node_7\", 1)\n", " G1.insertEdge(\"Node_3\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_5\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_6\" ,\"Node_5\", 1)\n", " G1.insertEdge(\"Node_6\" ,\"Node_8\", 1)\n", " G1.insertEdge(\"Node_7\" ,\"Node_9\", 1)\n", " G1.insertEdge(\"Node_8\" ,\"Node_9\", 1)\n", "```\n", "\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "G (sorted by start):\n", "Starting from Node_1\n", "Starting from Node_9\n", "[1] Node_1 start Time: 1 end Time: 16\n", "[2] Node_2 start Time: 2 end Time: 15\n", "[3] Node_3 start Time: 3 end Time: 8\n", "[4] Node_4 start Time: 4 end Time: 5\n", "[5] Node_6 start Time: 6 end Time: 7\n", "[6] Node_5 start Time: 9 end Time: 14\n", "[7] Node_8 start Time: 10 end Time: 13\n", "[8] Node_7 start Time: 11 end Time: 12\n", "[9] Node_9 start Time: 16 end Time: 17\n", "\n", "G (sorted by end):\n", "Starting from Node_1\n", "Starting from Node_9\n", "[1] Node_4 start Time: 4 end Time: 5\n", "[2] Node_6 start Time: 6 end Time: 7\n", "[3] Node_3 start Time: 3 end Time: 8\n", "[4] Node_7 start Time: 11 end Time: 12\n", "[5] Node_8 start Time: 10 end Time: 13\n", "[6] Node_5 start Time: 9 end Time: 14\n", "[7] Node_2 start Time: 2 end Time: 15\n", "[8] Node_1 start Time: 1 end Time: 16\n", "[9] Node_9 start Time: 16 end Time: 17\n", "\n", "G1 (sorted by end):\n", "Starting from Node_1\n", "Starting from Node_3\n", "[1] Node_9 start Time: 4 end Time: 5\n", "[2] Node_7 start Time: 3 end Time: 6\n", "[3] Node_2 start Time: 2 end Time: 7\n", "[4] Node_4 start Time: 8 end Time: 9\n", "[5] Node_5 start Time: 11 end Time: 12\n", "[6] Node_8 start Time: 13 end Time: 14\n", "[7] Node_6 start Time: 10 end Time: 15\n", "[8] Node_1 start Time: 1 end Time: 16\n", "[9] Node_3 start Time: 16 end Time: 17\n" ] } ], "source": [ "from collections import deque\n", "\n", "\n", "class DiGraphLLAnalyzer(DiGraphLL):\n", " \n", " # ... missing code ...\n", "\n", " def dfsTime(self, root, visited, times, time = 1):\n", " visited.add(root)\n", " #print(\"\\t--> {}\".format(root))\n", " start = int(time)\n", " time = int(time) + 1\n", " #print(\"\\tStack:{}\".format(recStack))\n", " outGoingEdges = self.adjacentEdge(root, incoming = False)\n", " #print(outGoingEdges)\n", " nextNodes = []\n", " if len(outGoingEdges) > 0:\n", " nextNodes = [x[1] for x in outGoingEdges]\n", " \n", " for nextN in nextNodes:\n", " if nextN not in visited:\n", " end = self.dfsTime(nextN, visited, times,time)\n", " time = end \n", " time += 1\n", " \n", " times[root]=(start, time) \n", " \n", " return time \n", " \n", " def getDFStime(self, start_sort = True):\n", " visited = set()\n", " times = dict()\n", " time = 1 \n", " for node in self.nodes():\n", " if node not in visited:\n", " print(\"Starting from {}\".format(node))\n", " time = self.dfsTime(node, visited,times, time)\n", " \n", " sortRes = []\n", " for node in self.nodes():\n", " sortRes.append((node,times[node][0],times[node][1]))\n", " \n", " if start_sort:\n", " sortRes.sort(key = lambda el : el[1])\n", " else:\n", " sortRes.sort(key = lambda el : el[2])\n", " \n", " for i in range(len(sortRes)):\n", " print(\"[{}] {} start Time: {} end Time: {}\".format(i+1, \n", " sortRes[i][0],\n", " sortRes[i][1],\n", " sortRes[i][2]))\n", "\n", " \n", "if __name__ == \"__main__\":\n", " G = DiGraphLLAnalyzer()\n", " G1 = DiGraphLLAnalyzer()\n", " for i in range(1,10):\n", " G.insertNode(\"Node_\" + str(i))\n", " G1.insertNode(\"Node_\" + str(i))\n", " \n", " G.insertEdge(\"Node_1\", \"Node_2\",1)\n", " G.insertEdge(\"Node_2\", \"Node_1\",1)\n", " G.insertEdge(\"Node_1\", \"Node_3\",1)\n", " G.insertEdge(\"Node_1\", \"Node_5\",1)\n", " G.insertEdge(\"Node_2\", \"Node_3\",1)\n", " G.insertEdge(\"Node_2\", \"Node_5\",1)\n", " G.insertEdge(\"Node_3\", \"Node_4\",1)\n", " G.insertEdge(\"Node_3\", \"Node_6\",1)\n", " G.insertEdge(\"Node_5\", \"Node_3\",1)\n", " G.insertEdge(\"Node_5\", \"Node_5\",1)\n", " G.insertEdge(\"Node_6\", \"Node_4\",1)\n", " G.insertEdge(\"Node_6\", \"Node_6\",1)\n", " G.insertEdge(\"Node_7\", \"Node_5\",1)\n", " G.insertEdge(\"Node_5\", \"Node_8\",1)\n", " G.insertEdge(\"Node_8\", \"Node_7\",1)\n", " G.insertEdge(\"Node_9\", \"Node_2\",1)\n", " #Graph G1\n", " G1.insertEdge(\"Node_1\" ,\"Node_2\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_6\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_7\", 1)\n", " G1.insertEdge(\"Node_2\" ,\"Node_7\", 1)\n", " G1.insertEdge(\"Node_3\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_5\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_6\" ,\"Node_5\", 1)\n", " G1.insertEdge(\"Node_6\" ,\"Node_8\", 1)\n", " G1.insertEdge(\"Node_7\" ,\"Node_9\", 1)\n", " G1.insertEdge(\"Node_8\" ,\"Node_9\", 1)\n", " \n", " print(\"G (sorted by start):\")\n", " G.getDFStime(start_sort = True)\n", " print(\"\\nG (sorted by end):\")\n", " G.getDFStime(start_sort = False)\n", " print(\"\\nG1 (sorted by end):\")\n", " G1.getDFStime(start_sort = False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [DiGraphLLAnalyzerEx2.py](data_structures/DiGraphLLAnalyzerEx2.py)\n", "
\n", "\n", "### Breadth First Search (BFS)\n", "\n", "\n", "Breadth-first search visits all the nodes starting from a *root* node and proceeding level by level. \n", "This means that we first visit **all the nodes at distance 1** from the *root*, then **all the nodes at distance 2** and so on. \n", "This algorithm, in general, does not visit all the nodes, but only those that are reachable from the specified root. If all nodes must be visited, another visit should start from a node not touched in the first visit.\n", "\n", "**This algorithm is quite useful to find the shortest path between two nodes.**\n", "\n", "**Example:** Let's implement BFS in the ```DiGraphLLAnalyzer``` class." ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "scrolled": true }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "BFS(Node_1):\n", "From Node_1:\n", "\t --> Node_2\n", "\t --> Node_3\n", "\t --> Node_5\n", "From Node_2:\n", "From Node_3:\n", "\t --> Node_4\n", "\t --> Node_6\n", "From Node_5:\n", "\t --> Node_8\n", "From Node_4:\n", "From Node_6:\n", "From Node_8:\n", "\t --> Node_7\n", "From Node_7:\n", "\n", "------------\n", "\n", "Now BFS(Node_5):\n", "From Node_5:\n", "\t --> Node_3\n", "\t --> Node_8\n", "From Node_3:\n", "\t --> Node_4\n", "\t --> Node_6\n", "From Node_8:\n", "\t --> Node_7\n", "From Node_4:\n", "From Node_6:\n", "From Node_7:\n", "\n", "------------\n", "\n", "Now BFS(Node_9):\n", "From Node_9:\n", "\t --> Node_2\n", "From Node_2:\n", "\t --> Node_1\n", "\t --> Node_3\n", "\t --> Node_5\n", "From Node_1:\n", "From Node_3:\n", "\t --> Node_4\n", "\t --> Node_6\n", "From Node_5:\n", "\t --> Node_8\n", "From Node_4:\n", "From Node_6:\n", "From Node_8:\n", "\t --> Node_7\n", "From Node_7:\n", "\n", "------------\n" ] } ], "source": [ "from collections import deque\n", "\n", "\n", "class DiGraphLLAnalyzer(DiGraphLL):\n", "\n", " # ... missing code ...\n", "\n", " def BFSvisit(self, root):\n", " if root in self.graph():\n", " Q = deque()\n", " Q.append(root)\n", " #visited is a set of visited nodes\n", " visited = set()\n", " visited.add(root)\n", " while len(Q) > 0:\n", " curNode = Q.popleft()\n", " outGoingEdges = self.adjacentEdge(curNode, incoming = False)\n", " nextNodes = []\n", " if outGoingEdges != None:\n", " #remember that self.adjacentEdge returns:\n", " #[('node1','node2', weight1), ...('node1', 'nodeX', weightX)]\n", " nextNodes = [x[1] for x in outGoingEdges]\n", " print(\"From {}:\".format(curNode))\n", " for nextNode in nextNodes:\n", " if nextNode not in visited:\n", " Q.append(nextNode)\n", " visited.add(nextNode)\n", " print(\"\\t --> {}\".format(nextNode ))\n", " \n", "\n", "if __name__ == \"__main__\":\n", " G = DiGraphLLAnalyzer()\n", " for i in range(1,10):\n", " G.insertNode(\"Node_\" + str(i))\n", " \n", " G.insertEdge(\"Node_1\", \"Node_2\",1)\n", " G.insertEdge(\"Node_2\", \"Node_1\",1)\n", " G.insertEdge(\"Node_1\", \"Node_3\",1)\n", " G.insertEdge(\"Node_1\", \"Node_5\",1)\n", " G.insertEdge(\"Node_2\", \"Node_3\",1)\n", " G.insertEdge(\"Node_2\", \"Node_5\",1)\n", " G.insertEdge(\"Node_3\", \"Node_4\",1)\n", " G.insertEdge(\"Node_3\", \"Node_6\",1)\n", " G.insertEdge(\"Node_5\", \"Node_3\",1)\n", " G.insertEdge(\"Node_5\", \"Node_5\",1)\n", " G.insertEdge(\"Node_6\", \"Node_4\",1)\n", " G.insertEdge(\"Node_6\", \"Node_6\",1)\n", " G.insertEdge(\"Node_7\", \"Node_5\",1)\n", " G.insertEdge(\"Node_5\", \"Node_8\",1)\n", " G.insertEdge(\"Node_8\", \"Node_7\",1)\n", " G.insertEdge(\"Node_9\", \"Node_2\",1)\n", "\n", " print(\"BFS(Node_1):\") \n", " G.BFSvisit(\"Node_1\")\n", " print(\"\\n------------\")\n", " print(\"\\nNow BFS(Node_5):\")\n", " G.BFSvisit(\"Node_5\")\n", " print(\"\\n------------\")\n", " print(\"\\nNow BFS(Node_9):\")\n", " G.BFSvisit(\"Node_9\") \n", " print(\"\\n------------\") " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The created graph is (do not look at the weights): \n", "\n", "![](images/testgraph.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [DiGraphLLAnalyzer4.py](data_structures/DiGraphLLAnalyzer4.py)\n", "\n", "**Also in this case Node_9 is not visited! (if you start from Node_1)**\n", "\n", "To visit all the nodes of the tree and get a forest of BFS trees we need to modify the code as follows:" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "BFS(Node_1):\n", "Starting from Node_1\n", "From Node_1:\n", "\t --> Node_2\n", "\t --> Node_3\n", "\t --> Node_5\n", "From Node_2:\n", "From Node_3:\n", "\t --> Node_4\n", "\t --> Node_6\n", "From Node_5:\n", "\t --> Node_8\n", "From Node_4:\n", "From Node_6:\n", "From Node_8:\n", "\t --> Node_7\n", "From Node_7:\n", "Starting from Node_2\n", "From Node_2:\n", "\t --> Node_1\n", "\t --> Node_3\n", "\t --> Node_5\n", "From Node_1:\n", "From Node_3:\n", "\t --> Node_4\n", "\t --> Node_6\n", "From Node_5:\n", "\t --> Node_8\n", "From Node_4:\n", "From Node_6:\n", "From Node_8:\n", "\t --> Node_7\n", "From Node_7:\n", "Starting from Node_3\n", "From Node_3:\n", "\t --> Node_4\n", "\t --> Node_6\n", "From Node_4:\n", "From Node_6:\n", "Starting from Node_4\n", "From Node_4:\n", "Starting from Node_5\n", "From Node_5:\n", "\t --> Node_3\n", "\t --> Node_8\n", "From Node_3:\n", "\t --> Node_4\n", "\t --> Node_6\n", "From Node_8:\n", "\t --> Node_7\n", "From Node_4:\n", "From Node_6:\n", "From Node_7:\n", "Starting from Node_6\n", "From Node_6:\n", "\t --> Node_4\n", "From Node_4:\n", "Starting from Node_7\n", "From Node_7:\n", "\t --> Node_5\n", "From Node_5:\n", "\t --> Node_3\n", "\t --> Node_8\n", "From Node_3:\n", "\t --> Node_4\n", "\t --> Node_6\n", "From Node_8:\n", "From Node_4:\n", "From Node_6:\n", "Starting from Node_8\n", "From Node_8:\n", "\t --> Node_7\n", "From Node_7:\n", "\t --> Node_5\n", "From Node_5:\n", "\t --> Node_3\n", "From Node_3:\n", "\t --> Node_4\n", "\t --> Node_6\n", "From Node_4:\n", "From Node_6:\n", "Starting from Node_9\n", "From Node_9:\n", "\t --> Node_2\n", "From Node_2:\n", "\t --> Node_1\n", "\t --> Node_3\n", "\t --> Node_5\n", "From Node_1:\n", "From Node_3:\n", "\t --> Node_4\n", "\t --> Node_6\n", "From Node_5:\n", "\t --> Node_8\n", "From Node_4:\n", "From Node_6:\n", "From Node_8:\n", "\t --> Node_7\n", "From Node_7:\n", "\n", "------------\n", "\n", "Now BFS(Node_5):\n", "\n", "------------\n", "\n", "Now BFS(Node_9):\n", "\n", "------------\n" ] } ], "source": [ "from collections import deque\n", "\n", "\n", "class DiGraphLLAnalyzer(DiGraphLL):\n", "\n", " # ... missing code ...\n", " \n", " def BFSvisit(self, root, target):\n", " len_path = 0\n", " \n", " if root in self.graph():\n", " Q = deque()\n", " Q.append(root)\n", " #visited is a set of visited nodes\n", " visited = set()\n", " if root == target:\n", " return len_path\n", " visited.add(root)\n", " while len(Q) > 0:\n", " curNode = Q.popleft()\n", " len_path = len_path + 1\n", " outGoingEdges = self.adjacentEdge(curNode, incoming = False)\n", " nextNodes = []\n", " if outGoingEdges != None:\n", " #remember that self.adjacentEdge returns:\n", " #[('node1','node2', weight1), ...('node1', 'nodeX', weightX)]\n", " nextNodes = [x[1] for x in outGoingEdges]\n", " if target in nextNodes:\n", " return len_path + 1\n", " print(\"From {}:\".format(curNode))\n", " for nextNode in nextNodes:\n", " if nextNode not in visited:\n", " Q.append(nextNode)\n", " visited.add(nextNode)\n", " print(\"\\t --> {}\".format(nextNode ))\n", " return None \n", " \n", " def BFS(self, root):\n", " print(\"Starting from {}\".format(root))\n", " visited = set()\n", " visited.add(root)\n", " self.BFSvisit(root,visited)\n", " for node in self.nodes():\n", " if node not in visited:\n", " print(\"Starting from {}\".format(node)) \n", " self.BFSvisit(node,visited)\n", "\n", "\n", "if __name__ == \"__main__\":\n", " G = DiGraphLLAnalyzer()\n", " for i in range(1,10):\n", " G.insertNode(\"Node_\" + str(i))\n", " \n", " G.insertEdge(\"Node_1\", \"Node_2\",1)\n", " G.insertEdge(\"Node_2\", \"Node_1\",1)\n", " G.insertEdge(\"Node_1\", \"Node_3\",1)\n", " G.insertEdge(\"Node_1\", \"Node_5\",1)\n", " G.insertEdge(\"Node_2\", \"Node_3\",1)\n", " G.insertEdge(\"Node_2\", \"Node_5\",1)\n", " G.insertEdge(\"Node_3\", \"Node_4\",1)\n", " G.insertEdge(\"Node_3\", \"Node_6\",1)\n", " G.insertEdge(\"Node_5\", \"Node_3\",1)\n", " G.insertEdge(\"Node_5\", \"Node_5\",1)\n", " G.insertEdge(\"Node_6\", \"Node_4\",1)\n", " G.insertEdge(\"Node_6\", \"Node_6\",1)\n", " G.insertEdge(\"Node_7\", \"Node_5\",1)\n", " G.insertEdge(\"Node_5\", \"Node_8\",1)\n", " G.insertEdge(\"Node_8\", \"Node_7\",1)\n", " G.insertEdge(\"Node_9\", \"Node_2\",1)\n", " \n", " print(\"BFS(Node_1):\") \n", " G.BFS(\"Node_1\")\n", " print(\"\\n------------\")\n", " print(\"\\nNow BFS(Node_5):\")\n", " #G.BFS(\"Node_5\")\n", " print(\"\\n------------\")\n", " print(\"\\nNow BFS(Node_9):\")\n", " #G.BFS(\"Node_9\")\n", " print(\"\\n------------\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [DiGraphLLAnalyzer5.py](data_structures/DiGraphLLAnalyzer5.py)\n", "\n", "### Exercise\n", "\n", "3. Write a method ```shortestPath(self, node1, node2)``` that finds the shortest path between two nodes ```node1``` and ```node2``` (if it exists) ignoring any weight on the edges. \n", "\n", "Hint: modify the BFS in such a way at it stops when the second node is reached (or when no more nodes can be explored). Apply this code twice, that is once from node1-->node2 and the other from node2-->node1 to find the shortest of the two. You need to change the code in order to obtain the path.\n", "\n", "Structuring the code (hints):\n", "\n", "a. Implement a method ```shortestPath(self,node1,node2)``` that finds and prints the shortest path between node1 and node2 (testing both node1 --> node2 and node2 --> node1 and returning the shortest of the two) calling the other two functions; \n", "\n", "b. Implement a method ```path = findShortestPath(self,node1,node2)``` that returns the path going from node1 to node2 if this exist. **Note:** in my implementation, path is a list starting with the terminal node \\[*node2, nodex, nodexx, node1*\\] and ending with the first node of the sought path. The idea behind the implementation of this method is to store somewhere (like in a dictionary) the parent of each visited node and then produce the list above going backwards from node2 up to node1.\n", "\n", "c. Implement a method ```printPath(self,path)``` that gets a path as specified above and prints it out like: \n", "\n", "```\n", "Shortest path between: Node_1 and Node_6\n", "Node_1 --> Node_3\n", "\tNode_3 --> Node_6\n", "``` \n", "\n", "\n", "Test the code with the following two graphs G and G1 (checking them with the pictures below):\n", "\n", "```python\n", "G = DiGraphLLAnalyzer()\n", "G1 = DiGraphLLAnalyzer()\n", "for i in range(1,10):\n", " G.insertNode(\"Node_\" + str(i))\n", " G1.insertNode(\"Node_\" + str(i))\n", "\n", "G.insertEdge(\"Node_1\", \"Node_2\",1)\n", "G.insertEdge(\"Node_2\", \"Node_1\",1)\n", "G.insertEdge(\"Node_1\", \"Node_3\",1)\n", "G.insertEdge(\"Node_1\", \"Node_5\",1)\n", "G.insertEdge(\"Node_2\", \"Node_3\",1)\n", "G.insertEdge(\"Node_2\", \"Node_5\",1)\n", "G.insertEdge(\"Node_3\", \"Node_4\",1)\n", "G.insertEdge(\"Node_3\", \"Node_6\",1)\n", "G.insertEdge(\"Node_5\", \"Node_3\",1)\n", "G.insertEdge(\"Node_5\", \"Node_5\",1)\n", "G.insertEdge(\"Node_6\", \"Node_4\",1)\n", "G.insertEdge(\"Node_6\", \"Node_6\",1)\n", "G.insertEdge(\"Node_7\", \"Node_5\",1)\n", "G.insertEdge(\"Node_5\", \"Node_8\",1)\n", "G.insertEdge(\"Node_8\", \"Node_7\",1)\n", "G.insertEdge(\"Node_9\", \"Node_2\",1)\n", "#Graph G1\n", "G1.insertEdge(\"Node_1\" ,\"Node_2\", 1)\n", "G1.insertEdge(\"Node_1\" ,\"Node_4\", 1)\n", "G1.insertEdge(\"Node_1\" ,\"Node_6\", 1)\n", "G1.insertEdge(\"Node_1\" ,\"Node_7\", 1)\n", "G1.insertEdge(\"Node_2\" ,\"Node_7\", 1)\n", "G1.insertEdge(\"Node_3\" ,\"Node_4\", 1)\n", "G1.insertEdge(\"Node_5\" ,\"Node_4\", 1)\n", "G1.insertEdge(\"Node_6\" ,\"Node_5\", 1)\n", "G1.insertEdge(\"Node_6\" ,\"Node_8\", 1)\n", "G1.insertEdge(\"Node_7\" ,\"Node_9\", 1)\n", "G1.insertEdge(\"Node_8\" ,\"Node_9\", 1)\n", "\n", "G.shortestPath(\"Node_1\",\"Node_6\") \n", "G.shortestPath(\"Node_8\",\"Node_9\")\n", "G.shortestPath(\"Node_8\",\"Node_4\")\n", "\n", "print(\"\\n\\nG1:\")\n", "G1.shortestPath(\"Node_8\",\"Node_4\")\n", "G1.shortestPath(\"Node_9\",\"Node_1\")\n", "G1.shortestPath(\"Node_4\",\"Node_1\")\n", "```\n", "\n", "![](images/g1_g2.png)\n", "\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Shortest path between: Node_1 and Node_6\n", "Node_1 --> Node_3\n", "\tNode_3 --> Node_6\n", "Shortest path between: Node_9 and Node_8\n", "Node_9 --> Node_2\n", "\tNode_2 --> Node_5\n", "\t\tNode_5 --> Node_8\n", "Shortest path between: Node_8 and Node_4\n", "Node_8 --> Node_7\n", "\tNode_7 --> Node_5\n", "\t\tNode_5 --> Node_3\n", "\t\t\tNode_3 --> Node_4\n", "Shortest path between: Node_9 and Node_4\n", "Node_9 --> Node_2\n", "\tNode_2 --> Node_3\n", "\t\tNode_3 --> Node_4\n", "\n", "\n", "G1:\n", "No paths exist between Node_8 and Node_4\n", "Shortest path between: Node_1 and Node_9\n", "Node_1 --> Node_7\n", "\tNode_7 --> Node_9\n", "Shortest path between: Node_1 and Node_4\n", "Node_1 --> Node_4\n" ] } ], "source": [ "from collections import deque\n", "\n", "class DiGraphLL:\n", "\n", " # ... missing code ...\n", "\n", "class DiGraphLLAnalyzer(DiGraphLL):\n", "\n", " # ... missing code ...\n", "\n", " def findShortestPath(self, node1, node2):\n", " Q = deque()\n", " Q.append(node1)\n", " visited = set()\n", " #visited is a set of visited nodes\n", " visited.add(node1)\n", " #for each node (apart from node1)\n", " #this will store the node that led to it\n", " #eg. if path is node1--> node3-->node2\n", " # previous[node2] = node3\n", " # previous[node3] = node1\n", " previous = dict()\n", " found = False\n", " while len(Q) > 0 and not found:\n", " curNode = Q.popleft()\n", " \n", " outGoingEdges = self.adjacentEdge(curNode, incoming = False)\n", " nextNodes = []\n", " if outGoingEdges != None:\n", " #remember that self.adjacentEdge returns:\n", " #[('node1','node2', weight1), ...('node1', 'nodeX', weightX)]\n", " nextNodes = [x[1] for x in outGoingEdges]\n", " \n", " for nextNode in nextNodes:\n", " if nextNode not in visited:\n", " if nextNode == node2:\n", " previous[node2] = curNode\n", " found = True\n", " else:\n", " Q.append(nextNode)\n", " visited.add(nextNode)\n", " previous[nextNode] = curNode\n", " \n", "\n", " #if node2 is in the previous dictionary:\n", " ret = [node2]\n", " p = previous.get(node2, None)\n", " \n", " while p != None:\n", " ret.append(p)\n", " p = previous.get(p,None)\n", " \n", " #note that ret has the reverseof the path\n", " #[node2, node3, node1]\n", " #or just [node2] if not path exists\n", " return ret\n", " \n", " def printPath(self,path):\n", " L = len(path)\n", " print(\"Shortest path between: {} and {}\".format(path[-1],\n", " path[0])\n", " )\n", " for i in range(len(path) -1,0,-1):\n", " print(\"{}{} --> {}\".format(\"\\t\"*(L-i-1),\n", " path[i],\n", " path[i-1]))\n", " \n", " def shortestPath(self, node1, node2):\n", " nodes = self.nodes()\n", " if node1 not in nodes or node2 not in nodes:\n", " \"\"\"one of the two is not in the graph\"\"\"\n", " return None \n", " else:\n", " if node1 == node2:\n", " \"\"\"the path is just the node\"\"\"\n", " return node1\n", " else:\n", " \n", " path = self.findShortestPath(node1,node2)\n", " path1 = self.findShortestPath(node2,node1)\n", " if path == [node2] and path1 == [node1]:\n", " print(\"No paths exist between {} and {}\".format(node1,\n", " node2))\n", " else:\n", " L = len(nodes)\n", " L1 = L\n", " if path != [node2]:\n", " L = len(path)\n", " if path1 != [node1]:\n", " L1 = len(path1)\n", "\n", " if L < L1:\n", " \"\"\"print first path\"\"\"\n", " self.printPath(path)\n", "\n", " else:\n", " \"\"\"print second path\"\"\"\n", " self.printPath(path1)\n", " \n", "\n", "if __name__ == \"__main__\":\n", " G = DiGraphLLAnalyzer()\n", " G1 = DiGraphLLAnalyzer()\n", " for i in range(1,10):\n", " G.insertNode(\"Node_\" + str(i))\n", " G1.insertNode(\"Node_\" + str(i))\n", " \n", " G.insertEdge(\"Node_1\", \"Node_2\",1)\n", " G.insertEdge(\"Node_2\", \"Node_1\",1)\n", " G.insertEdge(\"Node_1\", \"Node_3\",1)\n", " G.insertEdge(\"Node_1\", \"Node_5\",1)\n", " G.insertEdge(\"Node_2\", \"Node_3\",1)\n", " G.insertEdge(\"Node_2\", \"Node_5\",1)\n", " G.insertEdge(\"Node_3\", \"Node_4\",1)\n", " G.insertEdge(\"Node_3\", \"Node_6\",1)\n", " G.insertEdge(\"Node_5\", \"Node_3\",1)\n", " G.insertEdge(\"Node_5\", \"Node_5\",1)\n", " G.insertEdge(\"Node_6\", \"Node_4\",1)\n", " G.insertEdge(\"Node_6\", \"Node_6\",1)\n", " G.insertEdge(\"Node_7\", \"Node_5\",1)\n", " G.insertEdge(\"Node_5\", \"Node_8\",1)\n", " G.insertEdge(\"Node_8\", \"Node_7\",1)\n", " G.insertEdge(\"Node_9\", \"Node_2\",1)\n", " #Graph G1\n", " G1.insertEdge(\"Node_1\" ,\"Node_2\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_6\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_7\", 1)\n", " G1.insertEdge(\"Node_2\" ,\"Node_7\", 1)\n", " G1.insertEdge(\"Node_3\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_5\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_6\" ,\"Node_5\", 1)\n", " G1.insertEdge(\"Node_6\" ,\"Node_8\", 1)\n", " G1.insertEdge(\"Node_7\" ,\"Node_9\", 1)\n", " G1.insertEdge(\"Node_8\" ,\"Node_9\", 1)\n", "\n", " G.shortestPath(\"Node_1\",\"Node_6\") \n", " G.shortestPath(\"Node_8\",\"Node_9\")\n", " G.shortestPath(\"Node_8\",\"Node_4\")\n", " G.shortestPath(\"Node_9\",\"Node_4\") \n", " \n", " print(\"\\n\\nG1:\")\n", " G1.shortestPath(\"Node_8\",\"Node_4\")\n", " G1.shortestPath(\"Node_9\",\"Node_1\")\n", " G1.shortestPath(\"Node_4\",\"Node_1\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "![](images/g1_g2.png)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [DiGraphLLAnalyzerEx3.py](data_structures/DiGraphLLAnalyzerEx3.py)\n", "
\n", "\n", "## Exercise\n", "\n", "4. Write a method ```isCyclic(self)``` that identifies if a direct graph (implemented as a ```DiGraphLLAnalyzer```) is cyclic or not (i.e. returns True for a graph with cycles and False for a graph without cycles). \n", "\n", "**Hint**: you can perform a **recursive DFS** and check if any edge that is being explored is actually a back-edge (i.e. an edge that points back to one of the nodes present in the recursion-stack of the nodes found so far). To do that you have to store a set of nodes that are along the path that is traversed recursively and check if the nodes that you are adding to the path are already present in this set of nodes).\n", "\n", "Test the code with the following three graphs:\n", "\n", "```python\n", "G = DiGraphLLAnalyzer()\n", " G1 = DiGraphLLAnalyzer()\n", " G2 = DiGraphLLAnalyzer()\n", " for i in range(1,10):\n", " G.insertNode(\"Node_\" + str(i))\n", " G1.insertNode(\"Node_\" + str(i))\n", " if i<9:\n", " G2.insertNode(\"Node_\" + str(i))\n", " \n", " G.insertEdge(\"Node_1\", \"Node_2\",1)\n", " G.insertEdge(\"Node_2\", \"Node_1\",1)\n", " G.insertEdge(\"Node_1\", \"Node_3\",1)\n", " G.insertEdge(\"Node_1\", \"Node_5\",1)\n", " G.insertEdge(\"Node_2\", \"Node_3\",1)\n", " G.insertEdge(\"Node_2\", \"Node_5\",1)\n", " G.insertEdge(\"Node_3\", \"Node_4\",1)\n", " G.insertEdge(\"Node_3\", \"Node_6\",1)\n", " G.insertEdge(\"Node_5\", \"Node_3\",1)\n", " G.insertEdge(\"Node_5\", \"Node_5\",1)\n", " G.insertEdge(\"Node_6\", \"Node_4\",1)\n", " G.insertEdge(\"Node_6\", \"Node_6\",1)\n", " G.insertEdge(\"Node_7\", \"Node_5\",1)\n", " G.insertEdge(\"Node_5\", \"Node_8\",1)\n", " G.insertEdge(\"Node_8\", \"Node_7\",1)\n", " G.insertEdge(\"Node_9\", \"Node_2\",1)\n", " \n", " #Graph G1\n", " G1.insertEdge(\"Node_1\" ,\"Node_2\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_6\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_7\", 1)\n", " G1.insertEdge(\"Node_2\" ,\"Node_7\", 1)\n", " G1.insertEdge(\"Node_3\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_5\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_6\" ,\"Node_5\", 1)\n", " G1.insertEdge(\"Node_6\" ,\"Node_8\", 1)\n", " G1.insertEdge(\"Node_7\" ,\"Node_9\", 1)\n", " G1.insertEdge(\"Node_8\" ,\"Node_9\", 1)\n", " \n", " #Graph G2\n", " G2.insertEdge(\"Node_1\" ,\"Node_2\", 1)\n", " G2.insertEdge(\"Node_2\" ,\"Node_3\", 1)\n", " G2.insertEdge(\"Node_2\" ,\"Node_4\", 1)\n", " G2.insertEdge(\"Node_2\" ,\"Node_5\", 1)\n", " G2.insertEdge(\"Node_6\" ,\"Node_2\", 1)\n", " G2.insertEdge(\"Node_6\" ,\"Node_7\",1)\n", " G2.insertEdge(\"Node_8\" ,\"Node_7\", 1)\n", " G2.insertEdge(\"Node_8\" ,\"Node_4\", 1)\n", " G2.insertEdge(\"Node_7\" ,\"Node_5\", 1)\n", " \n", " print(\"Is G cyclic? {}\".format(G.isCyclic()))\n", " print(\"\\nG1:\")\n", " print(\"Is G1 cyclic? {}\".format(G1.isCyclic()))\n", " print(\"\\nG2:\")\n", " print(\"Is G2 cyclic? {}\".format(G2.isCyclic()))\n", "```\n", "\n", "\n", "Here are the graphs:\n", "\n", "![](images/3g.png)\n", "\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "from collections import deque\n", "\n", "class DiGraphLL:\n", "\n", " # ... missing code ...\n", "\n", "class DiGraphLLAnalyzer(DiGraphLL):\n", "\n", " # ... missing code ...\n", " \n", " def testCyclic(self, root, visited, recStack = set()):\n", " visited.add(root)\n", " recStack.add(root)\n", " ## Uncomment print lines to see what is going on\n", " print(\"CURRENT: {}\".format(root))\n", " print(\"\\tStack:{}\".format(recStack))\n", " outGoingEdges = self.adjacentEdge(root, incoming = False)\n", " nextNodes = []\n", " if len(outGoingEdges) > 0:\n", " nextNodes = [x[1] for x in outGoingEdges]\n", " print(\"\\tNEXTnodes:{}\".format(nextNodes))\n", " for nextN in nextNodes:\n", " if nextN not in visited:\n", " print(\"\\tNext:{}\".format(nextN))\n", " if self.testCyclic(nextN,visited,recStack) == True:\n", " return True\n", " else:\n", " if nextN in recStack:\n", " print(\"\\t{} --> {} closes cycle\".format(root,nextN))\n", " return True\n", " \n", " #when the recursion ends\n", " #we remove the element from the stack\n", " recStack.pop()\n", " return False\n", " \n", " def isCyclic(self):\n", " visited = set()\n", " ret = False\n", " stack = set()\n", " for node in self.nodes():\n", " if node not in visited:\n", " ret = ret or self.testCyclic(node, visited, stack)\n", " return ret\n", " \n", "if __name__ == \"__main__\":\n", " G = DiGraphLLAnalyzer()\n", " G1 = DiGraphLLAnalyzer()\n", " G2 = DiGraphLLAnalyzer()\n", " for i in range(1,10):\n", " G.insertNode(\"Node_\" + str(i))\n", " G1.insertNode(\"Node_\" + str(i))\n", " if i<9:\n", " G2.insertNode(\"Node_\" + str(i))\n", " \n", " G.insertEdge(\"Node_1\", \"Node_2\",1)\n", " G.insertEdge(\"Node_2\", \"Node_1\",1)\n", " G.insertEdge(\"Node_1\", \"Node_3\",1)\n", " G.insertEdge(\"Node_1\", \"Node_5\",1)\n", " G.insertEdge(\"Node_2\", \"Node_3\",1)\n", " G.insertEdge(\"Node_2\", \"Node_5\",1)\n", " G.insertEdge(\"Node_3\", \"Node_4\",1)\n", " G.insertEdge(\"Node_3\", \"Node_6\",1)\n", " G.insertEdge(\"Node_5\", \"Node_3\",1)\n", " G.insertEdge(\"Node_5\", \"Node_5\",1)\n", " G.insertEdge(\"Node_6\", \"Node_4\",1)\n", " G.insertEdge(\"Node_6\", \"Node_6\",1)\n", " G.insertEdge(\"Node_7\", \"Node_5\",1)\n", " G.insertEdge(\"Node_5\", \"Node_8\",1)\n", " G.insertEdge(\"Node_8\", \"Node_7\",1)\n", " G.insertEdge(\"Node_9\", \"Node_2\",1)\n", " \n", " #Graph G1\n", " G1.insertEdge(\"Node_1\" ,\"Node_2\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_6\", 1)\n", " G1.insertEdge(\"Node_1\" ,\"Node_7\", 1)\n", " G1.insertEdge(\"Node_2\" ,\"Node_7\", 1)\n", " G1.insertEdge(\"Node_3\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_5\" ,\"Node_4\", 1)\n", " G1.insertEdge(\"Node_6\" ,\"Node_5\", 1)\n", " G1.insertEdge(\"Node_6\" ,\"Node_8\", 1)\n", " G1.insertEdge(\"Node_7\" ,\"Node_9\", 1)\n", " G1.insertEdge(\"Node_8\" ,\"Node_9\", 1)\n", " \n", " #Graph G2\n", " G2.insertEdge(\"Node_1\" ,\"Node_2\", 1)\n", " G2.insertEdge(\"Node_2\" ,\"Node_3\", 1)\n", " G2.insertEdge(\"Node_2\" ,\"Node_4\", 1)\n", " G2.insertEdge(\"Node_2\" ,\"Node_5\", 1)\n", " G2.insertEdge(\"Node_6\" ,\"Node_2\", 1)\n", " G2.insertEdge(\"Node_6\" ,\"Node_7\",1)\n", " G2.insertEdge(\"Node_8\" ,\"Node_7\", 1)\n", " G2.insertEdge(\"Node_8\" ,\"Node_4\", 1)\n", " G2.insertEdge(\"Node_7\" ,\"Node_5\", 1)\n", " \n", " print(\"Is G cyclic? {}\".format(G.isCyclic()))\n", " print(\"\\nG1:\")\n", " print(\"Is G1 cyclic? {}\".format(G1.isCyclic()))\n", " print(\"\\nG2:\")\n", " print(\"Is G2 cyclic? {}\".format(G2.isCyclic()))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [DiGraphLLAnalyzerEx4.py](data_structures/DiGraphLLAnalyzerEx4.py)\n", "
" ] } ], "metadata": { "celltoolbar": "Edit Metadata", "kernelspec": { "display_name": "3.10.14", "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.10.14" } }, "nbformat": 4, "nbformat_minor": 2 }