The Pathfinder Graph Algorithm in Python

What is the output of this puzzle?

 

n = 5 # The number of vertices in the graph

# The graph represented as adjancy matrix
# See https://en.wikipedia.org/wiki/Adjacency_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]
     ]

# Is there a path from vertex i to vertex j?
def findPath(i,j,pathLength):
    
    # The maximal length of a path without a cycle is n
    # (traverse each vertex once)
    if pathLength>n:
        return False
    
    # Is there a direct path from i to j?
    if G[i][j]==1:
        return True
    
    # Is there an indirect path from i to j over i's neighbor k?
    for k in range(n):
        if G[i][k]==1: # Vertex k is a neighbor of i
            if findPath(k,j,pathLength+1):
                return True
    
    # We have not found any path
    return False

 

Knowing the basics is what sets apart the great from the intermediate coders. In other words, a simple and effective way to grow your skills is to learn the basics of computer science. A fundamental area of computer science is graph theory. Of course, you could solve this puzzle without even knowing about graph theory. After all, this is what your computer does when running this code. But the computer does not have to code—people do. So let us dive into graph theory via an ultra quick crash course.

So what is a graph? A graph is a complex data structure such as a list, a set, or a dictionary. The data structure is complex not because you can not understand it but because it consists of other data structures. You use the graph data structure if you want to represent relations between data items. We denote the relations as edges and the data items as vertices. An example 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.

How does the data structure look like? In the puzzle, we use an adjacency matrix as graph data structure G. Each row i in the matrix stores the out-neighbors of vertex i. Each column j stores the in-neighbors of vertex j. Thus, if we want to know whether there is an edge from vertex i to vertex j, we check whether G[i][j]==1.

How do we check whether there is a path between two vertices? The function findPath(i, j, pathLength) checks whether there is a direct or indirect path between two vertices i and j. We know that there is a direct path between vertices i and j if they are already neighbors, i.e., G[i][j]==1. To determine whether there is an indirect path, the idea is to use a recursive approach. There is an indirect path, if a vertex k exists such that there is a path i --> ... --> k --> ... --> j.

The variable pathLength 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 more than 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 the number of vertices in the graph.

This puzzle asks 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 both vertices 1 and 2 have no out-neighbors. Therefore, there is no such path from 3 to any other vertex (besides vertices 1 and 2).


Are you a master coder?
Test your skills now!

Related Video

Solution

False

 

Leave a Comment