Depth First Search in Python (including cycles)

Question

so i saw the following post in StackOverflow regarding DFS algorithm in Python(very helpful):

Does this python code employs Depth First Search (DFS) for finding all paths?

I also have a graph that need to analyze (to find every possible path between two nodes), but I need to include the cycles there also. For example, if I have a graph like this:

graph = {'Start': ['1'],
             '1': ['2'],
             '2': ['3','End'],
             '3': ['2','End']}

I would like to have the following output:

Start, 1, 2, 3, End
Start, 1, 2, End
Start, 1, 2, 3, 2, End
Start, 1, 2, 3, 2, 3, End

Is there any possible way to change the following code in order to do this?

def find_all_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if not graph.has_key(start):
            return []
        paths = []
        for node in graph[start]:
            if node not in path:
                paths += find_all_paths(graph, node, end, path)
        return paths

print find_all_paths(graph, 'Start', 'End')

Answer 1

This is not something you want to do with a simplistic Depth-First Search (DFS).

DFS, going depth-first, will be blocked if it hits a cycle. Cycles are infinitely-deep.

If you want to output (probably using a generator) the inifnite paths to each node when including cycles, you should use a Breadth-First Search (BFS). Being Breadth-first, means that a cycle won't block it from reaching other paths.

The give-and-take here is that Breadth-First Search consumes more memory, keeping more lists alive during it's run. If that's a problem, you should use DFS's iterative deepening solution.

Simple BFS Solution:

Using a Queue (BFS is easily implemented using a queue, DFs using a stack, as you can see here):

#!/usr/bin/env python

import Queue

graph = {'Start': ['1'],
             '1': ['2'],
             '2': ['3','End'],
             '3': ['2','End']}

expand_queue = Queue.Queue()

def BFS_generator(graph, start, end, path):
    # initialize generator
    expand_queue.put((graph, start, end, path))

    while not expand_queue.empty():
        graph, current, end, path = expand_queue.get()

        if current == end:
            # route done - yield result
            yield path + [current]

        if current in graph:
            # skip neighbor-less nodes
            for neighbor in graph[current]:
                # put all neighbors last in line to expand
                expand_queue.put((graph, neighbor, end, path + [current]))

gen = BFS_generator(graph, "Start", "End", [])

# get only 10 first paths
for _ in xrange(10):
    print next(gen)

Output:

['Start', '1', '2', 'End']
['Start', '1', '2', '3', 'End']
['Start', '1', '2', '3', '2', 'End']
['Start', '1', '2', '3', '2', '3', 'End']
['Start', '1', '2', '3', '2', '3', '2', 'End']
['Start', '1', '2', '3', '2', '3', '2', '3', 'End']
['Start', '1', '2', '3', '2', '3', '2', '3', '2', 'End']
['Start', '1', '2', '3', '2', '3', '2', '3', '2', '3', 'End']
['Start', '1', '2', '3', '2', '3', '2', '3', '2', '3', '2', 'End']
['Start', '1', '2', '3', '2', '3', '2', '3', '2', '3', '2', '3', 'End']

Generalizing the solution to both DFS and BFS, with iterative deepening:

You can also have a more general code that either uses a Queue or a Stack and then you easily have an iterative solution using either BFS (queue) or DFS(stack). Depends on what you need.

So first create a Stack class (for interface purposes, list has all we need):

class Stack():

    def __init__(self):
        self.stack = []

    def get(self):
        return self.stack.pop(0)

    def put(self, item):
        self.stack.insert(0, item)

    def empty(self):
        return len(self.stack) == 0

Now that you have both Queue and stack, a simple generalization for the algorithm, making it iterative and data-structure agnostic, will give us both solutions if we change the data structure used:

def iterative_search(data_structure, graph, start, end, limit=None):
    # initialize generator
    data_structure.put((graph, start, end,[]))

    while not data_structure.empty():
        graph, current, end, path = data_structure.get()

        if limit and len(path) > limit:
            continue

        if current == end:
            # route done - yield result
            yield tuple(path + [current])

        if current in graph:
            # skip neighbor-less nodes
            for neighbor in graph[current]:
                # store all neighbors according to data structure
                data_structure.put(
                    (graph, neighbor, end, path + [current])
                )

Putting the whole thing together:

We can see they select different routes (I've changed graph a bit to make it more interesting):

import Queue

class Stack():

    def __init__(self):
        self.stack = []

    def get(self):
        return self.stack.pop(0)

    def put(self, item):
        self.stack.insert(0, item)

    def empty(self):
        return len(self.stack) == 0

graph = {'Start': ['1'],
             '1': ['2'],
             '2': ['3','End'],
             '3': ['2', '4','End'],
             '4': ['3']}


def iterative_search(data_structure, graph, start, end, limit=None):
    # initialize generator
    data_structure.put((graph, start, end,[]))

    while not data_structure.empty():
        graph, current, end, path = data_structure.get()

        # make solution depth limited
        # makes it iterative - for DFS to use all paths
        if limit and len(path) > limit:
            continue

        if current == end:
            # route done - yield result
            yield tuple(path + [current])

        if current in graph:
            # skip neighbor-less nodes
            for neighbor in graph[current]:
                # store all neighbors according to data structure
                data_structure.put(
                    (graph, neighbor, end, path + [current])
                )

Now that we have a generalized function for iteratice DFS and BFS, we can compare the solutions they provide:

import os

# bfs - using queue
gen = iterative_search(Queue.Queue(), graph, "Start", "End")
print "BFS"
# get only 10 first paths
bfs_path_set = set()
while len(bfs_path_set) < 10:
    bfs_path_set.add(next(gen))

print os.linesep.join(map(str, bfs_path_set))

print "Iterative DFS"
# dfs  - using stack
gen = iterative_search(Stack(), graph, "Start", "End", limit=5)

# get only 10 first paths
dfs_path_set = set()
limit = 1
while len(dfs_path_set) < 10:
    try:
        dfs_path_set.add(next(gen))
    except StopIteration:
        limit += 1
        print "depth limit reached, increasing depth limit to %d" % limit
        gen = iterative_search(
            Stack(), graph, "Start", "End", limit=limit
        )

print os.linesep.join(map(str, dfs_path_set))

print "difference BFS - DFS: %s" % str(bfs_path_set - dfs_path_set)
print "difference DFS - BFS: %s" % str(dfs_path_set - bfs_path_set)

Output:

BFS
('Start', '1', '2', '3', '2', '3', '4', '3', 'End')
('Start', '1', '2', '3', '2', '3', '2', '3', 'End')
('Start', '1', '2', '3', '2', '3', '2', 'End')
('Start', '1', '2', '3', '4', '3', '2', 'End')
('Start', '1', '2', '3', '4', '3', 'End')
('Start', '1', '2', '3', 'End')
('Start', '1', '2', '3', '4', '3', '2', '3', 'End')
('Start', '1', '2', '3', '2', '3', 'End')
('Start', '1', '2', '3', '2', 'End')
('Start', '1', '2', 'End')
Iterative DFS
limit reached, increasing limit to 2
limit reached, increasing limit to 3
limit reached, increasing limit to 4
limit reached, increasing limit to 5
limit reached, increasing limit to 6
limit reached, increasing limit to 7
limit reached, increasing limit to 8
('Start', '1', '2', '3', '2', '3', '4', '3', 'End')
('Start', '1', '2', '3', '4', '3', '4', '3', 'End')
('Start', '1', '2', '3', '2', '3', '2', 'End')
('Start', '1', '2', '3', '4', '3', '2', 'End')
('Start', '1', '2', '3', '4', '3', 'End')
('Start', '1', '2', '3', 'End')
('Start', '1', '2', '3', '4', '3', '2', '3', 'End')
('Start', '1', '2', '3', '2', '3', 'End')
('Start', '1', '2', '3', '2', 'End')
('Start', '1', '2', 'End')
difference BFS - DFS: set([('Start', '1', '2', '3', '2', '3', '2', '3', 'End')])
difference DFS - BFS: set([('Start', '1', '2', '3', '4', '3', '4', '3', 'End')])

Notes:

Difference in solutions: You can see the solutions vary in their path selection. You can verify they do end up getting all paths by setting the length of solutions to 11 instead of 10 (this would make both solution sets identical - as they will consume all 9-length solutions).

Memory consumption: It's important to note that this implementation of DFS isn't optimal since it does store all neighbors of nodes along the way. It should be generally better than BFS, that stores more neighbors before consuming them, but a more optimal solution that uses backtracking and recursion should exist.

Answer 2

As mentioned in the comment, your algorithm has no reason to terminate if you allow arbitrary cycles. What you could do is allow for a maximum path length and dismiss all paths that are too long:

def find_all_paths(graph, start, end, path=[], max_length=10):
    if len(path) >= max_length:
        return []
    path = path + [start]
    if start == end:
        return [path]
    if start not in graph:
        return []
    paths = []
    for node in graph[start]:
        paths += find_all_paths(graph, node, end, path, max_length=max_length)
    return paths

with

graph = {'Start': ['1'],
         '1': ['2'],
         '2': ['3','End'],
         '3': ['2','End']}

print find_all_paths(graph, 'Start', 'End', max_length=10)

your algorithm prints:

[['Start', '1', '2', '3', '2', '3', '2', '3', '2', 'End'], ['Start', '1', '2', '3', '2', '3', '2', '3', 'End'], ['Start', '1', '2', '3', '2', '3', '2', 'End'], ['Start', '1', '2', '3', '2', '3', 'End'], ['Start', '1', '2', '3', '2', 'End'], ['Start', '1', '2', '3', 'End'], ['Start', '1', '2', 'End']]

EDIT:

Replaced not graph.has_key with the more pythonic start not in graph