Graph visit algorithms

graph_visit.py

# -*- coding: utf-8 -*-

from __future__ import unicode_literals, division, absolute_import

from collections import deque


class Node(object):
    def __init__(self, value, children=None):
        self.value = value
        self.children = children

    def __str__(self):
        return '(%s %s)' % (self.value, ''.join(str(child) for child in self.children))


def _search(start_node, target_value, extract_method):
    to_visit = deque([start_node])
    while to_visit:
        current_node = extract_method(to_visit)
        print current_node
        if current_node.value == target_value:
            return current_node
        to_visit.extend(current_node.children)


def breadth_first_search(start_node, target_value):
    return _search(start_node=graph, target_value=target_value, extract_method=deque.popleft)


def depth_first_search(start_node, target_value):
    return _search(start_node=graph, target_value=target_value, extract_method=deque.pop)


if __name__ == '__main__':
    graph = Node(
        1, children=[
            Node(
                2, children=[]
            ),
            Node(
                3, children=[
                    Node(
                        6, children=[]
                    ),
                    Node(
                        4, children=[]
                    ),
                    Node(
                        5, children=[]
                    )
                ]
            )
        ]
    )
    print 'graph: %s' % graph
    print
    print 'BFS: %s' % breadth_first_search(start_node=graph, target_value=6)
    print
    print 'DFS: %s' % depth_first_search(start_node=graph, target_value=6)