[Boost-users] incremental_components, component_index for listS, listS adjacency_list

From: Sean Kelly (sean.kelly_at_[hidden])
Date: 2006-05-01 15:34:52

Hi All,

I couldn't figure out how to use the component_index facility of the
incremental components algorithm when operating on an listS, listS
adjecency_list so I rolled my own as per below.
Any suggestion on how to use the provided interface are appreciated.

thanks

Sean

    using namespace boost;

    typedef graph_traits<BlockDependencyGraph>::vertices_size_type
size_type;
    typedef BlockDependencyGraph::vertex_descriptor vertex_descriptor;
    typedef BlockDependencyGraph::vertex_iterator vertex_iterator;    

    BlockDependencyGraph& graph = _blk_dep_view->get_graph();

    // Disjoint sets requires Rank to map vertex_descriptors onto
integers
    typedef std::map<vertex_descriptor, int> rank_storage_t;
    rank_storage_t rank_map;
    typedef associative_property_map<rank_storage_t> rank_t;
    
    // Disjoint sets requires Parent to map vertex_descriptors onto
vertex_descriptors
    typedef std::map<vertex_descriptor, vertex_descriptor>
parent_storage_t;
    parent_storage_t parent_map;
    typedef associative_property_map<parent_storage_t> parent_t;
    
    disjoint_sets<rank_t, parent_t>
component_set(make_assoc_property_map(rank_map), 
 
make_assoc_property_map(parent_map));
    
    initialize_incremental_components(graph, component_set);
    incremental_components(graph, component_set);

    // Not at all clear how to extract components using component_index
interface
    // when graph is listS, listS adjacency_list... so we roll our own.
    //
    // Index vertices by representative component in a multimap
    typedef std::map<vertex_descriptor, std::vector<vertex_descriptor> >
components_t;
    components_t components;
    vertex_iterator curr(0), end(0);
    for(tie(curr, end) = vertices(graph);
        curr != end; 
        ++curr) 
    {
        components[component_set.find_set(*curr)].push_back(*curr);
    }

    // Print all components
    size_t n_c(0);
    for(components_t::const_iterator c = components.begin(); c !=
components.end(); ++c, ++n_c)
    {
        std::cout << "component " << n_c << std::endl;
        for(std::vector<vertex_descriptor>::const_iterator element =
c->second.begin();
            element != c->second.end();
            ++element) 
        {
            std::cout << graph[*element]->get_name() << std::endl;
        }
    }