Generators and Inducers

This is really off-topic for my Summer of Code project, but I couldn't resist. I was flipping through some documentation for ​NetworkX and noticed how many generators they had for common graph types, and not wanting to be outdone, I decided to add a bunch to Boost.Graph.

So after about 10 hours of hacking (from 7 AM til about 5PM) I've created a sort of framework for creating and building graphs. To tell the truth, I don't actually create graphs, you just pass them into a generator or inducder and then your graph will contain the specified graph type as a subgraph. It's not necessary, but you can get the added vertices back from the functions also.

Now the big question should be, "What's a 'generator' and what's an 'inducer'?" Generators should be pretty straightforward. Give it a graph and it creates some vertices and edges for a subgraph. An inducer is basically the same thing except that you give an inducer a view into a set of vertices and the specified graph type is "induced" onto the vertex set. If you're wondering the word "induced" comes from the term "induced subset" - which is a view of a graph defined over a set of vertices that includes all the edges connecting them. So, an inducer takes a set of vertices and generates edges to connect them. A beautiful use of terminology.

It's actually a little better than that, because over the course of the day, I managed to write all of the generators in terms of inducers for a starter. Then I turned around and tried (mostly successfully) to write the graph generation algorithms in turns of induced building blocks. For example, a cycle is a path, so building a cycle graph over n verticces starts by inducing a path graph over n vertices and then connecting the tail to the head.

Supported Graph Types

I'm going to link all of these to ​Mathworld since they have pretty consistent documentation for the types of graphs.

• ​Path Graph on n vertices
• ​Cycle Graph on n vertices
• ​Star Graph on n vertices
• ​Wheel Graph on n vertices
• ​Prism Graph of n concentric cycles on m vertices each
• ​Web Graph on n - 1 concentric cycles of m vertices and m "hooks".
• ​Complete Graph on n vertices

I'm also kicking around some ideas for an Antiprism graph, Bipartite complete graphs, etc, but haven't implemented them.

Technicalities

Almost all of generators have the following signature:

make_xxx_graph(Graph& g, size_t n, ...);

Or generally something of that form where xxx is the name of the type of graph to create, g is pretty obviously some type of graph, and n generally determines the number of vertices being added to the graph, etc. There are some other parameters that I'l discuss later.

Inducers are a little more complicated. They're generally of the form:

induce_xxx_graph(Graph&, Iterator, size_t n, ...)

The iterator points into the vertex set upon which the graph is being induced. Many of the simple graphs can be generated over ForwardIterator models in linear time, but so far, I haven't been able to reduce type requirements of iterators for the PrismGraph and WebGraph. These require RandomAccessIterators. It's fun to try though.

The other parameters to these functions generally deal with how to generate edges for directed sets. Options for graphs with cycles include clockwise, counterclockwise, and bidirected. Options for graphs with spokes include inward, outward and bidirected spokes. The path edges can go forward backward or both. Interestingly, these have little to do with graph type, just how the edges are actually added.

Another parameter allows the user to provide an empty container to receive the created vertices.

A Mature Framework

This is really a prototpye framework for building graphs. I think there's a lot to be done. For example, we could build a visitor framework that would allow a user to interact with the process, to prevent the adding of edges or to add properties for vertices and edges when they are created. I think there's a lot of room for some good design work here.

Fun with Algorithms

The kind of fun part of building these algorithms is trying to reduce the iterator requirements of the inducers - essentially building complex graphs in linear time without random access or linear adapators to it. I'm not sure if it's entirely possible for all graphs, but it's fun to try. A lot of this refinement has to do with the pattern with which vertices are created, added to a vertex set, and finally, how the graph is induced over them. For right now, all of the vertex creation is fairly simple - build a bunch of vertices and stick them in a vector. This may not always be the case. For example, building a HypercubeGraph could require the creation of gray-coded integers and using a hash-map to associate them with vertices.

Building graphs could be a kind of generic programming challenge. Can you build a grid graph of m*n vertices using only a single loop and forward iterators? Probably, but it might take some time to figure it out.