#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Copyright (c) 2012 Jérémie DECOCK (http://www.jdhp.org)

# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:

# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.

class Node:
    """Node class"""

    def __init__(self, _value, _child_nodes = []):
        self.value = _value
        self.child_nodes = _child_nodes


traversed_nodes = []

def walk(node):
    """The graph traversal function"""

    traversed_nodes.append(node)
    
    # Do something with node value...
    print node.value

    # Recurse on each child node
    for child_node in node.child_nodes:
        if child_node not in traversed_nodes:
            walk(child_node)


def main():
    """Main function

    Build the following test graph and traverse it.

       ╭─▶ 1
       │  ↙↓↘ 
       │ 2 3 4
       │↙ ↘ ↗
       5   6

    "Depth-first search" traversal should print: 1, 2, 5, 6, 4, 3.
    """

    # Build the test graph
    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n4 = Node(4)
    n5 = Node(5)
    n6 = Node(6)
    n1.child_nodes = [n2, n3, n4]
    n2.child_nodes = [n5, n6]
    n5.child_nodes = [n1]
    n6.child_nodes = [n4]

    # Traverse the graph
    walk(n1)


if __name__ == '__main__':
    main()

3e05810773260bcc5f36d9d5d0e56642fee8b1c5
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Copyright (c) 2012 Jérémie DECOCK (http://www.jdhp.org)

# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:

# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.

class Node:
    """Node class"""

    def __init__(self, _value, _child_nodes = []):
        self.value = _value
        self.child_nodes = _child_nodes


traversed_nodes = []

def walk(node):
    """The graph traversal function"""

    traversed_nodes.append(node)
    
    # Do something with node value...
    print node.value

    # Recurse on each child node
    for child_node in node.child_nodes:
        if child_node not in traversed_nodes:
            walk(child_node)


def main():
    """Main function

    Build the following test graph and traverse it.

       ╭─▶ 1
       │  ↙↓↘ 
       │ 2 3 4
       │↙ ↘ ↗
       5   6

    "Depth-first search" traversal should print: 1, 2, 5, 6, 4, 3.
    """

    # Build the test graph
    n1 = Node(1)
    n2 = Node(2)
    n3 = Node(3)
    n4 = Node(4)
    n5 = Node(5)
    n6 = Node(6)
    n1.child_nodes = [n2, n3, n4]
    n2.child_nodes = [n5, n6]
    n5.child_nodes = [n1]
    n6.child_nodes = [n4]

    # Traverse the graph
    walk(n1)


if __name__ == '__main__':
    main()
