graph = { "a" : {"c"},
"b" : {"c", "e"},
"c" : {"a", "b", "d", "e"},
"d" : {"c"},
"e" : {"c", "b"},
"f" : {}
}
# The keys of the dictionary above are the nodes of our graph. The corresponding values are sets with the nodes, which are connected by an edge.
# A set is better than a list or a tuple, because this way, we can have only one edge between two nodes. There is no simpler and more elegant way
# to represent a graph.
# An edge can also be ideally implemented as a set with two elements, i.e. the end nodes. This is ideal for undirected graphs.
# For directed graphs we would prefer lists or tuples to implement edges.
# Function to generate the list of all edges:
def generate_edges(graph):
edges = []
for node in graph:
for neighbour in graph[node]:
edges.append({node, neighbour})
return edges
print(generate_edges(graph))
# As we can see, there is no edge containing the node "f". "f" is an isolated node of our graph.
[{'c', 'a'}, {'b', 'c'}, {'b', 'e'}, {'c', 'b'}, {'c', 'e'}, {'c', 'd'}, {'c', 'a'}, {'c', 'd'}, {'c', 'e'}, {'b', 'e'}]
# The following Python function calculates the isolated nodes of a given graph:
def find_isolated_nodes(graph):
""" returns a set of isolated nodes. """
isolated = set()
for node in graph:
if not graph[node]:
isolated.add(node)
return isolated
print(find_isolated_nodes(graph))
{'f'}
k = {3:7, 6:9}
for i in k:
print(i)
print(k[i])
3 7 6 9
# A simple Python graph class, demonstrating the essential facts and functionalities of graphs.
class Graph(object):
def __init__(self, graph_dict=None):
# initializes a graph object. If no dictionary or None is given, an empty dictionary will be used.
if graph_dict == None:
graph_dict = {}
self._graph_dict = graph_dict
# returns a list of all the edges of a vertice.
def edges(self, vertice):
return self._graph_dict[vertice]
# returns the vertices of a graph as a set.
def all_vertices(self):
return set(self._graph_dict.keys())
# returns the edges of a graph.
def all_edges(self):
return self.__generate_edges()
# 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.
def add_vertex(self, vertex):
if vertex not in self._graph_dict:
self._graph_dict[vertex] = []
# assumes that edge is of type set, tuple or list; between two vertices can be multiple edges!
def add_edge(self, edge):
edge = set(edge)
vertex1, vertex2 = tuple(edge)
for x, y in [(vertex1, vertex2), (vertex2, vertex1)]:
if x in self._graph_dict:
self._graph_dict[x].add(y) #as soon as the value is a list, this fails, i.e. when the vertex has just been added in line 31.
print(type(self._graph_dict[x]))
else:
self._graph_dict[x] = [y] # once a new pair is added with x as key, line 40 fails, too.
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 __iter__(self):
self._iter_obj = iter(self._graph_dict)
return self._iter_obj
def __next__(self):
# allows us to iterate over the vertices.
return next(self._iter_obj)
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
g = {"a": {"d"},
"b": {"c"},
"c": {"b", "c", "d", "e"},
"d": {"a", "c"},
"e": {"c"},
"f": {}
}
graph = Graph(g)
for vertice in graph:
print(f"Edges of vertice {vertice}: ", graph.edges(vertice))
graph.add_edge({"ab", "fg"})
graph.add_edge({"xyz", "bla"})
# graph.add_edge({"a", "z"}) # here the error in line 40 above gets revealed.
print("")
print("Vertices of graph:")
print(graph.all_vertices())
print("Edges of graph:")
print(graph.all_edges())
print("Add vertex:")
graph.add_vertex("z")
print("Add an edge:")
graph.add_edge({"a", "d"})
print("Vertices of graph:")
print(graph.all_vertices())
print("Edges of graph:")
print(graph.all_edges())
print('Adding an edge {"x","y"} with new vertices:')
graph.add_edge({"x","y"})
print("Vertices of graph:")
print(graph.all_vertices())
print("Edges of graph:")
print(graph.all_edges())
j = {"ab", "fg"}
vertex1, vertex2 = tuple(j)
for x, y in [(vertex1, vertex2), (vertex2, vertex1)]:
print(x,y)
l = {"a", "z"}
vertex1, vertex2 = tuple(l)
for x, y in [(vertex1, vertex2), (vertex2, vertex1)]:
print(x,y)
# We check in the following the way of working of our find_path and find_all_paths methods.
class Graph(object):
def __init__(self, graph_dict=None):
# initializes a graph object. If no dictionary or None is given, an empty dictionary will be used.
if graph_dict == None:
graph_dict = {}
self._graph_dict = graph_dict
def find_path(self, start_vertex, end_vertex, path=None):
# find a path from start_vertex to end_vertex in graph.
if path == None:
path = []
graph = self._graph_dict
path = path + [start_vertex]
if start_vertex == end_vertex:
return path
if start_vertex not in graph:
return None
for vertex in graph[start_vertex]:
if vertex not in path:
extended_path = self.find_path(vertex,
end_vertex,
path)
if extended_path:
return extended_path
return None
g = { "a" : {"d"},
"b" : {"c"},
"c" : {"b", "c", "d", "e"},
"d" : {"a", "c"},
"e" : {"c"},
"f" : {}
}
graph = Graph(g)
print('The path from vertex "a" to vertex "b":')
path = graph.find_path("a", "b")
print(path)
print('The path from vertex "a" to vertex "f":')
path = graph.find_path("a", "f")
print(path)
print('The path from vertex "c" to vertex "c":')
path = graph.find_path("c", "c")
print(path)
The path from vertex "a" to vertex "b": ['a', 'd', 'c', 'b'] The path from vertex "a" to vertex "f": None The path from vertex "c" to vertex "c": ['c']
class Graph(object):
def __init__(self, graph_dict=None):
# initializes a graph object. If no dictionary or None is given, an empty dictionary will be used.
if graph_dict == None:
graph_dict = {}
self._graph_dict = graph_dict
def find_all_paths(self, start_vertex, end_vertex, path=[]):
# find all paths from start_vertex to end_vertex in graph.
graph = self._graph_dict
path = path + [start_vertex]
if start_vertex == end_vertex:
return [path]
if start_vertex not in graph:
return []
paths = []
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.append(p)
return paths
g = { "a" : {"d", "f"},
"b" : {"c"},
"c" : {"b", "c", "d", "e"},
"d" : {"a", "c", "f"},
"e" : {"c"},
"f" : {"a", "d"}
}
graph = Graph(g)
print('All paths from vertex "a" to vertex "b":')
path = graph.find_all_paths("a", "b")
print(path)
print('All paths from vertex "a" to vertex "f":')
path = graph.find_all_paths("a", "f")
print(path)
print('All paths from vertex "c" to vertex "c":')
path = graph.find_all_paths("c", "c")
print(path)
All paths from vertex "a" to vertex "b": [['a', 'd', 'c', 'b'], ['a', 'f', 'd', 'c', 'b']] All paths from vertex "a" to vertex "f": [['a', 'd', 'f'], ['a', 'f']] All paths from vertex "c" to vertex "c": [['c']]
# We will design a new class Graph2 now, which inherits from our previously defined graph Graph and we add the following methods to it:
# vertex_degree, find_isolated_vertices, delta, degree_sequence.
class Graph2(Graph):
def vertex_degree(self, vertex):
# The degree of a vertex is the number of edges connecting it, i.e. the number of adjacent vertices. Loops are counted double, i.e. every
# occurence of vertex in the list of adjacent vertices.
degree = len(self._graph_dict[vertex])
if vertex in self._graph_dict[vertex]:
degree += 1
return degree
def find_isolated_vertices(self):
""" returns a list of isolated vertices. """
graph = self._graph_dict
isolated = []
for vertex in graph:
print(isolated, vertex)
if not graph[vertex]:
isolated += [vertex]
return isolated
def Delta(self):
""" the maximum degree of the vertices """
max = 0
for vertex in self._graph_dict:
vertex_degree = self.vertex_degree(vertex)
if vertex_degree > max:
max = vertex_degree
return max
def degree_sequence(self):
""" calculates the degree sequence """
seq = []
for vertex in self._graph_dict:
seq.append(self.vertex_degree(vertex))
seq.sort(reverse=True)
return tuple(seq)
g = { "a" : {"d", "f"},
"b" : {"c"},
"c" : {"b", "c", "d", "e"},
"d" : {"a", "c"},
"e" : {"c"},
"f" : {"d"}
}
graph = Graph2(g)
graph.degree_sequence()
(5, 2, 2, 1, 1, 1)
g = { "a" : {"d", "f"},
"b" : {"c"},
"c" : {"b", "c", "d", "e"},
"d" : {"a", "c", "f"},
"e" : {"c"},
"f" : {"a", "d"}
}
graph = Graph2(g)
graph.degree_sequence()
(5, 3, 2, 2, 1, 1)