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

[Anton Patrushev]

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 at 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 at 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 at georepublic.de
Web: http://georepublic.de

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

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