graphclass.py

class Graph(object):

	def __init__(self, graph_dict={}):
		""" initializes a graph object """
		self.__graph_dict = graph_dict

	def vertices(self):
		""" returns the vertices of a graph """
		return list(self.__graph_dict.keys())

	def edges(self):
		""" returns the edges of a graph """
		return self.__generate_edges()

	def add_vertex(self, vertex):
		""" If the vertex "vertex" is not in 
			self.__graph_dict, a key "vertex" with an empty
			list as a value is added to the dictionary. 
			Otherwise nothing has to be done. 
		"""
		if vertex not in self.__graph_dict:
			self.__graph_dict[vertex] = []

	def add_edge(self, edge):
		""" assumes that edge is of type set, tuple or list; 
			between two vertices can be multiple edges! 
		"""
		edge = set(edge)
		(vertex1, vertex2) = tuple(edge)
		if vertex1 in self.__graph_dict:
			self.__graph_dict[vertex1].append(vertex2)
		else:
			self.__graph_dict[vertex1] = [vertex2]

	def __generate_edges(self):
		""" A static method generating the edges of the 
			graph "graph". Edges are represented as sets 
			with one (a loop back to the vertex) or two 
			vertices 
		"""
		edges = []
		for vertex in self.__graph_dict:
			for neighbour in self.__graph_dict[vertex]:
				if {neighbour, vertex} not in edges:
					edges.append({vertex, neighbour})
		return edges

	def __str__(self):
		res = "vertices: "
		for k in self.__graph_dict:
			res += str(k) + " "
		res += "\nedges: "
		for edge in self.__generate_edges():
			res += str(edge) + " "
		return res
	
	def find_all_paths(self,start_vertex,end_vertex,path=[]):
		graph = self.__graph_dict
		path += start_vertex
		if start_vertex == end_vertex:
			return [path]
		if start_vertex not in graph:
			return None
		paths_list = []
		for vertex in graph[start_vertex]:
			if vertex not in path:
				extended_paths = self.find_all_paths(vertex,end_vertex,path)
				for p in extended_paths:
					paths_list.append(p)
		return paths_list

if __name__ == "__main__":

	g = { "a" : ["d"],
		  "b" : ["c"],
		  "c" : ["b", "c", "d", "e"],
		  "d" : ["a", "c"],
		  "e" : [],
		  "f" : []
		}


	graph = Graph(g)
	print (graph.find_all_paths("a","e"))