[pgrouting-dev] Error within pgr_kdijkstraPath

pgRouting pgrouting-dev
1

Hello,

I'm developing on a routing application which should route from 45.000
source nodes to several target nodes. Considering performance issues I
tried to use the pgr_kdijkstraPath function. It works really fast but
obviously there is a bug when calculating paths from several source nodes.

I tested with 1 source node and 2 target nodes. Result looks valid.
Then I increased the number of source nodes up to 100 and found out that
the target nodes in the result set wheren't 2 but 190! The function
internally decreased the node IDs.

This is the source:

CREATE OR REPLACE FUNCTION public.kdijkstra(in_from_node_id int,
in_to_node_ids int) RETURNS void AS $$
DECLARE

BEGIN

  INSERT INTO paths (seq, from_node_id, to_node_id, via_node_id, edge, cost)
  SELECT di.seq, in_from_node_id, di.id1, di.id2, di.id3, di.cost
  FROM pgr_kdijkstraPath (
    'SELECT id, source, target, cost, reverse_cost FROM osm_2po_4pgr',
    in_from_node_id, in_to_node_ids, true, true
  ) AS di
  ORDER BY seq;
  
END;
$$ LANGUAGE plpgsql;

The function has been called 100 times (100 source node IDs) each with
the target node IDs 29730 and 60778. The result is valid for the first 7
calls, on call number 8 the target node IDs has been decreased and so on.

Here are all target node IDs found in the result set:

(29636,29637,29638,29639,29640,29641,29642,29643,29644,29645,29646,29647,29648,29649,29650,29651,29652,29653,29654,29655,29656,29657,29658,29659,29660,29661,29662,29663,29664,29665,29666,29667,29668,29669,29670,29671,29672,29673,29674,29675,29676,29677,29678,29679,29680,29681,29682,29683,29684,29685,29686,29687,29688,29689,29690,29691,29692,29693,29694,29695,29696,29697,29698,29699,29700,29701,29702,29703,29704,29705,29706,29707,29708,29709,29710,29711,29712,29713,29714,29715,29716,29717,29718,29719,29720,29721,29722,29723,29724,29725,29726,29727,29728,29729,29730,60684,60685,60686,60687,60688,60689,60690,60691,60692,60693,60694,60695,60696,60697,60698,60699,60700,60701,60702,60703,60704,60705,60706,60707,60708,60709,60710,60711,60712,60713,60714,60715,60716,60717,60718,60719,60720,60721,60722,60723,60724,60725,60726,60727,60728,60729,60730,60731,60732,60733,60734,60735,60736,60737,60738,60739,60740,60741,60742,60743,60744,60745,60746,60747,60748,60749,60750,60751,60752,60753,60754,

60755,60756,60757,60758,60759,60760,60761,60762,60763,60764,60765,60766,60767,60768,60769,60770,60771,60772,60773,60774,60775,60776,60777,60778)

It looks like a bug, doesn't it?
Please help...

regards,
Michael

2

Hi Michael,

Please open an issue for this and provide a simple test case to reproduce the issue. You can put the test files in a file share site and link the files or send them to me in a zip file and I wil post them and link to the issue.

Thanks,
   -Steve

On 6/12/2015 7:12 AM, Michael Wimmer wrote:

Hello,

I'm developing on a routing application which should route from 45.000
source nodes to several target nodes. Considering performance issues I
tried to use the pgr_kdijkstraPath function. It works really fast but
obviously there is a bug when calculating paths from several source nodes.

I tested with 1 source node and 2 target nodes. Result looks valid.
Then I increased the number of source nodes up to 100 and found out that
the target nodes in the result set wheren't 2 but 190! The function
internally decreased the node IDs.

This is the source:

CREATE OR REPLACE FUNCTION public.kdijkstra(in_from_node_id int,
in_to_node_ids int) RETURNS void AS $$
DECLARE

BEGIN

  INSERT INTO paths (seq, from_node_id, to_node_id, via_node_id, edge, cost)
  SELECT di.seq, in_from_node_id, di.id1, di.id2, di.id3, di.cost
  FROM pgr_kdijkstraPath (
    'SELECT id, source, target, cost, reverse_cost FROM osm_2po_4pgr',
    in_from_node_id, in_to_node_ids, true, true
  ) AS di
  ORDER BY seq;
  
END;
$$ LANGUAGE plpgsql;

The function has been called 100 times (100 source node IDs) each with
the target node IDs 29730 and 60778. The result is valid for the first 7
calls, on call number 8 the target node IDs has been decreased and so on.

Here are all target node IDs found in the result set:

(29636,29637,29638,29639,29640,29641,29642,29643,29644,29645,29646,29647,29648,29649,29650,29651,29652,29653,29654,29655,29656,29657,29658,29659,29660,29661,29662,29663,29664,29665,29666,29667,29668,29669,29670,29671,29672,29673,29674,29675,29676,29677,29678,29679,29680,29681,29682,29683,29684,29685,29686,29687,29688,29689,29690,29691,29692,29693,29694,29695,29696,29697,29698,29699,29700,29701,29702,29703,29704,29705,29706,29707,29708,29709,29710,29711,29712,29713,29714,29715,29716,29717,29718,29719,29720,29721,29722,29723,29724,29725,29726,29727,29728,29729,29730,60684,60685,60686,60687,60688,60689,60690,60691,60692,60693,60694,60695,60696,60697,60698,60699,60700,60701,60702,60703,60704,60705,60706,60707,60708,60709,60710,60711,60712,60713,60714,60715,60716,60717,60718,60719,60720,60721,60722,60723,60724,60725,60726,60727,60728,60729,60730,60731,60732,60733,60734,60735,60736,60737,60738,60739,60740,60741,60742,60743,60744,60745,60746,60747,60748,60749,60750,60751,60752,60753,6075

4,

60755,60756,60757,60758,60759,60760,60761,60762,60763,60764,60765,60766,60767,60768,60769,60770,60771,60772,60773,60774,60775,60776,60777,60778)

It looks like a bug, doesn't it?
Please help...

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