root/tags/release-1.0-beta/shooting_star_relax.hpp

//=======================================================================
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek,
//
// Copyright 2007 Orkney, Inc.
// Author: Anton A. Patrushev
//
// 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 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>

#include <iostream>
#include <fstream>
#include <postgres.h>

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 {

    // The following version of the plus functor prevents
    // problems due to overflow at positive infinity.

    template <class T>
    struct closed_plus
    {
      // std::abs just isn't portable :(
      template <class X>
      inline X my_abs(const X& x) const { return x < 0 ? -x : x; }

      T operator()(const T& a, const T& b) const {
        using namespace std;
        T inf = (numeric_limits<T>::max)();
        if (b > 0 && my_abs(inf - a) < b)
          return inf;
        return a + b;
      }
    };
    
    template <class Edge, class Graph, class WeightMap, class EdgeMap,
            class PredecessorMap, class DistanceMap, class CostMap,
            class HistoryMap, 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,
               HistoryMap& his,
               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;
            
      Vertex u = source(e, g), v = target(e, g), pu = source(pe, g);

      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_e = get(w, e);
      
      //myfile<<"w(e) = "<<w_e<<"\n"<<std::flush;

      //myfile<<"cost("<<g[e].id<<") = "<<get(c, e)<<"\n"<<std::flush;

      //myfile<<"d("<<g[e].id<<") = "<<get(d, e)<<"\n"<<std::flush;

      //myfile<<g[u].id<<" - "<<g[v].id<<" : d_e="<<d_e<<"\n"<<std::flush;


      //edge where we came from
      bool edge_exists;
      //Edge pe;
      
      //pe = get(p, g[e].id);
      
      W w_pe_e;

      //E w_pe = get(em, pe);
      E w_pe = get(em, e);
      
      bool contains = false;
        

      //myfile<<"w(pe, e) = "<<w_pe_e<<"\n"<<std::flush;

      //myfile<<"id = "<<g[e].id<<", size = "<<w_pe[g[e].id].second.size()<<"\n"<<std::flush;

      Edge ce = pe;
      int e_id;

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

      //for(int i=w_pe[g[e].id].second.size()-1; i>=0; --i)
      
      if(w_pe[g[e].id].second.size() < 1 || w_pe[g[e].id].second.back() > 0)
      for(int i=0; i<w_pe[g[e].id].second.size(); ++i)
      {
        e_id = g[ce].id;
        //myfile<<"e_id="<<e_id<<", second["<<g[e].id<<"]="<<w_pe[g[e].id].second.at(i)<<"\n"<<std::flush;
        
        if(w_pe[g[e].id].second.at(i) == -1)
          continue;
          
        if(w_pe[g[e].id].second.at(i) == e_id || w_pe[g[e].id].second.at(i)+e_max_id == e_id)
        {
         contains = true;
         edge_h.push_back(ce);
        }
        else
        {
         contains = false;
        }
        
        ce = p[g[ce].id];
      }
      
      //calculate w_pe_e
      if(contains)
      {

        w_pe_e = w_pe[g[e].id].first;


      }
      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