Today we’ll be talking about paths in graphs.
This article is a continuation of the previous one, so make sure to read my previous article first where I covered the basics of graphs.
In this video we’ll be using a new graph. Here it is:
And here’s the dictionary that represents the graph:
graph = {'a': ['d'],
'b': ['d', 'f'],
'c': [],
'd': ['a', 'b', 'e', 'f'],
'e': ['d'],
'f': ['b', 'd']}
We’ll also need the Graph class defined in the previous article. In this article, we’ll be adding some methods to it, so make sure to grab the code from Github if you want to follow along.
In the picture we can see that there are several paths along the edges that we can take to get from one node to another. For example to go from a to b you can choose either the path through d or the path through d and f. The former is shorter.
Learn how to make beautiful GUI apps
in Python using the Kivy framework.
Comprehensive, for Kivy beginners, easy to follow.
Get the book here (PDF) or on Amazon:
ebook / paperback (black and white) / paperback (full color)
So, what is a path actually? Well, we can define a path as a sequence of nodes such that each node is adjacent to the node which was visited last, except for the first node naturally. Two nodes are adjacent if they are directly connected by an edge.
So, have a look at the picture of our graph and tell me which nodes are adjacent. The adjacent nodes are: a and d, b and f, b and d, d and e, d and f.
Let’s stick to our example. If we want to follow the path from a to b through d, we have a path of length 3 from a to b. If we follow the longer path through d and f, then we have a path of length 4 from a to b.
The path can be written as a list of all the nodes it contains. So, the two paths from a to b are: [‘a’, ‘d’, ‘b’] and [‘a’, ‘d’, ‘f’, ‘b’].
If we visit each node only once, it’s a simple path. Here are some examples of simple paths:
[‘e’, ‘d’, ‘b’, ‘f’]
[‘f’, ‘d’, ‘a’]
[‘d’, ‘e’]
On the other hand, the following path:
[‘a’, ‘d’, ‘f’, ‘b’, ‘d’, ‘e’]
is not simple because the node d is visited twice.
Now, what we want to do is find all the paths between two nodes and find the shortest path between two nodes.
Here’s our Graph class again. Let’s add the two methods we need at the end of the class definition:
class Graph:
def __init__(self, graph = {}):
self.__graph = graph
def edges(self):
return [(node, neighbor)
for node in self.__graph
for neighbor in self.__graph[node]]
def nodes(self):
return list(self.__graph.keys())
def isolated_nodes(self):
return [node for node in self.__graph if not self.__graph[node]]
def add_node(self, node):
if node not in self.__graph:
self.__graph[node] = []
def add_edge(self, node1, node2):
if node1 not in self.__graph:
self.add_node(node1)
if node2 not in self.__graph:
self.add_node(node2)
self.__graph[node1].append(node2)
self.__graph[node2].append(node1)
# Let's begin with the method that returns all the paths
# between two nodes.
# The optional path parameter is set to an empty list, so that
# we start with an empty path by default.
def all_paths(self, node1, node2, path = []):
# We add node1 to the path.
path = path + [node1]
# If node1 is not in the graph, the function returns an empty list.
if node1 not in self.__graph:
return []
# If node1 and node2 are one and the same node, we can return
# the path now.
if node1 == node2:
return [path]
# Let's create an empty list that will store the paths.
paths = []
# Now we'll take each node adjacent to node1 and recursively
# call the all_paths method for them to find all the paths
# from the adjacent node to node2.
# The adjacent nodes are the ones in the value lists in
# the graph dictionary.
for node in self.__graph[node1]:
if node not in path:
subpaths = self.all_paths(node, node2, path)
for subpath in subpaths:
paths.append(subpath)
return paths
# And now the other method that returns the shortest path.
# We'll just use the method that finds all the paths and then
# select the one with the minimum number of nodes.
# If there are more than one path with the minimum number of nodes,
# the first one will be returned.
def shortest_path(self, node1, node2):
return sorted(self.all_paths(node1, node2), key = len)[0]
g = Graph(graph)
Let’s now use the two methods in our code:
print("The paths from 'a' to 'b':")
print(g.all_paths('a', 'b'))
print("The shortest path: ", g.shortest_path('a', 'b'))
print("\nThe paths from 'e' to 'a':")
print(g.all_paths('e', 'a'))
print("The shortest path: ", g.shortest_path('e', 'a'))
print("\nThe paths from 'f' to 'e':")
print(g.all_paths('f', 'e'))
print("The shortest path: ", g.shortest_path('f', 'e'))
Here’s the output:
The paths from 'a' to 'b':
[['a', 'd', 'b'], ['a', 'd', 'f', 'b']]
The shortest path: ['a', 'd', 'b']
The paths from 'e' to 'a':
[['e', 'd', 'a']]
The shortest path: ['e', 'd', 'a']
The paths from 'f' to 'e':
[['f', 'b', 'd', 'e'], ['f', 'd', 'e']]
The shortest path: ['f', 'd', 'e']
Make Awesome Games and Other 3D Apps
with Panda3D and Blender using Python.
Cool stuff, easy to follow articles.
Get the magazine here (PDF).
A More Complex Graph
Let’s now test our path finding on a more complex graph. Here it is:
And here’s the graph dictionary:
complex_graph = {'a': ['b', 'e', 'i'],
'b': ['a', 'f'],
'c': ['d', 'f'],
'd': ['c', 'l'],
'e': ['a', 'g'],
'f': ['b', 'c', 'g'],
'g': ['e', 'f', 'i', 'j'],
'h': ['j', 'l'],
'i': ['a', 'g'],
'j': ['g', 'h', 'k'],
'k': ['j'],
'l': ['d', 'h']}
Learn the basics of Python, including OOP.
with lots of exercises, easy to follow
The course is available on Udemy.
Now let’s find some paths:
g = Graph(complex_graph)
print("The paths from 'a' to 'i':")
print(g.all_paths('a', 'i'))
print("The shortest path: ", g.shortest_path('a', 'i'))
print("\nThe paths from 'b' to 'g':")
print(g.all_paths('b', 'g'))
print("The shortest path: ", g.shortest_path('b', 'g'))
And here’s the output. As you can see, our methods work:
The paths from 'a' to 'i':
[['a', 'b', 'f', 'c', 'd', 'l', 'h', 'j', 'g', 'i'], ['a', 'b', 'f', 'g', 'i'], ['a', 'e', 'g', 'i'], ['a', 'i']]
The shortest path: ['a', 'i']
The paths from 'b' to 'g':
[['b', 'a', 'e', 'g'], ['b', 'a', 'i', 'g'], ['b', 'f', 'c', 'd', 'l', 'h', 'j', 'g'], ['b', 'f', 'g']]
The shortest path: ['b', 'f', 'g']
Learn the basics of 3D modeling in Blender.
step-by-step, easy to follow, visually rich
The course is available on Udemy and on Skillshare.
Here’s the video version of the article: