trjhtr

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, )
g.add_regular_edges(2)

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):
 self.add_edge(Edge(v,w))

 #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?