[pgrouting-dev] pgr_dijkstra(edges_sql, combinations_sql)

Tue May 19 14:34:29 PDT 2020

Hello Mahmoud,

When you have the repository ready we can make an appointment to check what
needs to be done.
Right now I am still working on the release of 3.0.0, some PR I need to
merge, then I will be able to make the release, and
get the develop branch ready for accepting PR merges.
By the way, I am not the only developer please subscribe to the
https://lists.osgeo.org/mailman/listinfo/pgrouting-dev
So that everyone knows what we are doing.

Regards

On Tue, May 19, 2020 at 8:22 AM Vicky Vergara <vicky at georepublic.de> wrote:

>
>
> ---------- Forwarded message ---------
> From: Mahmoud Sakr <m_attia_sakr at yahoo.com>
> Date: Tue, May 19, 2020 at 7:26 AM
> Subject: pgr_dijkstra(edges_sql, combinations_sql)
> To: Esteban Zimanyi <estebanzimanyi at gmail.com>, Vicky Vergara <
> vicky at georepublic.de>
> Cc: Arthur Lesuisse <alesuiss at gmail.com>
>
>
> Hi Vicky,
> The new signature is working now.
> The tests are quite impressive. Here I summarize the results, while the
> test queries are given below. Two tests have been done: speed/scalability,
> and correctness. The speed/scalability test shows that the new signature
> scales linearly, and can afford a big number of (source, target)
> combinations. It was possible to test up to 1e5 combinations. The 1e6 test
> ran out of memory. I think that the reason is that the size of the result
> is too big for the memory. The correctness test shows that the result is
> exactly the same as what one would get using multiple calls to
> pgr_dijkstra(edges, source, target).
>
> In another email, I'll share the git repository with you. Please guide us
> in the following:
> - what kind of testing shall be needed, and how to integrate it with the
> repository.
> - how to manage our fork, to ease the merge with pgRouting. The steps done
> so far: fork -> branch 'combinationsSQL' -> multiple push -> merge into
> master
> - what kind of documentation shall be needed, and how to integrate it
> with the repository. In the code, I copied the coding and commenting styles
> as good as I could observe.
>
> best regards,
> Mahmoud
>
>
>
> --------------------Speed/scalability test:
>
> do $$
> declare
>     i int;
>     count bigint;
>     startTime timestamptz;
>     endTime timestamptz;
> begin
>     for i in 0..100000 BY 10000 loop
>         DROP TABLE IF EXISTS temp;
>         CREATE TABLE temp AS (
>             select s.id as source, t.id as target
>             from nodes s, nodes t
>             limit i
>         );
>         SELECT clock_timestamp() INTO startTime;
> --> begin
>         PERFORM count(*)
>         FROM pgr_dijkstra(
>             'SELECT id, source, target, cost_s AS cost, reverse_cost_s as
> reverse_cost FROM edges',
>             'SELECT source, target FROM temp', true);
> --> end
>         SELECT clock_timestamp() INTO endTime;
>         raise notice 'count = %, time = %', i, endTime - startTime;
>     end loop;
> end; $$
>
>
> NOTICE: count = 0, time = 00:00:00.127069
> NOTICE: count = 10000, time = 00:00:04.514361
> NOTICE: count = 20000, time = 00:00:08.476031
> NOTICE: count = 30000, time = 00:00:11.895231
> NOTICE: count = 40000, time = 00:00:16.177429
> NOTICE: count = 50000, time = 00:00:19.482188
> NOTICE: count = 60000, time = 00:00:24.499867
> NOTICE: count = 70000, time = 00:00:34.240081
> NOTICE: count = 80000, time = 00:00:35.538692
> NOTICE: count = 90000, time = 00:00:44.128275
> NOTICE: count = 100000, time = 00:00:48.345672
>
> [image: Inline image]
>
>
> --------------------Correctness test:
>
> WITH solution1 AS(
> SELECT *
> FROM pgr_dijkstra(
>     'SELECT id, source, target, cost_s AS cost, reverse_cost_s as
> reverse_cost FROM edges',
>     'SELECT homeNode as source, workNode as target FROM Vehicle',
>     true)
> )
> , solution2 AS(
> SELECT * FROM
>     (SELECT * FROM Vehicle) V,
>     pgr_dijkstra(
>     'SELECT id, source, target, cost_s AS cost, reverse_cost_s as
> reverse_cost FROM edges',
>     V.homeNode, V.workNode, true) P
> )
> SELECT count(*) AS Joined,
>     (SELECT count(*) FROM solution1) AS NewSolution,
>     (SELECT count(*) FROM solution2) AS CurrentSolution
> FROM solution1 a, solution2 b
> WHERE a.start_vid = b.homeNode AND a.end_vid = b.workNode AND a.path_seq =
> b.path_seq
>
> --Successfully run. Total query runtime: 2 min 2 secs.
> --21121;    21121;    21121
>
>
>
> Best regards,
> Mahmoud Sakr
>
>
> On Monday, May 18, 2020, 5:52:42 PM GMT+2, Vicky Vergara <
> vicky at georepublic.de> wrote:
>
>
>
> https://drive.google.com/drive/u/0/folders/1uUWb-AtJGnckBDMBuFT_84ywksjoPALB
>
> On Sat, May 16, 2020 at 1:53 AM Esteban Zimanyi <estebanzimanyi at gmail.com>
> wrote:
>
> Dear Vicky
>
> In mobility applications we need to generate data according to a given
> scenario at various scale factors to make simulations. This requires to
> send thousands of requests to pgrouting and this number of requests
> increases with the scale factor used for the generation.
>
> As a concrete example, the BerlinMOD data generator
> http://dna.fernuni-hagen.de/secondo/BerlinMOD/BerlinMOD.html
> uses a workweek scenario in which persons go in the morning to work,
> return back to home in the afternoon, and possibly do an extra trip after
> working hours for leisure. As another example, we described in
> https://www.mdpi.com/2220-9964/8/4/170/htm
> a scenario in which a home appliances shop needs to deliver the appliances
> to the customers and thus vehicles are loaded at a warehouse in the morning
> and spent the day delivering to the clients given a specified schedule to
> finally return back to the warehouse at the end of the day.
>
> We have done a first profiling of these data generators and realized that
> 87% of the time is spent in pgrouting building the graph thousands of
> times, at each query sent to pgrouting. On the other hand, the real work of
> MobilityDB only accounts for 0.11%
>
> [image: VirtualBox_mobilitydb-dev_13_05_2020_17_11_39 (1).png]
>
> For this reason we would need an API in which we build the graph once at
> the beginning of the simulation, send to pgrouting thousands of calls to
> pgr_dijkstra, pgr_aStar, pgr_dijkstraVia, etc. and then delete the graph,
> free the memory and start the simulation.
>
> Any idea how to achieve this ?
>
> Many thanks for your valuable help.
>
> Esteban
>
> ------------------------------------------------------------
> Prof. Esteban Zimanyi
> Department of Computer & Decision Engineering  (CoDE) CP 165/15
> Universite Libre de Bruxelles
> Avenue F. D. Roosevelt 50
> B-1050 Brussels, Belgium
> fax: + 32.2.650.47.13
> tel: + 32.2.650.31.85
> e-mail: ezimanyi at ulb.ac.be
> Internet: http://cs.ulb.ac.be/members/esteban/
> ------------------------------------------------------------
>
>
>
> --
>
> Georepublic UG (haftungsbeschränkt)
> Salzmannstraße 44,
> 81739 München, Germany
>
> Vicky Vergara
> Operations Research
>
> eMail: vicky at georepublic.de
> Web: https://georepublic.info
>
> Tel: +49 (089) 4161 7698-1
> Fax: +49 (089) 4161 7698-9
>
> Commercial register: Amtsgericht München, HRB 181428
> CEO: Daniel Kastl
>
>
>
>
> --
>
> Georepublic UG (haftungsbeschränkt)
> Salzmannstraße 44,
> 81739 München, Germany
>
> Vicky Vergara
> Operations Research
>
> eMail: vicky at georepublic.de
> Web: https://georepublic.info
>
> Tel: +49 (089) 4161 7698-1
> Fax: +49 (089) 4161 7698-9
>
> Commercial register: Amtsgericht München, HRB 181428
> CEO: Daniel Kastl
>
>
>

-- 

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

Vicky Vergara
Operations Research

eMail: vicky at georepublic.de
Web: https://georepublic.info

Tel: +49 (089) 4161 7698-1
Fax: +49 (089) 4161 7698-9

Commercial register: Amtsgericht München, HRB 181428
CEO: Daniel Kastl
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20200519/2c255b61/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: VirtualBox_mobilitydb-dev_13_05_2020_17_11_39 (1).png
Type: image/png
Size: 199925 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20200519/2c255b61/attachment-0001.png>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 1589889424250blob.jpg
Type: image/jpeg
Size: 25003 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20200519/2c255b61/attachment-0001.jpg>