Data Scientists, The one Graph Algorithm you need to know

Let us start with a simple graph class written in Python to start up our exploits with code.This post will revolve more around code from here onwards.""" A Python ClassA simple Python graph class, demonstrating the essential facts and functionalities of graphs.Taken from https://www.python-course.eu/graphs_python.phpChanged the implementation a little bit to include weighted edges"""class Graph(object): def __init__(self, graph_dict=None): """ initializes a graph object If no dictionary or None is given, an empty dictionary will be used """ if graph_dict == None: graph_dict = {} self.__graph_dict = graph_dictdef vertices(self): """ returns the vertices of a graph """ return list(self.__graph_dict.keys())def edges(self): """ returns the edges of a graph """ return self.__generate_edges()def add_vertex(self, vertex): """ If the vertex "vertex" is not in self.__graph_dict, a key "vertex" with an empty dict as a value is added to the dictionary..""" if vertex not in self.__graph_dict: self.__graph_dict[vertex] = {}def add_edge(self, edge,weight=1): """ assumes that edge is of type set, tuple or list """ edge = set(edge) (vertex1, vertex2) = tuple(edge) if vertex1 in self.__graph_dict: self.__graph_dict[vertex1][vertex2] = weight else: self.__graph_dict[vertex1] = {vertex2:weight}if vertex2 in self.__graph_dict: self.__graph_dict[vertex2][vertex1] = weight else: self.__graph_dict[vertex2] = {vertex1:weight}def __generate_edges(self): """ A static method generating the edges of the graph "graph"..edges: " for edge in self.__generate_edges(): res += str(edge) + " " return res def adj_mat(self): return self.__graph_dictYou can certainly play with our new graph class..Here we try to build some graphs.g = { "a" : {"d":2}, "b" : {"c":2}, "c" : {"b":5, "d":3, "e":5} }graph = Graph(g)print("Vertices of graph:")print(graph.vertices())print("Edges of graph:")print(graph.edges())print("Add vertex:")graph.add_vertex("z")print("Vertices of graph:")print(graph.vertices()) print("Add an edge:")graph.add_edge({"a","z"}) print("Vertices of graph:")print(graph.vertices())print("Edges of graph:")print(graph.edges())print('Adding an edge {"x","y"} with new vertices:')graph.add_edge({"x","y"})print("Vertices of graph:")print(graph.vertices())print("Edges of graph:")print(graph.edges())—————————————————————–Output:Vertices of graph:['a', 'c', 'b']Edges of graph:[['a', 'd', 2], ['c', 'b', 5], ['c', 'e', 5], ['c', 'd', 3], ['b', 'c', 2]]Add vertex:Vertices of graph:['a', 'c', 'b', 'z']Add an edge:Vertices of graph:['a', 'c', 'b', 'z']Edges of graph:[['a', 'z', 1], ['a', 'd', 2], ['c', 'b', 5], ['c', 'e', 5], ['c', 'd', 3], ['b', 'c', 2], ['z', 'a', 1]]Adding an edge {"x","y"} with new vertices:Vertices of graph:['a', 'c', 'b', 'y', 'x', 'z']Edges of graph:[['a', 'z', 1], ['a', 'd', 2], ['c', 'b', 5], ['c', 'e', 5], ['c', 'd', 3], ['b', 'c', 2], ['y', 'x', 1], ['x', 'y', 1], ['z', 'a', 1]]Let's do something interesting now.We will use the above graph class for our understanding purpose..There are many modules in python which we can use to do whatever I am going to do next but to understand the methods we will write everything from scratch.Let us start with an example graph which we can use for our purpose.g = {'Frankfurt': {'Mannheim':85, 'Wurzburg':217, 'Kassel':173}, 'Mannheim': {'Frankfurt':85, 'Karlsruhe':80}, 'Karlsruhe': {'Augsburg':250, 'Mannheim':80}, 'Augsburg': {'Karlsruhe':250, 'Munchen':84}, 'Wurzburg': {'Erfurt':186, 'Numberg':103,'Frankfurt':217}, 'Erfurt': {'Wurzburg':186}, 'Numberg': {'Wurzburg':103, 'Stuttgart':183,'Munchen':167}, 'Munchen': {'Numberg':167, 'Augsburg':84,'Kassel':502}, 'Kassel': {'Frankfurt':173, 'Munchen':502}, 'Stuttgart': {'Numberg':183} } graph = Graph(g) print("Vertices of graph:") print(graph.vertices()) print("Edges of graph:") print(graph.edges())——————————————————————-Vertices of graph:['Mannheim', 'Erfurt', 'Munchen', 'Numberg', 'Stuttgart', 'Augsburg', 'Kassel', 'Frankfurt', 'Wurzburg', 'Karlsruhe']Edges of graph:[['Mannheim', 'Frankfurt', 85], ['Mannheim', 'Karlsruhe', 80], ['Erfurt', 'Wurzburg', 186], ['Munchen', 'Numberg', 167], ['Munchen', 'Augsburg', 84], ['Munchen', 'Kassel', 502], ['Numberg', 'Stuttgart', 183], ['Numberg', 'Wurzburg', 103], ['Numberg', 'Munchen', 167], ['Stuttgart', 'Numberg', 183], ['Augsburg', 'Munchen', 84], ['Augsburg', 'Karlsruhe', 250], ['Kassel', 'Munchen', 502], ['Kassel', 'Frankfurt', 173], ['Frankfurt', 'Mannheim', 85], ['Frankfurt', 'Wurzburg', 217], ['Frankfurt', 'Kassel', 173], ['Wurzburg', 'Numberg', 103], ['Wurzburg', 'Erfurt', 186], ['Wurzburg', 'Frankfurt', 217], ['Karlsruhe', 'Mannheim', 80], ['Karlsruhe', 'Augsburg', 250]]Let's say we are given a graph with the cities of Germany and the respective distance between them..Since we are popping the first element of a queue we are sure we will visit cities in the order of their level.Check out this good post about BFS to understand more about queues and BFS.min_num_edges_between_nodes(g,'Frankfurt')——————————————————————- ({'Augsburg': 3, 'Erfurt': 2, 'Frankfurt': 0, 'Karlsruhe': 2, 'Kassel': 1, 'Mannheim': 1, 'Munchen': 2, 'Numberg': 2, 'Stuttgart': 3, 'Wurzburg': 1}, {'Augsburg': ':->Frankfurt->Mannheim->Karlsruhe', 'Erfurt': ':->Frankfurt->Wurzburg', 'Frankfurt': ':', 'Karlsruhe': ':->Frankfurt->Mannheim', 'Kassel': ':->Frankfurt', 'Mannheim': ':->Frankfurt', 'Munchen': ':->Frankfurt->Kassel', 'Numberg': ':->Frankfurt->Wurzburg', 'Stuttgart': ':->Frankfurt->Wurzburg->Numberg', 'Wurzburg': ':->Frankfurt'})I did this example to show how BFS algorithm works.We can extend this algorithm to find out connected components in an unconnected graph. Let us say we need to find groups of unconnected vertices in the graph.For example, the below graph has 3 unconnected sub-graphs..Can we find what nodes belong to a particular subgraph?#We add another countries in the loop graph = Graph(g)graph.add_edge(("Mumbai", "Delhi"),400)graph.add_edge(("Delhi", "Kolkata"),500)graph.add_edge(("Kolkata", "Bangalore"),600)graph.add_edge(("TX", "NY"),1200)graph.add_edge(("ALB", "NY"),800)g = graph.adj_mat()def bfs_connected_components(graph): connected_components = [] nodes = graph.keys()while len(nodes)!=0: start_node = nodes.pop() queue = [start_node] #FIFO visited = [start_node] while len(queue)!=0: start = queue[0] queue.remove(start) neighbours = graph[start] for neighbour,_ in neighbours.iteritems(): if neighbour not in visited: queue.append(neighbour) visited.append(neighbour) nodes.remove(neighbour) connected_components.append(visited) return connected_componentsprint bfs_connected_components(g)——————————————————————–[['Kassel', 'Munchen', 'Frankfurt', 'Numberg', 'Augsburg', 'Mannheim', 'Wurzburg', 'Stuttgart', 'Karlsruhe', 'Erfurt'], ['Bangalore', 'Kolkata', 'Delhi', 'Mumbai'], ['NY', 'ALB', 'TX']]The above code is similar to the previous BFS code.. More details

Leave a Reply