# Method that adds edges to a graph until all nodes have the given degree

Exercise 2-3 in Think Complexity: Complexity Science and Computational Modeling by Allen B. Downey asks us to implement a method for a class of undirected graphs:

Write a method named add_regular_edges that starts with an edgeless graph and adds edges so that every vertex has the same degree. The degree of a node is the number of edges it is connected to.

To create a regular graph with degree 2, you would do something like this:

vertices = [ ... list of vertices ...]
g = Graph(vertices, [])


It is not always possible to create a regular graph with a given degree, so you should figure out and document the preconditions for this method.

This was a little difficult for me as I am still getting comfortable with Python. Here was what my solution ended up looking like (heavily commented for myself and others):

def add_regular_edges(self, deg):

#for every node in the graph
for v in self:

#set the degree tolerance to 1
tol = 1

#while the degree of current node is less than the given degree
while self.degree(v) < deg:

#traverse over every node
for w in self:

'''if the 2 nodes do not equal one another, the current degree (v) is less than the given degree,
and the other node (w) is less than the current tolerance -> add the edge'''
if v != w and (self.degree(v) < deg) and (self.degree(w) < tol):

#increase the tolerance in case we could not fill all nodes in the first pass
tol += 1

#if at any point the tolerance is more than the degree, then we cannot complete the graph with the given degree
if tol > (deg+1):
raise ValueError("The graph cannot be converted to the given degree")


However, I have a strong suspicion that this is not the most optimal way to go about this. One of my friends commented that I might be able to do this using lists and enumerating over them?

• Where are the rest of functions coming from? Have you overridden the __iter__ method? – hjpotter92 Feb 4 '18 at 22:09
• @hjpotter92 Yes I have overridden __iter__, it's only so I can initalize the graph with a list of Vertices and Edges if I need to though. The class just inherits from dict, so it's a dictionary of dictionaries (cause each vertex v is a dictionary as well). The other functions (degree() and add_edge()) were defined by me and just do exactly what they sound like. – avghdev Feb 4 '18 at 22:19
• Is Edge(v, w) different from Edge(w, v)? – hjpotter92 Feb 5 '18 at 8:16
• @hjpotter92 Nope they are the same - that’s not to say that v and w are the same though. – avghdev Feb 5 '18 at 9:34