2
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ Where are the rest of functions coming from? Have you overridden the __iter__ method? \$\endgroup\$ – hjpotter92 Feb 4 '18 at 22:09
  • \$\begingroup\$ @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. \$\endgroup\$ – avghdev Feb 4 '18 at 22:19
  • \$\begingroup\$ Is Edge(v, w) different from Edge(w, v)? \$\endgroup\$ – hjpotter92 Feb 5 '18 at 8:16
  • \$\begingroup\$ @hjpotter92 Nope they are the same - that’s not to say that v and w are the same though. \$\endgroup\$ – avghdev Feb 5 '18 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.