[pgrouting-dev] Finally getting back to integrating your TRSP improvements
Stephen Woodbridge
woodbri at swoodbridge.com
Mon May 5 20:22:40 PDT 2014
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 at swoodbridge.com
> <mailto:woodbri at 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 at swoodbridge.com <mailto:woodbri at swoodbridge.com>
> <mailto:woodbri at swoodbridge.__com
> <mailto:woodbri at 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 at lists.osgeo.org <mailto:pgrouting-dev at 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 at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
More information about the pgrouting-dev
mailing list