[pgrouting-dev] pgr_dijkstra(edges_sql, combinations_sql)

Mon May 25 07:35:51 PDT 2020

Ok for me. Thanks Vicky !
Best regards,
Mahmoud Sakr

    On Monday, May 25, 2020, 03:32:12 PM GMT+2, Vicky Vergara <vicky at georepublic.de> wrote:  

 Hello Mahmoud & pgRouting communityLets meet tuesday May 26 at 2pm UTC = 9am in Mexico = 7:30pm in India? 
regards

On Fri, May 22, 2020 at 4:10 AM Mahmoud Sakr <m_attia_sakr at yahoo.com> wrote:

Hello Vicky,What time would be ok for you to meet ? 
We have further tested the new function, and integrated it with our data generator. All the code has been revised an cleaned in the forked repository. 

Best regards,
Mahmoud Sakr

    On Tuesday, May 19, 2020, 11:34:45 PM GMT+2, Vicky Vergara <vicky at georepublic.de> wrote:  

 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, andget 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-devSo 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

--------------------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 generatorhttp://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 inhttps://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%

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

-- 
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/20200525/972d7719/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/20200525/972d7719/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/20200525/972d7719/attachment-0001.jpg>