root/sandbox/orkney/shooting_star_relax.hpp

/*
 * Copyright (c) 2007 Anton A. Patrushev, Orkney, Inc.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program 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 General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 *
 */
 
#ifndef BOOST_GRAPH_SHOOTING_STAR_RELAX_HPP
#define BOOST_GRAPH_SHOOTING_STAR_RELAX_HPP

#include <functional>
#include <boost/limits.hpp> // for numeric limits
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map.hpp>


#define U_TURN_COST 100000

bool is_equal ( int a[], int b[], int size )
{
  for ( int i = 0; i < size; i++ ) 
  {
    if ( a[i] != b[i] )
    return false;
  }
              
  return true;
}

namespace boost {
 
    template <class Edge, class Graph, class WeightMap, class EdgeMap,
            class PredecessorMap, class DistanceMap, class CostMap,
            class BinaryFunction, class BinaryPredicate>
    bool relax(Edge e, 
               Edge pe, 
               const Graph& g, const WeightMap& w, const EdgeMap& em,
               PredecessorMap& p, DistanceMap& d, CostMap& c,
               const BinaryFunction& combine, const BinaryPredicate& compare,
               int e_max_id)
    {
      typedef typename graph_traits<Graph>::directed_category DirCat;
      bool is_undirected = is_same<DirCat, undirected_tag>::value;

      typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
            
      typedef typename property_traits<DistanceMap>::value_type D;
      typedef typename property_traits<WeightMap>::value_type W;
      
      typedef typename property_traits<EdgeMap>::value_type E;
      
      D d_e = get(d, e);
      D d_pe = get(d, pe);
      
      W w_pe_e;

      E w_pe = get(em, e);
      
      int contains = -1;
        
      Edge ce = pe;
      int e_id;

      std::vector<Edge> edge_h;
      typedef typename std::vector<Edge>::iterator It;

      for(int i=0; i< w_pe[g[e].id].size(); ++i)
      
      if(w_pe[g[e].id].at(i).second.size() < 1 || w_pe[g[e].id].at(i).second.back() > 0)
      {
      
      for(int j=0; j<w_pe[g[e].id].at(i).second.size(); ++j)
      {
        e_id = g[ce].id;
        
        if(w_pe[g[e].id].at(i).second.at(j) == -1)
          continue;
        
        if(w_pe[g[e].id].at(i).second.at(j) == e_id || w_pe[g[e].id].at(i).second.at(j)+e_max_id == e_id||
           w_pe[g[e].id].at(i).second.at(j) == e_id+e_max_id || w_pe[g[e].id].at(i).second.at(j)+e_max_id == e_id+e_max_id)
        {
         contains = i;
         edge_h.push_back(ce);
        }
        else if(i == contains)
        {
         contains = -1;
        }
        
        ce = p[g[ce].id];
      }
      
      }
      
      //calculate w_pe_e
      if(contains >= 0)
      {
        w_pe_e = w_pe[g[e].id].at(contains).first;
      }
      else if(abs(g[e].id-g[pe].id) == e_max_id)
      {
        w_pe_e = U_TURN_COST;
      }
      else
      {
        w_pe_e = 0;
      }

      //Ugly combination with w_e_pe.

      if ( compare(combine(combine(d_pe, get(w, pe)), w_pe_e), d_e)) 
      {
        put(d, e, combine(combine(d_pe, get(w, pe)), w_pe_e));
        p[g[e].id] = pe;

        return true;
      }
      else
      {
        return false;
      }
    }

    template <class Graph, class WeightMap, class EdgeMap,
      class PredecessorMap, class DistanceMap>
    bool relax(typename graph_traits<Graph>::edge_descriptor e,
               const Graph& g, WeightMap w, EdgeMap em, PredecessorMap p, DistanceMap d)
    {
      typedef typename property_traits<DistanceMap>::value_type D;
      typedef closed_plus<D> Combine;
      typedef std::less<D> Compare;
      return relax(e, g, w, em, p, d, Combine(), Compare());
    }

} // namespace boost

#endif