root/sandbox/orkney/dijkstra.h

/*
 * Dijkstra Shortest path algorithm for PostgreSQL
 *
 * 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 _DIJKSTRA_H_INCLUDED
#define _DIJKSTRA_H_INCLUDED

#include "ogr_core.h"
#include "ogr_feature.h"
#include "ogr_geometry.h"

#include <boost/config.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

#include "algorithm.h"


using namespace std;
using namespace boost;

class Dijkstra : public Algorithm
{
  public:
             Dijkstra(){}
             Dijkstra( char *nameIn, bool directedIn, bool weightedIn, bool reverseCostIn )
             : Algorithm( nameIn, directedIn, weightedIn, reverseCostIn ){} 
    virtual ~Dijkstra(){}

    virtual bool addEdge(edge_descriptor *e, OGRFeature *edge, graph_t &graph)
    {
      bool inserted;  
        
      tie(*e, inserted) = add_edge(edge->GetFieldAsInteger(SOURCE_FIELD), 
                                   edge->GetFieldAsInteger(TARGET_FIELD), graph);
      return inserted;
    }
    
    virtual void fillFeature(OGRFeature **edges, unsigned int count, edge_descriptor *e, graph_t &graph, int j)
    {
      bool inserted = addEdge(e, edges[j], graph);

      graph[*e].cost = edges[j]->GetFieldAsDouble(COST_FIELD);//set cost
      graph[*e].id = j;//set id


      if (!IsDirected() || (IsDirected() && HasReverseCost()))
      {
        edge_descriptor *er; 
        //adding an edge for opposite direction
            bool inserted = addEdge(er, edges[j], graph);

        graph[*er].id = j;//set id
    
        if (HasReverseCost())
            {
          graph[*er].cost = edges[j]->GetFieldAsDouble(RC_FIELD);//set reverse cost
            }
            else 
            {
              graph[*er].cost = edges[j]->GetFieldAsDouble(COST_FIELD);//set cost
            }
      }    
    }

    virtual int getRoute(int start, int end, OGRFeature **edges, OGRFeature **result, int *resultCount, graph_t &graph)
    {
      std::vector<vertex_descriptor> predecessors(num_vertices(graph));

      vertex_descriptor source = vertex(start, graph);

      if (source < 0) 
      {
        return NO_SOURCE_FOUND;
      }

      vertex_descriptor target = vertex(end, graph);
      if (target < 0)
      {
        return NO_TARGET_FOUND;
      }

      std::vector<double> distances(num_vertices(graph));

      dijkstra_shortest_paths(graph, source,
                              predecessor_map(&predecessors[0]).
                              weight_map(get(&Edge::cost, graph))
                              .distance_map(&distances[0]));

      return makeResult(target, source, edges, predecessors, result, resultCount, graph);

    }  

    virtual int makeResult(vertex_descriptor target, vertex_descriptor source,
                           OGRFeature **edges,
                           std::vector<vertex_descriptor> &predecessors, 
                           OGRFeature **result, int *resultCount, graph_t &graph)
    {
      vector<int> path_vect;
      int max = MAX_NODES;
      path_vect.push_back(target);

      while (target != source) 
      {
            if (target == predecessors[target]) 
            {
              return NO_PATH_FOUND;
            }
            target = predecessors[target];

            path_vect.push_back(target);
            if (!max--) 
            {
              return RESULT_OVERFLOW;
            }
      }

      //*result = (OGRFeature *) malloc(sizeof(OGRFeature) * (path_vect.size() + 1));
      //Let's try to do it in C++ style
      result = new OGRFeature* [path_vect.size() + 1];
      *resultCount = path_vect.size();
      int i, j;

      for(i = path_vect.size() - 1, j = 0; i >= 0; i--, j++)
      {
            graph_traits < graph_t >::vertex_descriptor v_src;
            graph_traits < graph_t >::vertex_descriptor v_targ;
            graph_traits < graph_t >::edge_descriptor e;
            graph_traits < graph_t >::out_edge_iterator out_i, out_end;
        
            if (i == 0) 
            {
              continue;
            }

            v_src = path_vect.at(i);
            v_targ = path_vect.at(i - 1);

            for (tie(out_i, out_end) = out_edges(v_src, graph); 
                 out_i != out_end; ++out_i)
            {
              graph_traits < graph_t >::vertex_descriptor v, targ;
              e = *out_i;
              v = boost::source(e, graph);
              targ = boost::target(e, graph);
                                                                
              if (targ == v_targ)
              {
                result[j] = edges[graph[*out_i].id];
                break;
              }
            }
      }

      return EXIT_SUCCESS;
    }
};

#endif