[pgrouting-dev] Scheduled Routing Algorithm

Kishore_Kumar · June 27, 2011, 9:40pm

Hi,

After reading on Contraction Hierarchies[1] and APSP algorithms, I
came up with a plan to find the scheduled route. Here goes the plan:

* Pre-compute Shortest Time Graph for Directly reachable pair of stops
by going through every trip in a loop.
* Find Shortest Time Graph from every stop to every other
stop(Transitive closure) using APSP.
* Use Boost astar_search_no_init[2] function passing an Implicit
Graph[3] G with following definitions:
     Vertex : (Stop, Time)
     Edge : Trip
     Edge weight : Travel Time + Waiting Time
     Heuristic : Shortest Time from Trip destination to Target
* As Every Vertex is expanded, new Vertices and Edges are generated
for trips in the next 1 hour(or whatever is the Upper limit for
Waiting time).

I didn't find any examples using astar_search_no_init function. [4]
solves 8-puzzle problem using Implicit Graph for astar_search
function, but it uses astar_search function with a hacked BFS code.
So, it is going to be a challenge to code this out using BGL.

Please advise on ways to improve the algorithm.

Thanks,
J Kishore kumar.

[1] - http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf
[2] - http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html
[3] - http://en.wikipedia.org/wiki/Implicit_graph
[4] - http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf

Stephen_Woodbridge1 · June 27, 2011, 10:06pm

Hi Kishore,

I not sure I can improve on this algorithm as I'm do not think I have followed all the details and issues in implementing it. But I do have two thoughts:

1. if you are not on the boost-users mailing list [1] them you should subscribe to that list and ask questions about how to best tackle some of the boost problems you are facing. In the Subject: add the tag "[BGL]" to indicate this is a Boost Graph Library question and the developers are very helpful and responsive to question.

2. often I find that it is useful to transform my problem into another problem that has a simpler or known solution. It seems like you should be able to do this with your problem. If I understand it correct (and I confess I might not), It seems that your frequency problem could be transformed into a straight scheduling problem if your transfer is just a waiting time at a transfer point. One simple way to represent these transfer times is to add an additional edge that has the cost of the transfer associated to it.

So if we think about the route like, I start at a bus station at some time X, and there is some transfer cost representing the wait time W window. so I'm now on the the bus route at X+W+edge cost, and I continue accumulating wait times and edge costs as I trasfer between lines and travel the network to my destination. If this works, then this is just a straight time dependent solution but the trick is to analyze the data and create a network suitable for this type of solution.

[1] http://lists.boost.org/mailman/listinfo.cgi/boost-users

-Steve

On 6/27/2011 5:40 PM, Kishore Kumar wrote:

Hi,

After reading on Contraction Hierarchies[1] and APSP algorithms, I
came up with a plan to find the scheduled route. Here goes the plan:

* Pre-compute Shortest Time Graph for Directly reachable pair of stops
by going through every trip in a loop.
* Find Shortest Time Graph from every stop to every other
stop(Transitive closure) using APSP.
* Use Boost astar_search_no_init[2] function passing an Implicit
Graph[3] G with following definitions:
      Vertex : (Stop, Time)
      Edge : Trip
      Edge weight : Travel Time + Waiting Time
      Heuristic : Shortest Time from Trip destination to Target
* As Every Vertex is expanded, new Vertices and Edges are generated
for trips in the next 1 hour(or whatever is the Upper limit for
Waiting time).

I didn't find any examples using astar_search_no_init function. [4]
solves 8-puzzle problem using Implicit Graph for astar_search
function, but it uses astar_search function with a hacked BFS code.
So, it is going to be a challenge to code this out using BGL.

Please advise on ways to improve the algorithm.

Thanks,
J Kishore kumar.

[1] - http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf
[2] - http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html
[3] - http://en.wikipedia.org/wiki/Implicit_graph
[4] - http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf
_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

Kishore_Kumar · July 9, 2011, 3:17pm

Hi,

I commited the code[1] that implements the scheduled route using
modified boost astar search and Implicit graph. And, I have an issue
now:
1. The modified astar and breadth first search boost header files are
copied from Boost Version 1.46.1. I intent to test it on earlier boost
libraries. But, what is the best approach to handle this scenario?
Should we notify boost developers about having a non-const version to
support Implicit Graphs?

Thanks,
J Kishore kumar.

[1] - https://github.com/pgRouting/pgrouting/commit/3aa2b4e951c584fa3ae03235f7b2e06379cbb229

On Tue, Jun 28, 2011 at 3:36 AM, Stephen Woodbridge
<woodbri@swoodbridge.com> wrote:

Hi Kishore,

I not sure I can improve on this algorithm as I'm do not think I have
followed all the details and issues in implementing it. But I do have two
thoughts:

1. if you are not on the boost-users mailing list [1] them you should
subscribe to that list and ask questions about how to best tackle some of
the boost problems you are facing. In the Subject: add the tag "[BGL]" to
indicate this is a Boost Graph Library question and the developers are very
helpful and responsive to question.

2. often I find that it is useful to transform my problem into another
problem that has a simpler or known solution. It seems like you should be
able to do this with your problem. If I understand it correct (and I confess
I might not), It seems that your frequency problem could be transformed into
a straight scheduling problem if your transfer is just a waiting time at a
transfer point. One simple way to represent these transfer times is to add
an additional edge that has the cost of the transfer associated to it.

So if we think about the route like, I start at a bus station at some time
X, and there is some transfer cost representing the wait time W window. so
I'm now on the the bus route at X+W+edge cost, and I continue accumulating
wait times and edge costs as I trasfer between lines and travel the network
to my destination. If this works, then this is just a straight time
dependent solution but the trick is to analyze the data and create a network
suitable for this type of solution.

[1] http://lists.boost.org/mailman/listinfo.cgi/boost-users

-Steve

On 6/27/2011 5:40 PM, Kishore Kumar wrote:

Hi,

After reading on Contraction Hierarchies[1] and APSP algorithms, I
came up with a plan to find the scheduled route. Here goes the plan:

* Pre-compute Shortest Time Graph for Directly reachable pair of stops
by going through every trip in a loop.
* Find Shortest Time Graph from every stop to every other
stop(Transitive closure) using APSP.
* Use Boost astar_search_no_init[2] function passing an Implicit
Graph[3] G with following definitions:
Vertex : (Stop, Time)
Edge : Trip
Edge weight : Travel Time + Waiting Time
Heuristic : Shortest Time from Trip destination to Target
* As Every Vertex is expanded, new Vertices and Edges are generated
for trips in the next 1 hour(or whatever is the Upper limit for
Waiting time).

I didn't find any examples using astar_search_no_init function. [4]
solves 8-puzzle problem using Implicit Graph for astar_search
function, but it uses astar_search function with a hacked BFS code.
So, it is going to be a challenge to code this out using BGL.

Please advise on ways to improve the algorithm.

Thanks,
J Kishore kumar.

[1] - http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf
[2] -
http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html
[3] - http://en.wikipedia.org/wiki/Implicit_graph
[4] - http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf
_______________________________________________
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

Kishore_Kumar · August 10, 2011, 12:27pm

Hi,
Prepared this diagram(attached) depicting the file structure and flow
of control of scheduled routing algorithm. Currently the code works
for GTFS Trips with fixed timetable(Eg:Train). To make it multi-modal,
it has to support GTFS Trips with only frequency information(Eg:Bus)
and private transit(Eg:Walk, Cycle). The existing scheduled routing
can be extended a little by also including trips which have frequency
information only. And, for walking to be private transit options,
since the speed of transit is going to be a constant, the straight
line distance from X to goal divided by constant velocity will give
the shortest time heuristic. Hence, I'll possibly finish it in a day
or two.

Once that is finished, I'll start writing documentation, tests and
demo implementations at http://busroutemaps.in/ and of course, Code
cleanup and optimisations.

Thanks,
J Kishore kumar.

On Sat, Jul 9, 2011 at 8:47 PM, Kishore Kumar <justjkk@gmail.com> wrote:

Hi,

I commited the code[1] that implements the scheduled route using
modified boost astar search and Implicit graph. And, I have an issue
now:
1. The modified astar and breadth first search boost header files are
copied from Boost Version 1.46.1. I intent to test it on earlier boost
libraries. But, what is the best approach to handle this scenario?
Should we notify boost developers about having a non-const version to
support Implicit Graphs?

Thanks,
J Kishore kumar.

[1] - https://github.com/pgRouting/pgrouting/commit/3aa2b4e951c584fa3ae03235f7b2e06379cbb229

On Tue, Jun 28, 2011 at 3:36 AM, Stephen Woodbridge
<woodbri@swoodbridge.com> wrote:

Hi Kishore,

I not sure I can improve on this algorithm as I'm do not think I have
followed all the details and issues in implementing it. But I do have two
thoughts:

1. if you are not on the boost-users mailing list [1] them you should
subscribe to that list and ask questions about how to best tackle some of
the boost problems you are facing. In the Subject: add the tag "[BGL]" to
indicate this is a Boost Graph Library question and the developers are very
helpful and responsive to question.

2. often I find that it is useful to transform my problem into another
problem that has a simpler or known solution. It seems like you should be
able to do this with your problem. If I understand it correct (and I confess
I might not), It seems that your frequency problem could be transformed into
a straight scheduling problem if your transfer is just a waiting time at a
transfer point. One simple way to represent these transfer times is to add
an additional edge that has the cost of the transfer associated to it.

So if we think about the route like, I start at a bus station at some time
X, and there is some transfer cost representing the wait time W window. so
I'm now on the the bus route at X+W+edge cost, and I continue accumulating
wait times and edge costs as I trasfer between lines and travel the network
to my destination. If this works, then this is just a straight time
dependent solution but the trick is to analyze the data and create a network
suitable for this type of solution.

[1] http://lists.boost.org/mailman/listinfo.cgi/boost-users

-Steve

On 6/27/2011 5:40 PM, Kishore Kumar wrote:

Hi,

After reading on Contraction Hierarchies[1] and APSP algorithms, I
came up with a plan to find the scheduled route. Here goes the plan:

* Pre-compute Shortest Time Graph for Directly reachable pair of stops
by going through every trip in a loop.
* Find Shortest Time Graph from every stop to every other
stop(Transitive closure) using APSP.
* Use Boost astar_search_no_init[2] function passing an Implicit
Graph[3] G with following definitions:
Vertex : (Stop, Time)
Edge : Trip
Edge weight : Travel Time + Waiting Time
Heuristic : Shortest Time from Trip destination to Target
* As Every Vertex is expanded, new Vertices and Edges are generated
for trips in the next 1 hour(or whatever is the Upper limit for
Waiting time).

I didn't find any examples using astar_search_no_init function. [4]
solves 8-puzzle problem using Implicit Graph for astar_search
function, but it uses astar_search function with a hacked BFS code.
So, it is going to be a challenge to code this out using BGL.

Please advise on ways to improve the algorithm.

Thanks,
J Kishore kumar.

[1] - http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf
[2] -
http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html
[3] - http://en.wikipedia.org/wiki/Implicit_graph
[4] - http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf
_______________________________________________
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

mmptr_flowchart.pdf (57 KB)

Stephen_Woodbridge1 · August 10, 2011, 12:40pm

Hi Kishore,

Very nice diagram! This really helps me understand more of what you have been doing in this project and how the scheduled routing works.

Thanks,
-Steve

On 8/10/2011 8:27 AM, Kishore Kumar wrote:

Hi,
Prepared this diagram(attached) depicting the file structure and flow
of control of scheduled routing algorithm. Currently the code works
for GTFS Trips with fixed timetable(Eg:Train). To make it multi-modal,
it has to support GTFS Trips with only frequency information(Eg:Bus)
and private transit(Eg:Walk, Cycle). The existing scheduled routing
can be extended a little by also including trips which have frequency
information only. And, for walking to be private transit options,
since the speed of transit is going to be a constant, the straight
line distance from X to goal divided by constant velocity will give
the shortest time heuristic. Hence, I'll possibly finish it in a day
or two.

Once that is finished, I'll start writing documentation, tests and
demo implementations at http://busroutemaps.in/ and of course, Code
cleanup and optimisations.

Thanks,
J Kishore kumar.

On Sat, Jul 9, 2011 at 8:47 PM, Kishore Kumar<justjkk@gmail.com> wrote:

Hi,

I commited the code[1] that implements the scheduled route using
modified boost astar search and Implicit graph. And, I have an issue
now:
1. The modified astar and breadth first search boost header files are
copied from Boost Version 1.46.1. I intent to test it on earlier boost
libraries. But, what is the best approach to handle this scenario?
Should we notify boost developers about having a non-const version to
support Implicit Graphs?

Thanks,
J Kishore kumar.

[1] - https://github.com/pgRouting/pgrouting/commit/3aa2b4e951c584fa3ae03235f7b2e06379cbb229

On Tue, Jun 28, 2011 at 3:36 AM, Stephen Woodbridge
<woodbri@swoodbridge.com> wrote:

Hi Kishore,

I not sure I can improve on this algorithm as I'm do not think I have
followed all the details and issues in implementing it. But I do have two
thoughts:

1. if you are not on the boost-users mailing list [1] them you should
subscribe to that list and ask questions about how to best tackle some of
the boost problems you are facing. In the Subject: add the tag "[BGL]" to
indicate this is a Boost Graph Library question and the developers are very
helpful and responsive to question.

2. often I find that it is useful to transform my problem into another
problem that has a simpler or known solution. It seems like you should be
able to do this with your problem. If I understand it correct (and I confess
I might not), It seems that your frequency problem could be transformed into
a straight scheduling problem if your transfer is just a waiting time at a
transfer point. One simple way to represent these transfer times is to add
an additional edge that has the cost of the transfer associated to it.

So if we think about the route like, I start at a bus station at some time
X, and there is some transfer cost representing the wait time W window. so
I'm now on the the bus route at X+W+edge cost, and I continue accumulating
wait times and edge costs as I trasfer between lines and travel the network
to my destination. If this works, then this is just a straight time
dependent solution but the trick is to analyze the data and create a network
suitable for this type of solution.

[1] http://lists.boost.org/mailman/listinfo.cgi/boost-users

-Steve

On 6/27/2011 5:40 PM, Kishore Kumar wrote:

Hi,

After reading on Contraction Hierarchies[1] and APSP algorithms, I
came up with a plan to find the scheduled route. Here goes the plan:

* Pre-compute Shortest Time Graph for Directly reachable pair of stops
by going through every trip in a loop.
* Find Shortest Time Graph from every stop to every other
stop(Transitive closure) using APSP.
* Use Boost astar_search_no_init[2] function passing an Implicit
Graph[3] G with following definitions:
      Vertex : (Stop, Time)
      Edge : Trip
      Edge weight : Travel Time + Waiting Time
      Heuristic : Shortest Time from Trip destination to Target
* As Every Vertex is expanded, new Vertices and Edges are generated
for trips in the next 1 hour(or whatever is the Upper limit for
Waiting time).

I didn't find any examples using astar_search_no_init function. [4]
solves 8-puzzle problem using Implicit Graph for astar_search
function, but it uses astar_search function with a hacked BFS code.
So, it is going to be a challenge to code this out using BGL.

Please advise on ways to improve the algorithm.

Thanks,
J Kishore kumar.

[1] - http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf
[2] -
http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html
[3] - http://en.wikipedia.org/wiki/Implicit_graph
[4] - http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf
_______________________________________________
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

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

Jay_Mahadeokar · August 12, 2011, 7:07pm

Hi Kishore,

I read your report and saw the APSP_Johnson implementation. The prototype is:


CREATE OR REPLACE FUNCTION apsp_johnson(sql text)

         RETURNS SETOF apsp_edge

         AS '$libdir/librouting'
         LANGUAGE 'C' IMMUTABLE STRICT;

I guess this serves the same function as the apsp algorithm we already have[1].

I think for your application, you need APSP for all vertices in the database table. So, if you use:

SELECT * from all_pairs_shortest_path

    ('SELECT gid as id,source::integer,target::integer,length::double precision as cost 
    from ways where source in (select distinct(source) from ways)'::TEXT

    ,false,false);

it will solve your query. Please correct me if I am wrong, or any additional information is needed.

Also, Daniel, Steve -

Should we change my apsp implementation so that it gives option to use either johnsons boost implementation or warshall boost implementation? That would provide more options?

[1] [https://github.com/pgRouting/pgrouting/wiki/APSP](https://github.com/pgRouting/pgrouting/wiki/APSP)

On Wed, Aug 10, 2011 at 6:10 PM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

Hi Kishore,

Very nice diagram! This really helps me understand more of what you have been doing in this project and how the scheduled routing works.

Thanks,
-Steve

On 8/10/2011 8:27 AM, Kishore Kumar wrote:

Hi,
Prepared this diagram(attached) depicting the file structure and flow
of control of scheduled routing algorithm. Currently the code works
for GTFS Trips with fixed timetable(Eg:Train). To make it multi-modal,
it has to support GTFS Trips with only frequency information(Eg:Bus)
and private transit(Eg:Walk, Cycle). The existing scheduled routing
can be extended a little by also including trips which have frequency
information only. And, for walking to be private transit options,
since the speed of transit is going to be a constant, the straight
line distance from X to goal divided by constant velocity will give
the shortest time heuristic. Hence, I’ll possibly finish it in a day
or two.

Once that is finished, I’ll start writing documentation, tests and
demo implementations at http://busroutemaps.in/ and of course, Code
cleanup and optimisations.

Thanks,
J Kishore kumar.

On Sat, Jul 9, 2011 at 8:47 PM, Kishore Kumar<justjkk@gmail.com> wrote:

Hi,

I commited the code[1] that implements the scheduled route using
modified boost astar search and Implicit graph. And, I have an issue
now:

The modified astar and breadth first search boost header files are
copied from Boost Version 1.46.1. I intent to test it on earlier boost
libraries. But, what is the best approach to handle this scenario?
Should we notify boost developers about having a non-const version to
support Implicit Graphs?

Thanks,
J Kishore kumar.

[1] - https://github.com/pgRouting/pgrouting/commit/3aa2b4e951c584fa3ae03235f7b2e06379cbb229

On Tue, Jun 28, 2011 at 3:36 AM, Stephen Woodbridge
<woodbri@swoodbridge.com> wrote:

Hi Kishore,

I not sure I can improve on this algorithm as I’m do not think I have
followed all the details and issues in implementing it. But I do have two
thoughts:

if you are not on the boost-users mailing list [1] them you should
subscribe to that list and ask questions about how to best tackle some of
the boost problems you are facing. In the Subject: add the tag “[BGL]” to
indicate this is a Boost Graph Library question and the developers are very
helpful and responsive to question.

often I find that it is useful to transform my problem into another
problem that has a simpler or known solution. It seems like you should be
able to do this with your problem. If I understand it correct (and I confess
I might not), It seems that your frequency problem could be transformed into
a straight scheduling problem if your transfer is just a waiting time at a
transfer point. One simple way to represent these transfer times is to add
an additional edge that has the cost of the transfer associated to it.

So if we think about the route like, I start at a bus station at some time
X, and there is some transfer cost representing the wait time W window. so
I’m now on the the bus route at X+W+edge cost, and I continue accumulating
wait times and edge costs as I trasfer between lines and travel the network
to my destination. If this works, then this is just a straight time
dependent solution but the trick is to analyze the data and create a network
suitable for this type of solution.

[1] http://lists.boost.org/mailman/listinfo.cgi/boost-users

-Steve

On 6/27/2011 5:40 PM, Kishore Kumar wrote:

Hi,

After reading on Contraction Hierarchies[1] and APSP algorithms, I
came up with a plan to find the scheduled route. Here goes the plan:

Pre-compute Shortest Time Graph for Directly reachable pair of stops
by going through every trip in a loop.

Find Shortest Time Graph from every stop to every other
stop(Transitive closure) using APSP.

Use Boost astar_search_no_init[2] function passing an Implicit
Graph[3] G with following definitions:
Vertex : (Stop, Time)
Edge : Trip
Edge weight : Travel Time + Waiting Time
Heuristic : Shortest Time from Trip destination to Target

As Every Vertex is expanded, new Vertices and Edges are generated
for trips in the next 1 hour(or whatever is the Upper limit for
Waiting time).

I didn’t find any examples using astar_search_no_init function. [4]
solves 8-puzzle problem using Implicit Graph for astar_search
function, but it uses astar_search function with a hacked BFS code.
So, it is going to be a challenge to code this out using BGL.

Please advise on ways to improve the algorithm.

Thanks,
J Kishore kumar.

[1] - http://algo2.iti.kit.edu/documents/routeplanning/geisberger_dipl.pdf
[2] -
http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/astar_search.html
[3] - http://en.wikipedia.org/wiki/Implicit_graph
[4] - http://www.cs.rpi.edu/~beevek/research/astar_bgl04.pdf

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

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

–
Regards,
-Jay Mahadeokar

dkastl · August 12, 2011, 10:25pm

On Sat, Aug 13, 2011 at 4:07 AM, Jay Mahadeokar <jai.mahadeokar@gmail.com> wrote:

Hi Kishore,

I read your report and saw the APSP_Johnson implementation. The prototype is:
CREATE OR REPLACE FUNCTION apsp_johnson(sql text)

         RETURNS SETOF apsp_edge

         AS '$libdir/librouting'
         LANGUAGE 'C' IMMUTABLE STRICT;
I guess this serves the same function as the apsp algorithm we already have[1].

I think for your application, you need APSP for all vertices in the database table. So, if you use:
SELECT * from all_pairs_shortest_path

    ('SELECT gid as id,source::integer,target::integer,length::double precision as cost 
    from ways where source in (select distinct(source) from ways)'::TEXT

    ,false,false);
it will solve your query. Please correct me if I am wrong, or any additional information is needed.

Also, Daniel, Steve -

Should we change my apsp implementation so that it gives option to use either johnsons boost implementation or warshall boost implementation? That would provide more options?
[1] [https://github.com/pgRouting/pgrouting/wiki/APSP](https://github.com/pgRouting/pgrouting/wiki/APSP)

Hi Jay,

Thank you very much for looking into this and for your comments! That’s very valuable input.

Is it complicated to add this options?
If it’s not difficult, it would be nice to able to specify it as an option.

Daniel

–
Regards,
-Jay Mahadeokar

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

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de