Boost C++ Libraries

boost/graph/planar_detail/face_handles.hpp

//=======================================================================
// 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 __FACE_HANDLES_HPP__
#define __FACE_HANDLES_HPP__

#include <list>
#include <boost/graph/graph_traits.hpp>
#include <boost/shared_ptr.hpp>

// A "face handle" is an optimization meant to serve two purposes in
// the implementation of the Boyer-Myrvold planarity test: (1) it holds
// the partial planar embedding of a particular vertex as it's being
// constructed, and (2) it allows for efficient traversal around the
// outer face of the partial embedding at that particular vertex. A face
// handle is lightweight, just a shared pointer to the actual implementation,
// since it is passed around/copied liberally in the algorithm. It consists
// of an "anchor" (the actual vertex it's associated with) as well as a
// sequence of edges. The functions first_vertex/second_vertex and
// first_edge/second_edge allow fast access to the beginning and end of the
// stored sequence, which allows one to traverse the outer face of the partial
// planar embedding as it's being created.
//
// There are some policies below that define the contents of the face handles:
// in the case no embedding is needed (for example, if one just wants to use
// the Boyer-Myrvold algorithm as a true/false test for planarity, the
// no_embedding class can be passed as the StoreEmbedding policy. Otherwise,
// either std_list (which uses as std::list) or recursive_lazy_list can be
// passed as this policy. recursive_lazy_list has the best theoretical
// performance (O(n) for a sequence of interleaved concatenations and reversals
// of the underlying list), but I've noticed little difference between std_list
// and recursive_lazy_list in my tests, even though using std_list changes
// the worst-case complexity of the planarity test to O(n^2)
//
// Another policy is StoreOldHandlesPolicy, which specifies whether or not
// to keep a record of the previous first/second vertex/edge - this is needed
// if a Kuratowski subgraph needs to be isolated.

namespace boost
{
namespace graph
{
    namespace detail
    {

        // face handle policies

        // EmbeddingStorage policy
        struct store_embedding
        {
        };
        struct recursive_lazy_list : public store_embedding
        {
        };
        struct std_list : public store_embedding
        {
        };
        struct no_embedding
        {
        };

        // StoreOldHandlesPolicy
        struct store_old_handles
        {
        };
        struct no_old_handles
        {
        };

        template < typename DataType > struct lazy_list_node
        {
            typedef shared_ptr< lazy_list_node< DataType > > ptr_t;

            lazy_list_node(const DataType& data)
            : m_reversed(false), m_data(data), m_has_data(true)
            {
            }

            lazy_list_node(ptr_t left_child, ptr_t right_child)
            : m_reversed(false)
            , m_has_data(false)
            , m_left_child(left_child)
            , m_right_child(right_child)
            {
            }

            bool m_reversed;
            DataType m_data;
            bool m_has_data;
            shared_ptr< lazy_list_node > m_left_child;
            shared_ptr< lazy_list_node > m_right_child;
        };

        template < typename StoreOldHandlesPolicy, typename Vertex,
            typename Edge >
        struct old_handles_storage;

        template < typename Vertex, typename Edge >
        struct old_handles_storage< store_old_handles, Vertex, Edge >
        {
            Vertex first_vertex;
            Vertex second_vertex;
            Edge first_edge;
            Edge second_edge;
        };

        template < typename Vertex, typename Edge >
        struct old_handles_storage< no_old_handles, Vertex, Edge >
        {
        };

        template < typename StoreEmbeddingPolicy, typename Edge >
        struct edge_list_storage;

        template < typename Edge >
        struct edge_list_storage< no_embedding, Edge >
        {
            typedef void type;

            void push_back(Edge) {}
            void push_front(Edge) {}
            void reverse() {}
            void concat_front(edge_list_storage< no_embedding, Edge >) {}
            void concat_back(edge_list_storage< no_embedding, Edge >) {}
            template < typename OutputIterator > void get_list(OutputIterator)
            {
            }
        };

        template < typename Edge >
        struct edge_list_storage< recursive_lazy_list, Edge >
        {
            typedef lazy_list_node< Edge > node_type;
            typedef shared_ptr< node_type > type;
            type value;

            void push_back(Edge e)
            {
                type new_node(new node_type(e));
                value = type(new node_type(value, new_node));
            }

            void push_front(Edge e)
            {
                type new_node(new node_type(e));
                value = type(new node_type(new_node, value));
            }

            void reverse() { value->m_reversed = !value->m_reversed; }

            void concat_front(
                edge_list_storage< recursive_lazy_list, Edge > other)
            {
                value = type(new node_type(other.value, value));
            }

            void concat_back(
                edge_list_storage< recursive_lazy_list, Edge > other)
            {
                value = type(new node_type(value, other.value));
            }

            template < typename OutputIterator >
            void get_list(OutputIterator out)
            {
                get_list_helper(out, value);
            }

        private:
            template < typename OutputIterator >
            void get_list_helper(
                OutputIterator o_itr, type root, bool flipped = false)
            {
                if (!root)
                    return;

                if (root->m_has_data)
                    *o_itr = root->m_data;

                if ((flipped && !root->m_reversed)
                    || (!flipped && root->m_reversed))
                {
                    get_list_helper(o_itr, root->m_right_child, true);
                    get_list_helper(o_itr, root->m_left_child, true);
                }
                else
                {
                    get_list_helper(o_itr, root->m_left_child, false);
                    get_list_helper(o_itr, root->m_right_child, false);
                }
            }
        };

        template < typename Edge > struct edge_list_storage< std_list, Edge >
        {
            typedef std::list< Edge > type;
            type value;

            void push_back(Edge e) { value.push_back(e); }

            void push_front(Edge e) { value.push_front(e); }

            void reverse() { value.reverse(); }

            void concat_front(edge_list_storage< std_list, Edge > other)
            {
                value.splice(value.begin(), other.value);
            }

            void concat_back(edge_list_storage< std_list, Edge > other)
            {
                value.splice(value.end(), other.value);
            }

            template < typename OutputIterator >
            void get_list(OutputIterator out)
            {
                std::copy(value.begin(), value.end(), out);
            }
        };

        template < typename Graph, typename StoreOldHandlesPolicy,
            typename StoreEmbeddingPolicy >
        struct face_handle_impl
        {
            typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
            typedef typename graph_traits< Graph >::edge_descriptor edge_t;
            typedef
                typename edge_list_storage< StoreEmbeddingPolicy, edge_t >::type
                    edge_list_storage_t;

            face_handle_impl()
            : cached_first_vertex(graph_traits< Graph >::null_vertex())
            , cached_second_vertex(graph_traits< Graph >::null_vertex())
            , true_first_vertex(graph_traits< Graph >::null_vertex())
            , true_second_vertex(graph_traits< Graph >::null_vertex())
            , anchor(graph_traits< Graph >::null_vertex())
            {
                initialize_old_vertices_dispatch(StoreOldHandlesPolicy());
            }

            void initialize_old_vertices_dispatch(store_old_handles)
            {
                old_handles.first_vertex = graph_traits< Graph >::null_vertex();
                old_handles.second_vertex
                    = graph_traits< Graph >::null_vertex();
            }

            void initialize_old_vertices_dispatch(no_old_handles) {}

            vertex_t cached_first_vertex;
            vertex_t cached_second_vertex;
            vertex_t true_first_vertex;
            vertex_t true_second_vertex;
            vertex_t anchor;
            edge_t cached_first_edge;
            edge_t cached_second_edge;

            edge_list_storage< StoreEmbeddingPolicy, edge_t > edge_list;
            old_handles_storage< StoreOldHandlesPolicy, vertex_t, edge_t >
                old_handles;
        };

        template < typename Graph,
            typename StoreOldHandlesPolicy = store_old_handles,
            typename StoreEmbeddingPolicy = recursive_lazy_list >
        class face_handle
        {
        public:
            typedef typename graph_traits< Graph >::vertex_descriptor vertex_t;
            typedef typename graph_traits< Graph >::edge_descriptor edge_t;
            typedef face_handle_impl< Graph, StoreOldHandlesPolicy,
                StoreEmbeddingPolicy >
                impl_t;
            typedef face_handle< Graph, StoreOldHandlesPolicy,
                StoreEmbeddingPolicy >
                self_t;

            face_handle(vertex_t anchor = graph_traits< Graph >::null_vertex())
            : pimpl(new impl_t())
            {
                pimpl->anchor = anchor;
            }

            face_handle(vertex_t anchor, edge_t initial_edge, const Graph& g)
            : pimpl(new impl_t())
            {
                vertex_t s(source(initial_edge, g));
                vertex_t t(target(initial_edge, g));
                vertex_t other_vertex = s == anchor ? t : s;
                pimpl->anchor = anchor;
                pimpl->cached_first_edge = initial_edge;
                pimpl->cached_second_edge = initial_edge;
                pimpl->cached_first_vertex = other_vertex;
                pimpl->cached_second_vertex = other_vertex;
                pimpl->true_first_vertex = other_vertex;
                pimpl->true_second_vertex = other_vertex;

                pimpl->edge_list.push_back(initial_edge);
                store_old_face_handles_dispatch(StoreOldHandlesPolicy());
            }

            // default copy construction, assignment okay.

            void push_first(edge_t e, const Graph& g)
            {
                pimpl->edge_list.push_front(e);
                pimpl->cached_first_vertex = pimpl->true_first_vertex
                    = source(e, g) == pimpl->anchor ? target(e, g)
                                                    : source(e, g);
                pimpl->cached_first_edge = e;
            }

            void push_second(edge_t e, const Graph& g)
            {
                pimpl->edge_list.push_back(e);
                pimpl->cached_second_vertex = pimpl->true_second_vertex
                    = source(e, g) == pimpl->anchor ? target(e, g)
                                                    : source(e, g);
                pimpl->cached_second_edge = e;
            }

            inline void store_old_face_handles()
            {
                store_old_face_handles_dispatch(StoreOldHandlesPolicy());
            }

            inline vertex_t first_vertex() const
            {
                return pimpl->cached_first_vertex;
            }

            inline vertex_t second_vertex() const
            {
                return pimpl->cached_second_vertex;
            }

            inline vertex_t true_first_vertex() const
            {
                return pimpl->true_first_vertex;
            }

            inline vertex_t true_second_vertex() const
            {
                return pimpl->true_second_vertex;
            }

            inline vertex_t old_first_vertex() const
            {
                return pimpl->old_handles.first_vertex;
            }

            inline vertex_t old_second_vertex() const
            {
                return pimpl->old_handles.second_vertex;
            }

            inline edge_t old_first_edge() const
            {
                return pimpl->old_handles.first_edge;
            }

            inline edge_t old_second_edge() const
            {
                return pimpl->old_handles.second_edge;
            }

            inline edge_t first_edge() const
            {
                return pimpl->cached_first_edge;
            }

            inline edge_t second_edge() const
            {
                return pimpl->cached_second_edge;
            }

            inline vertex_t get_anchor() const { return pimpl->anchor; }

            void glue_first_to_second(face_handle< Graph, StoreOldHandlesPolicy,
                StoreEmbeddingPolicy >& bottom)
            {
                pimpl->edge_list.concat_front(bottom.pimpl->edge_list);
                pimpl->true_first_vertex = bottom.pimpl->true_first_vertex;
                pimpl->cached_first_vertex = bottom.pimpl->cached_first_vertex;
                pimpl->cached_first_edge = bottom.pimpl->cached_first_edge;
            }

            void glue_second_to_first(face_handle< Graph, StoreOldHandlesPolicy,
                StoreEmbeddingPolicy >& bottom)
            {
                pimpl->edge_list.concat_back(bottom.pimpl->edge_list);
                pimpl->true_second_vertex = bottom.pimpl->true_second_vertex;
                pimpl->cached_second_vertex
                    = bottom.pimpl->cached_second_vertex;
                pimpl->cached_second_edge = bottom.pimpl->cached_second_edge;
            }

            void flip()
            {
                pimpl->edge_list.reverse();
                std::swap(pimpl->true_first_vertex, pimpl->true_second_vertex);
                std::swap(
                    pimpl->cached_first_vertex, pimpl->cached_second_vertex);
                std::swap(pimpl->cached_first_edge, pimpl->cached_second_edge);
            }

            template < typename OutputIterator >
            void get_list(OutputIterator o_itr)
            {
                pimpl->edge_list.get_list(o_itr);
            }

            void reset_vertex_cache()
            {
                pimpl->cached_first_vertex = pimpl->true_first_vertex;
                pimpl->cached_second_vertex = pimpl->true_second_vertex;
            }

            inline void set_first_vertex(vertex_t v)
            {
                pimpl->cached_first_vertex = v;
            }

            inline void set_second_vertex(vertex_t v)
            {
                pimpl->cached_second_vertex = v;
            }

        private:
            void store_old_face_handles_dispatch(store_old_handles)
            {
                pimpl->old_handles.first_vertex = pimpl->true_first_vertex;
                pimpl->old_handles.second_vertex = pimpl->true_second_vertex;
                pimpl->old_handles.first_edge = pimpl->cached_first_edge;
                pimpl->old_handles.second_edge = pimpl->cached_second_edge;
            }

            void store_old_face_handles_dispatch(no_old_handles) {}

            boost::shared_ptr< impl_t > pimpl;
        };

    } /* namespace detail */
} /* namespace graph */
} /* namespace boost */

#endif //__FACE_HANDLES_HPP__