IDEAS home Printed from https://ideas.repec.org/a/gam/jdataj/v5y2020i1p8-d309637.html
   My bibliography  Save this article

A Python Algorithm for Shortest-Path River Network Distance Calculations Considering River Flow Direction

Author

Listed:
  • Nicolas Cadieux

    (Department of Geography, McGill University, Montreal, QC H3A 0B9, Canada)

  • Margaret Kalacska

    (Department of Geography, McGill University, Montreal, QC H3A 0B9, Canada)

  • Oliver T. Coomes

    (Department of Geography, McGill University, Montreal, QC H3A 0B9, Canada)

  • Mari Tanaka

    (Graduate School of Economics, Hitotsubashi University, Tokyo 186-8601, Japan)

  • Yoshito Takasaki

    (Graduate School of Economics, University of Tokyo, Tokyo 113-0033, Japan)

Abstract

Vector based shortest path analysis in geographic information system (GIS) is well established for road networks. Even though these network algorithms can be applied to river layers, they do not generally consider the direction of flow. This paper presents a Python 3.7 program (upstream_downstream_shortests_path_dijkstra.py) that was specifically developed for river networks. It implements multiple single-source (one to one) weighted Dijkstra shortest path calculations, on a list of provided source and target nodes, and returns the route geometry, the total distance between each source and target node, and the total upstream and downstream distances for each shortest path. The end result is similar to what would be obtained by an “all-pairs” weighted Dijkstra shortest path algorithm. Contrary to an “all-pairs” Dijkstra, the algorithm only operates on the source and target nodes that were specified by the user and not on all of the nodes contained within the graph. For efficiency, only the upper distance matrix is returned (e.g., distance from node A to node B), while the lower distance matrix (e.g., distance from nodes B to A) is not. The program is intended to be used in a multiprocessor environment and relies on Python’s multiprocessing package.

Suggested Citation

  • Nicolas Cadieux & Margaret Kalacska & Oliver T. Coomes & Mari Tanaka & Yoshito Takasaki, 2020. "A Python Algorithm for Shortest-Path River Network Distance Calculations Considering River Flow Direction," Data, MDPI, vol. 5(1), pages 1-14, January.
    • Handle: RePEc:gam:jdataj:v:5:y:2020:i:1:p:8-:d:309637
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2306-5729/5/1/8/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2306-5729/5/1/8/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Coomes, Oliver T. & Takasaki, Yoshito & Abizaid, Christian & Arroyo-Mora, J. Pablo, 2016. "Environmental and market determinants of economic orientation among rain forest communities: Evidence from a large-scale survey in western Amazonia," Ecological Economics, Elsevier, vol. 129(C), pages 260-271.
    2. Boeing, Geoff, 2017. "OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks," SocArXiv q86sd, Center for Open Science.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Polina Lemenkova, 2022. "Handling Dataset with Geophysical and Geological Variables on the Bolivian Andes by the GMT Scripts," Data, MDPI, vol. 7(6), pages 1-18, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Matteo Böhm & Mirco Nanni & Luca Pappalardo, 2022. "Gross polluters and vehicle emissions reduction," Nature Sustainability, Nature, vol. 5(8), pages 699-707, August.
    2. Shah, Nitesh R. & Ziedan, Abubakr & Brakewood, Candace & Cherry, Christopher R., 2023. "Shared e-scooter service providers with large fleet size have a competitive advantage: Findings from e-scooter demand and supply analysis of Nashville, Tennessee," Transportation Research Part A: Policy and Practice, Elsevier, vol. 178(C).
    3. Lorenzo Barbieri & Roberto D’Autilia & Paola Marrone & Ilaria Montella, 2023. "Graph Representation of the 15-Minute City: A Comparison between Rome, London, and Paris," Sustainability, MDPI, vol. 15(4), pages 1-14, February.
    4. Miotti, Marco & Needell, Zachary A. & Jain, Rishee K., 2023. "The impact of urban form on daily mobility demand and energy use: Evidence from the United States," Applied Energy, Elsevier, vol. 339(C).
    5. Shiqin Liu & Carl Higgs & Jonathan Arundel & Geoff Boeing & Nicholas Cerdera & David Moctezuma & Ester Cerin & Deepti Adlakha & Melanie Lowe & Billie Giles-Corti, 2021. "A Generalized Framework for Measuring Pedestrian Accessibility around the World Using Open Data," Papers 2105.08814, arXiv.org.
    6. Ospina, Juan P. & Duque, Juan C. & Botero-Fernández, Verónica & Montoya, Alejandro, 2022. "The maximal covering bicycle network design problem," Transportation Research Part A: Policy and Practice, Elsevier, vol. 159(C), pages 222-236.
    7. Brinkley, Catherine & Raj, Subhashni, 2022. "Perfusion and urban thickness: The shape of cities," Land Use Policy, Elsevier, vol. 115(C).
    8. Jorge Ubirajara Pedreira Junior & Antônio Nélson Rodrigues da Silva & Cira Souza Pitombo, 2022. "Car-Free Day on a University Campus: Determinants of Participation and Potential Impacts on Sustainable Travel Behavior," Sustainability, MDPI, vol. 14(6), pages 1-20, March.
    9. Spencer Leitch & Zhiyuan Wei, 2024. "Improving spatial access to healthcare facilities: an integrated approach with spatial analysis and optimization modeling," Annals of Operations Research, Springer, vol. 341(2), pages 1057-1074, October.
    10. Begazo Curie, Karin & Mertens, Kewan & Vranken, Liesbet, 2021. "Tenure regimes and remoteness: When does forest income reduce poverty and inequality? A case study from the Peruvian Amazon," Forest Policy and Economics, Elsevier, vol. 128(C).
    11. Geoff Boeing, 2020. "Planarity and street network representation in urban form analysis," Environment and Planning B, , vol. 47(5), pages 855-869, June.
    12. Aston, Laura & Currie, Graham & Kamruzzaman, Md. & Delbosc, Alexa & Brands, Ties & van Oort, Niels & Teller, David, 2021. "Multi-city exploration of built environment and transit mode use: Comparison of Melbourne, Amsterdam and Boston," Journal of Transport Geography, Elsevier, vol. 95(C).
    13. Alves d'Acampora, Bárbara Heliodora & Maraschin, Clarice & Taufemback, Cleiton Guollo, 2023. "Landscape ecology and urban spatial configuration: Exploring a methodological relationship. Application in Pelotas, Brazil," Ecological Modelling, Elsevier, vol. 486(C).
    14. Bowater, David & Stefanakis, Emmanuel, 2023. "Extending the Adapted PageRank Algorithm centrality model for urban street networks using non-local random walks," Applied Mathematics and Computation, Elsevier, vol. 446(C).
    15. Boeing, Geoff & Pilgram, Clemens & Lu, Yougeng, 2024. "Urban Street Network Design and Transport-Related Greenhouse Gas Emissions around the World," SocArXiv r32vj, Center for Open Science.
    16. Sadek, Bassel & Doig Godier, Jean & Cassidy, Michael J & Daganzo, Carlos F, 2022. "Traffic signal plans to decongest street grids," Transportation Research Part B: Methodological, Elsevier, vol. 162(C), pages 195-208.
    17. Lu, Qing-Long & Mahajan, Vishal & Lyu, Cheng & Antoniou, Constantinos, 2024. "Analyzing the impact of fare-free public transport policies on crowding patterns at stations using crowdsensing data," Transportation Research Part A: Policy and Practice, Elsevier, vol. 179(C).
    18. Garau, Michele & Torsæter, Bendik Nybakk, 2024. "A methodology for optimal placement of energy hubs with electric vehicle charging stations and renewable generation," Energy, Elsevier, vol. 304(C).
    19. Lu, Qing-Long & Sun, Wenzhe & Dai, Jiannan & Schmöcker, Jan-Dirk & Antoniou, Constantinos, 2024. "Traffic resilience quantification based on macroscopic fundamental diagrams and analysis using topological attributes," Reliability Engineering and System Safety, Elsevier, vol. 247(C).
    20. Olga L Sarmiento & Andrés F Useche & Daniel A Rodriguez & Iryna Dronova & Oscar Guaje & Felipe Montes & Ivana Stankov & Maria Alejandra Wilches & Usama Bilal & Xize Wang & Luis A Guzmán & Fabian Peña , 2021. "Built environment profiles for Latin American urban settings: The SALURBAL study," PLOS ONE, Public Library of Science, vol. 16(10), pages 1-25, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jdataj:v:5:y:2020:i:1:p:8-:d:309637. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.