6

I've been trying to develop some code for ArcMap (VB .net) that would take a river network, identify and label the loops. These loops can be simple bifurcations or highly thread braided channels.

I was tinkering around with a sample of the NHD from the USA which is supplied as a geometric network. I tried the find loops Trace Task and was blown away by the fact that A) it did what I wanted and B) it is incredibly fast (less than a couple of seconds for a huge network).

Below is a screen shot of a bit of a network for Alaska with the polylines highlighted in red indicating they are part of a loop.

Polylines selected by Find Loops Trace Task

So I started looking on the internet to see if the algorithm is documented anywhere and I have failed to find anything.

I'm not a mathetician but I got the impression that I was looking at some sort of algorithm that detects "strongly connected components in an acyclic directed graph". I have found many references to a Tarjans algorithm. I found this blog page which was the easiest attempt to explain these sorts of algorithms but as always they show a very simple graph which is not a realistic scenario when considering river networks. As the screen shot above shows you have loops within loops. I could not work out or even determine if it would work in a multi-threaded network.

So my question is what algorithm is ESRI using? What algorithm would find all the loops in a multi-threaded river network? I would like to try and implement it outside a geometric network as not everyone has an ArcInfo (Advanced) license and able to create a geometric network.

If anyone knows of a site\paper than describes such an algorithm in a simple manner that would be great!

Improve this question

2 Answers 2

Reset to default
2

This is a fairly standard Computer Science algorithm. I'd think it uses something like the optimal algorithms described on this page about looking for loops in a linked list.

Improve this answer
2
  • Jason, I had a good look at your page but I am struggling with understanding how one takes a multi-threading river network and turn it into a "singly linked list". It states "A singly linked list is made of nodes where each node has a pointer to the next node (or null to end the list)". Note this talks in the singular. So how do you represent a bifurcation or even tributary junction where a node can point to two or more branches of a river?
    – Hornbydd
    Aug 12, 2013 at 16:00
  • 2
    Duncan, let the vertices of the (arc representation of the) river network be the nodes and let each vertex v point to its immediate downstream vertex w. Visually we would diagram this as v-->w and mathematically we would represent it as the ordered pair (v,w). That's a directed graph. It is acyclic (for otherwise you have flows going in loops). The loops (or cycles) you are looking for are the cycles that exist when the directionality along this graph is ignored. That means you represent it as a collection of unordered pairs {v, w} where either v flows into w or w flows into v.
    – whuber
    Aug 12, 2013 at 16:39
0

I feel I should answer my own question here although it was more of a work around. I was interested in how ESRI could identify loops in a river network. I never really got to the bottom of this despite the advice above.

What I did do was revisit my algorithm and did some performance testing. I have a very iterative approach to solving this task and clearly nowhere near as efficient as ESRI's algorithm but it did work! The sticking block was the way I kept looping adding polyline ID's to a list.

I stumbled across something called a HashSet in VB .Net and tweaked my code to use this. This had an amazing improvement on the speed of my code, what took about an hour is now reduced to a few minutes. OK still not as fast as ESRI's algorithm but well within my accepted processing speed!

So in a nutshell if you are doing iterative union like operations on lists then try a HashSet it's super fast!

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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