[SoC] Framework which supports addition of contraction techniques for pgRouting - Final Report

[Rohith Reddy]

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
   <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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20160818/96788e44/attachment.html>