# -*- coding: utf-8 -*-
from __future__ import unicode_literals


class Graph(object):

    def __init__(self):
        """Create a new empty graph."""
        self.gdict = {}

    def nodes(self):
        """Return a list of nodes in the graph."""
        return self.gdict.keys()

    def edges(self):
        """Return a list of edges in the graph."""
        self.edges = []
        for node in self.gdict:
            for end in self.gdict[node]:
                self.edges.append((node, end))
        return self.edges

    def add_node(self, n):
        """Add a node n into the graph.
        Nodes must be hashable."""
        self.gdict.setdefault(n, [])

    def add_edge(self, n1, n2):
        """Add an edge connecting n1 and n2 to the graph."""
        self.gdict.setdefault(n2, [])
        try:
            self.gdict[n1].append(n2)
        except KeyError:
            self.gdict[n1] = [n2]

    def del_node(self, n):
        """Delete node n from the graph."""
        try:
            del self.gdict[n]
        except KeyError:
            raise KeyError('{} not in the graph.'.format(n))
        for nodelist in self.gdict.values():
            try:
                nodelist.remove(n)
            except ValueError:
                continue

    def del_edge(self, n1, n2):
        """Delete the edge connecting n1 and n2 from the graph."""
        try:
            self.gdict[n1].remove(n2)
        except (KeyError, ValueError):
            raise ValueError('Edge {}, {} not in the graph.'.format(n1, n2))

    def has_node(self, n):
        """Return True if n is in the graph, else False."""
        return n in self.gdict

    def neighbors(self, n):
        """Return the list of nodes n is pointing to."""
        try:
            return self.gdict[n]
        except KeyError:
            raise KeyError('{} not in the graph.'.format(n))

    def adjacent(self, n1, n2):
        """Return True if there is an edge connecting n1 and n2, else False."""
        if n1 not in self.gdict or n2 not in self.gdict:
            raise KeyError('One of these nodes is not in the graph.')
        return n2 in self.gdict[n1]

@@ -2134,8 +2134,1226 @@
 ict%5Bn1%5D%0A
+%0A    def depth_first_traversal(self, start):%0A        return self._depth_first_traversal(start, %5B%5D)%0A%0A    def _depth_first_traversal(self, current, visited):%0A        visited.append(current)%0A        for neighbor in self.neighbors(current):%0A            if neighbor not in visited:%0A                self._depth_first_traversal(neighbor, visited)%0A        return visited%0A%0A    def breadth_first_traversal(self, start):%0A        from queue import Queue%0A        q = Queue()%0A        q.enqueue(start)%0A        visited = %5Bstart%5D%0A        while q.size() %3E 0:%0A            current = q.dequeue()%0A            for neighbor in current.neighbors():%0A                if neighbor not in visited:%0A                    q.enqueue(neighbor)%0A                    visited.append(neighbor)%0A        return visited%0A%0A    def depth_first_traversal(self, start):%0A        from stack import Stack%0A        s = Stack()%0A        s.push(start)%0A        visited = %5B%5D%0A        while True:%0A            try:%0A                current = s.pop()%0A            except IndexError:%0A                return visited%0A            if current not in visited:%0A                visited.append(current)%0A                for neighbor in current.neighbors():%0A                    s.push(neighbor)%0A

add graph traversal functions to simple_graph.py