A simple and effective way to grow your computer science skills is to master the basics. Knowing the basics sets apart the great coders from the merely intermediate ones.
One such basic area in computer science is graph theory, a specific subproblem of which—the pathfinder algorithm—we’ll address in this tutorial. So first things first:
What Is a Graph?
You may already know data structures like lists, sets, and dictionaries. These data structures are denoted as complex data structures–not because they’re difficult to understand but because they build upon other data structures.
A graph is just another complex data structure for relational data.
Relational data consists of edges and vertices. Each vertex stands in one or more relations with other vertices. An example for relational data is the Facebook social graph. Facebook represents users as vertices and friendship relations as edges. Two users are connected via an edge in the graph if they are (Facebook) friends.
What is a graph? A graph is a basic data structure in computer science. It models relationships between data items. Using graphs to model real-world phenomena is not a new idea. In 1736, Leonhard Euler has invented the graph data structure to solve the problem of “seven bridges of Königsberg”. Graphs existed way before the first computer was even an idea. In fact, as we will see in this article, graphs helped to make the computer possible. Without graphs, there wouldn’t be a computer as we now know it today.
How to Represent a Graph Data Structure in the Code?
In this tutorial, we’ll use an adjacency matrix as graph data structure
G. Each row
i in the matrix stores the out-neighbors of vertex
i. And each column
j stores the in-neighbors of vertex
j. Thus, there is an edge from vertex
i to vertex
You can see an example of the adjacency matrix graph representation in the following code of the Pathfinder algorithm:
The Pathfinder Algorithm in Python
How to determine whether there is a path between two vertices?
find_path(graph, v_start, v_end, path_len) checks whether there is a direct or indirect path between two vertices
v_end in graph. We know that there is a direct path between
v_end if both are already neighbors, i.e.,
def find_path(graph, v_start, v_end, path_len=0): '''Is there a path between vertex v_start and vertex v_end?''' # Traverse each vertex only once if path_len >= len(graph): return False # Direct path from v_start to v_end? if graph[v_start][v_end]: return True # Indirect path via neighbor v_nbor? for v_nbor, edge in enumerate(graph[v_start]): if edge: # between v_start and v_nbor if find_path(graph, v_nbor, v_end, path_len + 1): return True # No direct or indirect path found return False # The graph represented as adjancy matrix G = [[1, 1, 0, 0, 0], [0, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 1, 1, 1, 0], [1, 0, 0, 1, 1]] print(find_path(graph=G, v_start=3, v_end=0)) # False print(find_path(G, 3, 1)) # True
However, even if there is not a direct path, there could be an indirect path between vertices
v_end. To check this, the algorithm uses a recursive approach. Specifically, there is an indirect path if a vertex
v_nbor exists such that there is a path:
v_start --> v_nbor --> ... --> v_end.
path_len stores the length of the current path. We increment it in each recursion level as the current path length increases by one. Note that all paths with length
>=n consist of at least
n vertices. In other words, at least one vertex is visited twice and a cycle exists in this recursion instance. Hence, we skip recursion for paths with length greater than or equal to the number of vertices in the graph.
In the code snippet, we check whether there is a path between 3 and 0. If you understand what the code is doing, it suffices to look at the adjacency matrix
G. There is a direct path from vertex 3 to vertices 1 and 2 (and to itself). But neither vertex 1 nor 2 has any out-neighbors. Therefore, there is no path from vertex 3 to any other vertex (besides vertices 1 and 2).