remove_cross_edges.hpp

Go to the documentation of this file.

#ifndef MSMAZES_CORE_GRAPH_REMOVE_CROSS_EDGES_HPP
#define MSMAZES_CORE_GRAPH_REMOVE_CROSS_EDGES_HPP

// std::vector
#include <vector>
// std::map
#include <map>
// std::pair and std::make_pair
#include <utility>
// boost::function_requires and basic concept check templates
#include <boost/concept_check.hpp>
// boost::queue
#include <boost/pending/queue.hpp>
// boost::property_map, boost::associative_property_map,
// boost::make_iterator_property_map, boost::get, and boost::put
#include <boost/property_map.hpp>
// boost::ref
#include <boost/ref.hpp>
// boost::tie
#include <boost/utility.hpp>
// BOOST_PP_LESS
#include <boost/preprocessor/comparison/less.hpp>
// boost::remove_const
#include <boost/type_traits/remove_const.hpp>
// boost::remove_reference
#include <boost/type_traits/remove_reference.hpp>
// BGL concept check templates
#include <boost/graph/graph_concepts.hpp>
// boost::graph_traits
#include <boost/graph/graph_traits.hpp>
// boost::color_traits
#include <boost/graph/properties.hpp>
// boost::predecessor_recorder and boost::null_visitor
#include <boost/graph/visitors.hpp>
// boost::breadth_first_visit and boost::make_bfs_visitor
#include <boost/graph/breadth_first_search.hpp>
// boost::dfs_visitor, boost::depth_first_visit, and boost::make_dfs_visitor
#include <boost/graph/depth_first_search.hpp>
//#include <boost/graph/adjacency_list.hpp> must be included before this file.
// msmazes::hasInEdges and msmazes::removeInEdges
#include <msmazes/core/graph/in_edges.hpp>
// Boost.Parameter keyword objects used by the Core Graph algorithms
#include <msmazes/core/graph/keywords.hpp>

#if BOOST_PP_LESS(BOOST_PARAMETER_MAX_ARITY, 9)
#error Set BOOST_PARAMETER_MAX_ARITY to 9 or higher, please.
#endif

namespace msmazes {

class DefaultCrossEdgeRemovalIntruder
{
 public:
    template <
        typename Graph
    >
    void
        pathEdgeTemporarilyRemoved(
            typename boost::graph_traits<Graph>::vertex_descriptor u
          , typename boost::graph_traits<Graph>::vertex_descriptor v
          , Graph& g
        )
    {
    }

    template <
        typename Graph
    >
    inline bool
        canRemoveCrossEdge(
            typename boost::graph_traits<Graph>::edge_descriptor e
          , Graph& g
        )
    {
        return true;
    }

    template <
        typename Graph
    >
    void
        pathEdgeReinstated(
            typename boost::graph_traits<Graph>::edge_descriptor e
          , Graph& g
        )
    {
    }
};

  namespace _removeCrossEdges {

    /*
     * This event visitor class template helps the AltPathRanker class template
     * by ranking the vertices that the latter class has classified as cycles.
     */
    template <typename VertexRankMap>
    class CycleRanker
      : public boost::base_visitor<CycleRanker<VertexRankMap> >
    {
     public:
        typedef boost::on_tree_edge
                event_filter;
        typedef typename boost::property_traits<VertexRankMap>::value_type
                Rank;

     private:
        VertexRankMap _rank_map;

     public:
        explicit CycleRanker(VertexRankMap rank_map)
          : _rank_map(rank_map)
        {
        }

        CycleRanker(const CycleRanker& copy)
          : _rank_map(copy._rank_map)
        {
        }

        ~CycleRanker()
        {
        }

        template <
            typename Graph
        >
        void
            operator()(
                typename boost::graph_traits<Graph>::edge_descriptor e
              , Graph& g
            )
        {
            boost::put(
                _rank_map
              , boost::target(e, g)
              , boost::get(_rank_map, boost::source(e, g))
            );
        }
    };

    /*
     * This event visitor class template carries out the actual removal of
     * cross-edges (with respect to the main path in the graph, not the
     * depth-first traversal that is passed an instance of this class).
     */
    template <
        typename InputGraph
      , typename VertexIndexMap
      , typename VertexRankMap
      , typename CrossEdgeRemovalIntruder
    >
    class CrossEdgeRemover
      : public boost::base_visitor<
                   CrossEdgeRemover<
                       InputGraph
                     , VertexIndexMap
                     , VertexRankMap
                     , CrossEdgeRemovalIntruder
                   >
               >
    {
     public:
        typedef boost::on_discover_vertex
                event_filter;
        typedef typename boost::property_traits<VertexRankMap>::value_type
                Rank;

     private:
        const Rank&               _root_rank;

        CrossEdgeRemovalIntruder& _intruder;
        InputGraph&               _g;
        VertexIndexMap            _index_map;
        VertexRankMap             _rank_map;

     public:
        CrossEdgeRemover(
            InputGraph& g
          , VertexIndexMap index_map
          , VertexRankMap rank_map
          , Rank& root_rank
          , CrossEdgeRemovalIntruder& intruder
        )
          : _root_rank(root_rank)
          , _intruder(intruder)
          , _g(g)
          , _index_map(index_map)
          , _rank_map(rank_map)
        {
        }

        CrossEdgeRemover(const CrossEdgeRemover& copy)
          : _root_rank(copy._root_rank)
          , _intruder(copy._intruder)
          , _g(copy._g)
          , _index_map(copy._index_map)
          , _rank_map(copy._rank_map)
        {
        }

        ~CrossEdgeRemover()
        {
        }

        template <
            typename Graph
        >
        void
            operator()(
                typename boost::graph_traits<Graph>::vertex_descriptor v
              , Graph& g
            )
        {
            typename boost::graph_traits<InputGraph>::vertex_descriptor
                vertex = boost::vertex(boost::get(_index_map, v), _g);
            typename boost::graph_traits<InputGraph>::out_edge_iterator
                oi, oend;

            boost::tie(oi, oend) = boost::out_edges(vertex, _g);

            while (oi != oend)
            {
                if (
                    (_root_rank < boost::get(_rank_map, boost::target(*oi, _g)))
                 && _intruder.canRemoveCrossEdge(*oi, _g)
                )
                {
                    /*
                     * This vertex is connected to a vertex that is farther
                     * down the main path than the source vertex of this
                     * traversal (the vertex whose rank is root_rank).
                     * Therefore, this edge is a cross edge.
                     */
                    boost::remove_edge(oi, _g);
                    boost::tie(oi, oend) = boost::out_edges(vertex, _g);
                }
                else
                {
                    ++oi;
                }
            }
        }
    };

    /*
     * This event visitor class template ranks the vertices that are not part of
     * the main path so that the CrossEdgeRemover class template can identify
     * which edges to remove.
     */
    template <
        typename VertexRankMap
      , typename VertexColorMap
    >
    class AltPathRanker
      : public boost::base_visitor<AltPathRanker<VertexRankMap,VertexColorMap> >
    {
     public:
        typedef boost::on_finish_vertex
                event_filter;
        typedef typename boost::property_traits<VertexColorMap>::value_type
                ColorValue;
        typedef boost::color_traits<ColorValue>
                Color;
        typedef typename boost::property_traits<VertexRankMap>::value_type
                Rank;
        typedef boost::dfs_visitor<
                    std::pair<CycleRanker<VertexRankMap>,boost::null_visitor>
                >
                CycleVisitor;

     private:
        static const Rank zero_rank = Rank();

        VertexRankMap  _rank_map;
        VertexColorMap _color_map;
        CycleVisitor   _cycle_visitor;

     public:
        AltPathRanker(VertexRankMap rank_map, VertexColorMap color_map)
          : _rank_map(rank_map)
          , _color_map(color_map)
          , _cycle_visitor(
                boost::make_dfs_visitor(
                    std::make_pair(
                        CycleRanker<VertexRankMap>(rank_map)
                      , boost::null_visitor()
                    )
                )
            )
        {
        }

        AltPathRanker(const AltPathRanker& copy)
          : _rank_map(copy._rank_map)
          , _color_map(copy._color_map)
          , _cycle_visitor(copy._cycle_visitor)
        {
        }

        ~AltPathRanker()
        {
        }

        template <typename Graph>
        void
            operator()(
                typename boost::graph_traits<Graph>::vertex_descriptor v
              , Graph& g
            )
        {
            typename boost::graph_traits<Graph>::adjacency_iterator vi, vend;
            bool has_cycles = false;
            Rank target_rank;

            for (boost::tie(vi, vend) = boost::adjacent_vertices(v, g);
                 vi != vend;
                 ++vi)
            {
                target_rank = boost::get(_rank_map, *vi);

                if (target_rank == zero_rank)
                {
                    /*
                     * The out-edge leads to a cycle.
                     */
                    has_cycles = true;
                }
                else if (
                   (boost::get(_color_map, *vi) != Color::gray())
                && (boost::get(_rank_map, v) < target_rank)
                )
                {
                    /*
                     * This vertex is connected to a vertex with a higher rank
                     * than zero (i.e. the first one so far) or a vertex farther
                     * down the main path than the one with the current rank but
                     * still is a predecessor to the source vertex of this
                     * traversal.
                     */
                    boost::put(_rank_map, v, target_rank);
                }
            }

            if (boost::get(_rank_map, v) == zero_rank)
            {
                /*
                 * Set the main depth-first traversal function to revisit this
                 * vertex once it has a non-zero rank.
                 */
                boost::put(_color_map, v, Color::white());
            }
            else if (has_cycles)
            {
                /*
                 * Give the zero-ranked vertices in the cycle(s) the same rank
                 * as that of this vertex.
                 */
                boost::depth_first_visit(g, v, _cycle_visitor, _color_map);
            }
        }
    };

    /*
     * The implementation.
     */
    template <
        typename PathIterator
      , typename InputGraph
      , typename PredecessorMap
      , typename VertexIndexMap
      , typename VertexColorMap
      , typename VertexRankMap
      , typename Buffer
      , typename CrossEdgeRemovalIntruder
    >
    void
        impl(
            PathIterator path_begin
          , PathIterator path_end
          , InputGraph& g
          , PredecessorMap predecessor_map
          , VertexIndexMap index_map
          , VertexColorMap color_map
          , VertexRankMap rank_map
          , Buffer& Q
          , CrossEdgeRemovalIntruder& intruder
        )
    {
        boost::function_requires<
            boost::BidirectionalIteratorConcept<PathIterator>
        >();
        boost::function_requires<
            boost::VertexListGraphConcept<InputGraph>
        >();
        boost::function_requires<
            boost::AdjacencyGraphConcept<InputGraph>
        >();
        boost::function_requires<
            boost::EdgeMutableGraphConcept<InputGraph>
        >();
        typedef boost::graph_traits<InputGraph>
                GraphTraits;
        boost::function_requires<
            boost::ConvertibleConcept<
                typename GraphTraits::directed_category
              , boost::directed_tag
            >
        >();
        typedef typename GraphTraits::edge_descriptor
                Edge;
        typedef typename GraphTraits::vertex_descriptor
                Vertex;
        boost::function_requires<
            boost::ReadWritePropertyMapConcept<PredecessorMap,Vertex>
        >();
        boost::function_requires<
            boost::ReadablePropertyMapConcept<VertexIndexMap,Vertex>
        >();
        boost::function_requires<
            boost::ReadWritePropertyMapConcept<VertexColorMap,Vertex>
        >();
        boost::function_requires<
            boost::ReadWritePropertyMapConcept<VertexRankMap,Vertex>
        >();
/*
        boost::function_requires<
            boost::BufferConcept<Buffer>
        >();
*/
        boost::function_requires<
            boost::ConvertibleConcept<typename Buffer::value_type,Vertex>
        >();
        typedef typename GraphTraits::vertex_iterator
                VertexIterator;
        typedef typename boost::property_traits<VertexRankMap>::value_type
                Rank;
        typedef typename boost::property_traits<VertexColorMap>::value_type
                ColorValue;
        typedef boost::color_traits<ColorValue>
                Color;
        typedef boost::predecessor_recorder<PredecessorMap,boost::on_tree_edge>
                PredVisitor;
        typedef boost::bfs_visitor<std::pair<PredVisitor,boost::null_visitor> >
                BFSVisitor;
        typedef CrossEdgeRemover<
                    InputGraph
                  , VertexIndexMap
                  , VertexRankMap
                  , CrossEdgeRemovalIntruder
                >
                CERVisitor;
        typedef AltPathRanker<VertexRankMap,VertexColorMap>
                APRVisitor;
        typedef boost::dfs_visitor<std::pair<CERVisitor,APRVisitor> >
                DFSVisitor;

        /*
         * The purpose of all the preparatory steps from here to the core
         * algorithm is to keep as many nontrivial complex paths (the ones that
         * don't contain the simple path or almost all of it unbroken) as
         * possible in the graph.
         *
         * Temporarily remove the main path from the graph so that the algorithm
         * does not mistake its edges for cross edges.
         */
        PathIterator path_i = path_begin;
        PathIterator path_j = path_i;

        while (++path_j != path_end)
        {
            boost::remove_edge(*path_i, *path_j, g);
            intruder.pathEdgeTemporarilyRemoved(*path_i, *path_j, g);
            path_i = path_j;
        }

        /*
         * Remove all in-edges from the path target.  Also remove all out-edges
         * from the path source.
         */
        boost::clear_out_edges(*path_begin, g);
        removeInEdges(*path_i, g);

        /*
         * Remove all in-edges from vertices between the farthest vertex down
         * the path with a non-zero in-degree (inclusive) and its most immediate
         * path predecessor with a non-zero out-degree (exclusive).
         */
        path_j = path_i;
        boost::clear_out_edges(*(--path_j), g);

        while ((path_j != path_begin) && !hasInEdges(*path_j, g))
        {
            --path_j;
        }

        while ((path_j != path_begin) && (boost::out_degree(*path_j, g) == 0))
        {
            removeInEdges(*path_j, g);
            --path_j;
        }

        boost::null_visitor
          vis_n;
        PredVisitor
          vis0(predecessor_map);
        BFSVisitor
          bfs_vis = boost::make_bfs_visitor(std::make_pair(vis0, vis_n));

        /*
         * Find the unweighted shortest paths using the path target as the
         * source.
         */
        boost::breadth_first_visit(g, *path_i, Q, bfs_vis, color_map);

        /*
         * Initialize all vertices in the graph to the "zero" rank and the
         * "unvisited" color.  Do this here, not in a visitor class definition.
         */
        const Rank zero_rank = Rank();

        VertexIterator v_i, v_end;

        for (boost::tie(v_i, v_end) = boost::vertices(g); v_i != v_end; ++v_i)
        {
            boost::put(color_map, *v_i, Color::white());
            boost::put(rank_map, *v_i, zero_rank);
        }

        /*
         * Assign ranks to all vertices in the main path, with the source vertex
         * having the highest rank and the target vertex having the lowest rank
         * higher than the "zero" rank.
         */
        Rank root_rank = zero_rank;

        for (path_j = path_begin; path_j != path_end; ++path_j)
        {
            boost::put(rank_map, *path_j, ++root_rank);
        }

        /*
         * In each "alternate path" resulting from the previous shortest-paths
         * call, assign all zero-ranked vertices the same rank as that path's
         * target.  If at least two alternate paths share one or more vertices,
         * these vertices get the same rank as that of the highest ranking
         * target of the alternate paths.
         */
        Vertex target_v;

        path_j = path_i;

        while (path_j != path_begin)
        {
            target_v = boost::get(predecessor_map, *(--path_j));

            if (target_v != *path_j)
            {
                /*
                 * Only use the ranks of the alternate path targets that are
                 * actually reachable from the main path target.
                 */
                for (
                    root_rank = boost::get(rank_map, *path_j);
                    boost::get(rank_map, target_v) == zero_rank;
                    target_v = boost::get(predecessor_map, target_v)
                )
                {
                    boost::put(color_map, target_v, Color::black());
                    boost::put(rank_map, target_v, root_rank);
                }
            }
        }

        /*
         * Run the core algorithm on each vertex in the main path, starting with
         * the main path target.
         */
        CERVisitor
          vis1(g, index_map, rank_map, root_rank, intruder);
        APRVisitor
          vis2(rank_map, color_map);
        DFSVisitor
          dfs_vis = boost::make_dfs_visitor(std::make_pair(vis1, vis2));

        path_j = path_i;

        while (--path_j != path_begin)
        {
            if (boost::out_degree(*path_j, g) > 0)
            {
                root_rank = boost::get(rank_map, *path_j);

                /*
                 * Set the path vertices as terminating vertices for the
                 * depth-first traversal.
                 */
                for (path_i = path_begin; path_i != path_end; ++path_i)
                {
                    boost::put(color_map, *path_i, Color::black());
                }

                boost::depth_first_visit(g, *path_j, dfs_vis, color_map);

                /*
                 * Reset the color map after each visit.
                 */
                for (
                    boost::tie(v_i, v_end) = boost::vertices(g);
                    v_i != v_end;
                    ++v_i
                )
                {
                    boost::put(color_map, *v_i, Color::white());
                }
            }
        }

        /*
         * Put the main path back in the graph.
         */
        Edge e;
        bool has_added_edge;

        for (path_i = path_j; ++path_j != path_end; path_i = path_j)
        {
            boost::tie(e, has_added_edge)
              = boost::add_edge(*path_i, *path_j, g);

            if (has_added_edge)
            {
                intruder.pathEdgeReinstated(e, g);
            }
        }

        target_v = *path_i;

        /*
         * Remove all edges that lead to dead ends (except for the destination).
         */
        bool has_dead_ends = true;

        while (has_dead_ends)
        {
            has_dead_ends = false;

            for (
                boost::tie(v_i, v_end) = boost::vertices(g);
                v_i != v_end;
                ++v_i
            )
            {
                if (
                    (*v_i != target_v)
                 && (boost::out_degree(*v_i, g) == 0)
                 && hasInEdges(*v_i, g)
                )
                {
                    removeInEdges(*v_i, g);
                    has_dead_ends = true;
                }
            }
        }
    }

    struct parameters
      : boost::parameter::parameters<
            boost::parameter::required<keyword_tag::path_begin_arg>
          , boost::parameter::required<keyword_tag::path_end_arg>
          , boost::parameter::required<keyword_tag::input_graph_arg>
          , boost::parameter::optional<keyword_tag::util_predecessor_map_arg>
          , boost::parameter::optional<keyword_tag::util_index_map_arg>
          , boost::parameter::optional<keyword_tag::util_color_map_arg>
          , boost::parameter::optional<keyword_tag::util_rank_map_arg>
          , boost::parameter::optional<keyword_tag::util_buffer_arg>
          , boost::parameter::optional<keyword_tag::intruder_arg>
        >
    {
    };
  }  // namespace _removeCrossEdges

#ifdef MSMAZES_DOX

template <
    typename PathIterator
  , typename InputGraph
  , typename PredecessorMap
  , typename VertexIndexMap
  , typename VertexColorMap
  , typename VertexRankMap
  , typename Buffer
  , typename CrossEdgeRemovalIntruder
>
void
    removeCrossEdges(
        PathIterator path_begin
      , PathIterator path_end
      , InputGraph& g
      , PredecessorMap predecessor_map
      , VertexIndexMap index_map
      , VertexColorMap color_map
      , VertexRankMap rank_map
      , Buffer& Q
      , CrossEdgeRemovalIntruder& intruder
    );

template <typename Params>
void removeCrossEdges_with_named_params(Params& p)
#else
BOOST_PARAMETER_FUN(
    void
  , removeCrossEdges
  , 3
  , 9
  , _removeCrossEdges::parameters
)
#endif  /* MSMAZES_DOX */
{
    typedef typename boost::remove_const<
                typename boost::remove_reference<
                    typename boost::parameter::binding<
                        Params
                      , keyword_tag::input_graph_arg
                    >::type
                >::type
            >::type
            InputGraph;
    typedef typename boost::graph_traits<InputGraph>::vertex_descriptor
            Vertex;
    typedef std::map<Vertex,Vertex>
            VertexMap;
    typedef boost::associative_property_map<VertexMap>
            PredecessorMap;
    typedef typename boost::remove_const<
                typename boost::remove_reference<
                    typename boost::parameter::binding<
                        Params
                      , keyword_tag::util_index_map_arg
                      , typename boost::property_map<
                            InputGraph
                          , boost::vertex_index_t
                        >::type
                    >::type
                >::type
            >::type
            VertexIndexMap;
    typedef typename boost::property_traits<VertexIndexMap>::value_type
            Rank;

    InputGraph& g
      = p[input_graph_arg];
    VertexIndexMap index_map
      = p[util_index_map_arg | boost::get(boost::vertex_index_t(), g)];
    VertexMap v_map;
    PredecessorMap pred_map(v_map);
    boost::queue<Vertex> Q;
    DefaultCrossEdgeRemovalIntruder intruder;

    _removeCrossEdges::impl(
        p[path_begin_arg]
      , p[path_end_arg]
      , g
      , p[util_predecessor_map_arg | pred_map]
      , index_map
      , p[
            util_color_map_arg
          | boost::make_iterator_property_map(
                std::vector<boost::default_color_type>(
                    boost::num_vertices(g)
                ).begin()
              , index_map
              , boost::white_color
            )
        ]
      , p[
            util_rank_map_arg
          | boost::make_iterator_property_map(
                std::vector<Rank>(boost::num_vertices(g)).begin()
              , index_map
              , Rank()
            )
        ]
      , p[util_buffer_arg | Q]
      , p[intruder_arg | intruder]
    );
}
}  // namespace msmazes

#endif  /* MSMAZES_CORE_GRAPH_REMOVE_CROSS_EDGES_HPP */

---

Multi-State Mazes in C++ is hosted by . Use the Table of Contents for navigation.