Skip to content
  • Tiago Peixoto's avatar
    Refactor metaprogramming engine · 0b66e272
    Tiago Peixoto authored
    This is a huge commit which completely refactors the metaprogramming
    engine which generates and selects (at run time) the graph view type and
    the desired algorithm implementation (template instantiation) that runs
    on it.
    
    Things are laid out now as following. There exists a main underlying
    graph type (GraphInterface::multigraph_t) and several other template
    classes that mask it some way or another, in a hierarchic fashion:
    
         multigraph_t -> filtered_graph (edges only, vertices only, both)
             |                               |           |           |
             |                               |           |           |
             |-------(reversed_graph)--------|-----------|-----------|
             |                               |           |           |
             \------(UndirectedAdaptor)------------------------------/
    
    The filtered_graph filters out edges and/or vertices from the graph
    based on some scalar boolean property. The reversed_graph reversed the
    direction of the edges and, finally, the UndirectedAdaptor treats the
    original directed graphs as undirected, transversing the in- and
    out-edges of each vertex indifferently. Thus, the total number of graph
    view types is 12. (The option --disable-graph-filtering can be passed to
    the configure script, which will disable graph filtering altogether and
    bring the total number down to 3, to reduce compile time and memory
    usage)
    
    In general, some specific algorithm, implemented as a template function
    object, needs to be instantiated for each of those types. Furthermore,
    the algorithm may also depend on other types, such as specific
    property_maps. Thus, the following scheme is used:
    
        struct my_algorithm // algorithm to be implemented
        {
            template <class Graph, class PropertyMap>
            void operator()(Graph *g, PropertyMap p, double& result) const
            {
                // ...
            }
        };
    
        // in order for the above code to be instantiated at compile time
        // and selected at run time, the run_action template function object
        // is used from a member function of the GraphInterface class:
    
        double GraphInterface::MyAlgorithm(string prop_name)
        {
            double result;
            boost::any vprop = prop(property, _vertex_index, _properties);
            run_action<>()(*this, bind<void>(my_algorithm(), _1, _2,
                                             var(result)),
                           vertex_scalar_properties())(vprop);
            return result;
        }
    
    The whole code was changed to reflect this scheme, but now things are
    more centralized and less ad-hoc code needed to be
    written. Unfortunately, due to GCC's high memory usage during template
    instantiations, some of the code (namely all the degree correlation
    things) had to be split in multiple compilation units... Maybe this will
    change in the future if GCC gets optimized.
    
    This commit also touches other parts of code. More specifically, the way
    filtering gets done is very different. Now we only filter on boolean
    properties, and with the above scheme, the desired implementation runs
    with the correct chosen type, and no implicit type conversions should
    ever happen, which would have a bad impact on performance.
    0b66e272