Chris@16: // Copyright (C) 2004-2008 The Trustees of Indiana University.
Chris@16: 
Chris@16: // Use, modification and distribution is subject to the Boost Software
Chris@16: // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16: // http://www.boost.org/LICENSE_1_0.txt)
Chris@16: 
Chris@16: //  Authors: Nick Edmonds
Chris@16: //           Douglas Gregor
Chris@16: //           Andrew Lumsdaine
Chris@16: #ifndef BOOST_GRAPH_DISTRIBUTED_SCC_HPP
Chris@16: #define BOOST_GRAPH_DISTRIBUTED_SCC_HPP
Chris@16: 
Chris@16: #ifndef BOOST_GRAPH_USE_MPI
Chris@16: #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
Chris@16: #endif
Chris@16: 
Chris@16: // #define PBGL_SCC_DEBUG
Chris@16: 
Chris@16: #include <boost/assert.hpp>
Chris@16: #include <boost/property_map/property_map.hpp>
Chris@16: #include <boost/property_map/parallel/distributed_property_map.hpp>
Chris@16: #include <boost/property_map/parallel/caching_property_map.hpp>
Chris@16: #include <boost/graph/parallel/algorithm.hpp>
Chris@16: #include <boost/graph/parallel/process_group.hpp>
Chris@16: #include <boost/graph/distributed/queue.hpp>
Chris@16: #include <boost/graph/distributed/filtered_graph.hpp>
Chris@16: #include <boost/pending/indirect_cmp.hpp>
Chris@16: #include <boost/graph/breadth_first_search.hpp>
Chris@16: #include <boost/graph/graph_traits.hpp>
Chris@16: #include <boost/graph/overloading.hpp>
Chris@16: #include <boost/graph/distributed/concepts.hpp>
Chris@16: #include <boost/graph/distributed/local_subgraph.hpp>
Chris@16: #include <boost/graph/parallel/properties.hpp>
Chris@16: #include <boost/graph/named_function_params.hpp>
Chris@16: #include <boost/graph/random.hpp>
Chris@16: #include <boost/graph/distributed/reverse_graph.hpp>
Chris@16: #include <boost/optional.hpp>
Chris@16: #include <boost/graph/distributed/detail/filtered_queue.hpp>
Chris@16: #include <boost/graph/distributed/adjacency_list.hpp>
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   #include <iostream>
Chris@16:   #include <cstdlib>
Chris@16:   #include <iomanip>
Chris@16:   #include <sys/time.h>
Chris@16:   #include <boost/graph/distributed/graphviz.hpp> // for ostringstream
Chris@16: #endif
Chris@16: #include <vector>
Chris@16: #include <map>
Chris@16: #include <boost/graph/parallel/container_traits.hpp>
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16: #  include <boost/graph/accounting.hpp>
Chris@16: #endif /* PBGL_SCC_DEBUG */
Chris@16: 
Chris@16: // If your graph is likely to have large numbers of small strongly connected
Chris@16: // components then running the sequential SCC algorithm on the local subgraph
Chris@16: // and filtering components with no remote edges may increase performance
Chris@16: // #define FILTER_LOCAL_COMPONENTS
Chris@16: 
Chris@16: namespace boost { namespace graph { namespace distributed { namespace detail {
Chris@16: 
Chris@16: template<typename vertex_descriptor>
Chris@16: struct v_sets{
Chris@16:   std::vector<vertex_descriptor> pred, succ, intersect, ps_union;
Chris@16: };
Chris@16: 
Chris@16: /* Serialize vertex set */
Chris@16: template<typename Graph>
Chris@16: void
Chris@16: marshal_set( std::vector<std::vector<typename graph_traits<Graph>::vertex_descriptor> > in,
Chris@16:              std::vector<typename graph_traits<Graph>::vertex_descriptor>& out )
Chris@16: {
Chris@16:   for( std::size_t i = 0; i < in.size(); ++i ) {
Chris@16:     out.insert( out.end(), graph_traits<Graph>::null_vertex() );
Chris@16:     out.insert( out.end(), in[i].begin(), in[i].end() );
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: /* Un-serialize vertex set */
Chris@16: template<typename Graph>
Chris@16: void
Chris@16: unmarshal_set( std::vector<typename graph_traits<Graph>::vertex_descriptor> in,
Chris@16:                std::vector<std::vector<typename graph_traits<Graph>::vertex_descriptor> >& out )
Chris@16: {
Chris@16:   typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16: 
Chris@16:   while( !in.empty() ) {
Chris@16:     typename std::vector<vertex_descriptor>::iterator end 
Chris@16:       = std::find( in.begin(), in.end(), graph_traits<Graph>::null_vertex() );
Chris@16: 
Chris@16:     if( end == in.begin() )
Chris@16:       in.erase( in.begin() );
Chris@16:     else {
Chris@16:       out.push_back(std::vector<vertex_descriptor>());
Chris@16:       out[out.size() - 1].insert( out[out.size() - 1].end(), in.begin(), end );
Chris@16:       in.erase( in.begin(), end );
Chris@16:     }
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: /* Determine if vertex is in subset */
Chris@16: template <typename Set>
Chris@16: struct in_subset {
Chris@16:   in_subset() : m_s(0) { }
Chris@16:   in_subset(const Set& s) : m_s(&s) { }
Chris@16: 
Chris@16:   template <typename Elt>
Chris@16:   bool operator()(const Elt& x) const {
Chris@16:     return ((*m_s).find(x) != (*m_s).end());
Chris@16:   }
Chris@16: 
Chris@16: private:
Chris@16:   const Set* m_s;
Chris@16: };
Chris@16: 
Chris@16: template<typename T>
Chris@16: struct vertex_identity_property_map
Chris@16:   : public boost::put_get_helper<T, vertex_identity_property_map<T> >
Chris@16: {
Chris@16:   typedef T key_type;
Chris@16:   typedef T value_type;
Chris@16:   typedef T reference;
Chris@16:   typedef boost::readable_property_map_tag category;
Chris@16: 
Chris@16:   inline value_type operator[](const key_type& v) const { return v; }
Chris@16:   inline void clear() { }
Chris@16: };
Chris@16: 
Chris@16: template <typename T>
Chris@16: inline void synchronize( vertex_identity_property_map<T> & ) { }
Chris@16: 
Chris@16: /* BFS visitor for SCC */
Chris@16: template<typename Graph, typename SourceMap>
Chris@16: struct scc_discovery_visitor : bfs_visitor<>
Chris@16: {
Chris@16:   scc_discovery_visitor(SourceMap& sourceM)
Chris@16:     : sourceM(sourceM) {}
Chris@16: 
Chris@16:   template<typename Edge>
Chris@16:   void tree_edge(Edge e, const Graph& g)
Chris@16:   {
Chris@16:     put(sourceM, target(e,g), get(sourceM, source(e,g)));
Chris@16:   }
Chris@16: 
Chris@16:  private:
Chris@16:   SourceMap& sourceM;
Chris@16: };
Chris@16: 
Chris@16: } } } } /* End namespace boost::graph::distributed::detail */
Chris@16: 
Chris@16: namespace boost { namespace graph { namespace distributed {
Chris@16:     enum fhp_message_tags { fhp_edges_size_msg, fhp_add_edges_msg, fhp_pred_size_msg, 
Chris@16:                             fhp_pred_msg, fhp_succ_size_msg, fhp_succ_msg };
Chris@16: 
Chris@16:     template<typename Graph, typename ReverseGraph,
Chris@16:              typename VertexComponentMap, typename IsoMapFR, typename IsoMapRF,
Chris@16:              typename VertexIndexMap>
Chris@16:     void
Chris@16:     fleischer_hendrickson_pinar_strong_components(const Graph& g,
Chris@16:                                                   VertexComponentMap c,
Chris@16:                                                   const ReverseGraph& gr,
Chris@16:                                                   IsoMapFR fr, IsoMapRF rf,
Chris@16:                                                   VertexIndexMap vertex_index_map)
Chris@16:     {
Chris@16:       typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
Chris@16:       typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16:       typedef typename graph_traits<ReverseGraph>::vertex_iterator rev_vertex_iterator;
Chris@16:       typedef typename graph_traits<ReverseGraph>::vertex_descriptor rev_vertex_descriptor;
Chris@16:       typedef typename boost::graph::parallel::process_group_type<Graph>::type
Chris@16:         process_group_type;
Chris@16:       typedef typename process_group_type::process_id_type process_id_type;
Chris@16:       typedef iterator_property_map<typename std::vector<vertex_descriptor>::iterator,
Chris@16:                                     VertexIndexMap> ParentMap;
Chris@16:       typedef iterator_property_map<typename std::vector<default_color_type>::iterator,
Chris@16:                                     VertexIndexMap> ColorMap;
Chris@16:       typedef iterator_property_map<typename std::vector<vertex_descriptor>::iterator,
Chris@16:                                     VertexIndexMap> Rev_ParentMap;
Chris@16:       typedef std::vector<std::pair<vertex_descriptor, vertex_descriptor> > VertexPairVec;
Chris@16: 
Chris@16:       typedef typename property_map<Graph, vertex_owner_t>::const_type
Chris@16:         OwnerMap;
Chris@16: 
Chris@16:       OwnerMap owner = get(vertex_owner, g);
Chris@16: 
Chris@16:       using boost::graph::parallel::process_group;
Chris@16:       process_group_type pg = process_group(g);
Chris@16:       process_id_type id = process_id(pg);
Chris@16:       int num_procs = num_processes(pg);
Chris@16:       int n = 0;
Chris@16: 
Chris@16:       int my_n = num_vertices(g);
Chris@16:       all_reduce(pg, &my_n, &my_n+1, &n, std::plus<int>());
Chris@16: 
Chris@16:       //
Chris@16:       // Initialization
Chris@16:       //
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   accounting::time_type start = accounting::get_time();
Chris@16: #endif
Chris@16: 
Chris@16:       vertex_iterator vstart, vend;
Chris@16:       rev_vertex_iterator rev_vstart, rev_vend;
Chris@16:       std::vector<std::vector<vertex_descriptor> > vertex_sets, new_vertex_sets;
Chris@16: 
Chris@16:       vertex_sets.push_back(std::vector<vertex_descriptor>());
Chris@16: 
Chris@16:       // Remove vertices that do not have at least one in edge and one out edge
Chris@16:       new_vertex_sets.push_back(std::vector<vertex_descriptor>());
Chris@16:       for( boost::tie(vstart, vend) = vertices(g); vstart != vend; vstart++ )
Chris@16:         if( out_degree( get(fr, *vstart), gr) > 0 && out_degree(*vstart, g) > 0 )
Chris@16:           new_vertex_sets[0].push_back( *vstart );
Chris@16: 
Chris@16:       // Perform sequential SCC on local subgraph, filter all components with external
Chris@16:       // edges, mark remaining components and remove them from vertex_sets
Chris@16: #ifdef FILTER_LOCAL_COMPONENTS  
Chris@16:       // This doesn't actually speed up SCC in connected graphs it seems, but it does work
Chris@16:       // and may help in the case where there are lots of small strong components.
Chris@16:       {
Chris@16:         local_subgraph<const Graph> ls(g);
Chris@16:         typedef typename property_map<local_subgraph<const Graph>, vertex_index_t>::type
Chris@16:           local_index_map_type;
Chris@16:         local_index_map_type local_index = get(vertex_index, ls);
Chris@16: 
Chris@16:         std::vector<int> ls_components_vec(num_vertices(ls));
Chris@16:         typedef iterator_property_map<std::vector<int>::iterator, local_index_map_type>
Chris@16:           ls_components_map_type;
Chris@16:         ls_components_map_type ls_component(ls_components_vec.begin(), local_index);
Chris@16:         int num_comp = boost::strong_components(ls, ls_component);
Chris@16: 
Chris@16:         // Create map of components
Chris@16:         std::map<int, std::vector<vertex_descriptor> > local_comp_map;
Chris@16:         typedef typename graph_traits<local_subgraph<const Graph> >::vertex_iterator ls_vertex_iterator;
Chris@16:         ls_vertex_iterator vstart, vend;
Chris@16:         for( boost::tie(vstart,vend) = vertices(ls); vstart != vend; vstart++ )
Chris@16:           local_comp_map[get(ls_component, *vstart)].push_back( *vstart );
Chris@16: 
Chris@16:         // Filter components that have no non-local edges
Chris@16:         typedef typename graph_traits<Graph>::adjacency_iterator adjacency_iterator;
Chris@16:         typedef typename graph_traits<ReverseGraph>::adjacency_iterator rev_adjacency_iterator;
Chris@16:         adjacency_iterator abegin, aend;
Chris@16:         rev_adjacency_iterator rev_abegin, rev_aend;
Chris@16:         for( std::size_t i = 0; i < num_comp; ++i ) {
Chris@16:           bool local = true;
Chris@16:           for( std::size_t j = 0; j < local_comp_map[i].size(); j++ ) {
Chris@16:             for( boost::tie(abegin,aend) = adjacent_vertices(local_comp_map[i][j], g);
Chris@16:                  abegin != aend; abegin++ )
Chris@16:               if( get(owner, *abegin) != id ) {
Chris@16:                 local = false;
Chris@16:                 break;
Chris@16:               }
Chris@16: 
Chris@16:             if( local )
Chris@16:               for( boost::tie(rev_abegin,rev_aend) = adjacent_vertices(get(fr, local_comp_map[i][j]), gr);
Chris@16:                    rev_abegin != rev_aend; rev_abegin++ )
Chris@16:                 if( get(owner, *rev_abegin) != id ) {
Chris@16:                   local = false;
Chris@16:                   break;
Chris@16:                 }
Chris@16: 
Chris@16:             if( !local ) break;
Chris@16:           }
Chris@16: 
Chris@16:           if( local ) // Mark and remove from new_vertex_sets
Chris@16:             for( std::size_t j = 0; j < local_comp_map[i].size(); j++ ) {
Chris@16:               put( c, local_comp_map[i][j], local_comp_map[i][0] );
Chris@16:               typename std::vector<vertex_descriptor>::iterator pos =
Chris@16:                 std::find(new_vertex_sets[0].begin(), new_vertex_sets[0].end(), local_comp_map[i][j]);
Chris@16:               if( pos != new_vertex_sets[0].end() )
Chris@16:                 new_vertex_sets[0].erase(pos);
Chris@16:             }
Chris@16:         }
Chris@16:       }
Chris@16: #endif // FILTER_LOCAL_COMPONENTS
Chris@16: 
Chris@16:       all_gather( pg, new_vertex_sets[0].begin(), new_vertex_sets[0].end(), vertex_sets[0] );
Chris@16:       new_vertex_sets.clear();
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   accounting::time_type end = accounting::get_time();
Chris@16:   if(id == 0)
Chris@16:     std::cerr << "Trim local SCCs time = " << accounting::print_time(end - start) << " seconds.\n";
Chris@16: #endif
Chris@16: 
Chris@16:       if( vertex_sets[0].empty() ) return;
Chris@16: 
Chris@16:       //
Chris@16:       // Recursively determine SCCs
Chris@16:       //
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   int iterations = 0;
Chris@16: #endif
Chris@16: 
Chris@16:       // Only need to be able to map starting vertices for BFS from now on
Chris@16:       fr.clear();
Chris@16: 
Chris@16:       do {
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   if(id == 0) {
Chris@16:     printf("\n\nIteration %d:\n\n", iterations++);
Chris@16: 
Chris@16:     if( iterations > 1 ) {
Chris@16:       end = accounting::get_time();
Chris@16:       std::cerr << "Running main loop destructors time = " << accounting::print_time(end - start) << " seconds.\n";
Chris@16:     }
Chris@16: 
Chris@16:     start = accounting::get_time();
Chris@16:   }
Chris@16: #endif
Chris@16: 
Chris@16:         // Get forward->reverse mappings for BFS start vertices
Chris@16:        for (std::size_t i = 0; i < vertex_sets.size(); ++i)
Chris@16:           get(fr, vertex_sets[i][0]);
Chris@16:         synchronize(fr);
Chris@16: 
Chris@16:         // Determine local vertices to start BFS from
Chris@16:         std::vector<vertex_descriptor> local_start;
Chris@16:         for( std::size_t i = id; i < vertex_sets.size(); i += num_procs )
Chris@16:           local_start.push_back(vertex_sets[i][0]);
Chris@16: 
Chris@16:         if( local_start.empty() )
Chris@16:           local_start.push_back(vertex_sets[0][0]);
Chris@16: 
Chris@16: 
Chris@16:         // Make filtered graphs
Chris@16:         typedef std::set<vertex_descriptor> VertexSet;
Chris@16:         typedef std::set<rev_vertex_descriptor> Rev_VertexSet;
Chris@16: 
Chris@16:         VertexSet filter_set_g;
Chris@16:         Rev_VertexSet filter_set_gr;
Chris@16:         typename VertexSet::iterator fs;
Chris@16: 
Chris@16:         int active_vertices = 0;
Chris@16:         for (std::size_t i = 0; i < vertex_sets.size(); i++)
Chris@16:           active_vertices += vertex_sets[i].size();
Chris@16: 
Chris@16:         // This is a completely random bound
Chris@16:         if ( active_vertices < 0.05*n ) {
Chris@16:           // TODO: This set insertion is ridiculously inefficient, make it an in-place-merge?
Chris@16:           for (std::size_t i = 0; i < vertex_sets.size(); i++)
Chris@16:             filter_set_g.insert(vertex_sets[i].begin(), vertex_sets[i].end());
Chris@16: 
Chris@16:           for (fs = filter_set_g.begin(); fs != filter_set_g.end(); ++fs )
Chris@16:             filter_set_gr.insert(get(fr, *fs));
Chris@16:         }
Chris@16: 
Chris@16:         filtered_graph<const Graph, keep_all, detail::in_subset<VertexSet> >
Chris@16:           fg(g, keep_all(), detail::in_subset<VertexSet>(filter_set_g));
Chris@16: 
Chris@16:         filtered_graph<const ReverseGraph, keep_all, detail::in_subset<VertexSet> >
Chris@16:           fgr(gr, keep_all(), detail::in_subset<VertexSet>(filter_set_gr));
Chris@16: 
Chris@16:         // Add additional starting vertices to BFS queue
Chris@16:         typedef filtered_queue<queue<vertex_descriptor>, boost::detail::has_not_been_seen<VertexIndexMap> >
Chris@16:           local_queue_type;
Chris@16:         typedef boost::graph::distributed::distributed_queue<process_group_type, OwnerMap, local_queue_type>
Chris@16:           queue_t;
Chris@16: 
Chris@16:         typedef typename property_map<ReverseGraph, vertex_owner_t>::const_type
Chris@16:           RevOwnerMap;
Chris@16: 
Chris@16:         typedef filtered_queue<queue<rev_vertex_descriptor>, boost::detail::has_not_been_seen<VertexIndexMap> >
Chris@16:           rev_local_queue_type;
Chris@16:         typedef boost::graph::distributed::distributed_queue<process_group_type, RevOwnerMap, rev_local_queue_type>
Chris@16:           rev_queue_t;
Chris@16: 
Chris@16:         queue_t Q(process_group(g),
Chris@16:                   owner,
Chris@16:                   make_filtered_queue(queue<vertex_descriptor>(),
Chris@16:                                       boost::detail::has_not_been_seen<VertexIndexMap>
Chris@16:                                       (num_vertices(g), vertex_index_map)),
Chris@16:                   false);
Chris@16: 
Chris@16:         rev_queue_t Qr(process_group(gr),
Chris@16:                        get(vertex_owner, gr),
Chris@16:                        make_filtered_queue(queue<rev_vertex_descriptor>(),
Chris@16:                                            boost::detail::has_not_been_seen<VertexIndexMap>
Chris@16:                                            (num_vertices(gr), vertex_index_map)),
Chris@16:                        false);
Chris@16: 
Chris@16:         for( std::size_t i = 1; i < local_start.size(); ++i ) {
Chris@16:           Q.push(local_start[i]);
Chris@16:           Qr.push(get(fr, local_start[i]));
Chris@16:         }
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   end = accounting::get_time();
Chris@16:   if(id == 0)
Chris@16:     std::cerr << "  Initialize BFS time = " << accounting::print_time(end - start) << " seconds.\n";
Chris@16:   start = accounting::get_time();
Chris@16: #endif
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   accounting::time_type start2 = accounting::get_time();
Chris@16: #endif
Chris@16: 
Chris@16:         // Forward BFS
Chris@16:         std::vector<default_color_type> color_map_s(num_vertices(g));
Chris@16:         ColorMap color_map(color_map_s.begin(), vertex_index_map);
Chris@16:         std::vector<vertex_descriptor> succ_map_s(num_vertices(g), graph_traits<Graph>::null_vertex());
Chris@16:         ParentMap succ_map(succ_map_s.begin(), vertex_index_map);
Chris@16: 
Chris@16:         for( std::size_t i = 0; i < vertex_sets.size(); ++i )
Chris@16:           put(succ_map, vertex_sets[i][0], vertex_sets[i][0]);
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   accounting::time_type end2 = accounting::get_time();
Chris@16:   if(id == 0)
Chris@16:     std::cerr << "  Initialize forward BFS time = " << accounting::print_time(end2 - start2) << " seconds.\n";
Chris@16: #endif
Chris@16: 
Chris@16:         if (active_vertices < 0.05*n)
Chris@16:           breadth_first_search(fg, local_start[0], Q,
Chris@16:                                detail::scc_discovery_visitor<filtered_graph<const Graph, keep_all,
Chris@16:                                                                             detail::in_subset<VertexSet> >, ParentMap>
Chris@16:                                (succ_map),
Chris@16:                                color_map);
Chris@16:         else
Chris@16:           breadth_first_search(g, local_start[0], Q,
Chris@16:                                detail::scc_discovery_visitor<const Graph, ParentMap>(succ_map),
Chris@16:                                color_map);
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   start2 = accounting::get_time();
Chris@16: #endif
Chris@16: 
Chris@16:         // Reverse BFS
Chris@16:         color_map.clear(); // reuse color map since g and gr have same vertex index
Chris@16:         std::vector<vertex_descriptor> pred_map_s(num_vertices(gr), graph_traits<Graph>::null_vertex());
Chris@16:         Rev_ParentMap pred_map(pred_map_s.begin(), vertex_index_map);
Chris@16: 
Chris@16:         for( std::size_t i = 0; i < vertex_sets.size(); ++i )
Chris@16:           put(pred_map, get(fr, vertex_sets[i][0]), vertex_sets[i][0]);
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   end2 = accounting::get_time();
Chris@16:   if(id == 0)
Chris@16:     std::cerr << "  Initialize reverse BFS time = " << accounting::print_time(end2 - start2) << " seconds.\n";
Chris@16: #endif
Chris@16: 
Chris@16:         if (active_vertices < 0.05*n)
Chris@16:           breadth_first_search(fgr, get(fr, local_start[0]),
Chris@16:                                Qr,
Chris@16:                                detail::scc_discovery_visitor<filtered_graph<const ReverseGraph, keep_all,
Chris@16:                                                                             detail::in_subset<Rev_VertexSet> >, Rev_ParentMap>
Chris@16:                                (pred_map),
Chris@16:                                color_map);
Chris@16:         else
Chris@16:           breadth_first_search(gr, get(fr, local_start[0]),
Chris@16:                                Qr,
Chris@16:                                detail::scc_discovery_visitor<const ReverseGraph, Rev_ParentMap>(pred_map),
Chris@16:                                color_map);
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   end = accounting::get_time();
Chris@16:   if(id == 0)
Chris@16:     std::cerr << "  Perform forward and reverse BFS time = " << accounting::print_time(end - start) << " seconds.\n";
Chris@16:   start = accounting::get_time();
Chris@16: #endif
Chris@16: 
Chris@16:         // Send predecessors and successors discovered by this proc to the proc responsible for
Chris@16:         // this BFS tree
Chris@16:         typedef struct detail::v_sets<vertex_descriptor> Vsets;
Chris@16:         std::map<vertex_descriptor, Vsets> set_map;
Chris@16: 
Chris@16:         std::map<vertex_descriptor, int> dest_map;
Chris@16: 
Chris@16:         std::vector<VertexPairVec> successors(num_procs);
Chris@16:         std::vector<VertexPairVec> predecessors(num_procs);
Chris@16: 
Chris@16:         // Calculate destinations for messages
Chris@16:         for (std::size_t i = 0; i < vertex_sets.size(); ++i)
Chris@16:           dest_map[vertex_sets[i][0]] = i % num_procs;
Chris@16: 
Chris@16:         for( boost::tie(vstart, vend) = vertices(g); vstart != vend; vstart++ ) {
Chris@16:           vertex_descriptor v = get(succ_map, *vstart);
Chris@16:           if( v != graph_traits<Graph>::null_vertex() ) {
Chris@16:             if (dest_map[v] == id)
Chris@16:               set_map[v].succ.push_back(*vstart);
Chris@16:             else
Chris@16:               successors[dest_map[v]].push_back( std::make_pair(v, *vstart) );
Chris@16:           }
Chris@16:         }
Chris@16: 
Chris@16:         for( boost::tie(rev_vstart, rev_vend) = vertices(gr); rev_vstart != rev_vend; rev_vstart++ ) {
Chris@16:           vertex_descriptor v = get(pred_map, *rev_vstart);
Chris@16:           if( v != graph_traits<Graph>::null_vertex() ) {
Chris@16:             if (dest_map[v] == id)
Chris@16:               set_map[v].pred.push_back(get(rf, *rev_vstart));
Chris@16:             else
Chris@16:               predecessors[dest_map[v]].push_back( std::make_pair(v, get(rf, *rev_vstart)) );
Chris@16:           }
Chris@16:         }
Chris@16: 
Chris@16:         // Send predecessor and successor messages
Chris@16:         for (process_id_type i = 0; i < num_procs; ++i) {
Chris@16:           if (!successors[i].empty()) {
Chris@16:             send(pg, i, fhp_succ_size_msg, successors[i].size());
Chris@16:             send(pg, i, fhp_succ_msg, &successors[i][0], successors[i].size());
Chris@16:           }
Chris@16:           if (!predecessors[i].empty()) {
Chris@16:             send(pg, i, fhp_pred_size_msg, predecessors[i].size());
Chris@16:             send(pg, i, fhp_pred_msg, &predecessors[i][0], predecessors[i].size());
Chris@16:           }
Chris@16:         }
Chris@16:         synchronize(pg);
Chris@16: 
Chris@16:         // Receive predecessor and successor messages and handle them
Chris@16:         while (optional<std::pair<process_id_type, int> > m = probe(pg)) {
Chris@16:           BOOST_ASSERT(m->second == fhp_succ_size_msg || m->second == fhp_pred_size_msg);
Chris@16:           std::size_t num_requests;
Chris@16:           receive(pg, m->first, m->second, num_requests);
Chris@16:           VertexPairVec requests(num_requests);
Chris@16:           if (m->second == fhp_succ_size_msg) {
Chris@16:             receive(pg, m->first, fhp_succ_msg, &requests[0],
Chris@16:                     num_requests);
Chris@16: 
Chris@16:             std::map<vertex_descriptor, int> added;
Chris@16:             for (std::size_t i = 0; i < requests.size(); ++i) {
Chris@16:               set_map[requests[i].first].succ.push_back(requests[i].second);
Chris@16:               added[requests[i].first]++;
Chris@16:             }
Chris@16: 
Chris@16:             // If order of vertex traversal in vertices() is std::less<vertex_descriptor>,
Chris@16:             // then the successor sets will be in order
Chris@16:             for (std::size_t i = 0; i < local_start.size(); ++i)
Chris@16:               if (added[local_start[i]] > 0)
Chris@16:                   std::inplace_merge(set_map[local_start[i]].succ.begin(),
Chris@16:                                      set_map[local_start[i]].succ.end() - added[local_start[i]],
Chris@16:                                      set_map[local_start[i]].succ.end(),
Chris@16:                                      std::less<vertex_descriptor>());
Chris@16: 
Chris@16:           } else {
Chris@16:             receive(pg, m->first, fhp_pred_msg, &requests[0],
Chris@16:                     num_requests);
Chris@16: 
Chris@16:             std::map<vertex_descriptor, int> added;
Chris@16:             for (std::size_t i = 0; i < requests.size(); ++i) {
Chris@16:               set_map[requests[i].first].pred.push_back(requests[i].second);
Chris@16:               added[requests[i].first]++;
Chris@16:             }
Chris@16: 
Chris@16:             if (boost::is_same<detail::vertex_identity_property_map<vertex_descriptor>, IsoMapRF>::value)
Chris@16:               for (std::size_t i = 0; i < local_start.size(); ++i)
Chris@16:                 if (added[local_start[i]] > 0)
Chris@16:                   std::inplace_merge(set_map[local_start[i]].pred.begin(),
Chris@16:                                      set_map[local_start[i]].pred.end() - added[local_start[i]],
Chris@16:                                      set_map[local_start[i]].pred.end(),
Chris@16:                                      std::less<vertex_descriptor>());
Chris@16:           }
Chris@16:         }
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   end = accounting::get_time();
Chris@16:   if(id == 0)
Chris@16:     std::cerr << "  All gather successors and predecessors time = " << accounting::print_time(end - start) << " seconds.\n";
Chris@16:   start = accounting::get_time();
Chris@16: #endif
Chris@16: 
Chris@16:         //
Chris@16:         // Filter predecessor and successor sets and perform set arithmetic
Chris@16:         //
Chris@16:         new_vertex_sets.clear();
Chris@16: 
Chris@16:         if( std::size_t(id) < vertex_sets.size() ) { //If this proc has one or more unique starting points
Chris@16: 
Chris@16:           for( std::size_t i = 0; i < local_start.size(); ++i ) {
Chris@16: 
Chris@16:             vertex_descriptor v = local_start[i];
Chris@16: 
Chris@16:             // Replace this sort with an in-place merges during receive step if possible
Chris@16:             if (!boost::is_same<detail::vertex_identity_property_map<vertex_descriptor>, IsoMapRF>::value) 
Chris@16:               std::sort(set_map[v].pred.begin(), set_map[v].pred.end(), std::less<vertex_descriptor>());
Chris@16: 
Chris@16:             // Limit predecessor and successor sets to members of the original set
Chris@16:             std::vector<vertex_descriptor> temp;
Chris@16: 
Chris@16:             std::set_intersection( vertex_sets[id + i*num_procs].begin(), vertex_sets[id + i*num_procs].end(),
Chris@16:                                    set_map[v].pred.begin(), set_map[v].pred.end(),
Chris@16:                                    back_inserter(temp),
Chris@16:                                    std::less<vertex_descriptor>());
Chris@16:             set_map[v].pred.clear();
Chris@16:             std::swap(set_map[v].pred, temp);
Chris@16: 
Chris@16:             std::set_intersection( vertex_sets[id + i*num_procs].begin(), vertex_sets[id + i*num_procs].end(),
Chris@16:                                    set_map[v].succ.begin(), set_map[v].succ.end(),
Chris@16:                                    back_inserter(temp),
Chris@16:                                    std::less<vertex_descriptor>());
Chris@16:             set_map[v].succ.clear();
Chris@16:             std::swap(set_map[v].succ, temp);
Chris@16: 
Chris@16:             // Intersection(pred, succ)
Chris@16:             std::set_intersection(set_map[v].pred.begin(), set_map[v].pred.end(),
Chris@16:                                     set_map[v].succ.begin(), set_map[v].succ.end(),
Chris@16:                                     back_inserter(set_map[v].intersect),
Chris@16:                                     std::less<vertex_descriptor>());
Chris@16: 
Chris@16:             // Union(pred, succ)
Chris@16:             std::set_union(set_map[v].pred.begin(), set_map[v].pred.end(),
Chris@16:                            set_map[v].succ.begin(), set_map[v].succ.end(),
Chris@16:                            back_inserter(set_map[v].ps_union),
Chris@16:                            std::less<vertex_descriptor>());
Chris@16: 
Chris@16:             new_vertex_sets.push_back(std::vector<vertex_descriptor>());
Chris@16:             // Original set - Union(pred, succ)
Chris@16:             std::set_difference(vertex_sets[id + i*num_procs].begin(), vertex_sets[id + i*num_procs].end(),
Chris@16:                                 set_map[v].ps_union.begin(), set_map[v].ps_union.end(),
Chris@16:                                 back_inserter(new_vertex_sets[new_vertex_sets.size() - 1]),
Chris@16:                                 std::less<vertex_descriptor>());
Chris@16: 
Chris@16:             set_map[v].ps_union.clear();
Chris@16: 
Chris@16:             new_vertex_sets.push_back(std::vector<vertex_descriptor>());
Chris@16:             // Pred - Intersect(pred, succ)
Chris@16:             std::set_difference(set_map[v].pred.begin(), set_map[v].pred.end(),
Chris@16:                                 set_map[v].intersect.begin(), set_map[v].intersect.end(),
Chris@16:                                 back_inserter(new_vertex_sets[new_vertex_sets.size() - 1]),
Chris@16:                                 std::less<vertex_descriptor>());
Chris@16: 
Chris@16:             set_map[v].pred.clear();
Chris@16: 
Chris@16:             new_vertex_sets.push_back(std::vector<vertex_descriptor>());
Chris@16:             // Succ - Intersect(pred, succ)
Chris@16:             std::set_difference(set_map[v].succ.begin(), set_map[v].succ.end(),
Chris@16:                                 set_map[v].intersect.begin(), set_map[v].intersect.end(),
Chris@16:                                 back_inserter(new_vertex_sets[new_vertex_sets.size() - 1]),
Chris@16:                                 std::less<vertex_descriptor>());
Chris@16: 
Chris@16:             set_map[v].succ.clear();
Chris@16: 
Chris@16:             // Label SCC just identified with the 'first' vertex in that SCC
Chris@16:             for( std::size_t j = 0; j < set_map[v].intersect.size(); j++ )
Chris@16:               put(c, set_map[v].intersect[j], set_map[v].intersect[0]);
Chris@16: 
Chris@16:             set_map[v].intersect.clear();
Chris@16:           }
Chris@16:         }
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   end = accounting::get_time();
Chris@16:   if(id == 0)
Chris@16:     std::cerr << "  Perform set arithemetic time = " << accounting::print_time(end - start) << " seconds.\n";
Chris@16:   start = accounting::get_time();
Chris@16: #endif
Chris@16: 
Chris@16:         // Remove sets of size 1 from new_vertex_sets
Chris@16:         typename std::vector<std::vector<vertex_descriptor> >::iterator vviter;
Chris@16:         for( vviter = new_vertex_sets.begin(); vviter != new_vertex_sets.end(); /*in loop*/ )
Chris@16:           if( (*vviter).size() < 2 )
Chris@16:             vviter = new_vertex_sets.erase( vviter );
Chris@16:           else
Chris@16:             vviter++;
Chris@16: 
Chris@16:         // All gather new sets and recur (gotta marshal and unmarshal sets first)
Chris@16:         vertex_sets.clear();
Chris@16:         std::vector<vertex_descriptor> serial_sets, all_serial_sets;
Chris@16:         detail::marshal_set<Graph>( new_vertex_sets, serial_sets );
Chris@16:         all_gather( pg, serial_sets.begin(), serial_sets.end(), all_serial_sets );
Chris@16:         detail::unmarshal_set<Graph>( all_serial_sets, vertex_sets );
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   end = accounting::get_time();
Chris@16:   if(id == 0) {
Chris@16:     std::cerr << "  Serialize and gather new vertex sets time = " << accounting::print_time(end - start) << " seconds.\n\n\n";
Chris@16: 
Chris@16:     printf("Vertex sets: %d\n", (int)vertex_sets.size() );
Chris@16:     for( std::size_t i = 0; i < vertex_sets.size(); ++i )
Chris@16:       printf("  %d: %d\n", i, (int)vertex_sets[i].size() );
Chris@16:   }
Chris@16:   start = accounting::get_time();
Chris@16: #endif
Chris@16: 
Chris@16:         // HACK!?!  --  This would be more properly implemented as a topological sort
Chris@16:         // Remove vertices without an edge to another vertex in the set and an edge from another
Chris@16:         // vertex in the set
Chris@16:        typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iterator;
Chris@16:        out_edge_iterator estart, eend;
Chris@16:        typedef typename graph_traits<ReverseGraph>::out_edge_iterator r_out_edge_iterator;
Chris@16:        r_out_edge_iterator restart, reend;
Chris@16:        for (std::size_t i = 0; i < vertex_sets.size(); ++i) {
Chris@16:          std::vector<vertex_descriptor> new_set;
Chris@16:          for (std::size_t j = 0; j < vertex_sets[i].size(); ++j) {
Chris@16:            vertex_descriptor v = vertex_sets[i][j];
Chris@16:            if (get(owner, v) == id) {
Chris@16:              boost::tie(estart, eend) = out_edges(v, g);
Chris@16:              while (estart != eend && find(vertex_sets[i].begin(), vertex_sets[i].end(),
Chris@16:                                            target(*estart,g)) == vertex_sets[i].end()) estart++;
Chris@16:              if (estart != eend) {
Chris@16:                boost::tie(restart, reend) = out_edges(get(fr, v), gr);
Chris@16:                while (restart != reend && find(vertex_sets[i].begin(), vertex_sets[i].end(),
Chris@16:                                                get(rf, target(*restart,gr))) == vertex_sets[i].end()) restart++;
Chris@16:                if (restart != reend)
Chris@16:                  new_set.push_back(v);
Chris@16:              }
Chris@16:            }
Chris@16:          }
Chris@16:          vertex_sets[i].clear();
Chris@16:          all_gather(pg, new_set.begin(), new_set.end(), vertex_sets[i]);
Chris@16:          std::sort(vertex_sets[i].begin(), vertex_sets[i].end(), std::less<vertex_descriptor>());
Chris@16:        }
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   end = accounting::get_time();
Chris@16:   if(id == 0)
Chris@16:     std::cerr << "  Trim vertex sets time = " << accounting::print_time(end - start) << " seconds.\n\n\n";
Chris@16:   start = accounting::get_time();
Chris@16: #endif
Chris@16: 
Chris@16:       } while ( !vertex_sets.empty() );
Chris@16: 
Chris@16: 
Chris@16:       // Label vertices not in a SCC as their own SCC
Chris@16:       for( boost::tie(vstart, vend) = vertices(g); vstart != vend; vstart++ )
Chris@16:         if( get(c, *vstart) == graph_traits<Graph>::null_vertex() )
Chris@16:           put(c, *vstart, *vstart);
Chris@16: 
Chris@16:       synchronize(c);
Chris@16:     }
Chris@16: 
Chris@16:     template<typename Graph, typename ReverseGraph, typename IsoMap>
Chris@16:     void
Chris@16:     build_reverse_graph( const Graph& g, ReverseGraph& gr, IsoMap& fr, IsoMap& rf )
Chris@16:     {
Chris@16:       typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
Chris@16:       typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16:       typedef typename graph_traits<Graph>::out_edge_iterator out_edge_iterator;
Chris@16:       typedef typename boost::graph::parallel::process_group_type<Graph>::type process_group_type;
Chris@16:       typedef typename process_group_type::process_id_type process_id_type;
Chris@16:       typedef std::vector<std::pair<vertex_descriptor, vertex_descriptor> > VertexPairVec;
Chris@16: 
Chris@16:       typename property_map<Graph, vertex_owner_t>::const_type
Chris@16:         owner = get(vertex_owner, g);
Chris@16: 
Chris@16:       process_group_type pg = process_group(g);
Chris@16:       process_id_type id = process_id(pg);
Chris@16: 
Chris@16:       int n;
Chris@16:       vertex_iterator vstart, vend;
Chris@16:       int num_procs = num_processes(pg);
Chris@16: 
Chris@16:       vertex_descriptor v;
Chris@16:       out_edge_iterator oestart, oeend;
Chris@16:       for( boost::tie(vstart, vend) = vertices(g); vstart != vend; vstart++ )
Chris@16:         {
Chris@16:           v = add_vertex(gr);
Chris@16:           put(fr, *vstart, v);
Chris@16:           put(rf, v, *vstart);
Chris@16:         }
Chris@16: 
Chris@16:       gr.distribution() = g.distribution();
Chris@16: 
Chris@16:       int my_n = num_vertices(g);
Chris@16:       all_reduce(pg, &my_n, &my_n+1, &n, std::plus<int>());
Chris@16: 
Chris@16:       for (int i = 0; i < n; ++i)
Chris@16:         get(fr, vertex(i,g));
Chris@16:       synchronize(fr);
Chris@16: 
Chris@16:       // Add edges to gr
Chris@16:       std::vector<std::pair<vertex_descriptor, vertex_descriptor> > new_edges;
Chris@16:       for( boost::tie(vstart, vend) = vertices(g); vstart != vend; vstart++ )
Chris@16:         for( boost::tie(oestart, oeend) = out_edges(*vstart, g); oestart != oeend; oestart++ )
Chris@16:           new_edges.push_back( std::make_pair(get(fr, target(*oestart,g)), get(fr, source(*oestart, g))) );
Chris@16: 
Chris@16:       std::vector<VertexPairVec> edge_requests(num_procs);
Chris@16: 
Chris@16:       typename std::vector<std::pair<vertex_descriptor, vertex_descriptor> >::iterator iter;
Chris@16:       for( iter = new_edges.begin(); iter != new_edges.end(); iter++ ) {
Chris@16:         std::pair<vertex_descriptor, vertex_descriptor> p1 = *iter;
Chris@16:         if( get(owner,  p1.first ) == id )
Chris@16:           add_edge( p1.first, p1.second, gr );
Chris@16:         else
Chris@16:           edge_requests[get(owner, p1.first)].push_back(p1);
Chris@16:       }
Chris@16:       new_edges.clear();
Chris@16: 
Chris@16:       // Send edge addition requests
Chris@16:       for (process_id_type p = 0; p < num_procs; ++p) {
Chris@16:         if (!edge_requests[p].empty()) {
Chris@16:           VertexPairVec reqs(edge_requests[p].begin(), edge_requests[p].end());
Chris@16:           send(pg, p, fhp_edges_size_msg, reqs.size());
Chris@16:           send(pg, p, fhp_add_edges_msg, &reqs[0], reqs.size());
Chris@16:         }
Chris@16:       }
Chris@16:       synchronize(pg);
Chris@16: 
Chris@16:       // Receive edge addition requests and handle them
Chris@16:       while (optional<std::pair<process_id_type, int> > m = probe(pg)) {
Chris@16:         BOOST_ASSERT(m->second == fhp_edges_size_msg);
Chris@16:         std::size_t num_requests;
Chris@16:         receive(pg, m->first, m->second, num_requests);
Chris@16:         VertexPairVec requests(num_requests);
Chris@16:         receive(pg, m->first, fhp_add_edges_msg, &requests[0],
Chris@16:                 num_requests);
Chris@16:         for( std::size_t i = 0; i < requests.size(); ++i )
Chris@16:           add_edge( requests[i].first, requests[i].second, gr );
Chris@16:       }
Chris@16:           synchronize(gr);
Chris@16:     }
Chris@16: 
Chris@16:     template<typename Graph, typename VertexComponentMap, typename ComponentMap>
Chris@16:     typename property_traits<ComponentMap>::value_type
Chris@16:     number_components(const Graph& g, VertexComponentMap r, ComponentMap c)
Chris@16:     {
Chris@16:       typedef typename boost::graph::parallel::process_group_type<Graph>::type process_group_type;
Chris@16:       typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator;
Chris@16:       typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16:       typedef typename property_traits<ComponentMap>::value_type ComponentMapType;
Chris@16:       std::vector<vertex_descriptor> my_roots, all_roots;
Chris@16:       vertex_iterator vstart, vend;
Chris@16: 
Chris@16:       for( boost::tie(vstart, vend) = vertices(g); vstart != vend; vstart++ )
Chris@16:         if( find( my_roots.begin(), my_roots.end(), get(r, *vstart) ) == my_roots.end() )
Chris@16:           my_roots.push_back( get(r, *vstart) );
Chris@16: 
Chris@16:       all_gather( process_group(g), my_roots.begin(), my_roots.end(), all_roots );
Chris@16: 
Chris@16:       /* Number components */
Chris@16:       std::map<vertex_descriptor, ComponentMapType> comp_numbers;
Chris@16:       ComponentMapType c_num = 0;
Chris@16: 
Chris@16:       // Compute component numbers
Chris@16:       for (std::size_t i = 0; i < all_roots.size(); ++i )
Chris@16:         if ( comp_numbers.count(all_roots[i]) == 0 )
Chris@16:           comp_numbers[all_roots[i]] = c_num++;
Chris@16: 
Chris@16:       // Broadcast component numbers
Chris@16:       for( boost::tie(vstart, vend) = vertices(g); vstart != vend; vstart++ )
Chris@16:         put( c, *vstart, comp_numbers[get(r,*vstart)] );
Chris@16: 
Chris@16:       // Broadcast number of components
Chris@16:       if (process_id(process_group(g)) == 0) {
Chris@16:         typedef typename process_group_type::process_size_type
Chris@16:           process_size_type;
Chris@16:         for (process_size_type dest = 1, n = num_processes(process_group(g));
Chris@16:               dest != n; ++dest)
Chris@16:           send(process_group(g), dest, 0, c_num);
Chris@16:       }
Chris@16: 
Chris@16:       synchronize(process_group(g));
Chris@16: 
Chris@16:       if (process_id(process_group(g)) != 0) receive(process_group(g), 0, 0, c_num);
Chris@16: 
Chris@16:       synchronize(c);
Chris@16:       return c_num;
Chris@16:     }
Chris@16: 
Chris@16: 
Chris@16:     template<typename Graph, typename ComponentMap, typename VertexComponentMap,
Chris@16:              typename VertexIndexMap>
Chris@16:     typename property_traits<ComponentMap>::value_type
Chris@16:     fleischer_hendrickson_pinar_strong_components_impl
Chris@16:       (const Graph& g,
Chris@16:        ComponentMap c,
Chris@16:        VertexComponentMap r,
Chris@16:        VertexIndexMap vertex_index_map,
Chris@16:        incidence_graph_tag)
Chris@16:     {
Chris@16:       typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16:       typedef iterator_property_map<typename std::vector<vertex_descriptor>::iterator,
Chris@16:                                     VertexIndexMap> IsoMap;
Chris@16:       typename boost::graph::parallel::process_group_type<Graph>::type pg = process_group(g);
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   accounting::time_type start = accounting::get_time();
Chris@16: #endif
Chris@16: 
Chris@16:       typedef adjacency_list<listS,
Chris@16:                              distributedS<typename boost::graph::parallel::process_group_type<Graph>::type, vecS>,
Chris@16:                              directedS > ReverseGraph;
Chris@16: 
Chris@16:       ReverseGraph gr(0, pg);
Chris@16:       std::vector<vertex_descriptor> fr_s(num_vertices(g));
Chris@16:       std::vector<vertex_descriptor> rf_s(num_vertices(g));
Chris@16:       IsoMap fr(fr_s.begin(), vertex_index_map);  // fr = forward->reverse
Chris@16:       IsoMap rf(rf_s.begin(), vertex_index_map); // rf = reverse->forward
Chris@16: 
Chris@16:       build_reverse_graph(g, gr, fr, rf);
Chris@16: 
Chris@16: #ifdef PBGL_SCC_DEBUG
Chris@16:   accounting::time_type end = accounting::get_time();
Chris@16:   if(process_id(process_group(g)) == 0)
Chris@16:     std::cerr << "Reverse graph initialization time = " << accounting::print_time(end - start) << " seconds.\n";
Chris@16: #endif
Chris@16: 
Chris@16:   fleischer_hendrickson_pinar_strong_components(g, r, gr, fr, rf, 
Chris@16:                                                 vertex_index_map);
Chris@16: 
Chris@16:       typename property_traits<ComponentMap>::value_type c_num = number_components(g, r, c);
Chris@16: 
Chris@16:       return c_num;
Chris@16:     }
Chris@16: 
Chris@16:     template<typename Graph, typename ComponentMap, typename VertexComponentMap,
Chris@16:              typename VertexIndexMap>
Chris@16:     typename property_traits<ComponentMap>::value_type
Chris@16:     fleischer_hendrickson_pinar_strong_components_impl
Chris@16:       (const Graph& g,
Chris@16:        ComponentMap c,
Chris@16:        VertexComponentMap r,
Chris@16:        VertexIndexMap vertex_index_map,
Chris@16:        bidirectional_graph_tag)
Chris@16:     {
Chris@16:       typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor;
Chris@16: 
Chris@16:       reverse_graph<Graph> gr(g);
Chris@16:       detail::vertex_identity_property_map<vertex_descriptor> fr, rf;
Chris@16: 
Chris@16:       fleischer_hendrickson_pinar_strong_components(g, r, gr, fr, rf, 
Chris@16:                                                     vertex_index_map);
Chris@16: 
Chris@16:       typename property_traits<ComponentMap>::value_type c_num
Chris@16:         = number_components(g, r, c);
Chris@16: 
Chris@16:       return c_num;
Chris@16:     }
Chris@16: 
Chris@16:     template<typename Graph, typename ComponentMap, typename VertexIndexMap>
Chris@16:     inline typename property_traits<ComponentMap>::value_type
Chris@16:     fleischer_hendrickson_pinar_strong_components
Chris@16:       (const Graph& g,
Chris@16:        ComponentMap c,
Chris@16:        VertexIndexMap vertex_index_map)
Chris@16:     {
Chris@16:       typedef typename graph_traits<Graph>::vertex_descriptor
Chris@16:         vertex_descriptor;
Chris@16:       typedef iterator_property_map<typename std::vector<vertex_descriptor>::iterator,
Chris@16:                                     VertexIndexMap> VertexComponentMap;
Chris@16:       typename boost::graph::parallel::process_group_type<Graph>::type pg 
Chris@16:         = process_group(g);
Chris@16: 
Chris@16:       if (num_processes(pg) == 1) {
Chris@16:         local_subgraph<const Graph> ls(g);
Chris@16:         return boost::strong_components(ls, c);
Chris@16:       }
Chris@16: 
Chris@16:       // Create a VertexComponentMap for intermediate labeling of SCCs
Chris@16:       std::vector<vertex_descriptor> r_s(num_vertices(g), graph_traits<Graph>::null_vertex());
Chris@16:       VertexComponentMap r(r_s.begin(), vertex_index_map);
Chris@16: 
Chris@16:       return fleischer_hendrickson_pinar_strong_components_impl
Chris@16:                (g, c, r, vertex_index_map,
Chris@16:                 typename graph_traits<Graph>::traversal_category());
Chris@16:     }
Chris@16: 
Chris@16:     template<typename Graph, typename ComponentMap>
Chris@16:     inline typename property_traits<ComponentMap>::value_type
Chris@16:     fleischer_hendrickson_pinar_strong_components(const Graph& g,
Chris@16:                                                   ComponentMap c)
Chris@16:     {
Chris@16:       return fleischer_hendrickson_pinar_strong_components(g, c, get(vertex_index, g));
Chris@16:     }
Chris@16: 
Chris@16: }  // end namespace distributed
Chris@16: 
Chris@16: using distributed::fleischer_hendrickson_pinar_strong_components;
Chris@16: 
Chris@16: } // end namespace graph
Chris@16: 
Chris@16: template<class Graph, class ComponentMap, class P, class T, class R>
Chris@16: inline typename property_traits<ComponentMap>::value_type
Chris@16: strong_components
Chris@16:  (const Graph& g, ComponentMap comp,
Chris@16:   const bgl_named_params<P, T, R>&
Chris@16:   BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, distributed_graph_tag))
Chris@16: {
Chris@16:   return graph::fleischer_hendrickson_pinar_strong_components(g, comp);
Chris@16: }
Chris@16: 
Chris@16: template<class Graph, class ComponentMap>
Chris@16: inline typename property_traits<ComponentMap>::value_type
Chris@16: strong_components
Chris@16:  (const Graph& g, ComponentMap comp
Chris@16:   BOOST_GRAPH_ENABLE_IF_MODELS_PARM(Graph, distributed_graph_tag))
Chris@16: {
Chris@16:   return graph::fleischer_hendrickson_pinar_strong_components(g, comp);
Chris@16: }
Chris@16: 
Chris@16: } /* end namespace boost */
Chris@16: 
Chris@16: #endif // BOOST_GRAPH_DISTRIBUTED_SCC_HPP