<div dir="ltr"><span style="font-size:12.8px">Hi all,</span><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">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.</div><div style="font-size:12.8px"><br><div style="font-size:12.8px"><span style="font-size:12.8px"><b>Brief Description</b></span></div><div style="font-size:12.8px"><span style="font-size:small"><br></span></div><div style="font-size:12.8px"><span style="font-size:small">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.</span><br></div></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px">This implementation gives a flexible framework for adding contraction algorithms in the future, currently, it supports two algorithms:</div><div style="font-size:12.8px"><ul><li style="margin-left:15px">Dead end contraction<br></li><li style="margin-left:15px">Linear contraction<br></li></ul></div><div style="font-size:12.8px">Allowing the user to:</div><div style="font-size:12.8px"><ul><li style="margin-left:15px">Forbid contraction on a set of nodes.</li><li style="margin-left:15px">Decide the order of the contraction algorithms and set the maximum number of times they are to be executed.</li></ul></div><div style="font-size:12.8px"><b style="font-size:12.8px"><br>State of the project before GSoC<br></b><br></div><div style="font-size:12.8px"><div>Previously there is no contraction functionality in the library.</div><div><br></div></div><div style="font-size:12.8px"><b style="font-size:12.8px">Addition that my project brought to the software<br></b><br><div>I implemented the following during the GSoC program</div><div><ul><li style="margin-left:15px">A framework which supports the addition of new contraction algorithms.<br></li><li style="margin-left:15px">Implementation of Dead end contraction.<br></li><li style="margin-left:15px">Implementation of Linear contraction which was used to refine the framework.</li><li style="margin-left:15px">The user can forbid to contract a particular set of nodes or edges.<br></li><li style="margin-left:15px">The user can decide how many times the cycle can be done.<br></li><li style="margin-left:15px">The user can decide the order of the operations on a cycle.<br></li><li style="margin-left:15px">Proper documentation and tests for the above ­mentioned components.</li></ul><span style="font-size:12.8px"><b>Links</b></span><br><ul><li style="margin-left:15px"><span style="font-size:small">Link to the branch working branch and directory:<br></span><span style="font-size:12.8px"><a href="https://github.com/pgRouting/pgrouting/tree/gsoc-ch/src/contraction" target="_blank">https://github.com/pgRouting/<wbr>pgrouting/tree/gsoc-ch/src/<wbr>contraction</a><br></span><br></li><li style="margin-left:15px"><span style="font-size:12.8px">Links to the documentation<br></span><a href="http://docs.pgrouting.org/dev/en/src/contraction/doc/contraction.html" target="_blank">http://docs.pgrouting.org/dev/<wbr>en/src/contraction/doc/<wbr>contraction.html</a><br><a href="http://docs.pgrouting.org/dev/en/src/contraction/doc/pgr_contractGraph.html" target="_blank">http://docs.pgrouting.org/dev/<wbr>en/src/contraction/doc/pgr_<wbr>contractGraph.html</a><br><br></li><li style="margin-left:15px">Link that shows all of my commits<br><a href="https://github.com/pgRouting/pgrouting/commits/gsoc-ch?author=sankepallyrohithreddy" target="_blank">https://github.com/pgRouting/<wbr>pgrouting/commits/gsoc-ch?<wbr>author=sankepallyrohithreddy</a><br><br></li><li style="margin-left:15px">Link that shows all of my pull requests to the main repository<br><a href="https://github.com/pgRouting/pgrouting/pulls?q=is%3Apr+author%3Asankepallyrohithreddy+is%3Aclosed4" target="_blank">https://github.com/pgRouting/<wbr>pgrouting/pulls?q=is%3Apr+<wbr>author%<wbr>3Asankepallyrohithreddy+is%<wbr>3Aclosed4</a><br><br></li><li style="margin-left:15px">Link to the wiki page<br><a href="https://github.com/pgRouting/pgrouting/wiki/GSoc-2016-Contraction" target="_blank">https://github.com/pgRouting/<wbr>pgrouting/wiki/GSoc-2016-<wbr>Contraction</a></li></ul><b>Slides<br><br></b><a href="https://github.com/pgRouting/pgrouting/files/423339/pgRouting.Contraction.pdf" target="_blank">https://github.com/pgRouting/<wbr>pgrouting/files/423339/<wbr>pgRouting.Contraction.pdf</a><br><div style="font-size:12.8px"><br><font style="font-size:12.8px;line-height:16.768px">I learned a lot from my mentors and it </font><span style="font-size:12.8px;line-height:16.768px">has been a very good learning experience</span><font style="font-size:12.8px;line-height:16.768px">. I hope this project keeps growing and</font><span style="font-size:12.8px;line-height:16.768px"> would like to continue my contribution.<br></span><span style="font-size:12.8px"><br>Regards,</span></div><div style="font-size:12.8px">Rohith Reddy</div><div style="font-size:12.8px">Lab for Spatial Informatics</div><div style="font-size:12.8px">International Institute of Information Technology</div><div style="font-size:12.8px">Hyderabad, India.</div></div></div><br><br><img width="0" height="0" class="mailtrack-img" src="https://mailtrack.io/trace/mail/f8f176183403e00d36e3f0ac8b71ecc75cf498f0.png?u=567036"></div>