Handles Directed & undirected graphs, simulates the input data and the output data, uses 3 boost libraries

boostDijkstraTest3.cpp

#include <boost/config.hpp>

#include <iostream>
#include <iterator>
#include <exception>

#include <stdlib.h>
#include <fstream>
#include "postgres.h"

#include <boost/bimap.hpp>
#include <boost/program_options.hpp>
namespace po = boost::program_options;
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

/* 
g++  -g boostDijkstraTest3.cpp -I /usr/include/postgresql/9.4/server/ -lboost_program_options
./a.out -f sampledataSparce.data -s 20 -t 30 -d true
./a.out -f sampledata.data -s 2 -t 3 -d true

./a.out 
Missing parameter.
Allowed options:
  --help                     produce help message
  -f [ --file ] arg          set file_name
  -s [ --source ] arg        set source
  -t [ --target ] arg        set target
  -d [ --directed ] arg (=1) True when directed graph

uses 3 boost libraries

To be able to distinguish the edges (source,target) from the (target,source)
"cost" column weights are set to 1 for (source,target)
"reverse_cost" column weights are set to 2 for (target,source)

*/

/****************************************
SIMULATES  PGR_TYPES.H
****************************************/
typedef struct {
  int64_t id;
  int64_t source;
  int64_t target;
  float8 cost;
  float8 reverse_cost;
} pgr_edge_t;

typedef struct {
  int seq;
  int64_t source;
  int64_t edge;
  float8 cost;
} pgr_path_t;

struct boost_vertex_t {
  int64_t id;
};

struct boost_edge_t{
  int64_t id;
  float8 cost;
  int64_t source_id;
  int64_t target_id;
} ;

/****************************************
SIMULATES  THE C CODE THAT LOADS THE DATA
****************************************/
void import_from_file(const std::string &input_file_name, pgr_edge_t *edges, unsigned int *count) {
        const char* file_name = input_file_name.c_str();

        std::ifstream ifs(file_name);
        if (!ifs) {
                std::cerr << "The file " << file_name << " can not be opened!" << std::endl;
                exit(1);
        }

        ifs >> (*count);

        long edge_id, start_id, end_id;
        double edge_weight, reverse_weight;

        int i = 0;
        while (i < (*count) && ifs >> edge_id) {
                if (edge_id == -1)  break;
                edges[i].id = edge_id;
                ifs >> edges[i].source;
                ifs >> edges[i].target;
                ifs >> edges[i].cost;
                ifs >> edges[i].reverse_cost;

                i++;
        }
  ifs.close();
}



/****************************************
SIMULATES A GENERAL GRAPH FILE
****************************************/
template <class G, class V, class M> void
get_path( pgr_path_t **path, int *result_size,
            G &graph, M &vertices_map,
            std::vector<V> &predecessors,
            std::vector<float8> distances, V source, V target) {

  V target_back = target;
  (*result_size) = 1;
  while (target != source) {
    if (target == predecessors[target]) break ;

    (*result_size)++;
    target = predecessors[target];
  }

  (*path) = (pgr_path_t *) malloc(sizeof(pgr_path_t) * (*result_size));

  target = target_back;
  int seq = (*result_size);

  (*path)[seq-1].seq  = seq;
  (*path)[seq-1].source  = seq == 1? vertices_map.right.find(source)->second:
                                     vertices_map.right.find(target)->second; 
  (*path)[seq-1].edge  = -1; 
  (*path)[seq-1].cost  = 0; 

  while (target != source) {
    if (target == predecessors[target]) {
      break ;
    }
    --seq;
    (*path)[seq-1].seq  = seq;
    (*path)[seq-1].source  = vertices_map.right.find(predecessors[target])->second; 
    (*path)[seq-1].cost  =  distances[target] - distances[predecessors[target]]; 
    (*path)[seq-1].edge  = get_edge_id(graph, predecessors[target], target, (*path)[seq-1].cost); 
    target = predecessors[target];
  }
}

template <class G, class V> int64_t
get_edge_id(G &graph, V from, V to, float8 distance) { 
    typename boost::graph_traits < G >::edge_descriptor e;
    typename boost::graph_traits < G >::out_edge_iterator out_i, out_end;
    V v_source, v_target;
    for (boost::tie(out_i, out_end) = boost::out_edges(from, graph);
        out_i != out_end; ++out_i) {
            e = *out_i;
            v_target = target(e, graph);
            if ((to == v_target) && (distance == graph[*out_i].cost))
                    return  graph[*out_i].id;
    }
    return -2;
}

template <class G, class E, class M>
static void
graph_add_edge(G &graph, const pgr_edge_t &edge, M &vertices_map, int64_t &numb_vertices )
{
  bool inserted;
  typename M::left_iterator vm_s, vm_t;
  typedef typename M::value_type VT;
  E e;

  vm_s= vertices_map.left.find(edge.source);
  if (vm_s == vertices_map.left.end()) {
    vertices_map.insert( VT (edge.source, numb_vertices++));
    vm_s= vertices_map.left.find(edge.source);
  }
  std::cout << numb_vertices << " ---- source\n";
  std::cout << edge.source << " == " << vm_s->first << " => " <<  vm_s->second << '\n';

  vm_t = vertices_map.left.find(edge.target);
  if (vm_t == vertices_map.left.end()) {
    vertices_map.insert( VT (edge.target, numb_vertices++));
    vm_t= vertices_map.left.find(edge.target);
  }
  std::cout << numb_vertices << " ---- target\n";
  std::cout << edge.target << " == " << vm_t->first << " => " <<  vm_t->second << '\n';

  if (edge.cost >= 0) {
    boost::tie(e, inserted) = boost::add_edge(vm_s->second, vm_t->second, graph);
    graph[e].cost = edge.cost;
    graph[e].id = edge.id;
  }

  if (edge.reverse_cost >= 0) {
    boost::tie(e, inserted) = boost::add_edge(vm_t->second, vm_s->second, graph);
    graph[e].cost = edge.reverse_cost;
    graph[e].id = edge.id;
  }
}

template <class G, class M>
static void
graph_insert_data(G &graph, const pgr_edge_t *data_edges, int64_t count, M &vertices_map) {
  typedef typename boost::graph_traits <G>::edge_descriptor edge_descriptor;
  int64_t numb_vertices = 0;
  for (int i=0; i < count; ++i) 
     graph_add_edge< G, edge_descriptor>(graph, data_edges[i], vertices_map, numb_vertices);
}




/****************************************
SIMULATES boost_dijkstra_wrapper.cpp
****************************************/
struct found_one_goal {}; // exception for termination
// visitor that terminates when we find the goal
template <class Vertex>
class dijkstra_one_goal_visitor : public boost::default_dijkstra_visitor
{
    public:
      dijkstra_one_goal_visitor(Vertex goal) : m_goal(goal) {}
      template <class Graph>
      void examine_vertex(Vertex u, Graph& g) {
        if(u == m_goal)
          throw found_one_goal();
      }
    private:
      Vertex m_goal;
};




template < class G , class V> bool
graph_dijkstra_1_to_1( G & digraph, V source, V target,
            std::vector<V> &predecessors,
            std::vector<float8> &distances ) {

  bool found = false;
  try {
  boost::dijkstra_shortest_paths(digraph, source,
      boost::predecessor_map(&predecessors[0])
      .weight_map(get(&boost_edge_t::cost, digraph))
      .distance_map(&distances[0])
      .visitor( dijkstra_one_goal_visitor<V>(target)));
  }
  catch(found_one_goal& fg) {
    found = true; // Target vertex found
  }
 std::cout << "found:" << found <<"\n";
  return found;
}




template <class G> void
process_dijkstra_1_to_1(pgr_path_t **path, int *result_size, G &graph, pgr_edge_t *data_edges, int64_t count, int64_t start_vertex, int64_t end_vertex )
{
      typedef typename boost::graph_traits <G>::vertex_descriptor V;
      // insert the edges
      typedef typename boost::bimap< int64_t, int64_t > bm_type;
      typename bm_type::left_iterator vm_s, vm_t;
      //typedef typename std::map<int64_t, int64_t> bm_type; 

      bm_type  vertices_map; 

      graph_insert_data(graph, data_edges, count, vertices_map);
      // get the source and target

      vm_s = vertices_map.left.find(start_vertex);
      vm_t = vertices_map.left.find(end_vertex);

      // no path if source and target are not in (this should be cheked at load time)
      // if checked at load time comment out
      if ((vm_s ==  vertices_map.left.end()) or (vm_t ==  vertices_map.left.end())) return;

      V source = vertex(vm_s->second, graph);
      V target = vertex(vm_t->second, graph);

      //if ( !check_start_end_vertices(graph, source, target)) return ;

      // create the predecessors and distances vectors
      std::vector<V> predecessors(boost::num_vertices(graph));
      std::vector<float8> distances(boost::num_vertices(graph));
      // perform the algorithm
      graph_dijkstra_1_to_1(graph, source, target, predecessors, distances);
      // get the results
      get_path(path, result_size, graph, vertices_map, predecessors,distances,source,target);

      for (int i= 0; i < distances.size(); ++i) 
          std::cout << "distances( " << i << ")=" << distances[i] << "\n";
}



/****************************************

****************************************/

int main(int ac, char* av[]) {
using namespace boost;
 // try {
    po::options_description desc("Allowed options");
    desc.add_options()
        ("help", "produce help message")
        ("file,f", po::value<std::string>(), "set file_name")
        ("source,s", po::value<int64_t>(), "set source")
        ("target,t", po::value<int64_t>(), "set target")
        ("directed,d", po::value<bool>()->default_value(true), "True when directed graph")
    ;

    po::variables_map vm;        
    po::store(po::parse_command_line(ac, av, desc), vm);
    po::notify(vm);    

    if (vm.count("help")) {
        std::cout << desc << "\n";
        return 0;
    }

    if (vm.count("file") & vm.count("source") & vm.count("target")) {
        std::cout << "File " 
             << vm["file"].as<std::string>() << "\t"
             << vm["source"].as<int64_t>() << "\t"
             << vm["target"].as<int64_t>() << ".\n";
    } else {
        std::cout << "Missing parameter.\n";
        std::cout << desc << "\n";
        return 1;
    }

    pgr_edge_t data_edges[100];
    unsigned int count = 0;

    //std::string fileName("./sampledata.data");
    std::string fileName(vm["file"].as<std::string>());
    int start_vertex(vm["source"].as<int64_t>());
    int end_vertex(vm["target"].as<int64_t>());
    int directedFlag(vm["directed"].as<bool>());
    import_from_file(fileName, data_edges, &count);
  
    typedef boost::adjacency_list < vecS, vecS, undirectedS,
      boost_vertex_t, boost_edge_t > UndirectedGraph;
    typedef boost::adjacency_list < vecS, vecS, directedS,
      boost_vertex_t, boost_edge_t > DirectedGraph;

    //typedef typename boost::graph_traits < DirectedGraph >::vertex_descriptor D_vd;
    //typedef typename boost::graph_traits < UndirectedGraph >::vertex_descriptor U_vd;

    pgr_path_t* path;
    int result_size;
    const int V = 1;
    if (directedFlag) {

      std::cout << "DIRECTED GRAPH DEMO\n";
      // create the graph
      DirectedGraph digraph(V);
      process_dijkstra_1_to_1(&path, &result_size, digraph, data_edges, count, start_vertex, end_vertex);

    } else { 

      std::cout << "UNDIRECTED GRAPH DEMO\n";
      // create the graph
      UndirectedGraph undigraph(V);
      // process
      process_dijkstra_1_to_1(&path, &result_size, undigraph, data_edges, count, start_vertex, end_vertex);
    }

    std::cout << "THE OPUTPUT\n";
    for (int i = 0; i < result_size; ++i)
       std::cout << path[i].seq << "\t" << path[i].source << "\t" << path[i].edge << "\t" << path[i].cost << "\n";

  return 0;
}