Boost logo

Boost :

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.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk