# HG changeset patch
# User Brian Neal <bgneal@gmail.com>
# Date 1354402299 21600
# Node ID 8e44660965efcc88ad5e6e6a3c2195a1ce689b6e
# Parent  9d0cf96b6a3bdca96616178608ca410b99f582e0
Completed chapter 2, exercise 3 on regular graphs.

diff -r 9d0cf96b6a3b -r 8e44660965ef Graph.py
--- a/Graph.py	Thu Nov 29 20:37:03 2012 -0600
+++ b/Graph.py	Sat Dec 01 16:51:39 2012 -0600
@@ -9,6 +9,11 @@
 import itertools
 
 
+class GraphError(Exception):
+    """Exception for Graph errors"""
+    pass
+
+
 class Vertex(object):
     """A Vertex is a node in a graph."""
 
@@ -117,20 +122,76 @@
 
         return self[v].values()
 
+    def remove_all_edges(self):
+        """Removes all edges in the graph."""
+        for v in self.iterkeys():
+            self[v] = {}
+
     def add_all_edges(self):
         """Makes the graph complete by adding edges between all pairs of
         vertices.
 
         """
         # Clear all edges first
-        for v in self.iterkeys():
-            self[v] = {}
+        self.remove_all_edges()
 
+        # For each combination of 2 vertices, create an edge between them:
         for v, w in itertools.combinations(self.iterkeys(), 2):
             e = Edge(v, w)
             self[v][w] = e
             self[w][v] = e
 
+    def add_regular_edges(self, k):
+        """Makes the graph regular by making every vertex have k edges.
+
+        It is not always possible to create a regular graph with a given degree.
+        If a graph has n vertices, then a regular graph can be constructed with
+        degree k if n >= k + 1 and n * k is even. If these conditions are not
+        met a GraphError exception is raised.
+
+        """
+        n = len(self.vertices())
+        if n < k + 1:
+            raise GraphError("Can't make a regular graph with degree >= number"
+                             " of vertices")
+        if (n * k) % 2 != 0:
+            raise GraphError("Can't make a regular graph of degree k and"
+                             " order n where k * n is odd")
+
+        # Remove all edges first
+        self.remove_all_edges()
+
+        if k % 2 != 0:      # if k is odd
+            self._add_regular_edges_even(k - 1)
+            self._add_regular_edges_odd()
+        else:
+            self._add_regular_edges_even(k)
+
+    def _add_regular_edges_even(self, k):
+        """Make a regular graph with degree k. k must be even."""
+
+        vs = self.vertices()
+        vs2 = vs * 2
+
+        for i, v in enumerate(vs):
+            for j in range(1, k / 2 + 1):
+                w = vs2[i + j]
+                self.add_edge(Edge(v, w))
+
+    def _add_regular_edges_odd(self):
+        """Adds an extra edge across the graph to finish off a regular graph
+        with odd degree. The number of vertices must be even.
+
+        """
+        vs = self.vertices()
+        vs2 = vs * 2
+        n = len(vs)
+
+        for i in range(n / 2):
+            v = vs2[i]
+            w = vs2[i + n / 2]
+            self.add_edge(Edge(v, w))
+
 
 def main(script, *args):
     import pprint
diff -r 9d0cf96b6a3b -r 8e44660965ef RegularGraphTest.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/RegularGraphTest.py	Sat Dec 01 16:51:39 2012 -0600
@@ -0,0 +1,35 @@
+"""Tests our regular graph making abilities by displaying examples.
+
+"""
+import string
+
+from Graph import Vertex, Graph, GraphError
+from GraphWorld import GraphWorld, CircleLayout
+
+def main(script_name, n, k):
+
+    # Attempt to create a regular graph of order n and degree k
+
+    n, k = int(n), int(k)
+
+    labels = string.ascii_lowercase + string.ascii_uppercase
+    vs = [Vertex(c) for c in labels[:n]]
+
+    # create graph and layout
+    g = Graph(vs)
+    g.add_regular_edges(k)
+    layout = CircleLayout(g)
+
+    # draw the graph
+
+    gw = GraphWorld()
+    gw.show_graph(g, layout)
+    gw.mainloop()
+
+
+if __name__ == '__main__':
+    import sys
+    try:
+        main(*sys.argv)
+    except GraphError, ex:
+        sys.stderr.write("GraphError: {}\n".format(ex))