Boost C++ Libraries

boost/graph/distributed/depth_first_search.hpp

// Copyright (C) 2004-2008 The Trustees of Indiana University.

// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Douglas Gregor
//           Andrew Lumsdaine
#ifndef BOOST_GRAPH_DISTRIBUTED_DFS_HPP
#define BOOST_GRAPH_DISTRIBUTED_DFS_HPP

#ifndef BOOST_GRAPH_USE_MPI
#error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
#endif

#include <boost/graph/graph_traits.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/overloading.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/distributed/concepts.hpp>
#include <boost/static_assert.hpp>
#include <boost/assert.hpp>
#include <boost/graph/parallel/process_group.hpp>
#include <boost/graph/parallel/container_traits.hpp>

namespace boost {
  namespace graph { namespace distributed { namespace detail {
    template<typename DistributedGraph, typename ColorMap, typename ParentMap,
             typename ExploreMap, typename VertexIndexMap, typename DFSVisitor>
    class parallel_dfs
    {
      typedef typename graph_traits<DistributedGraph>::vertex_iterator
        vertex_iterator;
      typedef typename graph_traits<DistributedGraph>::vertex_descriptor
        vertex_descriptor;
      typedef typename graph_traits<DistributedGraph>::out_edge_iterator
        out_edge_iterator;

      typedef typename boost::graph::parallel::process_group_type<DistributedGraph>
        ::type process_group_type;
      typedef typename process_group_type::process_id_type process_id_type;

      /**
       * The first vertex in the pair is the local node (i) and the
       * second vertex in the pair is the (possibly remote) node (j).
       */
      typedef boost::parallel::detail::untracked_pair<vertex_descriptor, vertex_descriptor> vertex_pair;

      typedef typename property_traits<ColorMap>::value_type color_type;
      typedef color_traits<color_type> Color;

      // Message types
      enum { discover_msg = 10, return_msg = 50, visited_msg = 100 , done_msg = 150};
        

    public:
      parallel_dfs(const DistributedGraph& g, ColorMap color,
                   ParentMap parent, ExploreMap explore,
                   VertexIndexMap index_map, DFSVisitor vis)
        : g(g), color(color), parent(parent), explore(explore),
          index_map(index_map), vis(vis), pg(process_group(g)),
          owner(get(vertex_owner, g)), next_out_edge(num_vertices(g))
      { }

      void run(vertex_descriptor s)
      {
        vertex_iterator vi, vi_end;
        for (boost::tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
          put(color, *vi, Color::white());
          put(parent, *vi, *vi); 
          put(explore, *vi, *vi);
          next_out_edge[get(index_map, *vi)] = out_edges(*vi, g).first;
          vis.initialize_vertex(*vi, g);
        }

        vis.start_vertex(s, g);
        
        if (get(owner, s) == process_id(pg)) {
          send_oob(pg, get(owner, s), discover_msg, vertex_pair(s, s));
        }
        
        bool done = false;
        while (!done) {
          std::pair<process_id_type, int> msg = *pg.poll(true);

          switch (msg.second) {
          case discover_msg:
            {
              vertex_pair p;
              receive_oob(pg, msg.first, msg.second, p);

              if (p.first != p.second) {
                // delete j from nomessage(j)
                if (get(color, p.second) != Color::black())
                  local_put(color, p.second, Color::gray());

                if (recover(p)) break;
              }

              if (get(color, p.first) == Color::white()) {
                put(color, p.first, Color::gray());
                put(parent, p.first, p.second);

                vis.discover_vertex(p.first, g);

                if (shift_center_of_activity(p.first)) break;
                
                out_edge_iterator ei, ei_end;
                for (boost::tie(ei,ei_end) = out_edges(p.first, g); ei != ei_end; ++ei)
                {
                  // Notify everyone who may not know that the source
                  // vertex has been visited. They can then mark the
                  // corresponding color map entry gray.
                  if (get(parent, p.first) != target(*ei, g)
                      && get(explore, p.first) != target(*ei, g)) {
                    vertex_pair visit(target(*ei, g), p.first);
                    
                    send_oob(pg, get(owner, target(*ei, g)), visited_msg, visit);
                  }
                }
              }
            }
            break;
            
          case visited_msg:
            {
              vertex_pair p;
              receive_oob(pg, msg.first, msg.second, p);
              
              // delete j from nomessage(j)
              if (get(color, p.second) != Color::black())
                local_put(color, p.second, Color::gray());

              recover(p);
            }
            break;
            
          case return_msg:
            {
              vertex_pair p;
              receive_oob(pg, msg.first, msg.second, p);
              
              // delete j from nomessage(i)
              local_put(color, p.second, Color::black());

              shift_center_of_activity(p.first);
            }
            break;
            
          case done_msg:
            {
              receive_oob(pg, msg.first, msg.second, done);

              // Propagate done message downward in tree
              done = true;
              process_id_type id = process_id(pg);
              process_id_type left = 2*id + 1;
              process_id_type right = left + 1;
              if (left < num_processes(pg))
                send_oob(pg, left, done_msg, done);
              if (right < num_processes(pg))
                send_oob(pg, right, done_msg, done);
            }
            break;

          default:
            BOOST_ASSERT(false);
          }
        }
      }
      
    private:
      bool recover(const vertex_pair& p)
      {
        if (get(explore, p.first) == p.second) {
          return shift_center_of_activity(p.first);
        }
        else
          return false;
      }
      
      bool shift_center_of_activity(vertex_descriptor i)
      {
        for (out_edge_iterator ei = next_out_edge[get(index_map, i)],
                               ei_end = out_edges(i, g).second;
             ei != ei_end; ++ei) {
          vis.examine_edge(*ei, g);

          vertex_descriptor k = target(*ei, g);
          color_type target_color = get(color, k);
          if (target_color == Color::black()) vis.forward_or_cross_edge(*ei, g);
          else if (target_color == Color::gray()) vis.back_edge(*ei, g);
          else {
            put(explore, i, k);
            vis.tree_edge(*ei, g);
            vertex_pair p(k, i);
            send_oob(pg, get(owner, k), discover_msg, p);
            next_out_edge[get(index_map, i)] = ++ei;
            return false;
          } 
        }

        next_out_edge[get(index_map, i)] = out_edges(i, g).second;
        put(explore, i, i);
        put(color, i, Color::black());
        vis.finish_vertex(i, g);
          
        if (get(parent, i) == i) {
          send_oob(pg, 0, done_msg, true);
          return true;
        }
        else {
          vertex_pair ret(get(parent, i), i);
          send_oob(pg, get(owner, ret.first), return_msg, ret);
        }
        return false;
      }

      const DistributedGraph& g; 
      ColorMap color;
      ParentMap parent; 
      ExploreMap explore;
      VertexIndexMap index_map;
      DFSVisitor vis;
      process_group_type pg;
      typename property_map<DistributedGraph, vertex_owner_t>::const_type owner;
      std::vector<out_edge_iterator> next_out_edge; 
    };
  } // end namespace detail

  template<typename DistributedGraph, typename ColorMap, typename ParentMap,
           typename ExploreMap, typename VertexIndexMap, typename DFSVisitor>
  void
  tsin_depth_first_visit
    (const DistributedGraph& g,
     typename graph_traits<DistributedGraph>::vertex_descriptor s,
     DFSVisitor vis, ColorMap color, ParentMap parent, ExploreMap explore, 
     VertexIndexMap index_map)
  {
    typedef typename graph_traits<DistributedGraph>::directed_category
      directed_category;
    BOOST_STATIC_ASSERT(
      (is_convertible<directed_category, undirected_tag>::value));

    set_property_map_role(vertex_color, color);
    graph::distributed::detail::parallel_dfs
      <DistributedGraph, ColorMap, ParentMap, ExploreMap, VertexIndexMap, 
       DFSVisitor> do_dfs(g, color, parent, explore, index_map, vis);
    do_dfs.run(s);

    using boost::graph::parallel::process_group;
    synchronize(process_group(g));
  }
    
  template<typename DistributedGraph, typename DFSVisitor, 
           typename VertexIndexMap>
  void
  tsin_depth_first_visit
    (const DistributedGraph& g,
     typename graph_traits<DistributedGraph>::vertex_descriptor s,
     DFSVisitor vis,
     VertexIndexMap index_map)
  {
    typedef typename graph_traits<DistributedGraph>::vertex_descriptor
      vertex_descriptor;

    std::vector<default_color_type> colors(num_vertices(g));
    std::vector<vertex_descriptor> parent(num_vertices(g));
    std::vector<vertex_descriptor> explore(num_vertices(g));
    tsin_depth_first_visit
      (g, s,
       vis,
       make_iterator_property_map(colors.begin(), index_map),
       make_iterator_property_map(parent.begin(), index_map),
       make_iterator_property_map(explore.begin(), index_map),
       index_map);
  }

  template<typename DistributedGraph, typename DFSVisitor, 
           typename VertexIndexMap>
  void
  tsin_depth_first_visit
    (const DistributedGraph& g,
     typename graph_traits<DistributedGraph>::vertex_descriptor s,
     DFSVisitor vis)
  {
    tsin_depth_first_visit(g, s, vis, get(vertex_index, g));
  }
} // end namespace distributed

using distributed::tsin_depth_first_visit;

} // end namespace graph

template<typename DistributedGraph, typename DFSVisitor>
void
depth_first_visit
  (const DistributedGraph& g,
   typename graph_traits<DistributedGraph>::vertex_descriptor s,
   DFSVisitor vis)
{
  graph::tsin_depth_first_visit(g, s, vis, get(vertex_index, g));
}

} // end namespace boost

#endif // BOOST_GRAPH_DISTRIBUTED_DFS_HPP