[pgrouting-dev] cloning boost_drivedist.cpp to return predecessors

pgRouting pgrouting-dev
1

Hi Anton,

I'm looking at boost_drivedist.cpp with the idea of clone it to also return the predecessor with each record output, but I have not worked in C++ before. So I think I have the idea but want to bounce it off you first.

...
   vertex_descriptor source_vertex = vertex( source_vertex_id, graph );

   std::vector<vertex_descriptor> predecessors(num_vertices(graph));
   std::vector<float8> distances(num_vertices(graph));

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

   graph_traits < graph_t >::vertex_iterator vi, vend;
   vector<path_element> path_vector; // <<<< ???
   int j=0;

   for(tie(vi, vend) = vertices(graph); vi != vend; vi++) {

     if( (double)distances[*vi] <= rdistance ) {

       path_element pe;

       graph_traits<graph_t>::vertex_descriptor s;
       graph_traits<graph_t>::vertex_descriptor p; // <<<< add this

       s = vertex(*vi, graph);
       p = vertex(predecessor[*vi], graph); // <<<< add this

       pe.vertex_id = graph[s].id;
       pe.parent_id = graph[p].id; // <<<< add this
       pe.edge_id = graph[s].edge_id;
       pe.cost = distances[*vi];

       path_vector.push_back( pe );
     }
   }

   if( path_vector.size() == 0 ) {
     *err_msg = (char *)"No path found";
     return 0;
   }

   vector<path_element>::iterator itr;
   *path = (path_element_t *) malloc( sizeof(path_element_t) *
                                      (path_vector.size() + 1) );
   *path_count = path_vector.size();

   for(j=0,itr=path_vector.begin();itr != path_vector.end();itr++,j++) {
     path_element pe = *itr;
     (*path)[j].vertex_id = pe.vertex_id;
     (*path)[j].parent_id = pe.parent_id; // <<<< add this
     (*path)[j].edge_id = pe.edge_id;
     (*path)[j].cost = pe.cost;
   }

   return EXIT_SUCCESS;
}

So in addition to the above 3 lines, I would need to modify core/src/dijkstra.h

typedef struct path_element
{
     int vertex_id;
     int parent_id; // <<< add this
     int edge_id;
     float8 cost;
} path_element_t;

What I'm not sure on is how (or if it is possible) to modify path_element pe to include parent_id item.

And finally in the C wrapper to this function I would need to update parent_id along with vertex_id to uncompress the range shift that was done.

Does this look like it will work? Did I forget anything?

Thoughts?

-Steve

2

Hi Steve,

Looks OK to me.
There's nothing wrong with one more int field in path_element structure.
I don't remember what path_vector is for, most likely it is bad
copy/paste from somewhere else and not used at all.

Anton.

On 5/17/11, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

Hi Anton,

I'm looking at boost_drivedist.cpp with the idea of clone it to also
return the predecessor with each record output, but I have not worked in
C++ before. So I think I have the idea but want to bounce it off you first.

...
   vertex_descriptor source_vertex = vertex( source_vertex_id, graph );

   std::vector<vertex_descriptor> predecessors(num_vertices(graph));
   std::vector<float8> distances(num_vertices(graph));

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

   graph_traits < graph_t >::vertex_iterator vi, vend;
   vector<path_element> path_vector; // <<<< ???
   int j=0;

   for(tie(vi, vend) = vertices(graph); vi != vend; vi++) {

     if( (double)distances[*vi] <= rdistance ) {

       path_element pe;

       graph_traits<graph_t>::vertex_descriptor s;
       graph_traits<graph_t>::vertex_descriptor p; // <<<< add this

       s = vertex(*vi, graph);
       p = vertex(predecessor[*vi], graph); // <<<< add this

       pe.vertex_id = graph[s].id;
       pe.parent_id = graph[p].id; // <<<< add this
       pe.edge_id = graph[s].edge_id;
       pe.cost = distances[*vi];

       path_vector.push_back( pe );
     }
   }

   if( path_vector.size() == 0 ) {
     *err_msg = (char *)"No path found";
     return 0;
   }

   vector<path_element>::iterator itr;
   *path = (path_element_t *) malloc( sizeof(path_element_t) *
                                      (path_vector.size() + 1) );
   *path_count = path_vector.size();

   for(j=0,itr=path_vector.begin();itr != path_vector.end();itr++,j++) {
     path_element pe = *itr;
     (*path)[j].vertex_id = pe.vertex_id;
     (*path)[j].parent_id = pe.parent_id; // <<<< add this
     (*path)[j].edge_id = pe.edge_id;
     (*path)[j].cost = pe.cost;
   }

   return EXIT_SUCCESS;
}

So in addition to the above 3 lines, I would need to modify
core/src/dijkstra.h

typedef struct path_element
{
     int vertex_id;
     int parent_id; // <<< add this
     int edge_id;
     float8 cost;
} path_element_t;

What I'm not sure on is how (or if it is possible) to modify
path_element pe to include parent_id item.

And finally in the C wrapper to this function I would need to update
parent_id along with vertex_id to uncompress the range shift that was done.

Does this look like it will work? Did I forget anything?

Thoughts?

-Steve
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

--
Georepublic UG (haftungsbeschränkt)
Salzmannstraße 44,
81739 München, Germany

Anton Patrushev
CTO

eMail: anton.patrushev@georepublic.de
Web: http://georepublic.de

Tel: +49 (089) 420 959 519
Sip: 1959519@sipgate.de

Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl

3

Hi Anton,

Welcome back and hope you are feeling better. I hate being sick, and I think a bad case of the flu is about the worse.

So I did play around with this a little but in the end ripped it out of the postgresql server environment and test things out in a plan command tool. I just using the libpq-fe.h to the database from C. You should see more on this in my follow up posts. In my code, with the predecessor changes I get all the result records that I would expect. So there is some bug in the pgRouting driving distance code that where the symptom is that some result records are not in the records set. With the node and edge of a result tuple you can reconstruct the tree, but some of the tuples are missing in the driving distance results, result in the fact that you reconstruct multiple disconnected trees that COULD be connected correctly if the missing tuples were in the result set.

That is as far as I have been able to get. Things to do:

1. add the predecessor changes below to the pg_routing code and see if the trigger returning the missing tuples (I suspect it will not).
2. I can modify my test code to look more like the pgrouting code and see if I can reproduce the missing tuples (I suspect it will not).

My intuitive GUESS, is that we are loosing the tuples somehow when we move them from the C/C++ structures into the set returning mechanism of postgresql. I looked at this code but not knowing the nuances of programming in the postgresql server environment, I did not see anything obvious to me.

So maybe you could look that over when you have a chance.

-Steve

On 6/2/2011 8:43 PM, Anton Patrushev wrote:

Hi Steve,

Looks OK to me.
There's nothing wrong with one more int field in path_element structure.
I don't remember what path_vector is for, most likely it is bad
copy/paste from somewhere else and not used at all.

Anton.

On 5/17/11, Stephen Woodbridge<woodbri@swoodbridge.com> wrote:

Hi Anton,

I'm looking at boost_drivedist.cpp with the idea of clone it to also
return the predecessor with each record output, but I have not worked in
C++ before. So I think I have the idea but want to bounce it off you first.

...
    vertex_descriptor source_vertex = vertex( source_vertex_id, graph );

    std::vector<vertex_descriptor> predecessors(num_vertices(graph));
    std::vector<float8> distances(num_vertices(graph));

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

    graph_traits< graph_t>::vertex_iterator vi, vend;
    vector<path_element> path_vector; //<<<< ???
    int j=0;

    for(tie(vi, vend) = vertices(graph); vi != vend; vi++) {

      if( (double)distances[*vi]<= rdistance ) {

        path_element pe;

        graph_traits<graph_t>::vertex_descriptor s;
        graph_traits<graph_t>::vertex_descriptor p; //<<<< add this

        s = vertex(*vi, graph);
        p = vertex(predecessor[*vi], graph); //<<<< add this

        pe.vertex_id = graph[s].id;
        pe.parent_id = graph[p].id; //<<<< add this
        pe.edge_id = graph[s].edge_id;
        pe.cost = distances[*vi];

        path_vector.push_back( pe );
      }
    }

    if( path_vector.size() == 0 ) {
      *err_msg = (char *)"No path found";
      return 0;
    }

    vector<path_element>::iterator itr;
    *path = (path_element_t *) malloc( sizeof(path_element_t) *
                                       (path_vector.size() + 1) );
    *path_count = path_vector.size();

    for(j=0,itr=path_vector.begin();itr != path_vector.end();itr++,j++) {
      path_element pe = *itr;
      (*path)[j].vertex_id = pe.vertex_id;
      (*path)[j].parent_id = pe.parent_id; //<<<< add this
      (*path)[j].edge_id = pe.edge_id;
      (*path)[j].cost = pe.cost;
    }

    return EXIT_SUCCESS;
}

So in addition to the above 3 lines, I would need to modify
core/src/dijkstra.h

typedef struct path_element
{
      int vertex_id;
      int parent_id; //<<< add this
      int edge_id;
      float8 cost;
} path_element_t;

What I'm not sure on is how (or if it is possible) to modify
path_element pe to include parent_id item.

And finally in the C wrapper to this function I would need to update
parent_id along with vertex_id to uncompress the range shift that was done.

Does this look like it will work? Did I forget anything?

Thoughts?

-Steve
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev