[boost] [metagraph] mpl_graph and MSM

Subject: [boost] [metagraph] mpl_graph and MSM
From: Gordon Woodhull (gordon_at_[hidden])
Date: 2010-05-14 05:50:06

Friends,

I'm pleased to announce that I'll soon be submitting mpl_graph for  
review.

This is an implementation of the BGL concepts for compile time  
metaprogramming.  Currently it supports incidence list, adjacency  
list, depth first search, and breadth first search.  It is available  
in the sandbox under metagraph.  I'll write some documentation soon;  
for now consult BGL's concepts, which are almost the same, just s/()/ 
typename <>::type/   ;-)

It's pretty small - 825 lines of code so far.  Standing on the  
shoulders of MPL...

I've also provided a minimal example of running depth first search on  
the canonical MSM CD Player example.  See sandbox/metagraph/libs/ 
metagraph/example/msm_adaptor.cpp

Christophe, thanks for prodding me to get this out the door in your  
talk here at BoostCon!  It sounds like we should write a connected  
components algorithm to get the features you are looking for, which  
will be easy with the right dfs visitor.

Running DFS does cost in compile time.  I haven't yet attempted to  
profile or optimize the template instantiations, and would appreciate  
any advice.

On this example, it increases the compile time from 3.775 to 5.634  
seconds on gcc 4.4.  Since the metadata graph structure is lazy (you  
pay approximately for each graph concept that you exercise),  
construction of the graph is only 0.2s out of the 1.85s.   
Interestingly, running BFS in addition to DFS on the same graph adds  
less than 0.2s -- this makes sense because the big expense should be  
generating the mpl::maps which support vertex and edge lookup.

Here is the test I ran.  (I took the median time from each DFS level.)
for((dfs=0;dfs<6;++dfs)); do
        echo; echo DFS=$dfs, 5 runs;
        for((i=0;i<5;++i)); do
                time g++ -D DO_DFS=$dfs -I ../../.. -I ~/src/MSMv2.10 -I ~/src/boost- 
trunk msm_adaptor.cpp -o msm_adaptor;
done ; done

The good news is that it takes less than 25 lines of code to turn the  
transition table into a graph and run DFS on it.

Thanks to everyone for a truly awesome BoostCon!

Gordon

P.S. mpl_graph is part of a larger effort to generate patterns of  
objects from graph metadata.  (Metagraph to me means "graph of  
graphs".)  Would people rather I submitted mpl_graph separately, or  
keep it as a sublibrary of metagraph?  (The full metagraph is still  
months or years away.)

P.P.S. Gurtovoy/Abrahams, is the name OK?  It's meant to emphasize  
that it's a simple extension of MPL into graphs.