Changes between Initial Version and Version 1 of soc/2007/UserFriendlyGraphs/Generators


Ignore:
Timestamp:
Jul 10, 2007, 1:31:35 AM (15 years ago)
Author:
Andrew Sutton
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • soc/2007/UserFriendlyGraphs/Generators

    v1 v1  
     1= Generators and Inducers =
     2This is really off-topic for my Summer of Code project, but I couldn't resist. I was flipping through some documentation for [https://networkx.lanl.gov/wiki 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.
     3
     4So 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.
     5
     6Now 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.
     7
     8It'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.
     9
     10== Supported Graph Types ==
     11I'm going to link all of these to [http://mathworld.wolfram.com/ Mathworld] since they have pretty consistent documentation for the types of graphs.
     12
     13 * [http://mathworld.wolfram.com/PathGraph.html Path Graph] on ''n'' vertices
     14 * [http://mathworld.wolfram.com/CycleGraph.html Cycle Graph] on ''n'' vertices
     15 * [http://mathworld.wolfram.com/StarGraph.html Star Graph] on ''n'' vertices
     16 * [http://mathworld.wolfram.com/WheelGraph.html Wheel Graph] on ''n'' vertices
     17 * [http://mathworld.wolfram.com/PrismGraph.html Prism Graph] of ''n'' concentric cycles on ''m'' vertices each
     18 * [http://mathworld.wolfram.com/WebGraph.html Web Graph] on ''n - 1'' concentric cycles of ''m'' vertices and ''m'' "hooks".
     19 * [http://mathworld.wolfram.com/WebGraph.html Complete Graph] on ''n'' vertices
     20
     21I'm also kicking around some ideas for an Antiprism graph, Bipartite complete graphs, etc, but haven't implemented them.
     22
     23== Technicalities ==
     24Almost all of generators have the following signature:
     25
     26{{{
     27#!cpp
     28make_xxx_graph(Graph& g, size_t n, ...);
     29}}}
     30
     31Or 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.
     32
     33Inducers are a little more complicated. They're generally of the form:
     34
     35{{{
     36#!cpp
     37induce_xxx_graph(Graph&, Iterator, size_t n, ...)
     38}}}
     39
     40The 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.
     41
     42The 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.
     43
     44Another parameter allows the user to provide an empty container to receive the created vertices.
     45
     46== A Mature Framework ==
     47This 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.
     48
     49== Fun with Algorithms ==
     50The 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.
     51
     52Building 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.