3

I am using pgr_ksp algorithm to find out the shortest path between a startnode and endnode by creating a network topology between all the nodes. Pgr_ksp algorithm very well gives me all the shortest paths taking the cost in consideration. But now, I also want to add a constraint that the path its giving between startnode and endnode must include or exclude a particular node or link. Below code works perfect. But how and where can I add a constraint such that the path will include a node for example 'nodeA'?

SELECT d.*, f.linkname ,SUM(cost) OVER (PARTITION BY path_id) AS aggregation
FROM pgr_ksp('Select id, source, target, airmiles as cost from f',
source,
target,
 2) AS d
INNER JOIN f ON d.edge= f.id
ORDER BY aggregation, path_id, path_seq; 
  • Could you break it into two shortest path problems? Startnode -> particular node, then particular node -> endnode. – Jon Sep 4 '18 at 20:48
  • run the function on those nodes in sequence. e.g. pgr_ksp(start_node, included_node) & pgr_ksp(included_node, end_node) – ThingumaBob Sep 4 '18 at 20:50
  • oh, or set the heap_path parameter to true and select only paths where the desired edge/node is traversed, e.g. as WHERE filter? can't test both now...I'd say write a function for the sequencing, but try this first... – ThingumaBob Sep 4 '18 at 21:03
1

I have no experience with the above library, but assuming no additional constraints (like "no edge should be taken more than once"), the shortest path from A to C that includes B is equivalent to the shortest path from A to B, plus the shortest path from B to C.

In other words, run the algorithm twice and combine the results.

  • Yes for now I have done the same, wanted to know if pgr_ksp or any shortest path algorithm provides any such functionality internally. Thanks for it though. – Ash Sep 4 '18 at 21:43
  • Thanks for your help. Can you also tell me, if I wish to exclude a particular node(such that the path should not be taken in which that node lies). How can that be achieved. – Ash Sep 10 '18 at 17:53
  • @Ash: Remove the node? – BlueRaja - Danny Pflughoeft Sep 10 '18 at 19:21
  • In short, I want a path returned by pgr_ksp, which excludes that particular node and returns other paths except the ones having that node. – Ash Sep 10 '18 at 21:44
  • @Ash: I understand. I'm saying, remove the node from the graph. – BlueRaja - Danny Pflughoeft Sep 10 '18 at 21:52
1

I had a minute and packed that functionality into a function; I more or less sticked to plain SQL here and couldn´t implement some smart moves (like using the original function if the length of the passed array is only 2 or general PL/pgSQL magic), since I haven´t had much time. But it works like a charm.

After creation (make sure it´s the same BD/schema where your pgRouting is installed), you can call this function just like the other pgr_KSP, but with an array (type INT) as argument instead of start_vid & end_vid, e.g.

SELECT * 
FROM pgr_ksp(
       <edge_sql>,
       ARRAY[<start_vid>, [<via_vid>, ...,] <end_vid>],  --the inner [] mean 'optional'; don´t include them in the array
       <k>,
       <directed>,         --optional
       <heap_paths>        --optional
     );

which will return the same set structure, having a continuous path for each matching path_id over all via_vids, and with

  • no intermediate -1 edges (marking the end of one function execution and the arrival at an via_vid)
  • a continuous path_seq column (over path_id)
  • a continuous agg_cost column (over path_id)

It's absolutely possible I have overseen cases where this doesnt work as expected. Also, having a continuous path based on a common path_id might or might not be what you want.

  • Thanks for your help. Can you also tell me, if I wish to exclude a particular node(such that the path should not be taken in which that node lies). How can that be achieved. – Ash Sep 10 '18 at 17:52
  • two options: 1.) simply exclude it in the WHERE filter; this, however, will return no route if there is no alternative to go via that point. 2.) assign humongous cost values (e.g. in a CASE construct) to the edges that connect to that node: the route through that node will be returned if it is still the only possible route. – ThingumaBob Sep 12 '18 at 10:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.