graph.py

# graph.py

class Vertex:
    def __init__(self, x):
        self.x = x
        self.edges = {}

    def __str__(self):
        return "Vertex %d: %s" % (self.x, self.edges)

    def __repr__(self):
        return "Vertex %d: %s" % (self.x, self.edges)

    def insert_edge(self, y, weight):
        if not self.edges.get(y):
            self.edges[y] = Edge(y, weight)

class Edge:
    def __init__(self, y, weight):
        self.y = y
        self.weight = weight

    def __str__(self):
        return "(%d)" % (self.weight)

    def __repr__(self):
        return "(%d)" % (self.weight)


class Graph:
    def __init__(self, directed=False):
        self.vertex = {}
        self.directed = directed
        self.num_edges = 0
        self.num_vertices = 0

    def __str__(self):
        s = ""
        for v in self.vertex.itervalues():
            s += "Vertex %d: %s \n" % (v.x, v.edges)
        return s

    def create_link(self, x, y, weight=1, directed=False):
        if not self.vertex.get(x):
            self.vertex[x] = Vertex(x)
            self.num_vertices += 1

        self.vertex[x].insert_edge(y, weight)

        if not directed:
            self.create_link(y, x, weight, True)
        else:
            self.num_edges += 1


 def bfs(g, source):
     undiscovered, discovered, processed = 0, 1, 2
 
     status = [0] * (g.num_vertices + 1)
     path = [0] * (g.num_vertices + 1)
     queue = [source]
 
     for v in g.vertex:
         status[v] = undiscovered
         path[v] = -1
 
     while queue:
         v = queue.pop(0)
         for child in g.vertex[v].edges:
             if status[child] is undiscovered:
                 status[child] = discovered
                 path[child] = v
                 queue.append(child)
         status[v] = processed
         
     return path



def dfs_paths_iter(g, source):
     paths = {source: []}
     stack = [source]
 
     while stack:
         v = stack.pop(0)
         for child in g.vertex[v].edges:
             if child not in paths:
                 paths[child] = list(paths.get(v))
                 paths[child].append(v)
                 stack.insert(0,child)
 
     return paths



g = Graph()
g.create_link(1, 2)
g.create_link(1, 5)
g.create_link(2, 5)
g.create_link(2, 4)
g.create_link(2, 3)
g.create_link(3, 4)
g.create_link(4, 5)

print(g)