Skip to content

GSoC 2017 Area Contraction

Jump to bottom Edit New page
Ankur Shukla edited this page Jun 25, 2017 · 69 revisions

Contents of the Wiki

Brief Idea of Area Contraction

Area contraction refers to contracting the graph of an area (defined by a set of border vertices and edges connecting the border vertices) taking only the shortest paths between each border vertex, keeping the border vertices prohibited from contraction.

State of Project Before GSoC 2017

Before GSoc 2017, Mr. Sankepally Rohith Reddy added a contraction framework to pgRouting along with dead contraction and linear contraction algorithms. The framework supports addition of new contraction algorithms to pgRouting. This work was undertaken as GSoC 2016 work for pgRouting. Details of his work can be found in his Wiki.

Additions Proposed in GSoc 2017

I propose to implement the area contraction algorithm in this GSoC. The detailed approach can be found in the proposal. The proposed additions are:

  • Implementation of a function Area Contraction
  • This implementation shall have the following characteristics:
    • The user will be able to select the border vertices of an area
    • Number of overlapping sub-paths will also be provided as output

Project

My Contributions

Biography

Meetings

The following issues contain the gist of my meetings with my mentors and fellow GSoC students. The meetings have been in the form of gitter chats as well as chats on google hangouts. These meetings have served as concepts building sessions, doubt clearing sessions and most importantly bonding sessions for the community: Meeting Issues

  • June 22 - Graphs, Vertices and Edges in pgRouting
  • June 21 - Psuedo Code for Area Contraction
  • June 13 - No Circular Merges
  • June 9 & 12 - Preparing Tests & Documentation
  • June 7 - contractGraph.c file Code
  • June 6 - Issues
  • June 3 - Code Structure
  • June 2 - New Documentation Structure Discussion
  • June 1 - Implement Changes in Template Code and Standardize Array Variable Names
  • May 31 - About flow of control in pgRouting
  • May 30 - Discussion on pgr_areaContraction
  • May 28 - Creating PR when in Doubt
  • May 26 - Keeping Upto Date

References

  1. CppCon 2015: Michael VanLoon “STL Algorithms in Action”
  2. Code Linting C++ Coding Style Guide
  3. PgRouting Developer's Documentation
  4. CPPReference

Weekly Consolidated Reports

Week 12

Week 11

Week 10

Week 9

Week 8

Week 7

Week 6

Week 5

Week 4

   June 20 - June 26
  • What did I plan to achieve this week?
    • Finish coding pgr_areaContraction
    • Write tests for function logic
    • Finish documentation for pgr_areaContraction
    • Finish proposal documentation
    • Prepare work for Phase 1 submission
  • What did I achieve this week?
  • What do I plan to do next week?
    • Finish coding pgr_areaContraction logic
    • Write tests for function logic
    • Finish documentation for pgr_areaContraction
    • Finish proposal documentation
    • Prepare work for Phase 1 submission
  • Impediments?
    • No impediments this week

Week 3

   June 13 - June 19
  • What did I plan to achieve this week?
    • Learn to use tests in pgRouting
    • Use pgTap to create unit tests for pgr_areaContraction
    • Generate documentation tests
  • What did I achieve this week?
  • What do I plan to do next week?
    • Finish coding pgr_areaContraction
    • Write tests for function logic
    • Finish documentation for pgr_areaContraction
    • Finish proposal documentation
    • Prepare work for Phase 1 submission
  • Impediments?
    • No impediments this week.

Week 2

   June 6 - June 12
  • What did I plan to do this week?
    • Study the signature of pgr_contractGraph designed by Rohith
    • Work on output parameters of pgr_areaContraction
    • Learn to use tests in pgRouting (pgTap)
    • Use pgTap to create unit tests for pgr_areaContraction
    • Generate documentation tests
    • Prepare a brief write up about my conclusions for my comparisons between the signatures of pgr_contractGraph and pgr_dijkstra and study of pgr_contractGraph
    • Complete remaining C++ videos
  • What did I achieve this week?
    • Made changes to areaContraction_driver.cpp file to fix Travis warning, change to C++ structures -> Issue #30 & PR #820, PR #816
    • Watched C++ videos -> Issue #2
    • Fixed a petite bug in contractGraph.c -> PR #817
    • Learned about contractGraph.c code -> Issue #29
    • Fitted areaContraction to contract_rt by modifying output parameters and C code -> Issue #28 & PR #816
    • Updated my fork and clone with latest documentation structure changes in develop branch. Moved documentation files in areaContraction directory to get in sync in with the new structure -> Issue #26 & PR #810
    • Started discussion on Contraction code. Opened an issue for Q & A on the code for doubt resolution -> Issue #25
  • What do I plan to do next week?
    • Learn to use tests in pgRouting (pgTap)
    • Use pgTap to create unit tests for pgr_areaContraction
    • Generate documentation tests
  • Impediments?
    • No impediments this week.

Week 1

   May 30 - June 4
  • What did I plan to do this week?
    • Understand the flow of control in pgRouting code for a new function
    • Compare the signatures of pgr_contractGraph and pgr_dijkstra_many_to_many
    • Draw conclusions weather the difference is trivial or not, based on the comparison
    • Design signature for pgr_areaContraction
    • Create template code for pgr_areaContraction from create.sh script
    • Modify the template code for pgr_areaContraction to suit the new signature
    • Fix Travis and Appveyor warnings
    • Create relevant issues for tasks and meetings
  • What did I achieve this week?
    • Understood the flow of control of code by extensive discussion on the topic with my mentors - Created relevant issues with notes of the discussion. They can come handy for me and others -> Issue #20 & Issue #24
    • Compared the signatures of pgr_contractGraph and pgr_dijkstra
    • Designed the input signature of pgr_areaContraction -> pgr_areaContraction(sql, borderVerticesArray)
    • Created template code for pgr_areaContraction using that of pgr_dijkstra by modifying create.sh script -> Issue #19 & Issue #21
    • Modified the template code for pgr_areaContraction to suit the new signature -> Issue #22
    • Implemented new standard of array names in template code
    • Fixed Travis and Appveyor warnings by removing tests from tests.conf file
    • Created relevant issues for tasks and meetings
  • What do I plan to do next week?
    • Study the signature of pgr_contractGraph designed by Rohith
    • Work on output parameters of pgr_areaContraction
    • Learn to use tests in pgRouting (pgTap)
    • Use pgTap to create unit tests for pgr_areaContraction
    • Generate documentation tests
    • Complete remaining C++ videos
  • Impediments?
    • Initially I was confused regarding the flow of control. But now I have gained clarity on the same.
    • My less knowledge about the STL and C++ is slowing me down. I plan to overcome this in the coming week.

Weekly Tasks

Week 12 Tasks

Week 11 Tasks

Week 10 Tasks

Week 9 Tasks

Week 8 Tasks

Week 7 Tasks

Week 6 Tasks

Week 5 Tasks

Week 4 Tasks

  • (20 June-26 June)
    • Added code to pgr_areaContraction code
      • Issue #35
        • Added code for calling Many Many Dijkstra
        • Added code for handling duplicate values in border vertices input
        • Started with Proof of Concept 1 Documentation
      • Solved by adding commits to PR #852

Week 3 Tasks

  • (13 June-19 June)
    • Skeleton Code in pgr_areaContract.hpp
      • Issue #35
        • Create pgr_areaContract.hpp file
        • Add skeletal code to pgr_areaContract.hpp
        • Add pgr_areaContraction.hpp
        • Define template class and functions for areaContraction logic
      • Solving in PR #852
    • Proposal Documentation
      • Issue #32
        • Add proposal documentation file areaContraction.rst
        • Add proposal documentation images
      • Solving in PR #854
    • Documentation for pgr_areaContraction
    • Tests for pgr_areaContraction
      • Issue #34
        • Modify the signature of the existing template test for pgr_areaContraction
      • Solved in PR #828

Week 2 Tasks

Week 1 Tasks

  • (30 May-5 June)
    • Fix Travis and Appveyor Warnings by modifying the code
    • Modify areaContraction file according to the new naming standard for array and array size variables
      • Vicky Vergara's Fork Issue #150
      • Modify the files according to the new standard
    • Learn about the flow of control in pgRouting via template excercise
    • Create a sample database with pgRouting sample data
    • Create template function for pgr_areaContraction
      • Issue #19
        • Modify generated template files to suit the needs of the desired function
          • Modify sql\areaContraction\areaContraction.sql file
          • Modify src\areaContraction\src\areaContraction.c file
          • Modify drivers\areaContraction\areaContraction_driver.h file
          • Modify src\areaContraction\src\areaContraction_driver.cpp file
        • Make a copy of create.sh as mycreate.sh
        • Change the new script to suit the function signature desired for pgr_areaContraction
        • Generate new function directories using the modified script
      • Solving by PR #151

Community Bonding Period

  • Week D (25-29 May)
  • Week C (18-24 May)
    • Updated my Wiki
    • Create a new function pgr_ankurDijkstra as team work practice task
      • Issue #18
        • Make a copy of create.sh as mycreate.sh
        • Execute mycreate.sh to create function directories - src/ankurDijkstra
        • Change template code to match new function code
        • Add pgr_ankurDijkstra to CmakeLists.txt
        • Fix pgTap tests
        • Fix Appveyor build fail
        • Make a pull request to cvvergara' fork
      • Solved in PR #138
    • Special Task
    • Create a new structure
      • Issue #10
        • Create the include/c_types/pgr_contracted_blob.h using create.sh
        • Copy pgr_contracted_blob structure from pgr_types.h to the new file
        • Code passed locally
        • Lint the header
        • sh tools/scripts/code_checker.sh h
        • Make PR
      • Solved in PR #783
  • Week B (11-17 May)
    • Practice Code Linting
    • Update OSGeo GSoC
      • Create OSGeo Login
      • Update Wiki and Github Repo details on OSGeo GSoC page
    • Learn about current organization pgRouting
    • An Experiment
      • Update fork
      • Compile locally
      • Time local compilation
  • Week A (4-10 May)
    • Add issues to milestones
    • Create Milestones on my fork
    • Get added to pgRouting on Github
    • Get acquainted with other GSoC wikis
    • Set up Wiki at main repo
    • Proposal Accepted

Pre-Community Bonding Period

Acquaintance with pgRouting and the Community

  • Make starting issues on my fork
  • Enable Issues on fork
  • Fork pgRouting
  • Compile pgRouting
  • Install pgRouting Dependencies
    • cmake - 3.5.1
    • C++ compiler - 5.4.0
    • postgreSQL - 9.5
    • postGIS - 2.2
    • Boost graph library - 1.58
    • CGAL - 4.7-4
    • perl - 5.22.1-9
    • pgtap - 3.31-2
  • Install Ubuntu 16.04 LTS Desktop
  • Introduce yourself
  • Approach the community

Contact: https://discourse.osgeo.org/c/pgrouting/pgrouting-dev

pgRouting Project

pgRouting Project

Quick Links

Clone this wiki locally