Skip to content

Instantly share code, notes, and snippets.

@tahia-khan tahia-khan/graph.py
Last active Nov 9, 2015

Embed
What would you like to do?
# 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.