This is actually a water network routing challenge, but I'm going to describe it like a road network problem since the "Nearest Fire Station" problem is a classical network/GIS problem and this is just the urban water supply network equivalent.I have to create a fast-calculating FME workflow that processes 75,000 possible, independent, "Road Intersection Closure" events that may or may not result in some other Intersection "Nodes" also becoming inaccessible to all 100 "Fire Stations" as a result of the closure.This particularly happens when you close a critical Intersection that cuts off all routes to the downstream intersections where they do not have a alternative network route ring road.Ironically, I have a proprietary piece of network analysis software that finishes the above calculation in 20 minutes and is the benchmark for an equivalent FME workflow. Whilst I've found Solutions, none so far have been very performant and so looking for alternative Suggestions/Solutions.So to take a 2 Fire Station + 10 Intersection Nodes Sample (noting this is to scale to 100 Fire Stations and 75,000 Intersections)If Intersection Nodes 1, 2, 3, 4, 8, 9 or 10 are shutdown such that no routes into them exist during the Shutdown Event, then there will be no other affected Intersections apart from itself. At least one route from at least one Fire Station still exists to all other Intersection Nodes. Eg. If Node 1 is isolated, then Nodes 2, 3, 4, 5 and 6 still have a route available to them from a Fire Station. Similarly if Node 2 is isolated, then Nodes 1, 3, 4, 5 and 6 still have a route available to them from a Fire Station.If Intersection Node 6 is shutdown such that no routes into it exists, then similarly the only affected Intersection Node is itself, being an End-Of-Network NodeHowever, if Intersection Node 4 is shutdown, then this cuts off Access to Intersections 4, 5 and 6.Similarly if Node 7 is shutdown, then this cuts off Access to 7, 8, 9 and 10.So the results table that the Workflow through Network Routing analysis is to produce looks like this:So I've come at this a few ways already:The "naive" way is to generate 75,000 separate Networks that each have the affected Network Edges/Links removed, each with a Group By Identifier by the Node Id and then perform NetworkToplogyCalculator or ShortestPathFinder on each of these. This is however, really, really expensive to generate and process would be 75,000 networks comprised of ~75,000 Nodes each, representing 5.6 billion Node Features alone let alone the (mostly) bi-directional Edges. Given that most Nodes are independent of each other and exist in independent subnetworks that don't relate to each other, this is sub-optimal and takes hours if not days to process.I've similarly tried this through a SQL way in generating Nodes and Links in InlineQuerier to analyse by doing WITH RECURSIVE statements to replicate the the Fire Station to Intersection routing checks to see which Nodes remain connected after taking out the Isolated Node and Related Links. A further optimisation I've applied to this is to generate a lookup table of "All Unique Routes between Nodes" list similar to my other posts on this subject to generate a list to tell me what Nodes have Network Pathways To-or-From a Fire Station that include the test shutdown Intersection, to limit the analysis to just checking if those Nodes are still connected to a Fire Station rather than naively checking all 75,000 them. Faster, but I've struggled to get a fast performing SQL query integrated into SQLite/InlineQuerier. SpatiaLite opens up more possibilities with its dedicated Network Routing VirtualRouting module, but that similarly starts to struggle when you need to iterate more than 1 network through it since it has to re-build the binary network graphing tables everytime and the latest SpatiaLite is not integrated into SQLExecutor either.A further possible optimisation on 2 is to restrict the tracing further to an interim step of just checking whether routes still exist to the immediately adjacent Nodes. If this is True, then no other affected Nodes exist. Eg. For Testing the impact of Node 1 Shutdown, Trace to Node 3 and if a Trace route from a Fire Station exists, then stop the analysis there, as there is no further need. I believe this is the methodology used by the proprietary software we have been using to date, and it uses progressive iteration to work its way upstream until it encounters adjacent nodes that are connected to a Fire Station and stops any further processing since by inference all the other Nodes most also be unaffected.I think probably the REAL answer may be instead to merge in an external Python module dedicated to Network Graphing/Analysis such as NetworkX https://networkx.github.io/ , but integrating that into a Workflow that has to be portable between PCs and can run once per month is I think the real pain.......and if there is a more "native" FME solution that can be achieved and still perform inline with the ~20 minute processing time benchmark, then I'm all for it!Hence, callling on the FME brains trust for any clever Solution Outlines. Not looking for a Detail Workflow Design, but rather broad FME methodologies that may be possible.

Network Routing Challenge: Detecting Road Intersections with No Route from a Fire Station

This is actually a water network routing challenge, but I'm going to describe it like a road network problem since the "Nearest Fire Station" problem is a classical network/GIS problem and this is just the urban water supply network equivalent.

I have to create a fast-calculating FME workflow that processes 75,000 possible, independent, "Road Intersection Closure" events that may or may not result in some other Intersection "Nodes" also becoming inaccessible to all 100 "Fire Stations" as a result of the closure.

This particularly happens when you close a critical Intersection that cuts off all routes to the downstream intersections where they do not have a alternative network route ring road.

Ironically, I have a proprietary piece of network analysis software that finishes the above calculation in 20 minutes and is the benchmark for an equivalent FME workflow. Whilst I've found Solutions, none so far have been very performant and so looking for alternative Suggestions/Solutions.

So to take a 2 Fire Station + 10 Intersection Nodes Sample (noting this is to scale to 100 Fire Stations and 75,000 Intersections)

If Intersection Nodes 1, 2, 3, 4, 8, 9 or 10 are shutdown such that no routes into them exist during the Shutdown Event, then there will be no other affected Intersections apart from itself. At least one route from at least one Fire Station still exists to all other Intersection Nodes. Eg. If Node 1 is isolated, then Nodes 2, 3, 4, 5 and 6 still have a route available to them from a Fire Station. Similarly if Node 2 is isolated, then Nodes 1, 3, 4, 5 and 6 still have a route available to them from a Fire Station.
If Intersection Node 6 is shutdown such that no routes into it exists, then similarly the only affected Intersection Node is itself, being an End-Of-Network Node
However, if Intersection Node 4 is shutdown, then this cuts off Access to Intersections 4, 5 and 6.
Similarly if Node 7 is shutdown, then this cuts off Access to 7, 8, 9 and 10.

So the results table that the Workflow through Network Routing analysis is to produce looks like this:

So I've come at this a few ways already:

The "naive" way is to generate 75,000 separate Networks that each have the affected Network Edges/Links removed, each with a Group By Identifier by the Node Id and then perform NetworkToplogyCalculator or ShortestPathFinder on each of these. This is however, really, really expensive to generate and process would be 75,000 networks comprised of ~75,000 Nodes each, representing 5.6 billion Node Features alone let alone the (mostly) bi-directional Edges. Given that most Nodes are independent of each other and exist in independent subnetworks that don't relate to each other, this is sub-optimal and takes hours if not days to process.
I've similarly tried this through a SQL way in generating Nodes and Links in InlineQuerier to analyse by doing WITH RECURSIVE statements to replicate the the Fire Station to Intersection routing checks to see which Nodes remain connected after taking out the Isolated Node and Related Links. A further optimisation I've applied to this is to generate a lookup table of "All Unique Routes between Nodes" list similar to my other posts on this subject to generate a list to tell me what Nodes have Network Pathways To-or-From a Fire Station that include the test shutdown Intersection, to limit the analysis to just checking if those Nodes are still connected to a Fire Station rather than naively checking all 75,000 them. Faster, but I've struggled to get a fast performing SQL query integrated into SQLite/InlineQuerier. SpatiaLite opens up more possibilities with its dedicated Network Routing VirtualRouting module, but that similarly starts to struggle when you need to iterate more than 1 network through it since it has to re-build the binary network graphing tables everytime and the latest SpatiaLite is not integrated into SQLExecutor either.
A further possible optimisation on 2 is to restrict the tracing further to an interim step of just checking whether routes still exist to the immediately adjacent Nodes. If this is True, then no other affected Nodes exist. Eg. For Testing the impact of Node 1 Shutdown, Trace to Node 3 and if a Trace route from a Fire Station exists, then stop the analysis there, as there is no further need. I believe this is the methodology used by the proprietary software we have been using to date, and it uses progressive iteration to work its way upstream until it encounters adjacent nodes that are connected to a Fire Station and stops any further processing since by inference all the other Nodes most also be unaffected.
I think probably the REAL answer may be instead to merge in an external Python module dedicated to Network Graphing/Analysis such as NetworkX https://networkx.github.io/ , but integrating that into a Workflow that has to be portable between PCs and can run once per month is I think the real pain.......and if there is a more "native" FME solution that can be achieved and still perform inline with the ~20 minute processing time benchmark, then I'm all for it!

Hence, callling on the FME brains trust for any clever Solution Outlines. Not looking for a Detail Workflow Design, but rather broad FME methodologies that may be possible.

Page 1 / 1

@bwn Try something along the lines of this example using Buffer, Clipper and NetworkTopologyBuilder. Use a small Buffer to clip the line segments at each 'road closure'. Then use NetworkTopologyBuilder to build a network.Use Aggregator and group y network ID to create multi-line aggregates. Now SpatialRelator or SpatailFilter should be able to tell you which network does or doesn't touch a firestation.

Thanks @markatsafe I'll take a look through that problem and solution.

Ironically, that example is the use case of analysing the impact of isolating a part of the water mains network on the rest of the network......which is exactly my use case, I just rewrote it into a "Fire Station" example to make it more a generalised problem description! "Fire Stations" = Water Pressure Source and "Road Intersections" = Network Valve shutoff block.

One thing on that solution I did do pre-processing first was, rather than use every Water Main Pipe Feature, which is unnecessarily expensive, is to first identify the individual groups of mains within the valve shutoff area. This reduced the "real" network 500,000 water mains down to 75,000 groups of water mains, as isolating any main within an individual group has an identical impact since it is the same isolation valves that need to be operated everytime. This was relatively straightforward with a Snipper around the Isolation Valves (although an earlier Prototype similarly used Bufferer+Clipper) and NetworkTopologyCalculator to assign each shutdown block of mains a Group ID.

It's the next bit that is the challenge, finding what other shutdown blocks in the network will also get disconnected from a water source as a result of isolating any one part of the network.

To finish this Post off, I finally returned to this module design last week after I concluded realistically the only way I was going to solve it was through my (really bad) Python. Hey.....at least it let me learn a few more "Pythonic" script techniques!

The basis of the solution was to install the public Python NetworkX Module to my Project Folder. If anyone else is interested, it is an absolutely awesome Library of Network and Graph analysis objects and functions.

https://networkx.github.io

...and you know, as an aside, maybe Safe should check NetworkX out, because if it was incorporated into FME as a standard plugin, and some basic transformers built on it that did some common Network analysis questions that seem to pop up Eg. "Find all Connected Network Paths", then this would really expand FME's network analytic capabilities.

Anyhow, the Code used in a PythonCaller attached.

Code file

https://networkx.github.io

Anyhow, the Code used in a PythonCaller attached.

Thanks for sharing

Reply

Community Stats

Reply

Community Stats

Sign up

An FME Account is required to contribute

Login to the community

An FME Account is required to contribute

Scanning file for viruses.

This file cannot be downloaded