Hydroinformatics advances for operational river forecasting: using graphs for drainage network descriptions

Distributed hydrologic models provide accurate river streamflow forecasts and a multitude of spatially varied products on basin scales. The distributed elements of the basins are pieced together using drainage networks. An efficient representation of drainage networks in computer code is necessary. Graph theory has long been applied in many engineering areas to solve network problems. In this paper we demonstrate that adjacent list graph is the most efficient way of presenting the drainage network in terms of development and execution. The authors have implemented drainage networks using the adjacency-list structure in both the research and operational versions of the US National Weather Service (NWS) distributed model. A parallel routing algorithm based on Dijsktra's shortest path algorithm was also developed using the MPI library, which was tested on a cluster using the Oklahoma Illinois River basin dataset. Theoretical analysis and test results show that inter-processor communication and unbalanced workload among the processors limit the scalability of the parallel algorithm. The parallel algorithm is more applicable to computers with high inter-processor bandwidth, and to basins where the number of grid cells is large and the maximum distance of the grid cells to the outlet is short.