• 1

• 31.7k
• 15
• 77
• 201

I have refactored the version of the previous (and initial) iteration according to the answer by alexwlchan. As a reminder, this snippet compares breadth-first search against its bidirectional variant. See what I have:

#! /usr/bin/env python3.4
import time
import random
from collections import deque
__author__ = 'Rodion "rodde" Efremov'
class DirectedGraphNode:
 """This class implements a node type for a directed graph."""
 def __init__(self, name):
 """Initializes a new DirectedGraphNode with a given name, and creates two sets for reprsenting child and parent
 nodes of this node."""
 if name is None:
 raise ValueError("The name of a new node is None.")
 self.name = name
 self.children = set()
 self.parents = set()
 def __hash__(self):
 """Makes this node eligible for using as a key in hash tables."""
 return self.name.__hash__()
 def __eq__(self, other):
 """Makes it possible to use another node with the same name as a key for hash tables."""
 return self.name == other.name
 def __str__(self):
 return "[DirectedGraphNode: " + self.name + "]"
 def __repr__(self):
 return '%s(%r)' % (self.__class__.__name__, self.name)
 def add_child(self, child):
 """Makes 'child' a child node of this node. This creates a directed arc from this node to 'child'."""
 self.children.add(child)
 child.parents.add(self)
 def has_child(self, child_candidate):
 """Checks that there is an arc from this node to 'child_candidate'."""
 return child_candidate in self.children
def traceback_path(target, parents):
 """Builds the path from implicit source node to the target node 'target' using the parent map 'parents'."""
 path = []
 current = target
 while current:
 path.append(current)
 current = parents[current]
 return list(reversed(path))
def bi_traceback_path(touch_node, parents_a, parents_b):
 """Builds a shortest path after a bidirectional search."""
 path = traceback_path(touch_node, parents_a)
 current = parents_b[touch_node]
 while current:
 path.append(current)
 current = parents_b[current]
 return path
def breadth_first_search(source, target):
 """Implements (unidirectional) breadth-first search for finding shortest (unweighted) paths between two input
 nodes ('source' and 'target')."""
 queue = deque([source])
 parents = {source: None}
 while queue:
 current = queue.popleft()
 if current is target:
 return traceback_path(target, parents)
 for child in current.children:
 if child not in parents.keys():
 parents[child] = current
 queue.append(child)
 return []
def bidirectional_breadth_first_search(source, target):
 """Implements a bidirectional breadth-first search for finding shortest (unweighted) paths between two input nodes
 ('source' and 'target')."""
 queue_a = deque([source])
 queue_b = deque([target])
 parents_a = {source: None}
 parents_b = {target: None}
 distance_a = {source: 0}
 distance_b = {target: 0}
 best_cost = {'value': 1000000000} # best_cost is ugly
 touch_node = {'value': None}
 """Implements an actual routine for generating all the neighbors of a node."""
 def expand(queue, distance, distance_opposite, neighbors, parents):
 current = queue.popleft()
 if current in distance_opposite.keys() and best_cost['value'] > dist_a + dist_b:
 best_cost ['value'] = dist_a + dist_b
 touch_node['value'] = current
 for neighbor in neighbors:
 if neighbor not in distance.keys():
 distance[neighbor] = distance[current] + 1
 parents[neighbor] = current
 queue.append(neighbor)
 while queue_a and queue_b:
 dist_a = distance_a[queue_a[0]]
 dist_b = distance_b[queue_b[0]]
 if touch_node['value'] and best_cost['value'] < dist_a + dist_b:
 return bi_traceback_path(touch_node['value'],
 parents_a,
 parents_b)
 # Trivial load balancing
 if len(distance_a) < len(distance_b):
 expand(queue_a,
 distance_a,
 distance_b,
 queue_a[0].children,
 parents_a)
 else:
 expand(queue_b,
 distance_b,
 distance_a,
 queue_b[0].parents,
 parents_b);
 return []
def create_directed_graph(nodes, edges):
 """Creates a random directed graph."""
 graph = [DirectedGraphNode(str(i + 1)) for i in range(nodes)]
 for _ in range(0, edges):
 j = random.randint(0, nodes - 1)
 k = random.randint(0, nodes - 1)
 graph[j].add_child(graph[k])
 return graph
def main():
 """Shows the performance demo by comparing the two BFS implementations."""
 graph = create_directed_graph(300000, 1000000)
 source = random.choice(graph)
 target = random.choice(graph)
 print("Source: ", source)
 print("Target: ", target)
 start_time = time.time()
 path1 = breadth_first_search(source, target)
 end_time = time.time()
 print("BFS path length", len(path1), ":")
 for node in path1:
 print(node)
 print("Time elapsed:", 1000.0 * (end_time - start_time), "milliseconds.")
 print()
 start_time = time.time()
 path2 = bidirectional_breadth_first_search(source, target)
 end_time = time.time()
 print("BiBFS path length", len(path2), ":")
 for node in path2:
 print(node)
 print("Time elapsed:", 1000.0 * (end_time - start_time), "milliseconds.")
if __name__ == "__main__":
 main()

What comes to performance, I get the following figures:

Source: [DirectedGraphNode: 175136]
Target: [DirectedGraphNode: 201592]
BFS path length 10 :
[DirectedGraphNode: 175136]
[DirectedGraphNode: 261456]
[DirectedGraphNode: 197655]
[DirectedGraphNode: 204679]
[DirectedGraphNode: 173619]
[DirectedGraphNode: 181346]
[DirectedGraphNode: 196030]
[DirectedGraphNode: 255045]
[DirectedGraphNode: 33826]
[DirectedGraphNode: 201592]
Time elapsed: 353.32489013671875 milliseconds.
BiBFS path length 10 :
[DirectedGraphNode: 175136]
[DirectedGraphNode: 261456]
[DirectedGraphNode: 197655]
[DirectedGraphNode: 204679]
[DirectedGraphNode: 173619]
[DirectedGraphNode: 181346]
[DirectedGraphNode: 196030]
[DirectedGraphNode: 255045]
[DirectedGraphNode: 33826]
[DirectedGraphNode: 201592]
Time elapsed: 1.5559196472167969 milliseconds.

Please, tell me anything that comes to mind.