Common/Util/GraphAlg.h

Go to the documentation of this file.

//-------------------------------------------------------------------
//  Copyright (c) 2005 Evan Sherbrooke
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//
//-------------------------------------------------------------------

#pragma once
#ifndef UTIL_GRAPHUTIL_H
#define UTIL_GRAPHUTIL_H

namespace util
{
   template<class Graph>
   typename boost::graph_traits<Graph>::out_edge_iterator findEdge (
      typename boost::graph_traits<Graph>::vertex_descriptor start,
      typename boost::graph_traits<Graph>::vertex_descriptor end,
      const Graph& g)
   {
      typename boost::graph_traits<Graph>::out_edge_iterator eIt, eEnd;
      boost::tie (eIt, eEnd) = boost::out_edges (start, g);
      for (; !OUT_EDGE_ITERATORS_EQUAL (eIt, eEnd) && boost::target (*eIt, g) != end; ++eIt);
      return eIt;
   }

   template<
      class Graph, class Vertex, class Visitor,
      class VertexMap, class VertexColorMap, class EdgeColorMap>
   void ccwVisit (Graph& g, Vertex u, Visitor vis, VertexMap vmap, VertexColorMap vcmap, EdgeColorMap ecmap)
   {
      typedef typename boost::property_traits<EdgeColorMap>::value_type ColorValue;
      boost::function_requires< boost::ColorValueConcept<ColorValue> >();
      typedef boost::color_traits<ColorValue> Color;

      vis.start_vertex (u, g);
      boost::put (vcmap, u, Color::gray());
      // Pick an initial edge
      boost::graph_traits<Graph>::out_edge_iterator eIt, eEnd;
      boost::tie (eIt, eEnd) = boost::out_edges (u, g);
      for (; eIt != eEnd && boost::get (ecmap, *eIt) != Color::white(); ++eIt);
      if (eIt == eEnd)
         return;
      Vertex v = boost::target (*eIt, g);

      // Now follow each edge we can in a CCW way
      for (;;)
      {
         boost::put (ecmap, *eIt, Color::black());
         boost::put (vcmap, v, Color::gray());
         vis.examine_edge (*eIt, g);
         const geom::Point2d& pu = boost::get (vmap, u).getLocation();
         const geom::Point2d& pv = boost::get (vmap, v).getLocation();

         // Look for the sharpest right turn. Right turns are negative, left turns positive
         double minAngle = 1e30;
         boost::tie (eIt, eEnd) = boost::out_edges (v, g);
         boost::graph_traits<Graph>::out_edge_iterator besteIt = eEnd;
         for (; eIt != eEnd; ++eIt)
         {
            if (boost::get (ecmap, *eIt) == Color::white())
            {
               Vertex w = boost::target (*eIt, g);
               const geom::Point2d& pw = boost::get (vmap, w).getLocation();
               double turningAngle = w == u ? util::pi : angle (geom::Vec2d (pv-pu), geom::Vec2d (pw-pv));
               if (turningAngle < minAngle)
               {
                  minAngle = turningAngle;
                  besteIt = eIt;
               }
            }
         }
         if (besteIt == eEnd)
            return;
         eIt = besteIt;
         u = v;
         v = boost::target (*eIt, g);
      }
   }
}

#endif

---