# Simple Graph in Python

Just the beginning of graphs API in Python:

# Simple graph API in Python, implementation uses adjacent lists.
# Classes: Graph, Depth_first_search, Depth_first_paths
# Usage:
# Creating new graph: gr1 = Graph(v) - creates new graph with no edges and v vertices;

# Search object: gr2 = Depth_first_search(graph, vertex) - creates search object,
# gr2.marked_vertex(vertex) - returns true if given vertex is reachable from source(above)

# Path object: gr3 = Depth_first_paths(graph, vertex)- creates a new path object,
# gr3.has_path(vertex) - thee same as above
# gr3.path_to(vertex) - returns path from source vertex (to the given)

class Graph:
"""class graph"""
def __init__(self, v_in):
"""constructor -  takes number of vertices and creates a graph
with no edges (E = 0) and an empty adjacent lists of vertices"""
self.V = v_in
self.E = 0
self.adj = []
for i in range(v_in):
self.adj.append([])

def V(self):
"""returns number of vertices"""
return self.V

def E(self):
"""returns number of edges"""
return self.E

def add_edge(self, v, w):
"""void, adds an edge to the graph"""
self.adj[v].append(w)
self.adj[w].append(v)
self.E += 1

def adj_list(self, v):
"""returns the adjacency lists of the vertex v"""
return self.adj[v]

def __str__(self):
"""to string method, prints the graph"""
s = str(self.V) + " vertices, " + str(self.E) + " edges\n"
for v in range(self.V):
s += str(v) + ": "
for w in self.adj[v]:
s += str(w) + " "
s += "\n"
return s

class Depth_first_search:
"""class depth forst search, creates an object,
constructor takes graph and a vertex"""
def __init__(self, gr_obj, v_obj):
self.marked = [False] * gr_obj.V
self.cnt = 0
self.__dfs(gr_obj, v_obj)

def __dfs(self, gr, v):
"""void depth first search, proceed recursively,
mutates marked - marks the all possible to reach
from given (v) vertices; also mutates cnt - number of visited vert"""
self.marked[v] = True
self.cnt += 1
for w in gr.adj_list(v):
if self.marked[w] == False:
self.__dfs(gr, w)

def marked_vertex(self, w):
"""returns True if given vertex (w) is reachable
from vertex v"""
return self.marked[w]

def count(self):
"""returns number of visited verticles
(from given in the constructor vertex)"""
return self.cnt

class Depth_first_paths:
"""class depth first paths, solves
single paths problem: given graph and a vertex (source vertex), find
a path to another vertex."""

def __init__(self, gr_obj, v_obj):
self.marked = [False] * gr_obj.V
self.edge_to =  * gr_obj.V
self.s = v_obj
self.__dfs(gr_obj, v_obj)

def __dfs(self, gr, v):
"""void recursive depth first search, mutates array marked,
mutates counter (cnt), and creates a path (filling an array     edge_to)"""
self.marked[v] = True
for w in gr.adj_list(v):
if self.marked[w] == False:
self.edge_to[w] = v
self.__dfs(gr, w)

def has_path(self, v):
"""returns true if there is a path from the source
vertex to the given, else false"""
return self.marked[v]

def path_to(self, v):
"""returns path from source to the given vertex"""
if self.has_path(v) == False:
return None
path = []
x = v
while x != self.s:
path.insert(0, x)
x = self.edge_to[x]
path.insert(0, self.s)
return path


I've used classes not function because there is no need for global variables. How do you think build the rest graph algorithms on it?

## 2 Answers

I've reviewed your code and I can make the following remarks. I'm only going to review the Graph class for now so lets start:

class Graph:
"""class graph"""


Here the comment is redundant. We know its a Graph and we know its a class. Also note for completeness I like to write class Graph(object)

def __init__(self, v_in):
"""constructor -  takes number of vertices and creates a graph
with no edges (E = 0) and an empty adjacent lists of vertices"""
self.V = v_in
self.E = 0
self.adj = []
for i in range(v_in):
self.adj.append([])


Again the comment is redundant We know its a constructor and what it initializes. However as you may notice the real problem here is not the comment but what it describes. Those V, E, v_in parameters are too short and do not mean anything. If I were to read the method body and not the class name I wouldn't be able to understand that they denote Vertices and Edges. So a better name for them would be vertices, edges and input_vertices. Note that we use lowercase names for class properties.

def V(self):
"""returns number of vertices"""
return self.V

def E(self):
"""returns number of edges"""
return self.E


More redundant notes as we know they return something. However the method names are wrong. Why V and E? And why do they return a number? I would suspect to return a list or an Object that I can query. A better name would be again vertices and edges.

def add_edge(self, v, w):
"""void, adds an edge to the graph"""
self.adj[v].append(w)
self.adj[w].append(v)
self.E += 1

def adj_list(self, v):
"""returns the adjacency lists of the vertex v"""
return self.adj[v]


That's not too bad although I would remove the void remark and add a better explanation about the input assumptions. For example what happens if do add_edge(set((1,2,3)), frozenset((4,5,6)))? Traceback error. So its better to specify that it assumes the input is integers.

def __str__(self):
"""to string method, prints the graph"""
s = str(self.V) + " vertices, " + str(self.E) + " edges\n"
for v in range(self.V):
s += str(v) + ": "
for w in self.adj[v]:
s += str(w) + " "
s += "\n"
return s


Ok nothing wrong here. I would only rename s to output or response so that I understand the meaning.

In general I would say to try to keep the names consistent and meaningful so a reader will not have to guess whats going on.

You should embrace the builtin types Python provides for you. I will show you how you can replace every method in your class with functions based on those. First __init__ becomes:

def create_graph(vertices):
return {v:set() for v in vertices}


Used like this: G = create_graph([1, 2, 3]) Then def V(self): is just len(G). E becomes

def edge_count(G):
return sum(len(v) for v in G.values()) / 2


add_edge becomes

def add_edge(G, f, t):
G[f].add(t)
G[t].add(f)


adj_list is just G[v]. __str__ is also very easy to replace.

Your Depth_first_search makes a class out of what should be a function. It can be implemented like this:

def dfs(G, at, visited = None):
if visited is None:
visited = set()
yield at
visited.add(at)
for neighbour in G[at]:
if neighbour not in visited:
for at in dfs(G, neighbour, visited):
yield at


And used like this to print all nodes found in a graph:

for at in dfs(G, 1):
print(at)


The problem of finding a path between two graphs can then be expressed as:

def path_to(G, at, to, sofar = None, visited = None):
if sofar is None:
sofar = []
sofar.append(at)
if visited is None:
visited = set()
visited.add(at)
if at == to:
return sofar
for neighbour in G[at]:
if neighbour not in visited:
res = path_to(G, neighbour, to, sofar, visited)
if res:
return res
return None

print(path_to(G, 1, 10))