Gear graph

[Dave Symonds <ds@seul.org>]

Below is a patch that implements a gear graph prefab. Feedback?

--
"Computer science is no more about computers
  than astronomy is about telescopes."
	- E.W. Dijkstra

----------------------< snip >----------------------
Index: factory.cc
===================================================================
RCS file: /usr/local/cvsroot/GraphThing/src/factory.cc,v
retrieving revision 1.20
retrieving revision 1.21
diff -u -d -r1.20 -r1.21
--- factory.cc	20 Dec 2002 13:35:45 -0000	1.20
+++ factory.cc	22 Feb 2003 04:04:12 -0000	1.21
@@ -3,6 +3,7 @@
 */
 
 #include <math.h>
+#include <queue>
 #include "edge.h"
 #include "factory.h"
 #include "graph.h"
@@ -58,6 +59,47 @@
 	if (n > 2) {
 		e = new Edge (prev, first);
 		g->add (e);
+	}
+
+	return g;
+}
+
+Graph *Factory::G (int n)
+{
+	Graph *g;
+
+	g = Factory::W (n + 1);
+
+	// Not quite correct, but we'll ignore "trivial" cases
+	if (n < 3)
+		return g;
+
+	Graph::e_const_iterator eit;
+	std::queue<Edge *> eq;
+	Vertex *middle;
+
+	middle = g->find (width / 2, height / 2);
+	if (!middle) {
+		std::cerr << "ARGH!\n";
+		return g;
+	}
+	for (eit = g->e_begin (); eit != g->e_end (); ++eit) {
+		Edge *e = *eit;
+		if (e->incident_to (middle))
+			continue;
+		eq.push (e);
+	}
+	while (!eq.empty ()) {
+		Edge *e = eq.front ();
+		eq.pop ();
+
+		Vertex *a = e->v, *b = e->w;
+		g->remove (e);
+		Vertex *mid = new Vertex ("", (a->x + b->x) / 2,
+							(a->y + b->y) / 2);
+		g->add (mid);
+		g->add (new Edge (a, mid));
+		g->add (new Edge (mid, b));
 	}
 
 	return g;
Index: factory.h
===================================================================
RCS file: /usr/local/cvsroot/GraphThing/src/factory.h,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -d -r1.16 -r1.17
--- factory.h	20 Dec 2002 13:35:45 -0000	1.16
+++ factory.h	22 Feb 2003 04:04:13 -0000	1.17
@@ -18,6 +18,7 @@
 	static int height;
 
 	static Graph *C (int n);		/* cycle */
+	static Graph *G (int n);		/* gear */
 	static Graph *K (int n);		/* complete */
 	static Graph *K (int n, int m);		/* complete bipartite */
 	static Graph *L (int n);		/* ladder */
Index: gui.cc
===================================================================
RCS file: /usr/local/cvsroot/GraphThing/src/gui.cc,v
retrieving revision 1.70
retrieving revision 1.71
diff -u -d -r1.70 -r1.71
--- gui.cc	19 Feb 2003 11:59:55 -0000	1.70
+++ gui.cc	22 Feb 2003 04:04:13 -0000	1.71
@@ -138,6 +138,8 @@
 		SigC::slot (this, &GUI::cb_Prefab_CompleteBipartite)));
 	lp.push_back (MenuElem (_("Cycle (_Cn)"),
 			SigC::slot (this, &GUI::cb_Prefab_Cycle)));
+	lp.push_back (MenuElem (_("Gear (_Gn)"),
+			SigC::slot (this, &GUI::cb_Prefab_Gear)));
 	lp.push_back (MenuElem (_("Hanoi (_Hn)")));
 	lp.back ()->set_sensitive (false);
 	lp.push_back (MenuElem (_("Ladder (_Ln)"),
Index: gui.h
===================================================================
RCS file: /usr/local/cvsroot/GraphThing/src/gui.h,v
retrieving revision 1.60
retrieving revision 1.61
diff -u -d -r1.60 -r1.61
--- gui.h	16 Feb 2003 00:58:00 -0000	1.60
+++ gui.h	22 Feb 2003 04:04:13 -0000	1.61
@@ -66,6 +66,7 @@
 	void cb_Prefab_Complete ();
 	void cb_Prefab_CompleteBipartite ();
 	void cb_Prefab_Cycle ();
+	void cb_Prefab_Gear ();
 	void cb_Prefab_Ladder ();
 	void cb_Prefab_Lattice ();
 	void cb_Prefab_Null ();
Index: phrases.lang
===================================================================
RCS file: /usr/local/cvsroot/GraphThing/src/phrases.lang,v
retrieving revision 1.16
retrieving revision 1.17
diff -u -d -r1.16 -r1.17
--- phrases.lang	17 Feb 2003 12:46:05 -0000	1.16
+++ phrases.lang	22 Feb 2003 04:04:13 -0000	1.17
@@ -254,6 +254,9 @@
 	Catalan = "Cicle (_Cn)"
 	SwedishChef = "Cycle-a (_Cn)"
 };
+"Gear (_Gn)" = {
+	SwedishChef = "Geer (_Gn)"
+};
 "Hanoi (_Hn)" = {
 	German = "Hanoi (_Hn)"
 	Spanish = "Hanoi (_Hn)"
@@ -530,6 +533,7 @@
 "Complete _Bipartite:" = "Complete _Bipartite (Kn,m)" subst " (Kn,m)" / ":";
 "Complete Bipartite:" = "Complete _Bipartite:" subst "_" / "";
 "Cycle:" = "Cycle (_Cn)" subst " (_Cn)" / ":";
+"Gear:" = "Gear (_Gn)" subst " (_Gn)" / ":";
 "Ladder:" = "Ladder (_Ln)" subst " (_Ln)" / ":";
 "Lattice:" = "Lattice (Ln,m)" subst " (Ln,m)" / ":";
 "Null:" = "Null (_Nn)" subst " (_Nn)" / ":";