[pgrouting-dev] Fwd: pgr_dijkstra(edges_sql, combinations_sql)
Vicky Vergara
vicky at georepublic.de
Tue May 19 06:22:50 PDT 2020
---------- 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20200519/152a2496/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/152a2496/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/152a2496/attachment-0001.jpg>
More information about the pgrouting-dev
mailing list