How to use bidirectional search implementation in Python

A graph is a network of nodes connected by arcs or edges.

The two basic graph search algorithms, Breadth-First SearchBFS and Depth-First SearchDFS aim to find a path between 2 nodes (preferably the shortest) and determine cycles in the graph.

A graph search is done in one direction, either from the source/initial vertex to the goal/target vertex.

To search from both ends simultaneously, a bidirectional search is implemented.

Bidirectional search

Bidirectional search is a graph search algorithm that finds the shortest path from a source vertex to a goal vertex.

In implementing bidirectional search in Python, the graph search can either be:

  1. Forward search from the source to the goal vertex.
  2. Backward search from the goal to the source vertex.

The intersection of both forward and backward graphs indicates the end of the search, as displayed below.

Advantages and disadvantages of bidirectional search in Python

Advantage Disadvantage
1. Less time consuming as the shortest path length is used for the search. The goal node has to be known before the search can be done simultaneously in both directions.

When is it possible to use bidirectional search in Python?

The bidirectional approach can be used:

  1. When the branching factor for the forward and reverse direction is the same.
  2. When both the source and goal vertices are specified and distinct from each other.
Bidirectional search implementation in Python

Below is an implementation of bidirectional search in Python using BFS:

class adjacent_Node:
	
	def __init__(self, v):
		
		self.vertex = v
		self.next = None
class bidirectional_Search:
	
	def __init__(self, vertices):
		
		self.vertices = vertices
		self.graph = [None] * self.vertices
		
		self.source_queue = list()
		self.last_node_queue = list()
		
		
		self.source_visited = [False] * self.vertices
		self.last_node_visited = [False] * self.vertices
		
		
		self.source_parent = [None] * self.vertices
		self.last_node_parent = [None] * self.vertices
		
	
	def AddEdge(self, source, last_node):
		
		node = adjacent_Node(last_node)
		node.next = self.graph[source]
		self.graph[source] = node
		node = adjacent_Node(source)
		node.next = self.graph[last_node]
		self.graph[last_node] = node
		
	
	def breadth_fs(self, direction = 'forward'):
		
		if direction == 'forward':
		
			current = self.source_queue.pop(0)
			connected_node = self.graph[current]
			
			while connected_node:
				vertex = connected_node.vertex
				
				if not self.source_visited[vertex]:
					self.source_queue.append(vertex)
					self.source_visited[vertex] = True
					self.source_parent[vertex] = current
					
				connected_node = connected_node.next
		else:
			
			current = self.last_node_queue.pop(0)
			connected_node = self.graph[current]
			
			while connected_node:
				vertex = connected_node.vertex
				
				if not self.last_node_visited[vertex]:
					self.last_node_queue.append(vertex)
					self.last_node_visited[vertex] = True
					self.last_node_parent[vertex] = current
					
				connected_node = connected_node.next
				
	
	def is_intersecting(self):
		
		#
		for i in range(self.vertices):
			if (self.source_visited[i] and
				self.last_node_visited[i]):
				return i
				
		return -1
	
	def path_st(self, intersecting_node,
				source, last_node):
						
	
		path = list()
		path.append(intersecting_node)
		i = intersecting_node
		
		while i != source:
			path.append(self.source_parent[i])
			i = self.source_parent[i]
			
		path = path[::-1]
		i = intersecting_node
		
		while i != last_node:
			path.append(self.last_node_parent[i])
			i = self.last_node_parent[i]
			
		print("*****Path*****")
		path = list(map(str, path))
		
		print(' '.join(path))
	
	def bidirectional_search(self, source, last_node):
		
		self.source_queue.append(source)
		self.source_visited[source] = True
		self.source_parent[source] = -1
		
		self.last_node_queue.append(last_node)
		self.last_node_visited[last_node] = True
		self.last_node_parent[last_node] = -1
		while self.source_queue and self.last_node_queue:
			
		
			self.breadth_fs(direction = 'forward')
			
			self.breadth_fs(direction = 'backward')
				
			intersecting_node = self.is_intersecting()
			
			if intersecting_node != -1:
				print("Path exists between {} and {}".format(source, last_node))
				print("Intersection at : {}".format(intersecting_node))
				self.path_st(intersecting_node,
								source, last_node)
				exit(0)
		return -1
if __name__ == '__main__':
	
	n = 17
	
	source = 1
	
	last_node = 16
	
	my_Graph = bidirectional_Search(n)
	my_Graph.AddEdge(1, 4)
	my_Graph.AddEdge(2, 4)
	my_Graph.AddEdge(3, 6)
	my_Graph.AddEdge(5, 6)
	my_Graph.AddEdge(4, 8)
	my_Graph.AddEdge(6, 8)
	my_Graph.AddEdge(8, 9)
	my_Graph.AddEdge(9, 10)
	my_Graph.AddEdge(10, 11)
	my_Graph.AddEdge(11, 13)
	my_Graph.AddEdge(11, 14)
	my_Graph.AddEdge(10, 12)
	my_Graph.AddEdge(12, 15)
	my_Graph.AddEdge(12, 16)
	
	out = my_Graph.bidirectional_search(source, last_node)
	
	if out == -1:
		print("No path between {} and {}".format(source, last_node))

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)