3
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.