boyer_myrvold_impl.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

//=======================================================================
// Copyright (c) Aaron Windsor 2007
//
// Distributed under 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)
//=======================================================================
#ifndef __BOYER_MYRVOLD_IMPL_HPP__
#define __BOYER_MYRVOLD_IMPL_HPP__

#include <vector>
#include <list>
#include <boost/utility.hpp>   //for boost::next
#include <boost/config.hpp>    //for std::min macros
#include <boost/shared_ptr.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/depth_first_search.hpp>
#include <boost/graph/planar_detail/face_handles.hpp>
#include <boost/graph/planar_detail/face_iterators.hpp>
#include <boost/graph/planar_detail/bucket_sort.hpp>



namespace boost
{

  template<typename LowPointMap, typename DFSParentMap,
           typename DFSNumberMap, typename LeastAncestorMap,
           typename DFSParentEdgeMap, typename SizeType>
  struct planar_dfs_visitor : public dfs_visitor<>
  {
    planar_dfs_visitor(LowPointMap lpm, DFSParentMap dfs_p, 
                       DFSNumberMap dfs_n, LeastAncestorMap lam,
                       DFSParentEdgeMap dfs_edge) 
      : low(lpm),
        parent(dfs_p),
        df_number(dfs_n),
        least_ancestor(lam),
        df_edge(dfs_edge),
        count(0) 
    {}
    
    
    template <typename Vertex, typename Graph>
    void start_vertex(const Vertex& u, Graph&)
    {
      put(parent, u, u);
      put(least_ancestor, u, count);
    }
    
    
    template <typename Vertex, typename Graph>
    void discover_vertex(const Vertex& u, Graph&)
    {
      put(low, u, count);
      put(df_number, u, count);
      ++count;
    }
    
    template <typename Edge, typename Graph>
    void tree_edge(const Edge& e, Graph& g)
    {
      typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
      vertex_t s(source(e,g));
      vertex_t t(target(e,g));

      put(parent, t, s);
      put(df_edge, t, e);
      put(least_ancestor, t, get(df_number, s));
    }
    
    template <typename Edge, typename Graph>
    void back_edge(const Edge& e, Graph& g)
    {
      typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
      typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
      
      vertex_t s(source(e,g));
      vertex_t t(target(e,g));
      BOOST_USING_STD_MIN();

      if ( t != get(parent, s) ) {
        v_size_t s_low_df_number = get(low, s);
        v_size_t t_df_number = get(df_number, t);
        v_size_t s_least_ancestor_df_number = get(least_ancestor, s);

        put(low, s, 
            min BOOST_PREVENT_MACRO_SUBSTITUTION(s_low_df_number,
                                                 t_df_number)
            );
        
        put(least_ancestor, s, 
            min BOOST_PREVENT_MACRO_SUBSTITUTION(s_least_ancestor_df_number, 
                                                 t_df_number
                                                 )
            );

      }
    }
    
    template <typename Vertex, typename Graph>
    void finish_vertex(const Vertex& u, Graph& g)
    {
      typedef typename graph_traits<Graph>::vertices_size_type v_size_t;

      Vertex u_parent = get(parent, u);
      v_size_t u_parent_lowpoint = get(low, u_parent);
      v_size_t u_lowpoint = get(low, u);
      BOOST_USING_STD_MIN();

      if (u_parent != u)
        {
          put(low, u_parent, 
              min BOOST_PREVENT_MACRO_SUBSTITUTION(u_lowpoint, 
                                                   u_parent_lowpoint
                                                   )
              );
        }
    }
    
    LowPointMap low;
    DFSParentMap parent;
    DFSNumberMap df_number;
    LeastAncestorMap least_ancestor;
    DFSParentEdgeMap df_edge;
    SizeType count;
    
  };






  template <typename Graph,
            typename VertexIndexMap,
            typename StoreOldHandlesPolicy = graph::detail::store_old_handles,
            typename StoreEmbeddingPolicy = graph::detail::recursive_lazy_list
            >
  class boyer_myrvold_impl
  {

    typedef typename graph_traits<Graph>::vertices_size_type v_size_t;
    typedef typename graph_traits<Graph>::vertex_descriptor vertex_t;
    typedef typename graph_traits<Graph>::edge_descriptor edge_t;
    typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator_t;
    typedef typename graph_traits<Graph>::edge_iterator edge_iterator_t;
    typedef typename graph_traits<Graph>::out_edge_iterator 
        out_edge_iterator_t;
    typedef graph::detail::face_handle
        <Graph, StoreOldHandlesPolicy, StoreEmbeddingPolicy> face_handle_t;
    typedef std::vector<vertex_t> vertex_vector_t;
    typedef std::vector<edge_t> edge_vector_t;
    typedef std::list<vertex_t> vertex_list_t;
    typedef std::list< face_handle_t > face_handle_list_t;
    typedef boost::shared_ptr< face_handle_list_t > face_handle_list_ptr_t;
    typedef boost::shared_ptr< vertex_list_t > vertex_list_ptr_t;
    typedef boost::tuple<vertex_t, bool, bool> merge_stack_frame_t;
    typedef std::vector<merge_stack_frame_t> merge_stack_t;

    template <typename T>
    struct map_vertex_to_
    {
      typedef iterator_property_map
          <typename std::vector<T>::iterator, VertexIndexMap> type;
    };

    typedef typename map_vertex_to_<v_size_t>::type vertex_to_v_size_map_t;
    typedef typename map_vertex_to_<vertex_t>::type vertex_to_vertex_map_t;
    typedef typename map_vertex_to_<edge_t>::type vertex_to_edge_map_t;
    typedef typename map_vertex_to_<vertex_list_ptr_t>::type 
        vertex_to_vertex_list_ptr_map_t;
    typedef typename map_vertex_to_< edge_vector_t >::type 
        vertex_to_edge_vector_map_t;
    typedef typename map_vertex_to_<bool>::type vertex_to_bool_map_t;
    typedef typename map_vertex_to_<face_handle_t>::type 
        vertex_to_face_handle_map_t;
    typedef typename map_vertex_to_<face_handle_list_ptr_t>::type 
        vertex_to_face_handle_list_ptr_map_t;
    typedef typename map_vertex_to_<typename vertex_list_t::iterator>::type 
        vertex_to_separated_node_map_t;

    template <typename BicompSideToTraverse = single_side,
              typename VisitorType = lead_visitor,
              typename Time = current_iteration>
    struct face_vertex_iterator
    {
      typedef face_iterator<Graph, 
                            vertex_to_face_handle_map_t, 
                            vertex_t, 
                            BicompSideToTraverse, 
                            VisitorType,
                            Time>
      type;
    };

    template <typename BicompSideToTraverse = single_side,
              typename Time = current_iteration>
    struct face_edge_iterator
    {
      typedef face_iterator<Graph,
                            vertex_to_face_handle_map_t,
                            edge_t,
                            BicompSideToTraverse,
                            lead_visitor,
                            Time>
      type;
    };



  public:

 

    boyer_myrvold_impl(const Graph& arg_g, VertexIndexMap arg_vm):
      g(arg_g),
      vm(arg_vm),

      low_point_vector(num_vertices(g)),
      dfs_parent_vector(num_vertices(g)),
      dfs_number_vector(num_vertices(g)),
      least_ancestor_vector(num_vertices(g)),
      pertinent_roots_vector(num_vertices(g)),
      backedge_flag_vector(num_vertices(g), num_vertices(g) + 1),
      visited_vector(num_vertices(g), num_vertices(g) + 1),
      face_handles_vector(num_vertices(g)),
      dfs_child_handles_vector(num_vertices(g)),
      separated_dfs_child_list_vector(num_vertices(g)),
      separated_node_in_parent_list_vector(num_vertices(g)),
      canonical_dfs_child_vector(num_vertices(g)),
      flipped_vector(num_vertices(g), false),
      backedges_vector(num_vertices(g)),
      dfs_parent_edge_vector(num_vertices(g)),
                        
      vertices_by_dfs_num(num_vertices(g)),

      low_point(low_point_vector.begin(), vm),
      dfs_parent(dfs_parent_vector.begin(), vm),
      dfs_number(dfs_number_vector.begin(), vm),
      least_ancestor(least_ancestor_vector.begin(), vm),
      pertinent_roots(pertinent_roots_vector.begin(), vm),
      backedge_flag(backedge_flag_vector.begin(), vm),
      visited(visited_vector.begin(), vm),
      face_handles(face_handles_vector.begin(), vm),
      dfs_child_handles(dfs_child_handles_vector.begin(), vm),
      separated_dfs_child_list(separated_dfs_child_list_vector.begin(), vm),
      separated_node_in_parent_list
          (separated_node_in_parent_list_vector.begin(), vm),
      canonical_dfs_child(canonical_dfs_child_vector.begin(), vm),
      flipped(flipped_vector.begin(), vm),
      backedges(backedges_vector.begin(), vm),
      dfs_parent_edge(dfs_parent_edge_vector.begin(), vm)

    {

      planar_dfs_visitor
        <vertex_to_v_size_map_t, vertex_to_vertex_map_t,
        vertex_to_v_size_map_t, vertex_to_v_size_map_t,
        vertex_to_edge_map_t, v_size_t> vis
        (low_point, dfs_parent, dfs_number, least_ancestor, dfs_parent_edge);

      // Perform a depth-first search to find each vertex's low point, least
      // ancestor, and dfs tree information
      depth_first_search(g, visitor(vis).vertex_index_map(vm));

      // Sort vertices by their lowpoint - need this later in the constructor
      vertex_vector_t vertices_by_lowpoint(num_vertices(g));
      std::copy( vertices(g).first, vertices(g).second, 
                 vertices_by_lowpoint.begin()
                 );
      bucket_sort(vertices_by_lowpoint.begin(), 
                  vertices_by_lowpoint.end(), 
                  low_point,
                  num_vertices(g)
                  );

      // Sort vertices by their dfs number - need this to iterate by reverse 
      // DFS number in the main loop.
      std::copy( vertices(g).first, vertices(g).second, 
                 vertices_by_dfs_num.begin()
                 );
      bucket_sort(vertices_by_dfs_num.begin(), 
                  vertices_by_dfs_num.end(), 
                  dfs_number,
                  num_vertices(g)
                  );

      // Initialize face handles. A face handle is an abstraction that serves 
      // two uses in our implementation - it allows us to efficiently move 
      // along the outer face of embedded bicomps in a partially embedded 
      // graph, and it provides storage for the planar embedding. Face 
      // handles are implemented by a sequence of edges and are associated 
      // with a particular vertex - the sequence of edges represents the 
      // current embedding of edges around that vertex, and the first and 
      // last edges in the sequence represent the pair of edges on the outer 
      // face that are adjacent to the associated vertex. This lets us embed 
      // edges in the graph by just pushing them on the front or back of the 
      // sequence of edges held by the face handles.
      // 
      // Our algorithm starts with a DFS tree of edges (where every vertex is
      // an articulation point and every edge is a singleton bicomp) and 
      // repeatedly merges bicomps by embedding additional edges. Note that 
      // any bicomp at any point in the algorithm can be associated with a 
      // unique edge connecting the vertex of that bicomp with the lowest DFS
      // number (which we refer to as the "root" of the bicomp) with its DFS 
      // child in the bicomp: the existence of two such edges would contradict
      // the properties of a DFS tree. We refer to the DFS child of the root 
      // of a bicomp as the "canonical DFS child" of the bicomp. Note that a 
      // vertex can be the root of more than one bicomp.
      //
      // We move around the external faces of a bicomp using a few property 
      // maps, which we'll initialize presently:
      //
      // - face_handles: maps a vertex to a face handle that can be used to 
      //   move "up" a bicomp. For a vertex that isn't an articulation point, 
      //   this holds the face handles that can be used to move around that 
      //   vertex's unique bicomp. For a vertex that is an articulation point,
      //   this holds the face handles associated with the unique bicomp that 
      //   the vertex is NOT the root of. These handles can therefore be used 
      //   to move from any point on the outer face of the tree of bicomps 
      //   around the current outer face towards the root of the DFS tree.
      //
      // - dfs_child_handles: these are used to hold face handles for 
      //   vertices that are articulation points - dfs_child_handles[v] holds
      //   the face handles corresponding to vertex u in the bicomp with root
      //   u and canonical DFS child v.
      //
      // - canonical_dfs_child: this property map allows one to determine the
      //   canonical DFS child of a bicomp while traversing the outer face.
      //   This property map is only valid when applied to one of the two 
      //   vertices adjacent to the root of the bicomp on the outer face. To
      //   be more precise, if v is the canonical DFS child of a bicomp,
      //   canonical_dfs_child[dfs_child_handles[v].first_vertex()] == v and 
      //   canonical_dfs_child[dfs_child_handles[v].second_vertex()] == v.
      //
      // - pertinent_roots: given a vertex v, pertinent_roots[v] contains a
      //   list of face handles pointing to the top of bicomps that need to
      //   be visited by the current walkdown traversal (since they lead to
      //   backedges that need to be embedded). These lists are populated by
      //   the walkup and consumed by the walkdown.

      vertex_iterator_t vi, vi_end;
      for(tie(vi,vi_end) = vertices(g); vi != vi_end; ++vi)
        {
          vertex_t v(*vi);
          vertex_t parent = dfs_parent[v];

          if (parent != v)
            {
              edge_t parent_edge = dfs_parent_edge[v];
              add_to_embedded_edges(parent_edge, StoreOldHandlesPolicy());
              face_handles[v] = face_handle_t(v, parent_edge, g);
              dfs_child_handles[v] = face_handle_t(parent, parent_edge, g);
            }