[pgrouting-dev] Finally getting back to integrating your TRSP improvements

Stephen_Woodbridge1 · April 13, 2014, 12:28am

Hi Roni,

I hope you and your family are doing well.
I am well but have been very busy. I'm between some contracts at the moment and I am looking at the TRSP improvements you did quite a ways back to add the reverse cost and routing from nodes A-B-C-...

Looking at multi_dijkstra it seems that I should be able to mimic that code based on how you clean up after each route A-B to restart for B-C and create a similar function that computes one to many destinations, A-B, A-C, A-D, etc.

What do you think?

So for integrating this code, I probably need to implement a family of additional functions like:

Existing functions:

pgr_trsp(text, integer, integer, boolean, boolean)
-- node to node

pgr_trsp(text, integer, integer, boolean, boolean, text)
-- node to node with restrictions

pgr_trsp(text, integer, double precision, integer, double precision, boolean, boolean)
-- edge to edge

pgr_trsp(text, integer, double precision, integer, double precision, boolean, boolean, text)
-- edge to edge with restrictions

pgr_trsp(text, integer, boolean, boolean, text)
-- array of nodes **this gets changed to use new code (1)**

pgr_trsp(text, integer, float8, boolean, boolean, text)
-- array of edges **this gets changed to use new code (2)**

(1) should plug directly into your code. I currently do this in C by calling your old code multiple times, but it will be more efficient to change this to call multi_dijkstra because we only build the graph once.

(2) I currently do this in C by making multiple calls to your old code. The multi_dijkstra only accepts nodes, not edges, so I'll look at making a version that can be called by edges. Unless you want to do that

Then I think I would like to add a new argument to (1) and (2) above "boolean onetomany" and if it is true then we compute A-B, A-C, A-D, ... and if it is false it will compute A-B-C-...

I'll have to think about how to return the results, but that should not be too hard.

TODO:

1. create function to support multi_dijkstra with edges
2. create new function onetomany_dijkstra for nodes
3. create new function onetomany_dijkstra for edges
4. update C code wrappers to support the above
5. develop test cases
6. write the documentation
7. check it in

Ok that is a bunch of work! Maybe I'll start with just getting (1) done so it calls your new code, and write a test case for that. Then tackle the rest.

Thoughts?

-Steve

Stephen_Woodbridge1 · April 13, 2014, 1:36pm

So a couple of more thoughts on refactoring TRSP. I think we can get away with having just two C wrapper functions:

1) to handle node input
2) to handle edge input

I think everything else can be handled as options in the plpgsql wrappers like:

a) input is always an array of nodes or edges
we can take two node arguments and create an array in psql wrapper
likewise for the start and end edge function

b) we can add an argument mode=n, where
    0 - point to point
    1 - one to many
    2 - many to many

c) it might be useful to have an option costonly if you only want the cost and not all the edge info

d) restrictions are optional and can be passed as null if none

The only issue with this is that we currently return different result types if we are returning a single route versus returning multiple routes in the result. I think we can deal with this by always returning the multiple results structure from the C code and filtering the column out in the plpgsql wrapper function to support the existing functions

My goal is to minimize code duplication and to simplify the lower level code for consistency, supportability, and testing. Long term we might deprecate some of the plpgsql wrapper functions to simplify the documentation and to make it easier to work with.

Thoughts and input are welcome. I'm still in the planning stage for this but will short start coding something

Thanks,
-Steve

On 4/12/2014 8:28 PM, Stephen Woodbridge wrote:

Hi Roni,

I hope you and your family are doing well.
I am well but have been very busy. I'm between some contracts at the
moment and I am looking at the TRSP improvements you did quite a ways
back to add the reverse cost and routing from nodes A-B-C-...

Looking at multi_dijkstra it seems that I should be able to mimic that
code based on how you clean up after each route A-B to restart for B-C
and create a similar function that computes one to many destinations,
A-B, A-C, A-D, etc.

What do you think?

So for integrating this code, I probably need to implement a family of
additional functions like:

Existing functions:

pgr_trsp(text, integer, integer, boolean, boolean)
-- node to node

pgr_trsp(text, integer, integer, boolean, boolean, text)
-- node to node with restrictions

pgr_trsp(text, integer, double precision, integer, double precision,
boolean, boolean)
-- edge to edge

pgr_trsp(text, integer, double precision, integer, double precision,
boolean, boolean, text)
-- edge to edge with restrictions

pgr_trsp(text, integer, boolean, boolean, text)
-- array of nodes **this gets changed to use new code (1)**

pgr_trsp(text, integer, float8, boolean, boolean, text)
-- array of edges **this gets changed to use new code (2)**

(1) should plug directly into your code. I currently do this in C by
calling your old code multiple times, but it will be more efficient to
change this to call multi_dijkstra because we only build the graph once.

(2) I currently do this in C by making multiple calls to your old code.
The multi_dijkstra only accepts nodes, not edges, so I'll look at making
a version that can be called by edges. Unless you want to do that

Then I think I would like to add a new argument to (1) and (2) above
"boolean onetomany" and if it is true then we compute A-B, A-C, A-D, ...
and if it is false it will compute A-B-C-...

I'll have to think about how to return the results, but that should not
be too hard.

TODO:

1. create function to support multi_dijkstra with edges
2. create new function onetomany_dijkstra for nodes
3. create new function onetomany_dijkstra for edges
4. update C code wrappers to support the above
5. develop test cases
6. write the documentation
7. check it in

Ok that is a bunch of work! Maybe I'll start with just getting (1) done
so it calls your new code, and write a test case for that. Then tackle
the rest.

Thoughts?

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

Helder_Alves · April 13, 2014, 3:50pm

Hi Steve,

Please consider this opportunity to consolidate current Dijkstra functions.

As you know, there are side situations where Dijkstra and KDijkstra are producing different results when that shouldn’t happen.

Maybe it’s time to merge everything into the same code base to be make it easier to tackle bugs and future improvements.

I can help with testing, if you want!

Thanks to all community!

–
Helder Alves

On Apr 13, 2014 2:41 PM, “Stephen Woodbridge” <woodbri@swoodbridge.com> wrote:

So a couple of more thoughts on refactoring TRSP. I think we can get away with having just two C wrapper functions:

to handle node input

to handle edge input

I think everything else can be handled as options in the plpgsql wrappers like:

a) input is always an array of nodes or edges
we can take two node arguments and create an array in psql wrapper
likewise for the start and end edge function

b) we can add an argument mode=n, where
0 - point to point
1 - one to many
2 - many to many

c) it might be useful to have an option costonly if you only want the cost and not all the edge info

d) restrictions are optional and can be passed as null if none

The only issue with this is that we currently return different result types if we are returning a single route versus returning multiple routes in the result. I think we can deal with this by always returning the multiple results structure from the C code and filtering the column out in the plpgsql wrapper function to support the existing functions

My goal is to minimize code duplication and to simplify the lower level code for consistency, supportability, and testing. Long term we might deprecate some of the plpgsql wrapper functions to simplify the documentation and to make it easier to work with.

Thoughts and input are welcome. I’m still in the planning stage for this but will short start coding something

Thanks,
-Steve

On 4/12/2014 8:28 PM, Stephen Woodbridge wrote:

Hi Roni,

I hope you and your family are doing well.
I am well but have been very busy. I’m between some contracts at the
moment and I am looking at the TRSP improvements you did quite a ways
back to add the reverse cost and routing from nodes A-B-C-…

Looking at multi_dijkstra it seems that I should be able to mimic that
code based on how you clean up after each route A-B to restart for B-C
and create a similar function that computes one to many destinations,
A-B, A-C, A-D, etc.

What do you think?

So for integrating this code, I probably need to implement a family of
additional functions like:

Existing functions:

pgr_trsp(text, integer, integer, boolean, boolean)
– node to node

pgr_trsp(text, integer, integer, boolean, boolean, text)
– node to node with restrictions

pgr_trsp(text, integer, double precision, integer, double precision,
boolean, boolean)
– edge to edge

pgr_trsp(text, integer, double precision, integer, double precision,
boolean, boolean, text)
– edge to edge with restrictions

pgr_trsp(text, integer, boolean, boolean, text)
– array of nodes this gets changed to use new code (1)

pgr_trsp(text, integer, float8, boolean, boolean, text)
– array of edges this gets changed to use new code (2)

(1) should plug directly into your code. I currently do this in C by
calling your old code multiple times, but it will be more efficient to
change this to call multi_dijkstra because we only build the graph once.

(2) I currently do this in C by making multiple calls to your old code.
The multi_dijkstra only accepts nodes, not edges, so I’ll look at making
a version that can be called by edges. Unless you want to do that

Then I think I would like to add a new argument to (1) and (2) above
“boolean onetomany” and if it is true then we compute A-B, A-C, A-D, …
and if it is false it will compute A-B-C-…

I’ll have to think about how to return the results, but that should not
be too hard.

TODO:

create function to support multi_dijkstra with edges

create new function onetomany_dijkstra for nodes

create new function onetomany_dijkstra for edges

update C code wrappers to support the above

develop test cases

write the documentation

check it in

Ok that is a bunch of work! Maybe I’ll start with just getting (1) done
so it calls your new code, and write a test case for that. Then tackle
the rest.

Thoughts?

-Steve

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

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

Ashraf_Hossain · April 13, 2014, 7:08pm

Dear Steve,

I am out of town in village, I will come back to you soon with my thoughts.

Regards

Roni

···

On Sun, Apr 13, 2014 at 6:28 AM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

Hi Roni,

I hope you and your family are doing well.
I am well but have been very busy. I’m between some contracts at the moment and I am looking at the TRSP improvements you did quite a ways back to add the reverse cost and routing from nodes A-B-C-…

Looking at multi_dijkstra it seems that I should be able to mimic that code based on how you clean up after each route A-B to restart for B-C and create a similar function that computes one to many destinations, A-B, A-C, A-D, etc.

What do you think?

So for integrating this code, I probably need to implement a family of additional functions like:

Existing functions:

pgr_trsp(text, integer, integer, boolean, boolean)
– node to node

pgr_trsp(text, integer, integer, boolean, boolean, text)
– node to node with restrictions

pgr_trsp(text, integer, double precision, integer, double precision, boolean, boolean)
– edge to edge

pgr_trsp(text, integer, double precision, integer, double precision, boolean, boolean, text)
– edge to edge with restrictions

pgr_trsp(text, integer, boolean, boolean, text)
– array of nodes this gets changed to use new code (1)

pgr_trsp(text, integer, float8, boolean, boolean, text)
– array of edges this gets changed to use new code (2)

(1) should plug directly into your code. I currently do this in C by calling your old code multiple times, but it will be more efficient to change this to call multi_dijkstra because we only build the graph once.

(2) I currently do this in C by making multiple calls to your old code. The multi_dijkstra only accepts nodes, not edges, so I’ll look at making a version that can be called by edges. Unless you want to do that

Then I think I would like to add a new argument to (1) and (2) above “boolean onetomany” and if it is true then we compute A-B, A-C, A-D, … and if it is false it will compute A-B-C-…

I’ll have to think about how to return the results, but that should not be too hard.

TODO:

create function to support multi_dijkstra with edges

create new function onetomany_dijkstra for nodes

create new function onetomany_dijkstra for edges

update C code wrappers to support the above

develop test cases

write the documentation

check it in

Ok that is a bunch of work! Maybe I’ll start with just getting (1) done so it calls your new code, and write a test case for that. Then tackle the rest.

Thoughts?

-Steve

Stephen_Woodbridge1 · April 14, 2014, 2:27pm

On 4/13/2014 3:08 PM, Ashraf Hossain wrote:

Dear Steve,
I am out of town in village, I will come back to you soon with my thoughts.

Hi Roni,

No problem, enjoy your time being mostly disconnected from the net

Looking at GraphDefinition.cpp, I'm thinking that a small refactoring might make it easier to deal with multi_dijkstra using edges versus nodes. Something along the lines of:

vector<int> GraphDefinition::makeVirtualNodes(vector<int> edge_ids, vector<double> edge_parts);

This could take a list of edges and position on the edges and create a vector of virtual nodes and add then to the graph and return vector of the new virtual node ids. Then in multi_dijkstra you can loop through these as the start and end nodes. If we only have one start and end then the existing code could be change to work with this vector.

And it would be easy to change or clone multi_dijkstra to add options for one_to_many and many_to_many loops.

We could also eliminate the existing edge to edge version of my_dijkstra or trivialize it to call multi_dijkstra where we pass it just a vector of the start and end points. This would remove redundant code and simplify testing and verification of the existing code.

Any thoughts on this when you have a chance to look over the code.

I'm not sure what the best way to do this in GraphDefinition. It looks like we have a few places where we check if(is<Start|End>Virtual) when evaluating restrictions because this gets a little trickier. If the node is a via point in the middle of a restriction, then we will continue on that edge as if there is no virtual node there, but if it is the first or last point in overall route we will treat it like the start or end case as we do now. In the case of one_to_many and many_to_many, the start and end points would get treated as they are now also.

I'm thinking that with these changes, we could potentially also replace pgr_dijkstra and pgr_kdijkstra with the trsp code so we have one common code base for

pgr_dijkstra() - pgr_trsp() point_to_point
pgr_kdijkstra() - pgr_trsp() one_to_many
pgr_makeDistanceMatrix() - pgr_trsp() many_to_many

We would be able to support turn restrictions or not with all these functions.

One question I have about trsp is when I do a dijkstra solution in Boost, I solve the whole graph so in the kdijkstra case (one_to_many) I make one solution of the graph and I can extract paths to the "many" end nodes in the graph rather than doing multiple solves like A-B, A-C, A-D, ...? Can we do the same (extract multiple end points) in trsp? If so then many_to_many becomes (N * one_to_many).

Hope this all makes some sense.

Thanks,
-Steve

Regards
Roni

On Sun, Apr 13, 2014 at 6:28 AM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    Hi Roni,

    I hope you and your family are doing well.
    I am well but have been very busy. I'm between some contracts at the
    moment and I am looking at the TRSP improvements you did quite a
    ways back to add the reverse cost and routing from nodes A-B-C-...

    Looking at multi_dijkstra it seems that I should be able to mimic
    that code based on how you clean up after each route A-B to restart
    for B-C and create a similar function that computes one to many
    destinations, A-B, A-C, A-D, etc.

    What do you think?

    So for integrating this code, I probably need to implement a family
    of additional functions like:

    Existing functions:

    pgr_trsp(text, integer, integer, boolean, boolean)
    -- node to node

    pgr_trsp(text, integer, integer, boolean, boolean, text)
    -- node to node with restrictions

    pgr_trsp(text, integer, double precision, integer, double precision,
    boolean, boolean)
    -- edge to edge

    pgr_trsp(text, integer, double precision, integer, double precision,
    boolean, boolean, text)
    -- edge to edge with restrictions

    pgr_trsp(text, integer, boolean, boolean, text)
    -- array of nodes **this gets changed to use new code (1)**

    pgr_trsp(text, integer, float8, boolean, boolean, text)
    -- array of edges **this gets changed to use new code (2)**

    (1) should plug directly into your code. I currently do this in C by
    calling your old code multiple times, but it will be more efficient
    to change this to call multi_dijkstra because we only build the
    graph once.

    (2) I currently do this in C by making multiple calls to your old
    code. The multi_dijkstra only accepts nodes, not edges, so I'll look
    at making a version that can be called by edges. Unless you want to
    do that

    Then I think I would like to add a new argument to (1) and (2) above
    "boolean onetomany" and if it is true then we compute A-B, A-C, A-D,
    ... and if it is false it will compute A-B-C-...

    I'll have to think about how to return the results, but that should
    not be too hard.

    TODO:

    1. create function to support multi_dijkstra with edges
    2. create new function onetomany_dijkstra for nodes
    3. create new function onetomany_dijkstra for edges
    4. update C code wrappers to support the above
    5. develop test cases
    6. write the documentation
    7. check it in

    Ok that is a bunch of work! Maybe I'll start with just getting (1)
    done so it calls your new code, and write a test case for that. Then
    tackle the rest.

    Thoughts?

    -Steve

Helder_Alves · May 5, 2014, 7:33am

Hi Steve and all!

Do you have any advance on this matter?

Thanks!

–
Helder Alves

On Apr 14, 2014 4:05 PM, “Stephen Woodbridge” <woodbri@swoodbridge.com> wrote:

On 4/13/2014 3:08 PM, Ashraf Hossain wrote:

Dear Steve,
I am out of town in village, I will come back to you soon with my thoughts.

Hi Roni,

No problem, enjoy your time being mostly disconnected from the net

Looking at GraphDefinition.cpp, I’m thinking that a small refactoring might make it easier to deal with multi_dijkstra using edges versus nodes. Something along the lines of:

vector GraphDefinition::makeVirtualNodes(vector edge_ids, vector edge_parts);

This could take a list of edges and position on the edges and create a vector of virtual nodes and add then to the graph and return vector of the new virtual node ids. Then in multi_dijkstra you can loop through these as the start and end nodes. If we only have one start and end then the existing code could be change to work with this vector.

And it would be easy to change or clone multi_dijkstra to add options for one_to_many and many_to_many loops.

We could also eliminate the existing edge to edge version of my_dijkstra or trivialize it to call multi_dijkstra where we pass it just a vector of the start and end points. This would remove redundant code and simplify testing and verification of the existing code.

Any thoughts on this when you have a chance to look over the code.

I’m not sure what the best way to do this in GraphDefinition. It looks like we have a few places where we check if(is<Start|End>Virtual) when evaluating restrictions because this gets a little trickier. If the node is a via point in the middle of a restriction, then we will continue on that edge as if there is no virtual node there, but if it is the first or last point in overall route we will treat it like the start or end case as we do now. In the case of one_to_many and many_to_many, the start and end points would get treated as they are now also.

I’m thinking that with these changes, we could potentially also replace pgr_dijkstra and pgr_kdijkstra with the trsp code so we have one common code base for

pgr_dijkstra() - pgr_trsp() point_to_point
pgr_kdijkstra() - pgr_trsp() one_to_many
pgr_makeDistanceMatrix() - pgr_trsp() many_to_many

We would be able to support turn restrictions or not with all these functions.

One question I have about trsp is when I do a dijkstra solution in Boost, I solve the whole graph so in the kdijkstra case (one_to_many) I make one solution of the graph and I can extract paths to the “many” end nodes in the graph rather than doing multiple solves like A-B, A-C, A-D, …? Can we do the same (extract multiple end points) in trsp? If so then many_to_many becomes (N * one_to_many).

Hope this all makes some sense.

Thanks,
-Steve

Regards
Roni

On Sun, Apr 13, 2014 at 6:28 AM, Stephen Woodbridge
<woodbri@swoodbridge.com mailto:[woodbri@swoodbridge.com](mailto:woodbri@swoodbridge.com)> wrote:

Hi Roni,

I hope you and your family are doing well.
I am well but have been very busy. I’m between some contracts at the
moment and I am looking at the TRSP improvements you did quite a
ways back to add the reverse cost and routing from nodes A-B-C-…

Looking at multi_dijkstra it seems that I should be able to mimic
that code based on how you clean up after each route A-B to restart
for B-C and create a similar function that computes one to many
destinations, A-B, A-C, A-D, etc.

What do you think?

So for integrating this code, I probably need to implement a family
of additional functions like:

Existing functions:

pgr_trsp(text, integer, integer, boolean, boolean)
– node to node

pgr_trsp(text, integer, integer, boolean, boolean, text)
– node to node with restrictions

pgr_trsp(text, integer, double precision, integer, double precision,
boolean, boolean)
– edge to edge

pgr_trsp(text, integer, double precision, integer, double precision,
boolean, boolean, text)
– edge to edge with restrictions

pgr_trsp(text, integer, boolean, boolean, text)
– array of nodes this gets changed to use new code (1)

pgr_trsp(text, integer, float8, boolean, boolean, text)
– array of edges this gets changed to use new code (2)

(1) should plug directly into your code. I currently do this in C by
calling your old code multiple times, but it will be more efficient
to change this to call multi_dijkstra because we only build the
graph once.

(2) I currently do this in C by making multiple calls to your old
code. The multi_dijkstra only accepts nodes, not edges, so I’ll look
at making a version that can be called by edges. Unless you want to
do that

Then I think I would like to add a new argument to (1) and (2) above
“boolean onetomany” and if it is true then we compute A-B, A-C, A-D,
… and if it is false it will compute A-B-C-…

I’ll have to think about how to return the results, but that should
not be too hard.

TODO:

create function to support multi_dijkstra with edges

create new function onetomany_dijkstra for nodes

create new function onetomany_dijkstra for edges

update C code wrappers to support the above

develop test cases

write the documentation

check it in

Ok that is a bunch of work! Maybe I’ll start with just getting (1)
done so it calls your new code, and write a test case for that. Then
tackle the rest.

Thoughts?

-Steve

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

Stephen_Woodbridge1 · May 6, 2014, 3:22am

Hi Helder,

I discussed this with Roni and my approach is probably reasonable but there are a lot of details and corner cases that need to be dealt with. So I will probably leave these changes to Roni as he has a beter handle on it than I do. He is hoping to have some time this summer to work on this.

So I checked in his code fixes and enhancements into the develop branch. The enhancements only have the C++ code in GraphDefinition.{cpp,h} but this has not be exposed to the SQl yet because I think we should do this as part of making a clean consistent interface. You can see I started to work this out in the discussion below. But didn't get much further than that.

-Steve

On 5/5/2014 3:33 AM, Helder Alves wrote:

Hi Steve and all!

Do you have any advance on this matter?

Thanks!

--
Helder Alves

On Apr 14, 2014 4:05 PM, "Stephen Woodbridge" <woodbri@swoodbridge.com
<mailto:woodbri@swoodbridge.com>> wrote:

    On 4/13/2014 3:08 PM, Ashraf Hossain wrote:

        Dear Steve,
        I am out of town in village, I will come back to you soon with
        my thoughts.

    Hi Roni,

    No problem, enjoy your time being mostly disconnected from the net

    Looking at GraphDefinition.cpp, I'm thinking that a small
    refactoring might make it easier to deal with multi_dijkstra using
    edges versus nodes. Something along the lines of:

    vector<int> GraphDefinition::__makeVirtualNodes(vector<int>
    edge_ids, vector<double> edge_parts);

    This could take a list of edges and position on the edges and create
    a vector of virtual nodes and add then to the graph and return
    vector of the new virtual node ids. Then in multi_dijkstra you can
    loop through these as the start and end nodes. If we only have one
    start and end then the existing code could be change to work with
    this vector.

    And it would be easy to change or clone multi_dijkstra to add
    options for one_to_many and many_to_many loops.

    We could also eliminate the existing edge to edge version of
    my_dijkstra or trivialize it to call multi_dijkstra where we pass it
    just a vector of the start and end points. This would remove
    redundant code and simplify testing and verification of the existing
    code.

    Any thoughts on this when you have a chance to look over the code.

    I'm not sure what the best way to do this in GraphDefinition. It
    looks like we have a few places where we check
    if(is<Start|End>Virtual) when evaluating restrictions because this
    gets a little trickier. If the node is a via point in the middle of
    a restriction, then we will continue on that edge as if there is no
    virtual node there, but if it is the first or last point in overall
    route we will treat it like the start or end case as we do now. In
    the case of one_to_many and many_to_many, the start and end points
    would get treated as they are now also.

    I'm thinking that with these changes, we could potentially also
    replace pgr_dijkstra and pgr_kdijkstra with the trsp code so we have
    one common code base for

    pgr_dijkstra() - pgr_trsp() point_to_point
    pgr_kdijkstra() - pgr_trsp() one_to_many
    pgr_makeDistanceMatrix() - pgr_trsp() many_to_many

    We would be able to support turn restrictions or not with all these
    functions.

    One question I have about trsp is when I do a dijkstra solution in
    Boost, I solve the whole graph so in the kdijkstra case
    (one_to_many) I make one solution of the graph and I can extract
    paths to the "many" end nodes in the graph rather than doing
    multiple solves like A-B, A-C, A-D, ...? Can we do the same (extract
    multiple end points) in trsp? If so then many_to_many becomes (N *
    one_to_many).

    Hope this all makes some sense.

    Thanks,
       -Steve

        Regards
        Roni

        On Sun, Apr 13, 2014 at 6:28 AM, Stephen Woodbridge
        <woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>
        <mailto:woodbri@swoodbridge.__com
        <mailto:woodbri@swoodbridge.com>>> wrote:

             Hi Roni,

             I hope you and your family are doing well.
             I am well but have been very busy. I'm between some
        contracts at the
             moment and I am looking at the TRSP improvements you did
        quite a
             ways back to add the reverse cost and routing from nodes
        A-B-C-...

             Looking at multi_dijkstra it seems that I should be able to
        mimic
             that code based on how you clean up after each route A-B to
        restart
             for B-C and create a similar function that computes one to many
             destinations, A-B, A-C, A-D, etc.

             What do you think?

             So for integrating this code, I probably need to implement
        a family
             of additional functions like:

             Existing functions:

             pgr_trsp(text, integer, integer, boolean, boolean)
             -- node to node

             pgr_trsp(text, integer, integer, boolean, boolean, text)
             -- node to node with restrictions

             pgr_trsp(text, integer, double precision, integer, double
        precision,
             boolean, boolean)
             -- edge to edge

             pgr_trsp(text, integer, double precision, integer, double
        precision,
             boolean, boolean, text)
             -- edge to edge with restrictions

             pgr_trsp(text, integer, boolean, boolean, text)
             -- array of nodes **this gets changed to use new code (1)**

             pgr_trsp(text, integer, float8, boolean, boolean, text)
             -- array of edges **this gets changed to use new code (2)**

             (1) should plug directly into your code. I currently do
        this in C by
             calling your old code multiple times, but it will be more
        efficient
             to change this to call multi_dijkstra because we only build the
             graph once.

             (2) I currently do this in C by making multiple calls to
        your old
             code. The multi_dijkstra only accepts nodes, not edges, so
        I'll look
             at making a version that can be called by edges. Unless you
        want to
             do that

             Then I think I would like to add a new argument to (1) and
        (2) above
             "boolean onetomany" and if it is true then we compute A-B,
        A-C, A-D,
             ... and if it is false it will compute A-B-C-...

             I'll have to think about how to return the results, but
        that should
             not be too hard.

             TODO:

             1. create function to support multi_dijkstra with edges
             2. create new function onetomany_dijkstra for nodes
             3. create new function onetomany_dijkstra for edges
             4. update C code wrappers to support the above
             5. develop test cases
             6. write the documentation
             7. check it in

             Ok that is a bunch of work! Maybe I'll start with just
        getting (1)
             done so it calls your new code, and write a test case for
        that. Then
             tackle the rest.

             Thoughts?

             -Steve

    _________________________________________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/__mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

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