Question

how to find the all paths (Longest and shortest ) between start node and end node

gogopotter90
Rank
Badge +13

how to find the all paths between start node and end node

exactly i have 8 nodes ,as point A,B,C;D;E;F;G ;H

i want to check the all paths possible what ever the length of path but i want to find any path available between every Node

between Node A and the rest of nodes (B,C;D;E;F;G;H)

then checck between Node B and the rest of Node (A,C;D;E;F;G;H)

and so on ,i want to check between one node and the rest of nodes

for sure some of them has no connections liens ,i want to define that also which two nodes has no possible paths.

 

i used shortest path finder but i think,it is working only to find the short path between path A and path B,but i want to find all possible paths between A and B even it is long or short and get the id of each line through this path .

 

i prepared my network so all lines are connected without any gaps so i have now paths between some nodes and some not depend on the network .

Thanks for any help

10 replies

redgeographics
Rank
Userlevel 4
Badge +25

The ShortestPathFinder indeed finds only the shortest path between two points. Theoretically, as long as you have a single, fully connected, network you already have all the possible paths between two points. But that's semantics.

You could try looping through the ShortestPathFinder and remove the found path from the network after every iteration (and if you want to be really picky, remove it segment by segment, rerunning every time) but that would take a lot of processing time.

gogopotter90
Rank
Badge +13

The ShortestPathFinder indeed finds only the shortest path between two points. Theoretically, as long as you have a single, fully connected, network you already have all the possible paths between two points. But that's semantics.

You could try looping through the ShortestPathFinder and remove the found path from the network after every iteration (and if you want to be really picky, remove it segment by segment, rerunning every time) but that would take a lot of processing time.

Could i do something but Iam not sure ,how could I do that if u can advice me .Between point and another point (around 20 points )

Could I as first I remove 19 point then he has no path except one path then keep another point and remove the rest and so on .but how could I do that automatic .and I know all points that should .org through it .

Or could I use neighbor finder and go step by step to find paths

At the end it is necessary for me to find all possible paths .thanks for help

redgeographics
Rank
Userlevel 4
Badge +25

So just to get things clear (as they say, an image says more than a thousand words)

Assuming this is your network:

And A and B are the nodes between which you would want to find routes. Which ones would you want to find exactly?

B
Badge +3

It can be done in InlineQuerier using SQL recursion in the SQLite engine, and indeed have done exactly such "All-Paths" analysis before.

Interestingly, once version 5.0+ of SpatiaLite is introduced and the SQLExecutor is updated to be able to use it, this also will support it through being able to create a network graph with the revised VirtualRouting module embedded into the SpatiaLite engine, with some simpler SQL and faster processing time.

Anyhow, with the more pure SQL available in InlineQuerier, finding all possible routes in a network looks like this:

WITH RECURSIVE View_AllRoutes(StartNode, StopNode, RouteLinks, RouteLength) AS
(
SELECT StartNode, StopNode, LinkID||';', LinkLength FROM Links
UNION ALL SELECT A.StartNode, B.StopNode, A.RouteLinks||B.LinkID||';', A.RouteLength+B.LinkLength
FROM View_AllRoutes A INNER JOIN Links B ON (A.StopNode=B.StartNode)
WHERE A.RouteLinks NOT LIKE '%'||B.LinkID||';%'
)
SELECT * FROM View_AllRoutes;

This starts with initializing all routes just being each single link, and then recursively builds on this until all LinkIDs have been exhausted (The WHERE statement checks that the LinkID hasn't already been used in the recursion). This will produce all Routes, with the Route identifier being just a ";" separated list of LinkIDs.

If your links are Bi-Directional, then they need to be input into the InlineQuerier Links table as two separate Links, with separate LinkIDs say "1" and "1-Reversed" and the Start and Stop Node IDs reversed.

Further examples are here https://www.sqlite.org/lang_with.html

Be warned, for complex networks this can take a long time to execute in highly looped networks, as the amount of possible paths increases exponentially, particularly if reverse links are allowed to be used as the same link will often get traced twice, once in both alternative directions, but it performs reasonably well in trunk and branch networks.

You would have to temper this with "What", exactly is the question being asked. Often this can be answered with a more constrained query than just a "Find all paths" brute force method.

If you want to do it outside FME, the above can be done simpler and faster inside the VirtualNetwork or VirtualRouting module interface in SpatiaLite here https://www.gaia-gis.it/fossil/libspatialite/wiki?name=VirtualRouting.

There are also Python Graphing methods roaming around, but haven't experimented with any of those yet.

 

 

M
Badge +2

@gogopotter90 'R' statistics is also very good for this kind of analysis. The igraph package has loads of network analysis tools. For example: https://igraph.org/r/doc/all_simple_paths.html This can be added to the RCaller transformer. Tutorial: Ins and outs of using R in FME. Also, users have contributed R examples to the FME HUB. The RMinimumSpanningTree custom transformer would probably be a good starting point.

So SQl as per @bwn or R - depending on what you're comfortable with.

gogopotter90
Rank
Badge +13

So just to get things clear (as they say, an image says more than a thousand words)

Assuming this is your network:

And A and B are the nodes between which you would want to find routes. Which ones would you want to find exactly?

 

 

I draw example similar to my target ,what i need exactly the lines in front of the arrows.

all possible way from node to another node but the liens that has no path to b so i do not need it just know the id.Thanks for replying me and caring about my question

gogopotter90
Rank
Badge +13

It can be done in InlineQuerier using SQL recursion in the SQLite engine, and indeed have done exactly such "All-Paths" analysis before.

Interestingly, once version 5.0+ of SpatiaLite is introduced and the SQLExecutor is updated to be able to use it, this also will support it through being able to create a network graph with the revised VirtualRouting module embedded into the SpatiaLite engine, with some simpler SQL and faster processing time.

Anyhow, with the more pure SQL available in InlineQuerier, finding all possible routes in a network looks like this:

WITH RECURSIVE View_AllRoutes(StartNode, StopNode, RouteLinks, RouteLength) AS
(
SELECT StartNode, StopNode, LinkID||';', LinkLength FROM Links
UNION ALL SELECT A.StartNode, B.StopNode, A.RouteLinks||B.LinkID||';', A.RouteLength+B.LinkLength
FROM View_AllRoutes A INNER JOIN Links B ON (A.StopNode=B.StartNode)
WHERE A.RouteLinks NOT LIKE '%'||B.LinkID||';%'
)
SELECT * FROM View_AllRoutes;

This starts with initializing all routes just being each single link, and then recursively builds on this until all LinkIDs have been exhausted (The WHERE statement checks that the LinkID hasn't already been used in the recursion). This will produce all Routes, with the Route identifier being just a ";" separated list of LinkIDs.

If your links are Bi-Directional, then they need to be input into the InlineQuerier Links table as two separate Links, with separate LinkIDs say "1" and "1-Reversed" and the Start and Stop Node IDs reversed.

Further examples are here https://www.sqlite.org/lang_with.html

Be warned, for complex networks this can take a long time to execute in highly looped networks, as the amount of possible paths increases exponentially, particularly if reverse links are allowed to be used as the same link will often get traced twice, once in both alternative directions, but it performs reasonably well in trunk and branch networks.

You would have to temper this with "What", exactly is the question being asked. Often this can be answered with a more constrained query than just a "Find all paths" brute force method.

If you want to do it outside FME, the above can be done simpler and faster inside the VirtualNetwork or VirtualRouting module interface in SpatiaLite here https://www.gaia-gis.it/fossil/libspatialite/wiki?name=VirtualRouting.

There are also Python Graphing methods roaming around, but haven't experimented with any of those yet.

 

 

thanks alot for ur replying , honestly i want to do it in ppure FME,or if it is possible if u have still small sample of what u did ,i will be thankful to u .i will keep trying and working on i will  ur suggestion.Thanks,u gave me hope that i can get a solution if u did it before

B
Badge +3

Sample workspace using a 4 x 4 Street Grid as an example, similar to the diagram posted by @redgeographics

allroutesfinder.fmw

Two slightly modified route analyses from the SQL posted earlier:

  • Simple Route Finder similar to the example by @markatsafe , which allows a Route/Path Link to be used only once, but allows the same Node to be traversed multiple times (but through different connecting Link pathways)
  • A more constrained variation that only allows a Node to be used in a Route/Path a total of once. This technically is not "All Routes", but rather "All Node Combinations possible in the Routes"

As can be seen, highly looped networks produce an extremely large number of possible routes from a Node, to all the rest of the Nodes. For a simple 16 Node Grid with 24 Links (With a forward and backward direction makes 2x24=48 possible path segments), there are 393,196 possible Routes between all Start Nodes and all Nodes that can be reached from this Start Node. However, the powerful SQLite engine inside InlineQuerier does execute very fast in doing this.

gogopotter90
Rank
Badge +13

Sample workspace using a 4 x 4 Street Grid as an example, similar to the diagram posted by @redgeographics

allroutesfinder.fmw

Two slightly modified route analyses from the SQL posted earlier:

  • Simple Route Finder similar to the example by @markatsafe , which allows a Route/Path Link to be used only once, but allows the same Node to be traversed multiple times (but through different connecting Link pathways)
  • A more constrained variation that only allows a Node to be used in a Route/Path a total of once. This technically is not "All Routes", but rather "All Node Combinations possible in the Routes"

As can be seen, highly looped networks produce an extremely large number of possible routes from a Node, to all the rest of the Nodes. For a simple 16 Node Grid with 24 Links (With a forward and backward direction makes 2x24=48 possible path segments), there are 393,196 possible Routes between all Start Nodes and all Nodes that can be reached from this Start Node. However, the powerful SQLite engine inside InlineQuerier does execute very fast in doing this.

thanks alot

gogopotter90
Rank
Badge +13

@gogopotter90 'R' statistics is also very good for this kind of analysis. The igraph package has loads of network analysis tools. For example: https://igraph.org/r/doc/all_simple_paths.html This can be added to the RCaller transformer. Tutorial: Ins and outs of using R in FME. Also, users have contributed R examples to the FME HUB. The RMinimumSpanningTree custom transformer would probably be a good starting point.

So SQl as per @bwn or R - depending on what you're comfortable with.

thanks alot

 

 

Reply


Community Stats

28,666
Posts
109,343
Replies
36,535
Members
Terms & ConditionsCookie settings
A product of
Safe Software respectfully acknowledges that we live, learn and work on the traditional and unceded territories of the Kwantlen, Katzie, and Semiahmoo First Nations.