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] Make graph simple as possible #10

Closed
LdDl opened this issue Jul 21, 2022 · 1 comment
Closed

[FEATURE REQUEST] Make graph simple as possible #10

LdDl opened this issue Jul 21, 2022 · 1 comment
Assignees
Labels
enhancement New feature or request

Comments

@LdDl
Copy link
Owner

LdDl commented Jul 21, 2022

Is your feature request related to a problem? Please describe.
There are too many generated edges/vertices after parsing OSM (via edge expansion). Contraction hierarchies algorithm could take very much time to process all set of vertices. I'd suggest to implement Edge contraction to reduce size of graph for further contraction hierarchies algorithm

Describe the solution you'd like and provide pseudocode examples if you can
Find all vertices with degree == 2. Then recursively:

while exists vertex v with degree 2:
    - remove v and the 2 outgoing edges
    - add a new edge between the neighbours of v
    - the weight of the new edge is the sum of the weights of the deleted edg

reference - https://stackoverflow.com/questions/54954644/algorithm-to-simplify-reduce-graph

Additional context

  • Would be cool to have an optional flag for CLI (for debugging purposes) also
  • Some numbers for "before" and "after" (kinda benchmark) on specific graph
@LdDl LdDl added the enhancement New feature or request label Jul 21, 2022
@LdDl LdDl self-assigned this Jul 21, 2022
@LdDl LdDl mentioned this issue Jul 25, 2022
Closed
@LdDl
Copy link
Owner Author

LdDl commented Sep 5, 2022

Some kind of workaround could be found in #12

@LdDl LdDl closed this as completed Feb 17, 2023
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