In [1]:

    

# A Graph implementation
# Source: http://stackoverflow.com/questions/19472530/representing-graphs-data-structure-in-python
from collections import defaultdict


class Graph(object):
    """ Graph data structure, undirected by default. """

    def __init__(self, connections, directed=False):
        self._graph = defaultdict(set)
        self._directed = directed
        self.add_connections(connections)

    def add_connections(self, connections):
        """ Add connections (list of tuple pairs) to graph """

        for node1, node2 in connections:
            self.add(node1, node2)

    def add(self, node1, node2):
        """ Add connection between node1 and node2 """

        self._graph[node1].add(node2)
        if not self._directed:
            self._graph[node2].add(node1)

    def remove(self, node):
        """ Remove all references to node """

        for n, cxns in self._graph.iteritems():
            try:
                cxns.remove(node)
            except KeyError:
                pass
        try:
            del self._graph[node]
        except KeyError:
            pass

    def is_connected(self, node1, node2):
        """ Is node1 directly connected to node2 """

        return node1 in self._graph and node2 in self._graph[node1]

    def find_path(self, node1, node2, path=[]):
        """ Find any path between node1 and node2 (may not be shortest) """

        path = path + [node1]
        if node1 == node2:
            return path
        if node1 not in self._graph:
            return None
        for node in self._graph[node1]:
            if node not in path:
                new_path = self.find_path(node, node2, path)
                if new_path:
                    return new_path
        return None

    def __str__(self):
        return '{}({})'.format(self.__class__.__name__, dict(self._graph))


    

In [7]:

    

# An example of an undirected graph implementation
import pprint as pp

p = pp.PrettyPrinter(indent=4)
connections = [('A', 'B'), ('B', 'C'), ('B', 'D'), ('C', 'D'), ('E', 'F'), ('F', 'C')]
g = Graph(connections, directed=True)
p.pprint(g._graph)

g = Graph(connections)  # undirected
p.pprint(g._graph)
g.add('E', 'D')
p.pprint(g._graph)
g.remove('A')
p.pprint(g._graph)
g.add('G', 'B')
p.pprint(g._graph)
g.find_path('G', 'E')


    

    




defaultdict(<class 'set'>,
            {   'A': {'B'},
                'B': {'C', 'D'},
                'C': {'D'},
                'E': {'F'},
                'F': {'C'}})
defaultdict(<class 'set'>,
            {   'A': {'B'},
                'B': {'C', 'A', 'D'},
                'C': {'F', 'B', 'D'},
                'D': {'B', 'C'},
                'E': {'F'},
                'F': {'E', 'C'}})
defaultdict(<class 'set'>,
            {   'A': {'B'},
                'B': {'C', 'A', 'D'},
                'C': {'F', 'B', 'D'},
                'D': {'B', 'E', 'C'},
                'E': {'F', 'D'},
                'F': {'E', 'C'}})






    




---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-7-0c0c8c67df4e> in <module>()
     11 g.add('E', 'D')
     12 p.pprint(g._graph)
---> 13 g.remove('A')
     14 p.pprint(g._graph)
     15 g.add('G', 'B')

<ipython-input-1-87f3d40aa384> in remove(self, node)
     28         """ Remove all references to node """
     29 
---> 30         for n, cxns in self._graph.iteritems():
     31             try:
     32                 cxns.remove(node)

AttributeError: 'collections.defaultdict' object has no attribute 'iteritems'

In [ ]: