search

NOAA-OWP / t-route

Tree based hydrologic and hydraulic routing
Other
44 stars 50 forks source link

Verify DAG property on graphs #34

Closed groutr closed 1 month ago

groutr commented 4 years ago

We assume that the network we are working with is a directed acyclic graph. There should be some sort of way to sanity check a new dataset to make sure it meets this assumption.

One way to verify a directed graph is acyclic is to topologically sort it. A graph has a topological sorting if and only if it is a directed acyclic graph. https://en.wikipedia.org/wiki/Directed_acyclic_graph#Definitions

jameshalgren commented 3 years ago

@groutr -- is this still relevant?

groutr commented 3 years ago

@jameshalgren yes, the topic is still relevant.

def is_dag(N):
    try:
        for n in kahn_toposort(N):
            pass
        return True
    except:
        return False

This only needs to be done one per dataset, but it would be good to expose a function to do that checking.

jameshalgren commented 3 years ago

Moving to Phase 4 Technical Debt.