how to find all possible paths in network ?

Hi @soly,

Thank you for the post!

I believe this article may assist in what you’re looking for:
Building a Topological Network from a Road Dataset | Using the TopologyBuilder

If you need more assistance please reach out again and I can look further into the problem!

Thank you,
Donal. 

@donalmateer

thanks for your reply .

i used topology builder but it did not provide me my target .

i would like to start from specific point  in only one direction till reach end point ,it should go in all possible paths ,show me all segment .

With topology builder :

i am not able to define the direction .

Is there any method to define the paths in topology builder in one direction from start point to end point ,show me all possible paths in one direction .

it is possible that I can build with shortest path finder but I have big data then it means ,I have to use more than shortest pathfinder and so critical and lots of time processing .

thanks for help  

@soly A couple questions, what do you mean by “all paths”?  Would you include every single street that could potentially be utilized to reach the destination, or are you looking for a specific number of routes? Does each route need to be fully unique (not using any segment used by a previous route)?

While an official best answer was not picked, there were multiple answers provided on this post and depending on what you are looking for, they may solve your problem.

@liamfez

i have electric geometric network with coordinates ,i have drawn ,what is my target and how it looks like the network as small example 

the data is clear, point and lines are connected topology 

As example :

start point 

End point 

My target to find all paths from Start till  reach end point .

between each two point ,there are some segments 

there are different paths ,some lines are common in paths 

i would like to find all paths possible from Start to End point ,and also getting the segment of paths ,  orderly from Start to end into one direction .

it is ok if it uses segment from previous route 

Is there any solution  for my problem in picture above ?

I don’t think there is, at least not with regular FME transformers.

The number of results will grow exponentially with the size of your network, so even if it were possible it’d be a pretty intensive operation for a large network.

@redgeographics Do you have any  suggestion that I can start to solve my problem ?

In this post ,he used inline querier using sql .

But I could not understand the code ,how could I implement the same code for my network? Will does this method work with me ?

https://community.safe.com/transformers%2D9/how%2Dto%2Dfind%2Dthe%2Dall%2Dpaths%2Dlongest%2Dand%2Dshortest%2Dbetween%2Dstart%2Dnode%2Dand%2Dend%2Dnode%2D11122?tid=11122

Best to ask the person who wrote that answer.

@redgeographics

 i have asked since some days but he did not reply .Do you have any suggestions or solution  that I can test ?

@soly Generally pathing requires iteration/recursion.

That is why my earlier posted solution uses a Recursive Common Table Expression

https://www.sqlite.org/draft/lang_with.html

In the first iteration step, all segments that are connected to the start node are found through Topology, then at each next step, to find the next segments that are connected to these segments, with a filter on these results to remove any segments found that were already found in the path earlier.

This logic is what my InlineQuerier SQL does, in the first part of the CTE WITH expression, the initial SELECT finds the links that are connected to the Start Node.

The UNION SELECT ALL in the CTE then takes those results and finds the next segments that connect to those Segments.  The way CTEs work is that they automatically filter out unique rows that were already found before, before adding them to the list of rows found, and so this is perfect for generally pathing logic.

The RECURSIVE part of the WITH statement tells SQLite to keep executing more UNION SELECT ALL attempts to find the next segments to connect to the connected segments found in the previous step, and SQLite will keep recursing/iterating until UNION SELECT ALL returns zero more rows, at which time it will stop running the query, and return the results.  All the paths found can then be checked to see if they terminate at the specified end point.

FME unfortunately is not very good at iteration, it is difficult to create the logic,and it is generally slow at solving large networks.   However, to attempt to do the same with “out-if-the-box” Transformers will generally involve reading on how to build In-Workspace Custom Transformers, that are the only types of Transformers that can be recursed/iterated.  The input to it would be the Start Point, End Point, and the Edge results of TopologyBuilder.  Then inside the Custom Transfomer is to find the Edges that have a Start or Stop Node ID  corresponding to the Start Point, and return those Edges and the Node(s) at the opposite ends of those Edges, and filter those results for any previously found Edges (and optionally any previously found Nodes is want to make it only return Paths that use a Node once and once only), and the send those Edges and Opposite End Nodes back into the input of the next iteration of the Custom Transformer.

Every “All Paths” solution I have ever used, for speed and ease-of-coding are either:

1. A recursive Common Table Expression (CTE).  SQLite is very good at doing this and as FME InlineQuerier is just a Workbench shell for creating a temporary SQLite database and executing SQL commands on it, this works very well for small to medium networks ; or
2. Using Python by calling the public Network Graphing Library NetworkX.   Using the FME Transformer PythonCaller, a Network Graph G can be built as a NetworkX Graph object by loading all Links and Nodes through the PythonCaller Input Port.   This then allows NetworkX Python functions such as All Simple Paths to be called on Graph G, and the results returned back to the FME workspace.  I have used this very successfully on 750,000 link networks.

https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.simple_paths.all_simple_paths.html

If you are not interested in paths, and instead only want to find the subnetworks between two points, I use a 1 mm Bufferer at the Start/End Node Points to split the network, and use NetworkTopologyCalculator to assign a Subnetwork ID to each subnetwork.

@bwn

thanks for replying ,I will read your explanation carefully and try to implement ur suggestions .

your suggestion inside a custom transformer :

I can find edges that have start or stop point but I did not understand the following sentence :  return those Edges and the Node(s) at the opposite ends of those Edges, 

What u mean here ?

i am interested in paths ,i need to order segments from start till the  end node .

then the network topology calc. will not be a good option for that .

I have tried to write a code in Python caller but I got error .

import fme

import fmeobjects

import networkx as nx

class FeatureProcessor(object):

    def __init__(self):

        self.graph = nx.DiGraph()

        self.start_end_pairs = []

    def input(self, feature):

        start_node = feature.getAttribute('start_node')

        end_node = feature.getAttribute('end_node')

        arc_id = feature.getAttribute('arc_id')

        self.graph.add_edge(start_node, end_node, arc_id=arc_id)

        self.start_end_pairs.append((start_node, end_node))

    def find_all_paths(self, start, end):

        return list(nx.all_simple_paths(self.graph, source=start, target=end))

    def close(self):

        for start, end in self.start_end_pairs:

            all_paths = self.find_all_paths(start, end)

            for path in all_paths:

                feature = fmeobjects.FMEFeature()

                feature.setAttribute('path', ' -> '.join(path))

                self.pyoutput(feature)

Python Exception <AttributeError>: module 'importlib.resources' has no attribute 'files'

Error executing string `import fme

Error :

Factory proxy not initialized

PythonCaller_3 (PythonFactory): PythonFactory failed to process feature

PythonCaller_3 (PythonFactory): A fatal error has occurred. Check the logfile above for details

AttributeCreator_164_OUTPUT_-1_6456_Player (RecorderFactory): A fatal error has occurred. Check the logfile above for details

thanks a lot for help .

FME 2021