LdDl / ch

Contraction Hierarchies (with bidirectional version of Dijkstra's algorithm) technique for computing shortest path in graph.
Apache License 2.0
44 stars 5 forks source link

[FEATURE REQUEST] Isochrones #8

Closed LdDl closed 3 years ago

LdDl commented 3 years ago

Is your feature request related to a problem? Please describe. Isochrones in terms of GIS - https://wiki.openstreetmap.org/wiki/Isochrone This is nice instrument for transport accessibility analysis.

Describe the solution you'd like and provide pseudocode examples if you can Implement shortest path finding algorithm with cost restristions (issue is #7 ) Wrap implemented function inside something like this (pseudocode):

Isochrones(source, max_cost) []int64{
    targets := graph.GetAllVertices
    isochrones := map[int64]bool
    answer = []int64
    for target in targets {
        if target == source ||  single_vertex is in isochrones {
             continue
        }
        _, single_isochrone_path = ShortestPath(source, target, max_cost)
        for single_vertex in single_isochrone_path {
           if single_vertex is not in isochrones {
                isochrones[single_vertex] = true
                answer = append(answer, single_vertex)
           }
        }
    }
    return answer
}

Describe alternatives you've considered and provide pseudocode examples if you can There is alternative solution: Just iterate all neighbor vertices on each step and collect them while estimated cost < max_cost It's just a bit modified (with provided max cost) BFS - https://en.m.wikipedia.org/wiki/Breadth-first_search

Additional context Nope

LdDl commented 3 years ago

See #9