copy_graph.py

"""
Given an input node that connects to a graph, return a deep copy of the node.
"""

class Node(object):

    def __init__(self, item):
        self.item = item
        self.neighbors = []

    def __repr__(self):
        return self.item

    def add_neighbor(self, neighbor_node):
        self.neighbors.append(neighbor_node)

    def get_neighbors(self):
        return self.neighbors

    def deep_copy(self, visited):
        copy = Node(self.item)
        visited[self] = copy
        stack = []
        for neighbor in self.get_neighbors():
            if neighbor not in visited:
                copy.add_neighbor(neighbor.deep_copy(visited))
            else:
                copy.add_neighbor(visited[neighbor])

        return copy


a = Node("a")
b = Node("b")
c = Node("c")
a.add_neighbor(b)
b.add_neighbor(c)
c.add_neighbor(a)


tmp = {}
a_prime = a.deep_copy(tmp)
print tmp
b = a_prime.get_neighbors()[0]
b.item = "b_prime"

print a.get_neighbors()
print a_prime.get_neighbors()