SPAR/AIModule/BWTA/vendors/CGAL/CGAL/graph_traits_Dual_Arrangement_2.h

Go to the documentation of this file.

// Copyright (c) 2005  Tel-Aviv University (Israel).
// All rights reserved.
//
// This file is part of CGAL (www.cgal.org); you may redistribute it under
// the terms of the Q Public License version 1.0.
// See the file LICENSE.QPL distributed with CGAL.
//
// Licensees holding a valid commercial license may use this file in
// accordance with the commercial license agreement provided with the software.
//
// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
//
// $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Arrangement_on_surface_2/include/CGAL/graph_traits_Dual_Arrangement_2.h $
// $Id: graph_traits_Dual_Arrangement_2.h 48358 2009-03-11 14:28:13Z ophirset $
// 
//
// Author(s)     : Ron Wein     <wein@post.tau.ac.il>
//                 Ophir Setter <ophirset@post.tau.ac.il>

#ifndef CGAL_GRAPH_TRAITS_DUAL_ARRANGEMENT_2_H
#define CGAL_GRAPH_TRAITS_DUAL_ARRANGEMENT_2_H

#include <CGAL/Arrangement_on_surface_2.h>
#include <CGAL/Arrangement_2.h>

CGAL_BEGIN_NAMESPACE

// Forward declaration.
template <class Type> class Dual;

template <class GeomTraits_, class TopTraits_>
class Dual<Arrangement_on_surface_2<GeomTraits_,TopTraits_> >
{
public:
  
  typedef GeomTraits_                          Geometry_traits_2;
  typedef TopTraits_                           Topology_traits;
  typedef CGAL::Arrangement_on_surface_2<Geometry_traits_2, Topology_traits>
                                               Arrangement_on_surface_2;

  typedef typename Arrangement_on_surface_2::Size              Size;
  typedef typename Arrangement_on_surface_2::Face_handle       Vertex_handle;
  typedef typename Arrangement_on_surface_2::Halfedge_handle   Edge_handle;

  typedef typename Arrangement_on_surface_2::Face_iterator     Vertex_iterator;
  typedef typename Arrangement_on_surface_2::Halfedge_iterator Edge_iterator;

protected:

  typedef typename Arrangement_on_surface_2::Face_handle       Face_handle;
  typedef typename Arrangement_on_surface_2::Ccb_halfedge_circulator
                                                      Ccb_halfedge_circulator;
  typedef typename Arrangement_on_surface_2::Outer_ccb_iterator
                                                      Outer_ccb_iterator;
  typedef typename Arrangement_on_surface_2::Inner_ccb_iterator
                                                      Inner_ccb_iterator;

  class Face_neighbor_iterator
  {
    typedef Face_neighbor_iterator               Self;

  public:

    typedef std::forward_iterator_tag            iterator_category;
    typedef Edge_handle                          value_type;
    typedef value_type                           reference;
    typedef value_type*                          pointer;
    typedef int                                  difference_type;

  private:

    Outer_ccb_iterator       _outer_ccb_iter;
    Inner_ccb_iterator       _inner_ccb_iter;
    Ccb_halfedge_circulator  _ccb_curr;
    Ccb_halfedge_circulator  _ccb_first;
    Face_handle              _face;
    bool                     _out;
    Edge_handle              _hh;
    bool                     _end;

  public:

    Face_neighbor_iterator () :
      _end (true)
    {}

    Face_neighbor_iterator (Face_handle face, 
                            bool out_edges,
                            bool start) :
      _face (face),
      _out (out_edges),
      _end (! start)
    {
      CGAL_precondition (! face->is_fictitious());

      if (start)
      {
        _outer_ccb_iter = _face->outer_ccbs_begin();
        _inner_ccb_iter = _face->inner_ccbs_begin();

        if (_outer_ccb_iter != _face->outer_ccbs_end())
        {
          // Start from the first outer CCB, if one exists.
          _ccb_curr = _ccb_first = *_outer_ccb_iter;
        }
        else if (_inner_ccb_iter != face->inner_ccbs_end())
        {
          // Otherwise, start from the first inner CCB.
          _ccb_curr = _ccb_first = *_inner_ccb_iter;
        }
        else
        {
          // In this case there are no CCBs to traverse:
          _end = true;
          return;
        }

        _hh = this->_dereference();

        // In case the incident face of the twin halfedge is fictitious,
        // skip it and proceed to the next edge.
        if (_hh->is_fictitious())
          ++(*this);
      }
      else // end iterator.
      {
        _outer_ccb_iter = _face->outer_ccbs_end();
        _inner_ccb_iter = _face->inner_ccbs_end();
      }
    }  

    bool operator== (const Self& it) const
    {
      return (this->_equal(it));
    }
    
    bool operator!= (const Self& it) const
    {
      return (! this->_equal(it));
    }
    
    reference operator* () const
    {
      return (_hh);
    }

    pointer operator-> () const
    {
      return (&_hh);
    }
    
    /* Increment operators. */
    Self& operator++ ()
    {
      do
      {
        this->_increment();
        if (_end)
          return (*this);

        _hh = this->_dereference();

      } while (_hh->is_fictitious());

      return (*this);
    }

    Self operator++ (int )
    {
      Self tmp = *this;

      do
      {
        this->_increment();
        if (_end)
          return (tmp);

        _hh = this->_dereference();

      } while (_hh->is_fictitious());

      return (tmp);
    }

  private:

    bool _equal (const Self& it) const
    {
      return (_out == it._out && _face == it._face &&
              ((_end && it._end) ||
               (_outer_ccb_iter == it._outer_ccb_iter &&
                _inner_ccb_iter == it._inner_ccb_iter &&
                _ccb_curr == it._ccb_curr)));
    }

    Edge_handle _dereference () const
    {
      if (_out)
        return (_ccb_curr);
      else
        return (_ccb_curr->twin());
    }

    // Increments of the iterator.
    void _increment ()
    {
      CGAL_assertion (! _end);

      // If we have not traversed the entire CCB in full, move to the next
      // halfedge along the current CCB.
      ++_ccb_curr;

      if (_ccb_curr != _ccb_first)
        return;

      // In this case we have completed the current CCB and we have to move
      // to the next one.
      if (_outer_ccb_iter != _face->outer_ccbs_end())
      {
        // Try to move to the next outer CCB.
        ++_outer_ccb_iter;
        if (_outer_ccb_iter != _face->outer_ccbs_end())
        {
          _ccb_curr = _ccb_first = *_outer_ccb_iter;
          return;
        }

        // In this case we start traversing the inner CCBs.
        if (_inner_ccb_iter != _face->inner_ccbs_end())
        {
          CGAL_assertion (_inner_ccb_iter == _face->inner_ccbs_begin());

          // Otherwise, start from the first inner CCB.
          _ccb_curr = _ccb_first = *_inner_ccb_iter;
          return;
        }
      }
      else if (_inner_ccb_iter != _face->inner_ccbs_end())
      {

        // In this case we have already traversed all outer CCBs (and at least
        // one inner CCB), so we try to move to the next inner CCB.
        ++_inner_ccb_iter;
        if (_inner_ccb_iter != _face->inner_ccbs_end())
        {
          // Otherwise, start from the first inner CCB.
          _ccb_curr = _ccb_first = *_inner_ccb_iter;
          return;
        }
      }

      // In this case we finished traversing all outer and inner CCBs:
      _end = true;
      return;
    }

  };

  // Data members:
  mutable Arrangement_on_surface_2    *p_arr;    // The primal arrangement.
  
public:

  typedef Face_neighbor_iterator            Incident_edge_iterator;

  Dual () :
    p_arr (NULL)
  {}

  Dual (const Arrangement_on_surface_2& arr) :
    p_arr (const_cast<Arrangement_on_surface_2 *> (&arr))
  {}

  const Arrangement_on_surface_2* arrangement () const
  {
    return (p_arr);
  }

  Arrangement_on_surface_2* arrangement ()
  {
    return (p_arr);
  }

  Size number_of_vertices () const
  {
    return (p_arr->number_of_faces());
  }

  Vertex_iterator vertices_begin () const
  {
    return (p_arr->faces_begin());
  }

  Vertex_iterator vertices_end () const
  {
    return (p_arr->faces_end());
  }

  Size number_of_edges () const
  {
    return (p_arr->number_of_halfedges());
  }

  Edge_iterator edges_begin () const
  {
    return (p_arr->halfedges_begin());
  }

  Edge_iterator edges_end () const
  {
    return (p_arr->halfedges_end());
  }

  Size degree (Vertex_handle v) const
  {
    Incident_edge_iterator   begin = Incident_edge_iterator (v, true, true);
    Incident_edge_iterator   end = Incident_edge_iterator (v, false, true);
    Size                     deg = 0;

    while (begin != end)
    {
      deg++;
      ++begin;
    }

    return (deg);
  }

  Incident_edge_iterator out_edges_begin (Vertex_handle v) const
  {
    return (Incident_edge_iterator (v, true, true));
  }

  Incident_edge_iterator out_edges_end (Vertex_handle v) const
  {
    return (Incident_edge_iterator (v, true, false));
  }

  Incident_edge_iterator in_edges_begin (Vertex_handle v) const
  {
    return (Incident_edge_iterator (v, false, true));
  }

  Incident_edge_iterator in_edges_end (Vertex_handle v) const
  {
    return (Incident_edge_iterator (v, false, false));
  }
};

template <class Traits_, class Dcel_>
class Dual<Arrangement_2<Traits_, Dcel_> > :
  public Dual<Arrangement_on_surface_2<
    typename CGAL::Arrangement_2<Traits_, Dcel_>::Geometry_traits_2,
    typename CGAL::Arrangement_2<Traits_, Dcel_>::Topology_traits> >
{
  typedef Traits_                                                     Traits_2;
  typedef Dcel_                                                       Dcel;
  typedef Dual<CGAL::Arrangement_on_surface_2<
    typename CGAL::Arrangement_2<Traits_2, Dcel>::Geometry_traits_2,
    typename CGAL::Arrangement_2<Traits_2, Dcel>::Topology_traits> >  Base;

public:

  Dual () :
    Base()
  {}

  Dual (const CGAL::Arrangement_2<Traits_2, Dcel>& arr) :
    Base (arr)
  {}
};

CGAL_END_NAMESPACE

#include <boost/graph/graph_concepts.hpp>
#include <boost/iterator/counting_iterator.hpp>

namespace boost {

template <class GeomTraits_, class TopTraits_>
class graph_traits<CGAL::Dual<CGAL::Arrangement_on_surface_2<GeomTraits_,
                                                             TopTraits_> > >
{
public:
  
  typedef GeomTraits_                           Geometry_traits_2;
  typedef TopTraits_                            Topology_traits;
  typedef CGAL::Arrangement_on_surface_2<Geometry_traits_2, Topology_traits>
                                                Arrangement_on_surface_2;
  typedef CGAL::Dual<Arrangement_on_surface_2>  Dual_arr_2;

private:

  typedef typename Dual_arr_2::Vertex_iterator         Vertex_iterator;
  typedef typename Dual_arr_2::Edge_iterator           Edge_iterator;
  typedef typename Dual_arr_2::Incident_edge_iterator  Incident_edge_iterator;
 
  struct Dual_arr_traversal_category : 
    public virtual boost::bidirectional_graph_tag,   // This tag refines the
                                                     // incidence_graph_tag.
    public virtual boost::vertex_list_graph_tag,  // Can iterate over vertices.
    public virtual boost::edge_list_graph_tag     // Can iterate over edges.
  {};
  
public:

  // Types required of the Graph concept:
  typedef typename Dual_arr_2::Vertex_handle            vertex_descriptor;
  typedef boost::directed_tag                           directed_category;
  typedef boost::allow_parallel_edge_tag                edge_parallel_category;

  typedef Dual_arr_traversal_category                   traversal_category;

  // Types required by the IncidenceGraph concept:
  typedef typename Dual_arr_2::Edge_handle              edge_descriptor;
  typedef Incident_edge_iterator                        out_edge_iterator;
  typedef typename Dual_arr_2::Size                     degree_size_type;

  // Types required by the BidirectionalGraph concept:
  typedef Incident_edge_iterator                        in_edge_iterator;

  // Types required by the VertexListGraph concept:
  typedef boost::counting_iterator<Vertex_iterator>     vertex_iterator;
  typedef typename Dual_arr_2::Size                     vertices_size_type;

  // Types required by the EdgeListGraph concept:
  typedef boost::counting_iterator<Edge_iterator>       edge_iterator;
  typedef typename Dual_arr_2::Size                     edges_size_type;

  // Types not required by any of these concepts:
  typedef void                                          adjacency_iterator;

};

template <class Traits_, class Dcel_>
class graph_traits<CGAL::Dual<CGAL::Arrangement_2<Traits_, Dcel_> > > :
    public graph_traits<CGAL::Dual<CGAL::Arrangement_on_surface_2<
      typename CGAL::Arrangement_2<Traits_, Dcel_>::Geometry_traits_2,
      typename CGAL::Arrangement_2<Traits_, Dcel_>::Topology_traits> > >
{};

}; // namespace boost

CGAL_BEGIN_NAMESPACE

// Functions required by the IncidenceGraph concept:
// -------------------------------------------------

template <class GeomTraits_, class TopTraits_>
typename 
boost::graph_traits<CGAL::Dual<CGAL::
  Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::degree_size_type
out_degree(typename 
           boost::graph_traits<CGAL::Dual<CGAL::
           Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                           vertex_descriptor v,
           const CGAL::Dual<CGAL::
             Arrangement_on_surface_2<GeomTraits_, TopTraits_> >& darr)
{
  return darr.degree (v);
}

template <class GeomTraits_, class TopTraits_>
std::pair<typename
          boost::graph_traits<CGAL::Dual<CGAL::
            Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                             out_edge_iterator,
          typename
          boost::graph_traits<CGAL::Dual<CGAL::
            Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                             out_edge_iterator>
out_edges(typename
          boost::graph_traits<CGAL::Dual<CGAL::
          Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                           vertex_descriptor v,
          const CGAL::Dual<CGAL::
            Arrangement_on_surface_2<GeomTraits_, TopTraits_> >& darr)
{
  return std::make_pair (darr.out_edges_begin (v), darr.out_edges_end (v));
}

template <class GeomTraits_, class TopTraits_>
typename
boost::graph_traits<CGAL::Dual<CGAL::
  Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::vertex_descriptor
source(typename
       boost::graph_traits<CGAL::Dual<CGAL::
         Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                           edge_descriptor e,
       const CGAL::Dual<CGAL::
         Arrangement_on_surface_2<GeomTraits_, TopTraits_> >& /* darr */)
{
  return e->face();
}

template <class GeomTraits_, class TopTraits_>
typename
boost::graph_traits<CGAL::Dual<CGAL::
  Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::vertex_descriptor
target(typename
       boost::graph_traits<CGAL::Dual<CGAL::
         Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                           edge_descriptor e,
       const CGAL::Dual<CGAL::
         Arrangement_on_surface_2<GeomTraits_, TopTraits_> >& /* darr */)
{
  return e->twin()->face();
}

// Functions required by the BidirectionalGraph concept:
// -----------------------------------------------------

template <class GeomTraits_, class TopTraits_>
typename
boost::graph_traits<CGAL::Dual<CGAL::
  Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::degree_size_type
in_degree(typename
          boost::graph_traits<CGAL::Dual<CGAL::
            Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                           vertex_descriptor v,
          const CGAL::Dual<CGAL::
            Arrangement_on_surface_2<GeomTraits_, TopTraits_> >& darr)
{
  return darr.degree (v);
}

template <class GeomTraits_, class TopTraits_>
std::pair<typename
          boost::graph_traits<CGAL::Dual<CGAL::
            Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                             in_edge_iterator,
          typename
          boost::graph_traits<CGAL::Dual<CGAL::
            Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                             in_edge_iterator>
in_edges(typename
         boost::graph_traits<CGAL::Dual<CGAL::
           Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                           vertex_descriptor v,
         const CGAL::Dual<CGAL::
           Arrangement_on_surface_2<GeomTraits_, TopTraits_> >& darr)
{
  return std::make_pair (darr.in_edges_begin (v), darr.in_edges_end (v));
}

template <class GeomTraits_, class TopTraits_>
typename
boost::graph_traits<CGAL::Dual<CGAL::
  Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::degree_size_type
degree(typename
       boost::graph_traits<CGAL::Dual<CGAL::
         Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                           vertex_descriptor v,
       const CGAL::Dual<CGAL::
         Arrangement_on_surface_2<GeomTraits_, TopTraits_> >& darr)
{
  return (2 * darr.degree (v));
}

// Functions required by the VertexListGraph concept:
// --------------------------------------------------

template <class GeomTraits_, class TopTraits_>
typename
boost::graph_traits<CGAL::Dual<CGAL::
  Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::vertices_size_type
num_vertices(const CGAL::Dual<CGAL::
               Arrangement_on_surface_2<GeomTraits_, TopTraits_> >& darr)
{
  return darr.number_of_vertices();
}

template <class GeomTraits_, class TopTraits_>
std::pair<typename
          boost::graph_traits<CGAL::Dual<CGAL::
            Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                               vertex_iterator,
          typename
          boost::graph_traits<CGAL::Dual<CGAL::
            Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                               vertex_iterator>
vertices (const CGAL::Dual<CGAL::
            Arrangement_on_surface_2<GeomTraits_, TopTraits_> >& darr)
{
  return std::make_pair (darr.vertices_begin(), darr.vertices_end());
}

// Functions required by the EdgeListGraph concept:
// ------------------------------------------------

template <class GeomTraits_, class TopTraits_>
typename
boost::graph_traits<CGAL::Dual<CGAL::
  Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::edges_size_type
num_edges(const CGAL::Dual<CGAL::
            Arrangement_on_surface_2<GeomTraits_, TopTraits_> >& darr)
{
  return darr.number_of_edges(); 
}

template <class GeomTraits_, class TopTraits_>
std::pair<typename
          boost::graph_traits<CGAL::Dual<CGAL::
            Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                               edge_iterator,
          typename
          boost::graph_traits<CGAL::Dual<CGAL::
            Arrangement_on_surface_2<GeomTraits_, TopTraits_> > >::
                                                               edge_iterator>
edges (const CGAL::Dual<CGAL::
         Arrangement_on_surface_2<GeomTraits_, TopTraits_> >& darr)
{
  return std::make_pair (darr.edges_begin(), darr.edges_end());
}

CGAL_END_NAMESPACE

#endif