Hi all,
I am working on the implementation of a framework which supports addition of contraction techniques for pgRouting for the GsoC 2016. This is my final report. I would like to thank my mentors, Vicky Vergara and Daniel Kastl for their constant support and guidance.
Brief Description
In big graphs, like the road graphs, or electric networks, graph contraction can be used to speed up some graph algorithms. Contraction reduces the size of the graph by removing some of the vertices and edges and, for example, might add edges that represent a sequence of original edges decreasing the total time and space used in graph algorithms.
This implementation gives a flexible framework for adding contraction algorithms in the future, currently, it supports two algorithms:
-
Dead end contraction
-
Linear contraction
Allowing the user to:
- Forbid contraction on a set of nodes.
- Decide the order of the contraction algorithms and set the maximum number of times they are to be executed.
State of the project before GSoC
Previously there is no contraction functionality in the library.
Addition that my project brought to the software
I implemented the following during the GSoC program
-
A framework which supports the addition of new contraction algorithms.
-
Implementation of Dead end contraction.
-
Implementation of Linear contraction which was used to refine the framework.
-
The user can forbid to contract a particular set of nodes or edges.
-
The user can decide how many times the cycle can be done.
-
The user can decide the order of the operations on a cycle.
-
Proper documentation and tests for the above mentioned components.
Links -
Link to the branch working branch and directory:
https://github.com/pgRouting/pgrouting/tree/gsoc-ch/src/contraction -
Links to the documentation
http://docs.pgrouting.org/dev/en/src/contraction/doc/contraction.html
http://docs.pgrouting.org/dev/en/src/contraction/doc/pgr_contractGraph.html -
Link that shows all of my commits
https://github.com/pgRouting/pgrouting/commits/gsoc-ch?author=sankepallyrohithreddy -
Link that shows all of my pull requests to the main repository
https://github.com/pgRouting/pgrouting/pulls?q=is%3Apr+author%3Asankepallyrohithreddy+is%3Aclosed4 -
Link to the wiki page
https://github.com/pgRouting/pgrouting/wiki/GSoc-2016-Contraction
Slides
https://github.com/pgRouting/pgrouting/files/423339/pgRouting.Contraction.pdf
I learned a lot from my mentors and it has been a very good learning experience. I hope this project keeps growing and would like to continue my contribution.
Regards,
Rohith Reddy
Lab for Spatial Informatics
International Institute of Information Technology
Hyderabad, India.