Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[FEATURE REQUEST] Isochrones #8

Closed
LdDl opened this issue Oct 16, 2020 · 1 comment
Closed

[FEATURE REQUEST] Isochrones #8

LdDl opened this issue Oct 16, 2020 · 1 comment
Assignees
Labels
enhancement New feature or request

Comments

@LdDl
Copy link
Owner

LdDl commented Oct 16, 2020

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 LdDl added the enhancement New feature or request label Oct 16, 2020
@LdDl LdDl self-assigned this Oct 16, 2020
@LdDl LdDl changed the title [FEATURE REQUEST] Isocrones [FEATURE REQUEST] Isochrones Oct 16, 2020
@LdDl
Copy link
Owner Author

LdDl commented Oct 22, 2020

See #9

@LdDl LdDl closed this as completed Oct 22, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant