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