graph-tool issueshttps://git.skewed.de/count0/graph-tool/-/issues2017-07-10T12:50:58Zhttps://git.skewed.de/count0/graph-tool/-/issues/259[request for feature] hierarchical contraction2017-07-10T12:50:58ZFrançois Kawala[request for feature] hierarchical contractionIn this Issue we discuss the implementation of **hierarchical contraction**.
# Motivation
As per Wikipedia "the method of contraction hierarchies is a technique to speed up shortest-path routing by first creating precomputed "contr...In this Issue we discuss the implementation of **hierarchical contraction**.
# Motivation
As per Wikipedia "the method of contraction hierarchies is a technique to speed up shortest-path routing by first creating precomputed "contracted" versions of the connection graph."
# Overview
More precisely, as per Robert Geisberger "*[...] the nodes of a weighted
directed graph __G = (V, E)__ are ordered by “importance” given a total node order __<.__ Let __u < v__,
then the node __v__ is more important than __u__. We now construct a hierarchy by contracting the
nodes in this order. A node _u_ is contracted by _removing it_ from the network in such a way
that shortest paths in the remaining overlay graph are preserved. This property is achieved by
replacing paths of the form __⟨hv, u, wi⟩__ by a shortcut edge __⟨hv, wi⟩__. Note that the shortcut __⟨hv, wi⟩__ is only required if __⟨hv, u, wi⟩__ is the only shortest path from _v_ to _w_. We shall view the contraction process as a way to add all discovered shortcuts to the edge set E. We obtain a contraction hierarchy (CH).*"
# Existing implementations
(1) Graphhopper (JAVA) [https://github.com/graphhopper/graphhopper]
(2) OSMR (CPP) [https://github.com/Project-OSRM/osrm-backend]
# Bibliography (extracted from wikipedia)
(1) Robert Geisberger [http://algo2.iti.kit.edu/schultes/hwy/contract.pdf]
(2) Rice and Tsotras [http://www.vldb.org/pvldb/vol4/p69-rice.pdf]
(3) Prof. Dr. Hannah Bast's lectures https://ad-wiki.informatik.uni-freiburg.de/teaching/EfficientRoutePlanningSS2012
Tiago PeixotoTiago Peixotohttps://git.skewed.de/count0/graph-tool/-/issues/196Request for feature: Bipartite Graph Projection2018-04-20T07:37:00ZCarlosRequest for feature: Bipartite Graph ProjectionHi,
From our discussion:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Efficient-Bipartite-Projection-tp4025895.html;cid=1417425123974-777
I was told to open an issue for this feature here.
I a...Hi,
From our discussion:
http://main-discussion-list-for-the-graph-tool-project.982480.n3.nabble.com/Efficient-Bipartite-Projection-tp4025895.html;cid=1417425123974-777
I was told to open an issue for this feature here.
I am looking for a bipartite graph projection feature. Specifically I have 'g', a weighted graph and would like to have some way that the projections 'g1', and 'g2' to be also a weighted graph. I have been particularly curious on seeing both a way the projections receive on their edges the sum of the weights on graph g as well.
Thank you,
Carlos A. Tiago PeixotoTiago Peixotohttps://git.skewed.de/count0/graph-tool/-/issues/172Maximum cardinality matching for weighted graphs2017-07-26T11:47:50ZPedroMaximum cardinality matching for weighted graphsPlease implement a version for weighted graphs that finds the optimum result, not just a fast heuristic version.
I'm currently using igraph and R, but your library is definitely faster in all aspects. I'm currently working with hundre...Please implement a version for weighted graphs that finds the optimum result, not just a fast heuristic version.
I'm currently using igraph and R, but your library is definitely faster in all aspects. I'm currently working with hundred thousandth edges bipartite graphs, but it will probably scale up in the near future.
Thanks.
PedroTiago PeixotoTiago Peixotohttps://git.skewed.de/count0/graph-tool/-/issues/140Cygwin support2017-07-26T11:47:50ZTiago PeixotoCygwin supportI have reported this issue on StackOverflow and thought you would be interested on knowing about and adding cygwin support of the platform at some point.
http://stackoverflow.com/questions/22735669/cygwin-bad-reloc-address-linking-laI have reported this issue on StackOverflow and thought you would be interested on knowing about and adding cygwin support of the platform at some point.
http://stackoverflow.com/questions/22735669/cygwin-bad-reloc-address-linking-laTiago PeixotoTiago Peixotohttps://git.skewed.de/count0/graph-tool/-/issues/44Add support for the following random generators: Kleinberg and geometric2017-07-26T11:47:50ZTiago PeixotoAdd support for the following random generators: Kleinberg and geometricKleinberg:
http://www.maths.strath.ac.uk/~aap05145/contest/kleinberg.m
http://www.maths.strath.ac.uk/~aap05145/contest/geo.m
these are part of a nice matlab toolbox:
http://www.maths.strath.ac.uk/~aap05145/contest/home.html
Kleinberg:
http://www.maths.strath.ac.uk/~aap05145/contest/kleinberg.m
http://www.maths.strath.ac.uk/~aap05145/contest/geo.m
these are part of a nice matlab toolbox:
http://www.maths.strath.ac.uk/~aap05145/contest/home.html
Tiago PeixotoTiago Peixoto