k_regular.py

"""
This is my answer to Exercise 3 in Chapter 2 of ThinkComplexity. It 
works by cycling through the nodes in the graph, adding edges until 
it is k-regular.

See: http://greenteapress.com/complexity/html/thinkcomplexity003.html
"""

def add_regular_edges(self, degree):
    """
    Produces a k-regular graph from an edgeless graph.
    """
    vs = self.vertices()
    l = len(vs)

    if (degree + 1) > l or (degree * l % 2) != 0:
        print 'k-regular graph not possible.'
    
    # keep a count of the number of edges on each 
    # node
    edge_count = {v: 0 for v in vs}

    i, c = 0, 0

    while True:
        if c == l:
            # all nodes have the required degree
            break

        if edge_count[vs[i]] < degree:
            # this node doesn't have the required degree 
            # find a potential neighbour to connect to
            for j in range(i + 1, i + l - 1):
                # get index of potential neighbor
                ni = j % l

                if not self[vs[i]].get(vs[ni]) and edge_count[vs[ni]] < degree:
                    # we are not connected to this node, and it also doesn't 
                    # have the required degree--connect
                    self.add_edge((vs[i], vs[ni]))
                    
                    # update edge counts
                    edge_count[vs[i]] += 1
                    edge_count[vs[ni]] += 1

                    # start the next iteration at the node next to the 
                    # one we just connected to
                    i = j
                    break
            c = 0
        else:
            # this node has the required degree
            c += 1

        # on to next node
        i = (i + 1) % l