{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Module 2, Practical 8\n", "\n", "In this practical we will keep working with data structures. In particular, we will see a very important and quite complex data structure called **graph**. \n", "\n", "## Graphs\n", "\n", "Graphs are mathematical structures made of two key elements: **nodes** (or **vertices**) and **edges**. \n", "Nodes are objects that we want to represent and edges are relationships among these 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 most often represented as circles, while edges (relationships) are represented by lines/arrows connecting the nodes. An example follows:\n", "\n", "![](images/graph_1.png)\n", "\n", "\n", "Relations represented by edges can be **symmetric** (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. When edges are symmetric the graph is **undirected**. \n", "\n", "If relationships are **not symmetric** (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 **directed**.\n", "\n", "Some terminology (from the lecture):\n", "\n", "![](images/graphTerms.png)\n", "\n", "The **degree** of a node is the number of connections 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" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Graph ADT\n", "\n", "Graphs are dynamic data structures in which nodes and edges can be added/removed. The description of the *Graph* Abstract Data Type follows (from the lecture): \n", "\n", "![](images/graphADT.png)\n", "\n", "This is the most general definition, as in some cases nodes and edges can only be added and not removed.\n", "\n", "There are two classic ways of implementing a Graph: **adjacency matrices** and **linked lists**. \n", "\n", "## Implementation as adjacency matrix\n", "\n", "A square matrix $G$ having the size $N \\times N$ where $N$ is the number of nodes, is used to represent every possible connection among the nodes of the graph. In particular $G[i,j] = 1$ if the graph has an edge connecting node $i$ to node $j$, if that is not the case $G[i,j] = 0$. \n", "\n", "An example of graph as adjacency matrix follows (from lecture):\n", "\n", "![](images/adjacency.png)\n", "\n", "This representation of a graph has both advantages and disadvantages:\n", "\n", "* it is quite *flexible* as it is possible to put weights on the values of the matrix instead of only 0 and 1;\n", "\n", "* it is quite *quick to check the presence of an edge* (both ways!): this just requires a lookup in the matrix G;\n", "\n", "* it *uses a lot of space* and most of the values often are 0 (sparse matrix, a lot of space is therefore wasted);\n", "\n", "* in undirected graphs, the matrix is symmetric therefore *half of the space could be saved*.\n", "\n", "Let's see how we can implement a directed weighted graph as an **adjacency matrix** in Python.\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\tNode_1\tNode_2\tNode_3\tNode_4\tNode_5\tNode_6\n", "Node_1\t0\t0.5\t0\t0\t0\t1\n", "Node_2\t0\t0\t0.5\t0\t0\t1\n", "Node_3\t0\t0\t0\t0.5\t0\t1\n", "Node_4\t0\t0\t0\t0\t0.5\t1\n", "Node_5\t0.5\t0\t0\t0\t0\t1\n", "Node_6\t0\t0\t0\t0\t0\t1\n", "\n", "Size is: 7\n", "Nodes: ['Node_1', 'Node_2', 'Node_3', 'Node_4', 'Node_5', 'Node_6', 'Node_7']\n", "\n", "Matrix:\n", "\tNode_1\tNode_2\tNode_3\tNode_4\tNode_5\tNode_6\tNode_7\n", "Node_1\t0\t0.5\t0\t0\t0\t1\t-1\n", "Node_2\t0\t0\t0.5\t0\t0\t1\t-2\n", "Node_3\t0\t0\t0\t0.5\t0\t1\t0\n", "Node_4\t0\t0\t0\t0\t0.5\t1\t0\n", "Node_5\t0.5\t0\t0\t0\t0\t1\t-5\n", "Node_6\t0\t0\t0\t0\t0\t1\t0\n", "Node_7\t0\t-2\t-3\t0\t0\t0\t0\n", "\n", "\tNode_1\tNode_2\tNode_3\tNode_4\tNode_5\tNode_6\n", "Node_1\t0\t0.5\t0\t0\t0\t1\n", "Node_2\t0\t0\t0.5\t0\t0\t1\n", "Node_3\t0\t0\t0\t0.5\t0\t1\n", "Node_4\t0\t0\t0\t0\t0.5\t1\n", "Node_5\t0.5\t0\t0\t0\t0\t1\n", "Node_6\t0\t0\t0\t0\t0\t1\n", "\n" ] } ], "source": [ "class DiGraphAsAdjacencyMatrix:\n", " def __init__(self):\n", " self.__nodes = list() # a set would be better, but we need an index to define \n", " # the adjacency matrix\n", " self.__matrix = list()\n", " \n", " def __len__(self):\n", " \"\"\"gets the number of nodes\"\"\"\n", " return len(self.__nodes)\n", " \n", " def nodes(self):\n", " return self.__nodes\n", " def matrix(self):\n", " return self.__matrix\n", " \n", " def __str__(self):\n", " header = \"\\t\".join([n for n in self.__nodes])\n", " data = \"\"\n", " for i in range(0,len(self.__matrix)):\n", " data += str(self.__nodes[i]) + \"\\t\" \n", " data += \"\\t\".join([str(x) for x in self.__matrix[i]]) + \"\\n\"\n", "\n", " return \"\\t\"+ header +\"\\n\" + data\n", " \n", " def insertNode(self, node):\n", " #add the node if not there already.\n", " if node not in self.__nodes:\n", " self.__nodes.append(node)\n", " #add a row and a column of zeros in the matrix\n", " if len(self.__matrix) == 0:\n", " #first node\n", " self.__matrix = [[0]]\n", " else:\n", " N = len(self.__nodes)\n", " for row in self.__matrix:\n", " row.append(0)\n", " self.__matrix.append([0 for x in range(N)])\n", " \n", " def insertEdge(self, node1, node2, weight):\n", " i = -1\n", " j = -1\n", " if node1 in self.__nodes:\n", " i = self.__nodes.index(node1)\n", " if node2 in self.__nodes:\n", " j = self.__nodes.index(node2)\n", " if i != -1 and j != -1:\n", " self.__matrix[i][j] = weight\n", " \n", " def deleteEdge(self, node1,node2):\n", " \"\"\"removing an edge means setting its\n", " corresponding slot in the matrix to 0\"\"\"\n", " i = -1\n", " j = -1\n", " if node1 in self.__nodes:\n", " i = self.__nodes.index(node1)\n", " if node2 in self.__nodes:\n", " j = self.__nodes.index(node2)\n", " if i != -1 and j != -1:\n", " self.__matrix[i][j] = 0\n", " \n", " def deleteNode(self, node):\n", " \"\"\"removing a node means removing\n", " its corresponding row and column in the matrix\"\"\"\n", " i = -1\n", "\n", " if node in self.__nodes:\n", " i = self.__nodes.index(node)\n", " #print(\"Removing {} at index {}\".format(node, i))\n", " if node != -1:\n", " self.__matrix.pop(i)\n", " for row in self.__matrix:\n", " row.pop(i)\n", " self.__nodes.pop(i)\n", " \n", " def adjacent(self, node):\n", " \"\"\"Your treat! (see exercise 1)\"\"\"\n", " \n", " def edges(self):\n", " \"\"\"Your treat! (see exercise1). Returns all the edges\"\"\"\n", " \n", "if __name__ == \"__main__\":\n", " G = DiGraphAsAdjacencyMatrix()\n", " \n", " for i in range(6):\n", " n = \"Node_{}\".format(i+1)\n", " G.insertNode(n)\n", "\n", " for i in range(0,4):\n", " n = \"Node_\" + str(i+1)\n", " six = \"Node_6\"\n", " n_plus = \"Node_\" + str((i+2) % 6)\n", " G.insertEdge(n, n_plus,0.5)\n", " G.insertEdge(n, six,1)\n", " G.insertEdge(\"Node_5\", \"Node_1\", 0.5)\n", " G.insertEdge(\"Node_5\", \"Node_6\", 1)\n", " G.insertEdge(\"Node_6\", \"Node_6\", 1)\n", " print(G)\n", " \n", " G.insertNode(\"Node_7\")\n", " G.insertEdge(\"Node_1\", \"Node_7\", -1)\n", " G.insertEdge(\"Node_2\", \"Node_7\", -2)\n", " G.insertEdge(\"Node_5\", \"Node_7\", -5)\n", " G.insertEdge(\"Node_7\", \"Node_2\", -2)\n", " G.insertEdge(\"Node_7\", \"Node_3\", -3)\n", " \n", " print(\"Size is: {}\".format(len(G)))\n", " print(\"Nodes: {}\".format(G.nodes()))\n", " print(\"\\nMatrix:\")\n", " print(G)\n", " G.deleteNode(\"Node_7\")\n", " G.deleteEdge(\"Node_6\", \"Node_2\")\n", " #no effect, nodes do not exist!\n", " G.insertEdge(\"72\", \"25\",3)\n", " print(G)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The matrix above represents the following graph:\n", "\n", "![](images/star.png)\n", "\n", "Download the complete source file: [DiGraphAsAdjacencyMatrix.py](data_structures/DiGraphAsAdjacencyMatrix.py)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercises\n", "\n", "1. Consider the ```DiGraphAsAdjacencyMatrix``` graph class. Add the following methods:\n", "\n", "* ```adjacent(self, node)``` : given a node returns all the nodes connected to it;\n", "\n", "* ```adjacentEdge(self, node, incoming=True)``` : given a node, returns all the nodes close to it (incoming if \"incoming=True\" or outgoing if \"incoming = False\") as a list of triplets (source_node, dest_node, weight);\n", "\n", "* ```edges(self)``` : returns all the edges in the graph as triplets (i,j, weight);\n", "\n", "* ```edgeIn(self, node1, node2)``` : check if the edge node1 --> node2 is in the graph;\n", "\n", "\n", "\n", "\n", "\n", "Test the code with:\n", "\n", "```python\n", " G = DiGraphAsAdjacencyMatrix()\n", " for i in range(6):\n", " n = \"Node_{}\".format(i+1)\n", " G.insertNode(n)\n", "\n", " for i in range(0,4):\n", " n = \"Node_\" + str(i+1)\n", " six = \"Node_6\"\n", " n_plus = \"Node_\" + str((i+2) % 6)\n", " G.insertEdge(n, n_plus,0.5)\n", " G.insertEdge(n, six,1)\n", " G.insertEdge(\"Node_5\", \"Node_1\", 0.5)\n", " G.insertEdge(\"Node_5\", \"Node_6\", 1)\n", " G.insertEdge(\"Node_6\", \"Node_6\", 1)\n", " \n", " \n", " G.insertNode(\"Node_7\")\n", " G.insertEdge(\"Node_1\", \"Node_7\", -1)\n", " G.insertEdge(\"Node_2\", \"Node_7\", -2)\n", " G.insertEdge(\"Node_5\", \"Node_7\", -5)\n", " G.insertEdge(\"Node_7\", \"Node_2\", -2)\n", " G.insertEdge(\"Node_7\", \"Node_3\", -3)\n", " \n", "\n", " G.deleteNode(\"Node_7\")\n", " G.deleteEdge(\"Node_6\", \"Node_2\")\n", " #no effect, nodes do not exist!\n", " G.insertEdge(\"72\", \"25\",3)\n", " print(G)\n", " \n", " print(\"\\nNodes connected to Node_6:\")\n", " print(G.adjacent(\"Node_6\"))\n", " print(\"\\nNodes connected to Node_4:\")\n", " print(G.adjacent(\"Node_4\"))\n", " print(\"\\nNodes connected to Node_3:\")\n", " print(G.adjacent(\"Node_3\"))\n", " print(\"Edges outgoing from Node_3:\")\n", " print(G.adjacentEdge(\"Node_3\", incoming = False))\n", " print(\"Edges incoming to Node_3:\")\n", " print(G.adjacentEdge(\"Node_3\", incoming = True))\n", " print(\"\\nEdges incoming to Node_6:\")\n", " print(G.adjacentEdge(\"Node_6\", incoming = True))\n", " print(\"\\nEdges incoming to Node_743432:\")\n", " print(G.adjacentEdge(\"Node_743432\", incoming = True))\n", " print(\"\\nAll edges:\")\n", "\n", " print(G.edges())\n", " \n", " print(\"\\nIs (Node_4,Node_5) there? {}\".format( G.edgeIn(\"Node_4\",\"Node_5\")))\n", " print(\"Is (Node_4,Node_3) there? {}\".format( G.edgeIn(\"Node_4\",\"Node_3\")))\n", " print(\"Is (Node_3,Node_4) there? {}\".format( G.edgeIn(\"Node_3\",\"Node_4\")))\n", " print(\"Is (Node_6,Node_6) there? {}\".format( G.edgeIn(\"Node_6\",\"Node_6\")))\n", "```\n", "\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\tNode_1\tNode_2\tNode_3\tNode_4\tNode_5\tNode_6\n", "Node_1\t0\t0.5\t0\t0\t0\t1\n", "Node_2\t0\t0\t0.5\t0\t0\t1\n", "Node_3\t0\t0\t0\t0.5\t0\t1\n", "Node_4\t0\t0\t0\t0\t0.5\t1\n", "Node_5\t0.5\t0\t0\t0\t0\t1\n", "Node_6\t0\t0\t0\t0\t0\t1\n", "\n", "\n", "Nodes connected to Node_6:\n", "['Node_6']\n", "\n", "Nodes connected to Node_4:\n", "['Node_5', 'Node_6']\n", "\n", "Nodes connected to Node_3:\n", "['Node_4', 'Node_6']\n", "Edges outgoing from Node_3:\n", "[('Node_3', 'Node_4', 0.5), ('Node_3', 'Node_6', 1)]\n", "Edges incoming to Node_3:\n", "[('Node_2', 'Node_3', 0.5)]\n", "\n", "Edges incoming to Node_6:\n", "[('Node_1', 'Node_6', 1), ('Node_2', 'Node_6', 1), ('Node_3', 'Node_6', 1), ('Node_4', 'Node_6', 1), ('Node_5', 'Node_6', 1), ('Node_6', 'Node_6', 1)]\n", "\n", "Edges incoming to Node_743432:\n", "None\n", "\n", "All edges:\n", "[('Node_1', 'Node_2', 0.5), ('Node_1', 'Node_6', 1), ('Node_2', 'Node_3', 0.5), ('Node_2', 'Node_6', 1), ('Node_3', 'Node_4', 0.5), ('Node_3', 'Node_6', 1), ('Node_4', 'Node_5', 0.5), ('Node_4', 'Node_6', 1), ('Node_5', 'Node_1', 0.5), ('Node_5', 'Node_6', 1), ('Node_6', 'Node_6', 1)]\n", "\n", "Is (Node_4,Node_5) there? True\n", "Is (Node_4,Node_3) there? False\n", "Is (Node_3,Node_4) there? True\n", "Is (Node_6,Node_6) there? True\n" ] } ], "source": [ "class DiGraphAsAdjacencyMatrix:\n", " def __init__(self):\n", " self.__nodes = list()\n", " self.__matrix = list()\n", " \n", " def __len__(self):\n", " \"\"\"gets the number of nodes\"\"\"\n", " return len(self.__nodes)\n", " \n", " def nodes(self):\n", " return self.__nodes\n", " def matrix(self):\n", " return self.__matrix\n", " \n", " def __str__(self):\n", " header = \"\\t\".join([n for n in self.__nodes])\n", " data = \"\"\n", " for i in range(0,len(self.__matrix)):\n", " data += str(self.__nodes[i]) +\"\\t\" + \"\\t\".join([str(x) for x in self.__matrix[i]]) + \"\\n\"\n", "\n", " return \"\\t\"+ header +\"\\n\" + data\n", " \n", " def insertNode(self, node):\n", " #add the node if not there.\n", " if node not in self.__nodes:\n", " self.__nodes.append(node)\n", " #add a row and a column of zeros in the matrix\n", " if len(self.__matrix) == 0:\n", " #first node\n", " self.__matrix = [[0]]\n", " else:\n", " N = len(self.__nodes)\n", " for row in self.__matrix:\n", " row.append(0)\n", " self.__matrix.append([0 for x in range(N)])\n", " \n", " def insertEdge(self, node1, node2, weight):\n", " i = -1\n", " j = -1\n", " if node1 in self.__nodes:\n", " i = self.__nodes.index(node1)\n", " if node2 in self.__nodes:\n", " j = self.__nodes.index(node2)\n", " if i != -1 and j != -1:\n", " self.__matrix[i][j] = weight\n", " \n", " def deleteEdge(self, node1,node2):\n", " \"\"\"removing an edge means to set its\n", " corresponding place in the matrix to 0\"\"\"\n", " i = -1\n", " j = -1\n", " if node1 in self.__nodes:\n", " i = self.__nodes.index(node1)\n", " if node2 in self.__nodes:\n", " j = self.__nodes.index(node2)\n", " if i != -1 and j != -1:\n", " self.__matrix[i][j] = 0\n", " \n", " def deleteNode(self, node):\n", " \"\"\"removing a node means removing\n", " its corresponding row and column in the matrix\"\"\"\n", " i = -1\n", "\n", " if node in self.__nodes:\n", " i = self.__nodes.index(node)\n", " #print(\"Removing {} at index {}\".format(node, i))\n", " if node != -1:\n", " self.__matrix.pop(i)\n", " for row in self.__matrix:\n", " row.pop(i)\n", " self.__nodes.pop(i)\n", " \n", " \n", " def adjacent(self, node):\n", " \"\"\"returns a list of nodes connected to node\"\"\"\n", " ret = []\n", " if node in self.__nodes:\n", " i = self.__nodes.index(node)\n", " for j in range(len(self.__nodes)):\n", " nodeJ = self.__nodes[j]\n", " if self.__matrix[i][j] != 0:\n", " ret.append(nodeJ)\n", "\n", " return ret\n", " \n", " def adjacentEdge(self, node, incoming = True):\n", " \"\"\"\n", " If incoming == False we look at the row of the node,\n", " else at the column. An edge is present if weight\n", " is different from zero\n", " \"\"\"\n", " ret = []\n", " i = -1\n", " if node in self.__nodes:\n", " i = self.__nodes.index(node)\n", " if i != -1:\n", " #if the node is present\n", " if incoming == False:\n", " for e in range(len(self.__matrix[i])):\n", " node2 = self.__nodes[e]\n", " w = self.__matrix[i][e]\n", " if w != 0:\n", " ret.append((node, node2, w)) \n", " else:\n", " for e in range(len(self.__matrix)):\n", " node2 = self.__nodes[e]\n", " w = self.__matrix[e][i]\n", " if w != 0:\n", " ret.append((node2, node, w))\n", " return ret\n", " \n", " def edges(self):\n", " \"\"\"Returns all the edges in the graph as triplets\"\"\"\n", " ret = []\n", " for i in range(len(self.__nodes)):\n", " start = self.__nodes[i]\n", " for j in range(len(self.__nodes)):\n", " end = self.__nodes[j]\n", " w = self.__matrix[i][j]\n", " if w != 0:\n", " ret.append((start, end, w))\n", " return ret\n", " \n", " def edgeIn(self,node1,node2):\n", " \"\"\"\n", " Checks if there exist an edge between node1 and node2\n", " (i.e. weight != 0)\n", " \"\"\"\n", " if node1 in self.__nodes and node2 in self.__nodes:\n", " n1 = self.__nodes.index(node1)\n", " n2 = self.__nodes.index(node2)\n", " w = self.__matrix[n1][n2]\n", " \n", " if w != 0:\n", " return True\n", " else:\n", " return False\n", " \n", " else:\n", " return False\n", " \n", "if __name__ == \"__main__\":\n", " G = DiGraphAsAdjacencyMatrix()\n", " for i in range(6):\n", " n = \"Node_{}\".format(i+1)\n", " G.insertNode(n)\n", "\n", " for i in range(0,4):\n", " n = \"Node_\" + str(i+1)\n", " six = \"Node_6\"\n", " n_plus = \"Node_\" + str((i+2) % 6)\n", " G.insertEdge(n, n_plus,0.5)\n", " G.insertEdge(n, six,1)\n", " G.insertEdge(\"Node_5\", \"Node_1\", 0.5)\n", " G.insertEdge(\"Node_5\", \"Node_6\", 1)\n", " G.insertEdge(\"Node_6\", \"Node_6\", 1)\n", " \n", " G.insertNode(\"Node_7\")\n", " G.insertEdge(\"Node_1\", \"Node_7\", -1)\n", " G.insertEdge(\"Node_2\", \"Node_7\", -2)\n", " G.insertEdge(\"Node_5\", \"Node_7\", -5)\n", " G.insertEdge(\"Node_7\", \"Node_2\", -2)\n", " G.insertEdge(\"Node_7\", \"Node_3\", -3)\n", "\n", " G.deleteNode(\"Node_7\")\n", " G.deleteEdge(\"Node_6\", \"Node_2\")\n", " #no effect, nodes do not exist!\n", " G.insertEdge(\"72\", \"25\",3)\n", " print(G)\n", " \n", " print(\"\\nNodes connected to Node_6:\")\n", " print(G.adjacent(\"Node_6\"))\n", " print(\"\\nNodes connected to Node_4:\")\n", " print(G.adjacent(\"Node_4\"))\n", " print(\"\\nNodes connected to Node_3:\")\n", " print(G.adjacent(\"Node_3\"))\n", " print(\"Edges outgoing from Node_3:\")\n", " print(G.adjacentEdge(\"Node_3\", incoming = False))\n", " print(\"Edges incoming to Node_3:\")\n", " print(G.adjacentEdge(\"Node_3\", incoming = True))\n", " print(\"\\nEdges incoming to Node_6:\")\n", " print(G.adjacentEdge(\"Node_6\", incoming = True))\n", " print(\"\\nEdges incoming to Node_743432:\")\n", " print(G.adjacentEdge(\"Node_743432\", incoming = True))\n", " print(\"\\nAll edges:\")\n", "\n", " print(G.edges())\n", " \n", " print(\"\\nIs (Node_4,Node_5) there? {}\".format( G.edgeIn(\"Node_4\",\"Node_5\")))\n", " print(\"Is (Node_4,Node_3) there? {}\".format( G.edgeIn(\"Node_4\",\"Node_3\")))\n", " print(\"Is (Node_3,Node_4) there? {}\".format( G.edgeIn(\"Node_3\",\"Node_4\")))\n", " print(\"Is (Node_6,Node_6) there? {}\".format( G.edgeIn(\"Node_6\",\"Node_6\")))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [DiGraphAsAdjacencyMatrixEx1.py](data_structures/DiGraphAsAdjacencyMatrixEx1.py)\n", "
\n", "\n", "2. Extend the ```DiGraphAsAdjacencyMatrix``` class creating a subclass ```DiGraphAmAnalyzer``` and adding the following methods:\n", "\n", "* ```getTopConnected_incoming(self)```: finds the node with the highest number of in-coming connections;\n", "\n", "* ```getTopConnected_outgoing(self)```: finds the node with the highest number of out-going connections;\n", "\n", "* ```hasPath(self, node1,node2)``` to check if there is a path connecting node1 to node2 (if it exists return the path as a list of pair of nodes, otherwise None;\n", "\n", "You can test your methods with the following code:\n", "\n", "```python\n", "G = DiGraphAmAnalyzer()\n", "for i in range(6):\n", " n = \"Node_{}\".format(i+1)\n", " G.insertNode(n)\n", "\n", "for i in range(0,4):\n", " n = \"Node_\" + str(i+1)\n", " six = \"Node_6\"\n", " n_plus = \"Node_\" + str((i+2) % 6)\n", " G.insertEdge(n, n_plus,0.5)\n", " G.insertEdge(n, six,1)\n", "\n", "G.insertEdge(\"Node_5\", \"Node_1\", 0.5)\n", "G.insertEdge(\"Node_5\", \"Node_6\", 1)\n", "G.insertEdge(\"Node_6\", \"Node_6\", 1)\n", "print(\"Top connected (outgoing):\")\n", "print(G.getTopConnected_outgoing())\n", "print(\"Top connected (incoming):\")\n", "print(G.getTopConnected_incoming()) \n", "print(\"\\nAdding edge Node_5 -- 0.5 --> Node_5\")\n", "G.insertEdge(\"Node_5\", \"Node_5\", 0.5)\n", "print(\"Top connected (outgoing):\")\n", "print(G.getTopConnected_outgoing())\n", "print(\"\\nAre Node_1 and Node_4 connected?\")\n", "print(\"{}\".format(G.hasPath(\"Node_1\",\"Node_4\")))\n", "print(\"\\nRemoving Node_6\")\n", "G.deleteNode(\"Node_6\")\n", "print(\"Top connected (outgoing):\")\n", "print(G.getTopConnected_outgoing())\n", "print(\"Top connected (incoming):\")\n", "print(G.getTopConnected_incoming())\n", "G.insertNode(\"Node_alone\")\n", "G.insertNode(\"Node_alone2\")\n", "G.insertEdge(\"Node_alone\", \"Node_alone2\", 1)\n", "\n", "print(\"\\nAre Node_1 and Node_alone2 connected?\")\n", "print(G.hasPath(\"Node_1\", \"Node_alone2\"))\n", "print(\"Are Node_alone2 and Node_alone connected?\")\n", "print(G.hasPath(\"Node_alone2\", \"Node_alone\"))\n", "```\n", "\n", "
Show/Hide Solution
\n" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Top connected (outgoing):\n", "['Node_1', 'Node_2', 'Node_3', 'Node_4', 'Node_5']\n", "Top connected (incoming):\n", "['Node_6']\n", "\n", "Adding edge Node_5 -- 0.5 --> Node_5\n", "Top connected (outgoing):\n", "['Node_5']\n", "\n", "Are Node_1 and Node_4 connected?\n", "True\n", "\n", "Removing Node_6\n", "Top connected (outgoing):\n", "['Node_5']\n", "Top connected (incoming):\n", "['Node_5']\n", "\n", "Are Node_1 and Node_alone2 connected?\n", "False\n", "Are Node_alone2 and Node_alone connected?\n", "True\n" ] } ], "source": [ "from collections import deque\n", "\n", "class DiGraphAsAdjacencyMatrix:\n", " def __init__(self):\n", " self.__nodes = list()\n", " self.__matrix = list()\n", " \n", " def __len__(self):\n", " \"\"\"gets the number of nodes\"\"\"\n", " return len(self.__nodes)\n", " \n", " def nodes(self):\n", " return self.__nodes\n", " def matrix(self):\n", " return self.__matrix\n", " \n", " def __str__(self):\n", " header = \"\\t\".join([n for n in self.__nodes])\n", " data = \"\"\n", " for i in range(0,len(self.__matrix)):\n", " data += str(self.__nodes[i]) +\"\\t\" + \"\\t\".join([str(x) for x in self.__matrix[i]]) + \"\\n\"\n", "\n", " return \"\\t\"+ header +\"\\n\" + data\n", " \n", " def insertNode(self, node):\n", " #add the node if not there.\n", " if node not in self.__nodes:\n", " self.__nodes.append(node)\n", " #add a row and a column of zeros in the matrix\n", " if len(self.__matrix) == 0:\n", " #first node\n", " self.__matrix = [[0]]\n", " else:\n", " N = len(self.__nodes)\n", " for row in self.__matrix:\n", " row.append(0)\n", " self.__matrix.append([0 for x in range(N)])\n", " \n", " def insertEdge(self, node1, node2, weight):\n", " i = -1\n", " j = -1\n", " if node1 in self.__nodes:\n", " i = self.__nodes.index(node1)\n", " if node2 in self.__nodes:\n", " j = self.__nodes.index(node2)\n", " if i != -1 and j != -1:\n", " self.__matrix[i][j] = weight\n", " \n", " def deleteEdge(self, node1,node2):\n", " \"\"\"removing an edge means to set its\n", " corresponding place in the matrix to 0\"\"\"\n", " i = -1\n", " j = -1\n", " if node1 in self.__nodes:\n", " i = self.__nodes.index(node1)\n", " if node2 in self.__nodes:\n", " j = self.__nodes.index(node2)\n", " if i != -1 and j != -1:\n", " self.__matrix[i][j] = 0\n", " \n", " def deleteNode(self, node):\n", " \"\"\"removing a node means removing\n", " its corresponding row and column in the matrix\"\"\"\n", " i = -1\n", "\n", " if node in self.__nodes:\n", " i = self.__nodes.index(node)\n", " #print(\"Removing {} at index {}\".format(node, i))\n", " if node != -1:\n", " self.__matrix.pop(i)\n", " for row in self.__matrix:\n", " row.pop(i)\n", " self.__nodes.pop(i)\n", " \n", " \n", " def adjacent(self, node):\n", " \"\"\"returns a list of nodes connected to node\"\"\"\n", " ret = []\n", " if node in self.__nodes:\n", " i = self.__nodes.index(node)\n", " #get both incoming and outgoing edges to return nodes\n", " for j in range(len(self.__nodes)):\n", " nodeJ = self.__nodes[j]\n", " \n", " #incoming edges\n", " if self.__matrix[i][j] != 0:\n", " ret.append(nodeJ)\n", "\n", " return ret\n", " \n", " def adjacentEdge(self, node, incoming = True):\n", " \"\"\"\n", " If incoming == False we look at the row of the node,\n", " else at the column. An edge is present if weight\n", " is different from zero\n", " \"\"\"\n", " ret = []\n", " i = -1\n", " if node in self.__nodes:\n", " i = self.__nodes.index(node)\n", " if i != -1:\n", " #if the node is present\n", " if incoming == False:\n", " for e in range(len(self.__matrix[i])):\n", " node2 = self.__nodes[e]\n", " w = self.__matrix[i][e]\n", " if w != 0:\n", " ret.append((node, node2, self.__matrix[i][e])) \n", " else:\n", " for e in range(len(self.__matrix)):\n", " node2 = self.__nodes[e]\n", " w = self.__matrix[e][i]\n", " if w != 0:\n", " ret.append((node2, node, self.__matrix[e][i]))\n", " return ret\n", " \n", " def edges(self):\n", " \"\"\"Returns all the edges in the graph as triplets\"\"\"\n", " ret = []\n", " for i in range(len(self.__nodes)):\n", " start = self.__nodes[i]\n", " for j in range(len(self.__nodes)):\n", " end = self.__nodes[j]\n", " w = self.__matrix[i][j]\n", " if w != 0:\n", " ret.append((start, end, w))\n", " return ret\n", " \n", " def edgeIn(self,node1,node2):\n", " \"\"\"\n", " Checks if there exist an edge between node1 and node2\n", " (i.e. weight != 0)\n", " \"\"\"\n", " if node1 in self.__nodes and node2 in self.__nodes:\n", " n1 = self.__nodes.index(node1)\n", " n2 = self.__nodes.index(node2)\n", " w = self.__matrix[n1][n2]\n", " \n", " if w != 0:\n", " return True\n", " else:\n", " return False\n", " \n", " else:\n", " return False\n", "\n", "class DiGraphAmAnalyzer(DiGraphAsAdjacencyMatrix): \n", " def getTopConnected_incoming(self):\n", " topN = \"\"\n", " #accumulator to count connections\n", " conn = [0]*len(self.nodes())\n", " for node in range(len(self.nodes())):\n", " for el in range(len(self.matrix()[node])):\n", " w = self.matrix()[node][el]\n", " if w != 0:\n", " conn[el] +=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 range(len(self.nodes())):\n", " n = len([x for x in self.matrix()[node] if x != 0])\n", " if n > conn:\n", " topN = [self.nodes()[node]]\n", " conn = n\n", " else:\n", " if n == conn:\n", " topN.append(self.nodes()[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", " i2 = self.nodes().index(node2)\n", " while len(Q) > 0:\n", " curN = Q.popleft()\n", " i1 = self.nodes().index(curN)\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 range(len(self.matrix()[i1])):\n", " w = self.matrix()[i1][edge]\n", " if w != 0:\n", " if edge == i2:\n", " return True\n", " else:\n", " Q.append(self.nodes()[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", "if __name__ == \"__main__\": \n", " G = DiGraphAmAnalyzer()\n", " for i in range(6):\n", " n = \"Node_{}\".format(i+1)\n", " G.insertNode(n)\n", "\n", " for i in range(0,4):\n", " n = \"Node_\" + str(i+1)\n", " six = \"Node_6\"\n", " n_plus = \"Node_\" + str((i+2) % 6)\n", " G.insertEdge(n, n_plus,0.5)\n", " G.insertEdge(n, six,1)\n", " \n", " G.insertEdge(\"Node_5\", \"Node_1\", 0.5)\n", " G.insertEdge(\"Node_5\", \"Node_6\", 1)\n", " G.insertEdge(\"Node_6\", \"Node_6\", 1)\n", " print(\"Top connected (outgoing):\")\n", " print(G.getTopConnected_outgoing())\n", " print(\"Top connected (incoming):\")\n", " print(G.getTopConnected_incoming()) \n", " print(\"\\nAdding edge Node_5 -- 0.5 --> Node_5\")\n", " G.insertEdge(\"Node_5\", \"Node_5\", 0.5)\n", " print(\"Top connected (outgoing):\")\n", " print(G.getTopConnected_outgoing())\n", " print(\"\\nAre Node_1 and Node_4 connected?\")\n", " print(\"{}\".format(G.hasPath(\"Node_1\",\"Node_4\")))\n", " print(\"\\nRemoving Node_6\")\n", " G.deleteNode(\"Node_6\")\n", " print(\"Top connected (outgoing):\")\n", " print(G.getTopConnected_outgoing())\n", " print(\"Top connected (incoming):\")\n", " print(G.getTopConnected_incoming())\n", " G.insertNode(\"Node_alone\")\n", " G.insertNode(\"Node_alone2\")\n", " G.insertEdge(\"Node_alone\", \"Node_alone2\", 1)\n", " \n", " print(\"\\nAre Node_1 and Node_alone2 connected?\")\n", " print(G.hasPath(\"Node_1\", \"Node_alone2\"))\n", " print(\"Are Node_alone2 and Node_alone connected?\")\n", " print(G.hasPath(\"Node_alone2\", \"Node_alone\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [DiGraphAmAnalyzer.py](data_structures/DiGraphAmAnalyzer.py)\n", "\n", "\n", "## Implementation as (adjacency) linked list\n", "\n", "In this case a graph $G$ is represented as an **adjacency linked list**, where each node $N$ has a linked-list of nodes connected to it in $G$. In the case of directed graphs, every node contains a list of all the nodes reachable through some **outgoing** edges, while in the case of undirected graphs the list will be of all nodes connected together by means of an edge. \n", "\n", "Some examples follow for both the cases of directed \n", "\n", "![](images/linkedlistdir.png)\n", "\n", "and undirected graphs (from lecture):\n", "\n", "![](images/linkedlistundir.png)\n", "\n", "The implementation through adjacency linked lists has both advantages and disadvantages:\n", "\n", "* it is *flexible*, nodes can be complex objects (with the only requirement of the attribute linking to the neighboring nodes);\n", "\n", "* in general, *it uses less space*, only that required by the pointers encoding for the existing edges;\n", "\n", "* checking presence of an edge is in general *slower* (this requires going through the list of source node);\n", "\n", "* getting all incoming edges of a node is *slow* (requires going through all nodes!). A workaround to this problem is to store not only outgoing-edges but also incoming edges (but this requires more memory).\n", "\n", "\n", "Let's see how we can implement a *directed weighted graph* as an **adjacency linked list** in Python. \n", "We will use a dictionary to represent nodes and corresponding connections. \n", "Therefore, we are not going to implement a linked list, but rather a **dictionary of outgoing edges**. That is, each node N is a dictionary of edges (the key of the dictionary is the node to which N is connected and the value is the weight).\n", "\n", "*Example:*\n", "\n", "\n", "\n", "\n", "```\n", "{\n", " \"Node_1\": {\n", " \"Node_2\": 0.5,\n", " \"Node_6\": 1\n", " },\n", " \"Node_2\": {\n", " \"Node_3\": 0.5,\n", " \"Node_6\": 1\n", " },\n", " \"Node_3\": {\n", " \"Node_4\": 0.5,\n", " \"Node_6\": 1\n", " },\n", " \"Node_4\": {\n", " \"Node_5\": 0.5,\n", " \"Node_6\": 1\n", " },\n", " \"Node_5\": {\n", " \"Node_1\": 0.5,\n", " \"Node_6\": 1\n", " },\n", " \"Node_6\": {\n", " \"Node_6\": 1\n", " }\n", "}\n", "\n", "```\n", "\n", "\n", "The nested dictionary above (before the addition of Node 7) represents the following graph:\n", "\n", "![](images/star.png)\n" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Node_1 -- 0.5 --> Node_2\n", "Node_1 -- 1 --> Node_6\n", "Node_2 -- 0.5 --> Node_3\n", "Node_2 -- 1 --> Node_6\n", "Node_3 -- 0.5 --> Node_4\n", "Node_3 -- 1 --> Node_6\n", "Node_4 -- 0.5 --> Node_5\n", "Node_4 -- 1 --> Node_6\n", "Node_5 -- 0.5 --> Node_1\n", "Node_5 -- 1 --> Node_6\n", "Node_6 -- 1 --> Node_6\n", "\n", "Size is: 7\n", "Nodes: ['Node_1', 'Node_2', 'Node_3', 'Node_4', 'Node_5', 'Node_6', 'Node_7']\n", "Graph:\n", "Node_1 -- 0.5 --> Node_2\n", "Node_1 -- 1 --> Node_6\n", "Node_1 -- -1 --> Node_7\n", "Node_2 -- 0.5 --> Node_3\n", "Node_2 -- 1 --> Node_6\n", "Node_2 -- -2 --> Node_7\n", "Node_3 -- 0.5 --> Node_4\n", "Node_3 -- 1 --> Node_6\n", "Node_4 -- 0.5 --> Node_5\n", "Node_4 -- 1 --> Node_6\n", "Node_5 -- 0.5 --> Node_1\n", "Node_5 -- 1 --> Node_6\n", "Node_5 -- -5 --> Node_7\n", "Node_6 -- 1 --> Node_6\n", "Node_7 -- -2 --> Node_2\n", "Node_7 -- -3 --> Node_3\n", "\n", "Node_1 -- 0.5 --> Node_2\n", "Node_1 -- 1 --> Node_6\n", "Node_2 -- 0.5 --> Node_3\n", "Node_2 -- 1 --> Node_6\n", "Node_3 -- 0.5 --> Node_4\n", "Node_3 -- 1 --> Node_6\n", "Node_4 -- 0.5 --> Node_5\n", "Node_4 -- 1 --> Node_6\n", "Node_5 -- 0.5 --> Node_1\n", "Node_5 -- 1 --> Node_6\n", "Node_6 -- 1 --> Node_6\n", "\n", "Nodes: ['Node_1', 'Node_2', 'Node_3', 'Node_4', 'Node_5', 'Node_6']\n", "Nodes: ['Node_1', 'Node_2', 'Node_3', 'Node_4', 'Node_5', 'Node_6']\n", "Node_1 -- 0.5 --> Node_2\n", "Node_1 -- 1 --> Node_6\n", "Node_2 -- 0.5 --> Node_3\n", "Node_2 -- 1 --> Node_6\n", "Node_3 -- 0.5 --> Node_4\n", "Node_3 -- 1 --> Node_6\n", "Node_4 -- 0.5 --> Node_5\n", "Node_4 -- 1 --> Node_6\n", "Node_5 -- 0.5 --> Node_1\n", "Node_5 -- 1 --> Node_6\n", "Node_6 -- 1 --> Node_6\n", "\n" ] } ], "source": [ "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", " \n", " ret += \"{} -- {} --> {}\\n\".format(str(n),\n", " str(self.__nodes[n][edge]),\n", " str(edge))\n", " return ret\n", " \n", " def adjacent(self, node, incoming = True):\n", " \"\"\"Your treat! (see exercise 3)\"\"\"\n", " \n", " def edges(self):\n", " \"\"\"Your treat! (see exercise 3). Returns all the edges\"\"\"\n", " \n", " \n", "if __name__ == \"__main__\":\n", " G = DiGraphLL()\n", " for i in range(6):\n", " n = \"Node_{}\".format(i+1)\n", " G.insertNode(n)\n", "\n", " for i in range(0,4):\n", " n = \"Node_\" + str(i+1)\n", " six = \"Node_6\"\n", " n_plus = \"Node_\" + str((i+2) % 6)\n", " G.insertEdge(n, n_plus,0.5)\n", " G.insertEdge(n, six,1)\n", " G.insertEdge(\"Node_5\", \"Node_1\", 0.5)\n", " G.insertEdge(\"Node_5\", \"Node_6\", 1)\n", " G.insertEdge(\"Node_6\", \"Node_6\", 1)\n", " print(G)\n", " \n", " G.insertNode(\"Node_7\")\n", " G.insertEdge(\"Node_1\", \"Node_7\", -1)\n", " G.insertEdge(\"Node_2\", \"Node_7\", -2)\n", " G.insertEdge(\"Node_5\", \"Node_7\", -5)\n", " G.insertEdge(\"Node_7\", \"Node_2\", -2)\n", " G.insertEdge(\"Node_7\", \"Node_3\", -3)\n", " \n", " print(\"Size is: {}\".format(len(G)))\n", " print(\"Nodes: {}\".format(G.nodes()))\n", " print(\"Graph:\")\n", " print(G)\n", " G.deleteNode(\"Node_7\")\n", " G.deleteEdge(\"Node_6\", \"Node_2\")\n", " #nodes do not exist! Therefore nothing happens!\n", " G.insertEdge(\"72\", \"25\",3)\n", " print(G)\n", " print(\"Nodes: {}\".format(G.nodes()))\n", " G.deleteEdge(\"72\",\"25\")\n", " print(\"Nodes: {}\".format(G.nodes()))\n", " print(G)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [DiGraphLL.py](data_structures/DiGraphLL.py)\n", "\n", "### Exercises\n", "\n", "3. Consider the ```DiGraphLL``` graph class. Add the following methods:\n", "\n", "* ```adjacent(self, node)``` : given a node returns all the nodes connected to it (both incoming and outgoing);\n", "\n", "* ```adjacentEdge(self, node, incoming=True)``` : given a node, returns all the nodes close to it (incoming if \"incoming=True\" or outgoing if \"incoming = False\") as a list of pairs (node, other, weight);\n", "\n", "* ```edges(self)``` : returns all the edges in the graph as pairs (i,j, weight);\n", "\n", "* ```edgeIn(self, node1, node2)``` : check if the edge node1 --> node2 is in the graph;\n", "\n", "Test your methods with the test code from the previous exercise, changing ```DiGraphAsAdjacencyMatrix``` with ```DiGraphLL```.\n", "\n", "
Show/Hide Solution\n" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Node_1 -- 0.5 --> Node_2\n", "Node_1 -- 1 --> Node_6\n", "Node_2 -- 0.5 --> Node_3\n", "Node_2 -- 1 --> Node_6\n", "Node_3 -- 0.5 --> Node_4\n", "Node_3 -- 1 --> Node_6\n", "Node_4 -- 0.5 --> Node_5\n", "Node_4 -- 1 --> Node_6\n", "Node_5 -- 0.5 --> Node_1\n", "Node_5 -- 1 --> Node_6\n", "Node_6 -- 1 --> Node_6\n", "\n", "\n", "Nodes connected to Node_6:\n", "['Node_1', 'Node_2', 'Node_3', 'Node_4', 'Node_5', 'Node_6']\n", "\n", "Nodes connected to Node_4:\n", "['Node_3', 'Node_5', 'Node_6']\n", "\n", "Nodes connected to Node_3:\n", "['Node_2', 'Node_4', 'Node_6']\n", "Edges outgoing from Node_3:\n", "[('Node_3', 'Node_4', 0.5), ('Node_3', 'Node_6', 1)]\n", "Edges incoming to Node_3:\n", "[('Node_2', 'Node_3', 0.5)]\n", "\n", "Edges incoming to Node_6:\n", "[('Node_1', 'Node_6', 1), ('Node_2', 'Node_6', 1), ('Node_3', 'Node_6', 1), ('Node_4', 'Node_6', 1), ('Node_5', 'Node_6', 1), ('Node_6', 'Node_6', 1)]\n", "\n", "Edges incoming to Node_743432:\n", "[]\n", "\n", "All edges:\n", "[('Node_1', 'Node_2', 0.5), ('Node_1', 'Node_6', 1), ('Node_2', 'Node_3', 0.5), ('Node_2', 'Node_6', 1), ('Node_3', 'Node_4', 0.5), ('Node_3', 'Node_6', 1), ('Node_4', 'Node_5', 0.5), ('Node_4', 'Node_6', 1), ('Node_5', 'Node_1', 0.5), ('Node_5', 'Node_6', 1), ('Node_6', 'Node_6', 1)]\n", "\n", "Is (Node_4,Node_5) there? True\n", "Is (Node_4,Node_3) there? False\n", "Is (Node_3,Node_4) there? True\n", "Is (Node_6,Node_6) there? True\n" ] } ], "source": [ "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", " \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", " otherNode = self.__nodes.get(node,None)\n", " if otherNode != None:\n", " for e in otherNode:\n", " w = self.__nodes[node][e]\n", " ret.append((node, e, w))\n", " return ret\n", " else:\n", " for n in self.__nodes:\n", " other = self.__nodes[n].get(node,None)\n", " if other != None:\n", " ret.append((n,node, other))\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 \n", " \n", "if __name__ == \"__main__\":\n", " G = DiGraphLL()\n", " for i in range(6):\n", " n = \"Node_{}\".format(i+1)\n", " G.insertNode(n)\n", "\n", " for i in range(0,4):\n", " n = \"Node_\" + str(i+1)\n", " six = \"Node_6\"\n", " n_plus = \"Node_\" + str((i+2) % 6)\n", " G.insertEdge(n, n_plus,0.5)\n", " G.insertEdge(n, six,1)\n", " G.insertEdge(\"Node_5\", \"Node_1\", 0.5)\n", " G.insertEdge(\"Node_5\", \"Node_6\", 1)\n", " G.insertEdge(\"Node_6\", \"Node_6\", 1)\n", " \n", " G.insertNode(\"Node_7\")\n", " G.insertEdge(\"Node_1\", \"Node_7\", -1)\n", " G.insertEdge(\"Node_2\", \"Node_7\", -2)\n", " G.insertEdge(\"Node_5\", \"Node_7\", -5)\n", " G.insertEdge(\"Node_7\", \"Node_2\", -2)\n", " G.insertEdge(\"Node_7\", \"Node_3\", -3)\n", "\n", " G.deleteNode(\"Node_7\")\n", " G.deleteEdge(\"Node_6\", \"Node_2\")\n", " #no effect, nodes do not exist!\n", " G.insertEdge(\"72\", \"25\",3)\n", " print(G)\n", " \n", " print(\"\\nNodes connected to Node_6:\")\n", " print(G.adjacent(\"Node_6\"))\n", " print(\"\\nNodes connected to Node_4:\")\n", " print(G.adjacent(\"Node_4\"))\n", " print(\"\\nNodes connected to Node_3:\")\n", " print(G.adjacent(\"Node_3\"))\n", " print(\"Edges outgoing from Node_3:\")\n", " print(G.adjacentEdge(\"Node_3\", incoming = False))\n", " print(\"Edges incoming to Node_3:\")\n", " print(G.adjacentEdge(\"Node_3\", incoming = True))\n", " print(\"\\nEdges incoming to Node_6:\")\n", " print(G.adjacentEdge(\"Node_6\", incoming = True))\n", " print(\"\\nEdges incoming to Node_743432:\")\n", " print(G.adjacentEdge(\"Node_743432\", incoming = True))\n", " print(\"\\nAll edges:\")\n", "\n", " print(G.edges())\n", " \n", " print(\"\\nIs (Node_4,Node_5) there? {}\".format( G.edgeIn(\"Node_4\",\"Node_5\")))\n", " print(\"Is (Node_4,Node_3) there? {}\".format( G.edgeIn(\"Node_4\",\"Node_3\")))\n", " print(\"Is (Node_3,Node_4) there? {}\".format( G.edgeIn(\"Node_3\",\"Node_4\")))\n", " print(\"Is (Node_6,Node_6) there? {}\".format( G.edgeIn(\"Node_6\",\"Node_6\")))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [DiGraphLLEx3.py](data_structures/DiGraphLLEx3.py)\n", "
\n", "\n", "4. Extend the ```DiGraphLL``` class creating a subclass ```DiGraphLLAnalyzer``` by adding the following methods:\n", "\n", "* ```getTopConnected_incoming(self)```: finds the node with the highest number of in-coming connections;\n", "\n", "* ```getTopConnected_outgoing(self)```: finds the node with the highest number of out-going connections;\n", "\n", "* ```hasPath(self, node1,node2)``` to check if there is a path connecting node1 to node2 (if it exists return the path as a list of pair of nodes, otherwise None;\n", "\n", "Test your class with the following code:\n", "\n", "```python\n", "G = DiGraphLLAnalyzer()\n", " for i in range(6):\n", " n = \"Node_{}\".format(i+1)\n", " G.insertNode(n)\n", "\n", " for i in range(0,4):\n", " n = \"Node_\" + str(i+1)\n", " six = \"Node_6\"\n", " n_plus = \"Node_\" + str((i+2) % 6)\n", " G.insertEdge(n, n_plus,0.5)\n", " G.insertEdge(n, six,1)\n", " G.insertEdge(\"Node_5\", \"Node_1\", 0.5)\n", " G.insertEdge(\"Node_5\", \"Node_6\", 1)\n", " G.insertEdge(\"Node_6\", \"Node_6\", 1)\n", " print(\"Top connected (outgoing):\")\n", " print(G.getTopConnected_outgoing())\n", " print(\"Top connected (incoming):\")\n", " print(G.getTopConnected_incoming()) \n", " print(\"\\nAdding edge Node_5 -- 0.5 --> Node_5\")\n", " G.insertEdge(\"Node_5\", \"Node_5\", 0.5)\n", " print(\"Top connected (outgoing):\")\n", " print(G.getTopConnected_outgoing())\n", " print(\"\\nAre Node_1 and Node_4 connected?\")\n", " print(\"{}\".format(G.hasPath(\"Node_1\",\"Node_4\")))\n", " print(\"\\nRemoving Node_6\")\n", " G.deleteNode(\"Node_6\")\n", " print(\"Top connected (outgoing):\")\n", " print(G.getTopConnected_outgoing())\n", " print(\"Top connected (incoming):\")\n", " print(G.getTopConnected_incoming())\n", " G.insertNode(\"Node_alone\")\n", " G.insertNode(\"Node_alone2\")\n", " G.insertEdge(\"Node_alone\", \"Node_alone2\", 1)\n", " \n", " print(\"\\nAre Node_1 and Node_alone2 connected?\")\n", " print(G.hasPath(\"Node_1\", \"Node_alone2\"))\n", " print(\"Are Node_alone2 and Node_alone connected?\")\n", " print(G.hasPath(\"Node_alone2\", \"Node_alone\"))\n", "```\n", "\n", "\n", "
Show/Hide Solution
\n" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Top connected (outgoing):\n", "['Node_1', 'Node_2', 'Node_3', 'Node_4', 'Node_5']\n", "Top connected (incoming):\n", "['Node_6']\n", "\n", "Adding edge Node_5 -- 0.5 --> Node_5\n", "Top connected (outgoing):\n", "['Node_5']\n", "\n", "Are Node_1 and Node_4 connected?\n", "True\n", "\n", "Removing Node_6\n", "Top connected (outgoing):\n", "['Node_5']\n", "Top connected (incoming):\n", "['Node_5']\n", "\n", "Adding Node_alone and Node_alone2\n", "Adding Node_alone --> Node_alone2\n", "\n", "Are Node_1 and Node_alone2 connected?\n", "False\n", "Are Node_alone2 and Node_alone connected?\n", "True\n" ] } ], "source": [ "from collections import deque\n", "\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", " \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", " otherNode = self.__nodes.get(node,None)\n", " if otherNode != None:\n", " for e in otherNode:\n", " w = self.__nodes[node][e]\n", " ret.append((node, e, w))\n", " return ret\n", " else:\n", " for n in self.__nodes:\n", " other = self.__nodes[n].get(node,None)\n", " if other != None:\n", " ret.append((n,node, other))\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 \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", "if __name__ == \"__main__\": \n", " G = DiGraphLLAnalyzer()\n", " for i in range(6):\n", " n = \"Node_{}\".format(i+1)\n", " G.insertNode(n)\n", "\n", " for i in range(0,4):\n", " n = \"Node_\" + str(i+1)\n", " six = \"Node_6\"\n", " n_plus = \"Node_\" + str((i+2) % 6)\n", " G.insertEdge(n, n_plus,0.5)\n", " G.insertEdge(n, six,1)\n", " \n", " G.insertEdge(\"Node_5\", \"Node_1\", 0.5)\n", " G.insertEdge(\"Node_5\", \"Node_6\", 1)\n", " G.insertEdge(\"Node_6\", \"Node_6\", 1)\n", " print(\"Top connected (outgoing):\")\n", " print(G.getTopConnected_outgoing())\n", " print(\"Top connected (incoming):\")\n", " print(G.getTopConnected_incoming()) \n", " print(\"\\nAdding edge Node_5 -- 0.5 --> Node_5\")\n", " G.insertEdge(\"Node_5\", \"Node_5\", 0.5)\n", " print(\"Top connected (outgoing):\")\n", " print(G.getTopConnected_outgoing())\n", " print(\"\\nAre Node_1 and Node_4 connected?\")\n", " print(\"{}\".format(G.hasPath(\"Node_1\",\"Node_4\")))\n", " print(\"\\nRemoving Node_6\")\n", " G.deleteNode(\"Node_6\")\n", " print(\"Top connected (outgoing):\")\n", " print(G.getTopConnected_outgoing())\n", " print(\"Top connected (incoming):\")\n", " print(G.getTopConnected_incoming())\n", " print(\"\\nAdding Node_alone and Node_alone2\")\n", " G.insertNode(\"Node_alone\")\n", " G.insertNode(\"Node_alone2\")\n", " print(\"Adding Node_alone --> Node_alone2\")\n", " G.insertEdge(\"Node_alone\", \"Node_alone2\", 1)\n", " \n", " print(\"\\nAre Node_1 and Node_alone2 connected?\")\n", " print(G.hasPath(\"Node_1\", \"Node_alone2\"))\n", " print(\"Are Node_alone2 and Node_alone connected?\")\n", " print(G.hasPath(\"Node_alone2\", \"Node_alone\"))" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Download the complete source file: [DiGraphLLAnalyzer.py](data_structures/DiGraphLLAnalyzer.py)\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "nbsphinx": "hidden" }, "source": [ "" ] } ], "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 }