graph_adjaceny_list.py

"""
Implementation of Undirected Graph using Adjaceny Lists
"""


class Vertex(object):
    def __init__(self, name):
        self.name = name
        self.neighbors = list()

    def add_neighbor(self, v):
        if v not in self.neighbors:
            self.neighbors.append(v)
            self.neighbors.sort()


class Graph(object):
    vertices = {}

    def add_vertex(self, vertex):
        if isinstance(vertex, Vertex) and vertex.name not in self.vertices:
            self.vertices[vertex.name] = vertex
            return True
        else:
            return False

    def add_edge(self, u, v):
        if u in self.vertices and v in self.vertices:
            self.vertices[u].add_neighbor(v)
            self.vertices[v].add_neighbor(u)
            return True
        else:
            return False

    def print_graph(self):
        for key in sorted(list(self.vertices.keys())):
            print(key + str(self.vertices[key].neighbors))


if __name__ == "__main__":


        g = Graph()
        a = Vertex('A')
        g.add_vertex(a)
        g.add_vertex(Vertex('B'))
        for i in range(ord('A'), ord('K')):
            g.add_vertex(Vertex(chr(i)))

        edges = ['AB', 'AE', 'BF', 'CG', 'DE', 'DH', 'EH', 'FG', 'FI', 'FJ', 'GJ', 'HI']

        for edge in edges:
            g.add_edge(edge[:1], edge[1:])


        g.print_graph()