{ "cells": [ { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "view-in-github" }, "source": [ "\"Open" ] }, { "cell_type": "markdown", "metadata": { "id": "tyFvzv_djNWw" }, "source": [ "# Network Model " ] }, { "cell_type": "markdown", "metadata": { "id": "Nc5NT9WpZHkN" }, "source": [ "## Introduction\n" ] }, { "cell_type": "markdown", "metadata": { "id": "92wkrOTjh8ot" }, "source": [ "Many problems in computer science can be presented in the form of graphs which consists of nodes & links between them. Network flow problems can be taken as an example, as it involves the transportation of goods and material across networks. The motivation for taking advantage of their structure usually has been the need to solve larger problems than otherwise would be possible to solve with\n", "existing computer technology. Historically, the first of these special structures to be analyzed was the transportation problem, which is a particular type of network problem. The development of an efficient solution procedure for this problem resulted in the first widespread application of linear programming to problems of\n", "industrial logistics. More recently, the development of algorithms to efficiently solve particular large-scale systems has become a major concern in applied mathematical programming.\n" ] }, { "cell_type": "markdown", "metadata": { "id": "kLY1of_91b2K" }, "source": [ "### History Of Network Model\n", "It was introduced by Charles Bachaman and developed into standard specifications by Conference on Data System Language (CODASYL) Consortium in 1969.Researchers sponsered by the U.S. Department of Defensen's Advanced Researvh Projects Agency created the First Packet-switched network, called the ARPANET, in 1969.\n", "\n", "Today’s globalization as the world has evolved to an advanced planet in Information Technology because of computer networks. One of the key contributing factors of the information technology rise in the world is network and data communication because of network and technology’s advancement as the system. The goal of network model has always been same, which is convergence and achieving service integration. From early 1960s to present, the development and progress that network model has gone through has always accommodated the rapidly increasing number of users and applications. It has made the global environment of information and technology transparent to applications. " ] }, { "cell_type": "markdown", "metadata": { "id": "2zIO8oLPlrfu" }, "source": [ "## Example 1\n", "\n", "\n", "### Shortest Route/Path Problem\n", "In Network Models, problems can be presented in many ways. Here, one of the common problem is the shortest route problems. Shortest route problem is a network model problem which has received a great deal of attention for both the practical and theoretical reasons. For instance, given a network with a distance associated with each arc, this network model helps us to find the shortest distance from origin (source) to the destination (which is called sink).\n", " \n", "These problems can be formulated in real life problems like equipment replacement, capital, investment, project scheduling, and inventory planning. The theoretical interest of this problem is due to the efficient solution problems. Shortest route problems can be interpreted as a network problem very easily. \n", "\n", "\n", "A graph's shortest route issue asks for a path between vertices that has the least total weight of all its edges [5-7]. In which we must identify all the paths and then we must sum of all the distances of specific path. Then the path has less distance it will be considered as the shortest route. \n", "\n", "***\n", "\n", "### Example\n", "\n", "**Find the shortest path in the given graph from point A to E.**\n", "\n", "

\n", "\n", "It’s a directed graph firstly we will see all possible path in it. So, the possible paths are:\n", "\n", "| Path no. | Path |\n", "|-----------------|------------------|\n", "| 1 | A-C-E |\n", "| 2 | A-C-D-E |\n", "| 3 | A-B-C-E |\n", "| 4 | A-B-C-D-E |\n", "| 5 | A-B-D-E |\n", "\n", "After executing the whole path, we will calculate the distance of every node included in the selected path then the path has overall less distance will be the shortest path.\n", "\n", "**Path 1:**\n", "\n", "

\n", "\n", "In the bracket [m, n] m is basically distance between two nodes and the n is parent node from which we are coming from. So, as above 3 is distance between A to C which is m and, C parent node is A which is n.\n", "So, the distance of path 1 is 10\n", "\n", "**Path 2:**\n", "\n", "

\n", "\n", "The distance of path 2 is 12\n", "\n", "**Path 3:**\n", "\n", "

\n", "\n", "The distance of path 3 is 15\n", "\n", "**Path 4:**\n", "\n", "

\n", "\n", "The distance of path 4 is 17\n", "\n", "**Path 5:**\n", "\n", "

\n", "\n", "The distance of path 5 is 7.\n", "\n", "So, the results are in the given table:\n", "\n", "| Path no. | Path | Distance |\n", "|-----------------|------------------|-----------------|\n", "| 1 | A-C-E | 10 |\n", "| 2 | A-C-D-E | 12 |\n", "| 3 | A-B-C-E | 15 |\n", "| 4 | A-B-C-D-E | 17 |\n", "| **5** | **A-B-D-E** | **7** |\n", "\n", "**So, the shortest path is path 5 which is A-B-D-E with distance 7.**\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "id": "2T5R6O6eOcEF" }, "source": [ "### Solving Example 1 to find shortest path using python" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "GoSXcdtCLPcY", "outputId": "deb16c68-adf3-4610-c13f-629d611fe05f" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The shortest path from A to F is:- \n", "11\n" ] } ], "source": [ "#Solving Example 1 to find the Shortest path using python...\n", "\n", "import sys\n", "\n", "class Graph():\n", "\n", " def __init__(self, vertices):\n", " self.V = vertices\n", " self.graph = [[0 for column in range(vertices)]\n", " for row in range(vertices)]\n", "\n", " def printSolution(self, dist):\n", " print (\"The shortest path from A to F is:- \")\n", " print(dist[self.V-1])\n", "\n", " #A utility function to find the vertex with\n", " # minimum distance value, from the set of vertices\n", " # not yet included in shortest path tree\n", "\n", " def minDistance(self, dist, sptSet):\n", "\n", " # Initialize minimum distance for next node\n", " min = sys.maxsize\n", "\n", "\n", " for u in range(self.V):\n", " if dist[u] < min and sptSet[u] == False:\n", " min = dist[u]\n", " min_index = u\n", "\n", " return min_index\n", "\n", " # Funtion that implements Dijkstra's single source\n", " # shortest path algorithm for a graph represented\n", " # using adjacency matrix representation\n", "\n", " # Implementation\n", " def dijkstra(self, src):\n", " \n", " dist = [sys.maxsize] * self.V\n", " dist[src] = 0\n", " sptSet = [False] * self.V\n", " \n", " for cout in range(self.V):\n", "\n", " x = self.minDistance(dist, sptSet)\n", "\n", " sptSet[x] = True\n", "\n", " for y in range(self.V):\n", " if self.graph[x][y] > 0 and sptSet[y] == False and dist[y] > dist[x] + self.graph[x][y]:\n", " dist[y] = dist[x] + self.graph[x][y]\n", "\n", " self.printSolution(dist)\n", "\n", "# Driver program\n", "g = Graph(5)\n", "g.graph = [[0,13,13,7,0],\n", " [13,0,0,1,6],\n", " [13,0,0,6,0],\n", " [7,1,6,0,4],\n", " [0,6,0,4,0]\n", " ];\n", "\n", "g.dijkstra(0);" ] }, { "cell_type": "markdown", "metadata": { "id": "IoLc8n1pJmFE" }, "source": [ "## Example 2\n", "\n", "### Maximal Overflow\n", "The maximum quantity of flow that can flow from a source to a sink across a network is what this term refers to. The maximum flow problem may be solved using a variety of techniques [1]. Ford-Fulkerson method and Dinic's Algorithm are two popular solutions methods to this type of problem. Here, we are going to be using **Ford-Fulkerson** method to solve the problems. \n", "\n", "#### Heres how to implement the problems. \n", "\n", "\n", "***\n", "### Example\n", "\n", " **Find the Max flow for the given graph G from the source S to destination T.**\n", "\n", "

\n", "\n", "**Path 1:**Set the edge flow to 0 on all of them. Find a augmenting path in the residual network that has a higher capacity. In this case, I'm going to choose the S-a-b-d-c-T. A bottleneck capacity is the maximum flow that a route can handle in a certain time. You can see that the bottleneck capacity is 2 along this line. Update the edge flow values in the augmenting path now, but don't go over the capacity limit. After that, you'll have the flow network below and the residual network to deal with.\n", "\n", "

\n", "\n", "Flow= S-a-b-d-c-T =2\n", "\n", "**Path 2:** Then I select the augmenting path S-a-c--T. Now the bottleneck capacity is 4.\n", "\n", "

\n", "\n", "Flow= S-a-c-T = 4\n", "\n", "**Path 3:** Then I select the augmenting path S-a-d-c-T. Now the bottleneck capacity is 4.\n", "\n", "

\n", "\n", "Flow= S-a-d-c-T= 4\n", "\n", "**Path 4:** Then I select the augmenting path S-b-a-d-T. Reverse flow in it so there is no bottleneck.\n", "\n", "

\n", "\n", "Reverse FLOW\n", "\n", "**Path 5:** Then I select the augmenting path S-b-d-T. Now the bottleneck capacity is 9.\n", "\n", "

\n", "\n", "Flow=S-b-d-T= 9
\n", "The residual graph is now empty since there are no more routes connecting s and t. As a result, there's no way to make it flow. The Ford Fulkerson technique is complete, and we can now proceed to finding the highest flow rate possible using this information.\n", "The maximum flow is equal to the source flow. And the max flow for this is given below
\n", "Max Flow= 2+4+4+9=19\n" ] }, { "cell_type": "markdown", "metadata": { "id": "4BR4O1MhOySg" }, "source": [ "### Solving the above Question in example 2 to find maximal flow using python" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "NEz4zlvDSMzW", "outputId": "7549d3bf-fff8-4136-deee-f373af3d5c95" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The maximum possible flow is 19 \n" ] } ], "source": [ "#Solving the above Question in example 2 to find maximal flow using python\n", "#We took the codes as references from different python language sources and encoded in here.\n", "\n", "class Graph:\n", " \n", " def __init__(self, graph):\n", " self.graph = graph # residual graph\n", " self. ROW = len(graph)\n", "\n", " '''Returns true if there is a path from source 's' to sink 't' in\n", " residual graph. Also fills parent[] to store the path '''\n", " \n", " def BFS(self, s, t, parent):\n", " \n", " # Mark all the vertices as not visited\n", " visited = [False]*(self.ROW)\n", " \n", " # Create a queue for BFS\n", " queue = []\n", " \n", " # Mark the source node as visited and enqueue it\n", " queue.append(s)\n", " visited[s] = True\n", " \n", " # Standard BFS Loop\n", " while queue:\n", " \n", " # Dequeue a vertex from queue and print it\n", " u = queue.pop(0)\n", " \n", " \n", " for ind, val in enumerate(self.graph[u]):\n", " if visited[ind] == False and val > 0:\n", " \n", " queue.append(ind)\n", " visited[ind] = True\n", " parent[ind] = u\n", " if ind == t:\n", " return True\n", " \n", " \n", " return False\n", " \n", " \n", " # Returns tne maximum flow from s to t in the given graph\n", " def FordFulkerson(self, source, sink):\n", " \n", " # This array is filled by BFS and to store path\n", " parent = [-1]*(self.ROW)\n", " \n", " max_flow = 0 # There is no flow initially\n", " \n", " while self.BFS(source, sink, parent) :\n", " \n", " \n", " path_flow = float(\"Inf\")\n", " s = sink\n", " while(s != source):\n", " path_flow = min (path_flow, self.graph[parent[s]][s])\n", " s = parent[s]\n", " \n", " # Add path flow to overall flow\n", " max_flow += path_flow\n", " \n", " # update residual capacities of the edges and reverse edges\n", " # along the path\n", " v = sink\n", " while(v != source):\n", " u = parent[v]\n", " self.graph[u][v] -= path_flow\n", " self.graph[v][u] += path_flow\n", " v = parent[v]\n", " \n", " return max_flow\n", "graph = [[0, 10, 10, 0, 0, 0],\n", " [0, 0, 2, 4, 8, 0],\n", " [0, 0, 0, 0, 9, 0],\n", " [0, 0, 0, 0, 0, 10],\n", " [0, 0, 0, 6, 0, 10],\n", " [0, 0, 0, 0, 0, 0]]\n", " \n", "g = Graph(graph)\n", " \n", "source = 0; sink = 5\n", " \n", "print (\"The maximum possible flow is %d \" % g.FordFulkerson(source, sink))\n" ] }, { "cell_type": "markdown", "metadata": { "id": "CLgX2PiiLRLJ" }, "source": [ "## Example 3\n", "\n", "### Minimum Spanning Tree\n", "Minimizing the lengths (or \"weights\") of the edges of a tree is known as a minimal spanning tree [2],[3], [4]. A cable company, for example, could wish to build cable in several areas at the same time. By laying less cable, the cable business saves money.
\n", "For any pair of vertices in a tree, there is only one path that connects them.
\n", "A graph's spanning tree is one that:
\n", "\n", "
\n", "\n", "***\n", "\n", "

\n", "\n", "### **Example**\n", "\n", "**Step 1:** Here we are writing the edges that connected with each other and their distance is also mentioned in the table so find the minimum spanning tree for this tree.\n", "\n", "

\n", "\n", "| Edge | distance | |\n", "|-----------------|------------------|--------------|\n", "| (D,E) | 2 | |\n", "| (D,G) | 3 | |\n", "| (E,G) | 4 | |\n", "| (C,D) | 4 | |\n", "| (G,H) | 4 | |\n", "| (C,F) | 4 | |\n", "| (B,C) | 5 | |\n", "| (B,E) | 5 | |\n", "| (B,F) | 5 | |\n", "| (B,H) | 5 | |\n", "| (A,H) | 6 | |\n", "| (D,F) | 7 | |\n", "| (A,B) | 9 | |\n", "| (A,F) | 11 | |\n", "\n", "\n", "\n", "**Step 2:**Firstly, we are selecting the edge which has most less distance between the so D to E has less distance that’s why we choose it.\n", "\n", "

\n", "\n", "| Edge | distance | |\n", "|-----------------|------------------|--------------|\n", "| (D,E) | 2 | ✔ |\n", "| (D,G) | 3 | |\n", "| (E,G) | 4 | |\n", "| (C,D) | 4 | |\n", "| (G,H) | 4 | |\n", "| (C,F) | 4 | |\n", "| (B,C) | 5 | |\n", "| (B,E) | 5 | |\n", "| (B,F) | 5 | |\n", "| (B,H) | 5 | |\n", "| (A,H) | 6 | |\n", "| (D,F) | 7 | |\n", "| (A,B) | 9 | |\n", "| (A,F) | 11 | |\n", "\n", "\n", "\n", "**Step 3:**Now, select the node that is connected to D or E with with the less distance as we see in the tree D to G is 3 which is less distance among all the nodes connected with the D and E. Also adding their entry in the table.\n", "\n", "

\n", "\n", "| Edge | distance | |\n", "|-----------------|------------------|--------------|\n", "| (D,E) | 2 | ✔ |\n", "| (D,G) | 3 | ✔ |\n", "| (E,G) | 4 | |\n", "| (C,D) | 4 | |\n", "| (G,H) | 4 | |\n", "| (C,F) | 4 | |\n", "| (B,C) | 5 | |\n", "| (B,E) | 5 | |\n", "| (B,F) | 5 | |\n", "| (B,H) | 5 | |\n", "| (A,H) | 6 | |\n", "| (D,F) | 7 | |\n", "| (A,B) | 9 | |\n", "| (A,F) | 11 | |\n", "\n", "\n", "**Step 4:**Now here we are also searching for the node that has least distance among all the nodes connected to D, E, and G.\n", "\n", "

\n", "\n", "| Edge | distance | |\n", "|-----------------|------------------|--------------|\n", "| (D,E) | 2 | ✔ |\n", "| (D,G) | 3 | ✔ |\n", "| (E,G) | 4 | ✖ |\n", "| (E,G) | 4 | ✔ |\n", "| (C,D) | 4 | |\n", "| (G,H) | 4 | |\n", "| (C,F) | 4 | |\n", "| (B,C) | 5 | |\n", "| (B,E) | 5 | |\n", "| (B,F) | 5 | |\n", "| (B,H) | 5 | |\n", "| (A,H) | 6 | |\n", "| (D,F) | 7 | |\n", "| (A,B) | 9 | |\n", "| (A,F) | 11 | |\n", "\n", "\n", "**Step 5:** Searching for the node that has least distance among all the nodes connected to D, E, C and G.\n", "\n", "

\n", "\n", "| Edge | distance | |\n", "|-----------------|------------------|--------------|\n", "| (D,E) | 2 | ✔ |\n", "| (D,G) | 3 | ✔ |\n", "| (E,G) | 4 | ✖ |\n", "| (C,D) | 4 | ✔ |\n", "| (G,H) | 4 | ✔ |\n", "| (C,F) | 4 | |\n", "| (B,C) | 5 | |\n", "| (B,E) | 5 | |\n", "| (B,F) | 5 | |\n", "| (B,H) | 5 | |\n", "| (A,H) | 6 | |\n", "| (D,F) | 7 | |\n", "| (A,B) | 9 | |\n", "| (A,F) | 11 | |\n", "\n", "\n", "**Step 6:** Searching for the node that has least distance among all the nodes connected to D, E, C, H and G.\n", "\n", "

\n", "\n", "| Edge | distance | |\n", "|-----------------|------------------|--------------|\n", "| (D,E) | 2 | ✔ |\n", "| (D,G) | 3 | ✔ |\n", "| (E,G) | 4 | ✖ |\n", "| (C,D) | 4 | ✔ |\n", "| (G,H) | 4 | ✔ |\n", "| (C,F) | 4 | ✔ |\n", "| (B,C) | 5 | |\n", "| (B,E) | 5 | |\n", "| (B,F) | 5 | |\n", "| (B,H) | 5 | |\n", "| (A,H) | 6 | |\n", "| (D,F) | 7 | |\n", "| (A,B) | 9 | |\n", "| (A,F) | 11 | |\n", "\n", "\n", "**Step 7:** Searching for the node that has least distance among all the nodes connected to D, E, C, H, F and G.\n", "\n", "

\n", "\n", "| Edge | distance | |\n", "|-----------------|------------------|--------------|\n", "| (D,E) | 2 | ✔ |\n", "| (D,G) | 3 | ✔ |\n", "| (E,G) | 4 | ✖ |\n", "| (C,D) | 4 | ✔ |\n", "| (G,H) | 4 | ✔ |\n", "| (C,F) | 4 | ✔ |\n", "| (B,C) | 5 | ✔ |\n", "| (B,E) | 5 | |\n", "| (B,F) | 5 | |\n", "| (B,H) | 5 | |\n", "| (A,H) | 6 | |\n", "| (D,F) | 7 | |\n", "| (A,B) | 9 | |\n", "| (A,F) | 11 | |\n", "\n", "**Step 8:** Searching for the node that has least distance among all the nodes connected to D, E, C, H, F, B and G.\n", "\n", "

\n", "\n", "| Edge | distance | |\n", "|-----------------|------------------|--------------|\n", "| (D,E) | 2 | ✔ |\n", "| (D,G) | 3 | ✔ |\n", "| (E,G) | 4 | ✖ |\n", "| (C,D) | 4 | ✔ |\n", "| (G,H) | 4 | ✔ |\n", "| (C,F) | 4 | ✔ |\n", "| (B,C) | 5 | ✔ |\n", "| (B,E) | 5 | ✖ |\n", "| (B,F) | 5 | ✖ |\n", "| (B,H) | 5 | ✖ |\n", "| (A,H) | 6 | ✔ |\n", "| (D,F) | 7 | |\n", "| (A,B) | 9 | |\n", "| (A,F) | 11 | |\n", "\n", "\n", "**Step 9:** So here we discover all the nodes and discovered all these through visiting the path with smallest distance and we can’t make a cycle in it and cant visit the node twice.\n", "\n", "

\n", "\n", "| Edge | distance | |\n", "|-----------------|------------------|--------------|\n", "| (D,E) | 2 | ✔ |\n", "| (D,G) | 3 | ✔ |\n", "| (E,G) | 4 | ✖ |\n", "| (C,D) | 4 | ✔ |\n", "| (G,H) | 4 | ✔ |\n", "| (C,F) | 4 | ✔ |\n", "| (B,C) | 5 | ✔ |\n", "| (B,E) | 5 | ✖ |\n", "| (B,F) | 5 | ✖ |\n", "| (B,H) | 5 | ✖ |\n", "| (A,H) | 6 | ✔ |\n", "| (D,F) | 7 | - |\n", "| (A,B) | 9 | - |\n", "| (A,F) | 11 | - |\n", "\n", "\n", "So, the total cost we got = 28\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", " \n", "\n", "\n", "\n", "\n", "\n", " " ] }, { "cell_type": "markdown", "metadata": { "id": "6uDfJH4gyxmm" }, "source": [ "### Solving the above Question in example 3 for Minimum spanning tree using python" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "ggpcEdDlWJ3b", "outputId": "67c15c73-c729-4ef3-8460-d429750aa024" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "0 2\n", "Edges in the constructed MST\n", "0 -- 2 == 1\n", "Minimum Spanning Tree 1\n", "3 4\n", "Edges in the constructed MST\n", "0 -- 2 == 1\n", "3 -- 4 == 2\n", "Minimum Spanning Tree 3\n", "3 5\n", "Edges in the constructed MST\n", "0 -- 2 == 1\n", "3 -- 4 == 2\n", "3 -- 5 == 3\n", "Minimum Spanning Tree 6\n", "3 3\n", "Edges in the constructed MST\n", "0 -- 2 == 1\n", "3 -- 4 == 2\n", "3 -- 5 == 3\n", "Minimum Spanning Tree 6\n", "0 3\n", "Edges in the constructed MST\n", "0 -- 2 == 1\n", "3 -- 4 == 2\n", "3 -- 5 == 3\n", "0 -- 5 == 4\n", "Minimum Spanning Tree 10\n", "1 0\n", "Edges in the constructed MST\n", "0 -- 2 == 1\n", "3 -- 4 == 2\n", "3 -- 5 == 3\n", "0 -- 5 == 4\n", "1 -- 2 == 5\n", "Minimum Spanning Tree 15\n" ] } ], "source": [ "#Solving the above Question in example 3 to solve Minimum spanning tree using python\n", "#We took the codes as references from different python language sources.\n", "\n", "# to do union by rank of x and y\n", "def union(parent, rank, x, y):\n", " xparent = find(parent, x)\n", " yparent = find(parent, y)\n", "\n", " if rank[xparent] < rank[yparent]:\n", " parent[xparent] = yparent\n", " elif rank[xparent] > rank[yparent]:\n", " parent[yparent] = xparent\n", " else:\n", " parent[yparent] = xparent\n", " rank[xparent] += 1\n", "\n", "# Function to find parent of X Uses path compression technique\n", "def find(parent, x):\n", " if parent[x] == x:\n", " return x\n", " return find(parent, parent[x])\n", "\n", "def mst(graph, V, E):\n", " # to keep track for vertices covered\n", " e = 0\n", " # to keep track of newly added edges into MST\n", " k = 0\n", "\n", " # to store the parent of each node\n", " parent=[]\n", "\n", " # to store rank of\n", " rank = []\n", " for vertex in range(V):\n", " parent.append(vertex)\n", " rank.append(0)\n", "\n", " result = []\n", " # Total Number of edges going into mst are 1 Less then number of vertices\n", " while e < V - 1:\n", " # Selecting the edge having smallest weight\n", " v1, v2, w = graph[k]\n", " k = k + 1\n", " x = find(parent, v1)\n", " y = find(parent, v2)\n", " print(x,y)\n", " # Checking if including this edge creates a cycle\n", " if x != y:\n", " e = e + 1\n", " result.append([v1, v2, w])\n", " union(parent, rank, x, y)\n", " # if v1 and v2 hav the same parent which is x==y ignore the edge\n", "\n", " minimumCost = 0\n", " print (\"Edges in the constructed MST\")\n", " for u, v, weight in result:\n", " minimumCost += weight\n", " print(\"%d -- %d == %d\" % (u, v, weight))\n", " print(\"Minimum Spanning Tree\" , minimumCost)\n", "\n", "\n", "# Creating A Graph\n", "graph = []\n", "no_of_Vertices = 6\n", "no_of_Edges = 10\n", "\n", "graph.append([0,1,11])\n", "graph.append([0,2,1])\n", "graph.append([1,2,5])\n", "graph.append([1,3,7])\n", "graph.append([2,3,7])\n", "graph.append([1,4,5])\n", "graph.append([3,4,2])\n", "graph.append([3,5,3])\n", "graph.append([4,5,4])\n", "graph.append([0,5,4])\n", "\n", "\n", "# Code for taking Input From user\n", "# for i in range(no_of_Edges):\n", "# print(\"Enter Vertex1, Vertex2, Weight space separated\\n\")\n", "# v1,v2,w = input().strip().split(\" \")\n", "# graph.append([int(v1),int(v2),int(w)])\n", "\n", "# Sort the graph according to Edge weights\n", "graph = sorted(graph,key=lambda x: x[2])\n", "# Calling Minimum Spanning Tree Function\n", "mst(graph,no_of_Vertices,no_of_Edges)" ] }, { "cell_type": "markdown", "metadata": { "id": "-B3ke7O9j3ud" }, "source": [ "## Problems\n", "\n", "### Question 1\n", "\n", "**Find the shortest path from the given graph from point A to E.**\n", "\n", "

\n", "\n", " \n", "### Question 2\n", "\n", "**Find the shortest path from the given graph from point A to F.**\n", "\n", "

\n", "\n", "### Question 3\n", "\n", "**Find the shortest path from the given graph from point A to F.**\n", "\n", "

\n", "\n", "### Question 4\n", "**Find the Max flow for the given graph G from the source S to destination T.**\n", "\n", "

\n", "\n", "\n", "\n", "### Question 5\n", "**Find the Max flow for the given graph G from the source S to destination T.**\n", "\n", "

\n", "\n", "\n", "\n", "### Question 6\n", "**Find the Max flow for the given graph G from the source S to destination T.**\n", "\n", "

\n", "\n", "### Question 7\n", "**Find the Minimum Spanning Tree of the following from point A to G.**\n", "\n", "

\n", "\n", "\n", "### Question 8\n", "**Find the Minimum Spanning Tree of the following from point A to H.**\n", "\n", "

\n", "\n", "\n", "### Question 9\n", "**Find the Minimum Spanning Tree of the following network from point 1 to 8.**\n", "\n", "

\n", "\n", "\n", "\n", "### Question 10\n", "**Find the Minimum Spanning Tree of the following from poinnt 1 to 9.**\n", "\n", "

\n", "\n", "\n", "\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "id": "Ylz68cn4mGOG" }, "source": [ "## Project Ideas\n", "Network model is such a huge topic, it pretty much covers every concepts within the information and technology. One of the reasons why one must understand the concept of network model is because it helps to break down larger problems into smallers ones and split them into chunks so that they can be easilt managed. They represent a framework for dividing up the tasks needed to implement a network. The basic features of network model, such as optimization and modularity, has always been a boon for large scale industries to small businessess which as continuouly helped them enhance and modify systems for a common cause.\n", "\n", "Overall, we were so fascinated by this topic and the idea of network science, we wanted to explore the diversity, history and culture of this model. This really got us going." ] }, { "cell_type": "markdown", "metadata": { "id": "qUjLRtpJh829" }, "source": [ "## References\n", "\n", "- Bradley, Hax, and Magnanti. Network Models. Applied Mathematical Programming. Addison – Wesley, 1977. http://web.mit.edu/15.053/www/AMP.htm. Accessed 16 Sep 2021. \n", "\n", "- Barua, Saurav. (2019). Operation Research Problems Solving in Python. 10.13140/RG.2.2.20719.38565. https://www.researchgate.net/publication/335572221_Operation_Research_Problems_Solving_in_Python. Accessed 18 Sep 2021.\n", "\n", "- Taha, H. A. (2017). Network Model). In Operations research: An introduction (10th ed.). pp. 220, 225, 235, Pearson. Accessed 19 Sept 2021.\n", "\n", "- L. R. Ford and D. R. Fulkerson, “Maximal Flow Through a Network,” Canadian Journal of Mathematics, vol. 8, pp. 399–404, 1956, doi: 10.4153/cjm-1956-045-5. Accessed 20 Oct 2021.\n", "\n", "- A. Kershenbaum, “Computing capacitated minimal spanning trees efficiently,” Networks, vol. 4, no. 4, pp. 299–310, 1974, doi: 10.1002/net.3230040403. Accessed 18 Oct 2021.\n", "\n", "- T. C. Hu, “Optimum Communication Spanning Trees,” SIAM Journal on Computing, vol. 3, no. 3, pp. 188–195, Sep. 1974, doi: 10.1137/0203015. Accessed 18 Sep 2021.\n", "\n", "- A. A. and N. Eckson, “Robust Water Distribution System using Minimal Spanning Tree Algorithm,” International Journal of Computer Applications, vol. 158, no. 1, pp. 1–4, Jan. 2017, doi: 10.5120/ijca2017912724. Accessed 18 Oct 2021.\n", "\n", "- A. Fitro, S. Suryono, and R. Kusumaningrum, “Shortest Route at Dynamic Location with Node Combination-Dijkstra Algorithm,” Proceeding of the Electrical Engineering Computer Science and Informatics, vol. 5, no. 1, Nov. 2018, doi: 10.11591/eecsi.v5.1604. Accessed 18 Oct 2021.\n", "\n", "- Bing Liu et al., “Finding the shortest route using cases, knowledge, and Djikstra’s algorithm,” IEEE Expert, vol. 9, no. 5, pp. 7–11, Oct. 1994, doi: 10.1109/64.331478. Accessed 18 Oct 2021.\n", "\n", "- J. Wang and T. Kaempke, “Shortest route computation in distributed systems,” Computers & Operations Research, vol. 31, no. 10, pp. 1621–1633, Sep. 2004, doi: 10.1016/s0305-0548(03)00111-4. Accessed 9 Oct 2021.\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "id": "QrMPtdSHnfs0" }, "source": [ "### Authors\n", "\n", " Principal author of this chapter were: Sachin Samal, Prakash Silwal, Watan Chaudhary\n", "\n", " Contributions were also made by: Dr. Nicholas Jacob" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "colab": { "collapsed_sections": [], "include_colab_link": true, "name": "Chapter5NetworkModels.ipynb", "provenance": [] }, "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.9.7" } }, "nbformat": 4, "nbformat_minor": 4 }