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'."""

    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:
        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:
        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

    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

    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'],
        # Trivial load balancing
        if len(distance_a) < len(distance_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)

    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("Time elapsed:", 1000.0 * (end_time - start_time), "milliseconds.")

    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("Time elapsed:", 1000.0 * (end_time - start_time), "milliseconds.")

if __name__ == "__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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.