Using biconnected components for efficient identification of upstream features in large spatial networks (GIS cup)
Zach Goldthorpe, Jason Cannon, Jesse Farebrother, Zachary Friggstad, Mário A. Nascimento · 2018
This paper presents a solution to the problem posed in the ACM SIGSPATIAL GIS Cup 2018, namely to identify all upstream features---nodes and edges existing on simple paths between starting points and controllers---in a given spatial network. Our approach is based primarily on a two-sweep depth-first search which decomposes a graph into its biconnected components prior to collecting the upstream features. Our algorithm runs in linear time in the size of the graph and, in practice, is able to solve large instances with millions of features within seconds on an ordinary personal laptop, identifying features if and only if they are upstream.