GSoC 2018 Minimum cost flow and ChPP
Table of Contents
- Community Bonding Period (April 23 to May 13, 2018)
- Official Coding Period Phase 1 (May 14 to June 10, 2018)
- First evaluation period (June 11 to June 15, 2018)
- Official Coding Period Phase 2 (June 11 to July 8, 2018)
- Second evaluation period (July 9 to July 13, 2018)
- Official Coding Period Phase 3 (July 9 to August 5, 2018)
- Final evaluation period (August 6 to August 14, 2018)
- Week 12
- Week 11
- Week 10
- Week 9
- Week 8
- Week 7
- Week 6
- Week 5
- Week 4
- Week 3
- Week 2
- Week 1
Minimum-cost flow problem is an extension of maximum flow problem with an added cost (per unit flow) for each edge. The Chinese Postman Problem (ChPP) in a directed graph can be solved by Minimum-cost flow algorithm.
This project is proposing to add Minimum-cost flow algorithm and directed ChPP algorithms to pgRouting during GSoC 2018.
State of the project before GSoC
Previously there is no functionality which calculates Minimum-cost flow or ChPP in the library.
Community Bonding Period (April 23 to May 13, 2018)
- Read and understand the BGL docs
- Read more about directed ChPP.
- Prepare the wiki page (TODO lists and weekly reports).
- Discuss the design of function signatures with mentors.
- Write an introductory email to our SOC mailing list and to your community dev mailing list, detailing your project and asking for feedback. Also include information about your wiki page, public repository and any other way the community can follow updates for your project, like a blog, a Twitter account, etc...
- Add the links to your wiki page and public repository in the accepted students wiki page.
- Now it's a good time to study again Google's GSoC students guide and OSGeo's specific instructions, they contain useful advices from past years.
- Public interaction is important -- it is a key principle of open source -- work happens where everyone can see it.
Official Coding Period Phase 1 (May 14 to June 10, 2018)
Week 1 (May 14 to May 20, 2018)
- Prepare basic code and test framework for Minimum-cost flow implementation.
- Analyze whether the current sample data is good for testing and documenting the functions. If not, create new sample data for these functions.
Week 2 (May 21 to May 27, 2018)
- Implement Minimum-cost flow algorithm by the BGL.
- If needed, copy the needed BGL header file to pgRouting.
Week 3 (May 28 to June 3, 2018)
- Write full documentation for Minimum-cost flow implementation.
Week 4 (June 4 to June 10, 2018)
- Create unit tests and documentation tests for Minimum-cost flow implementation.
First evaluation period (June 11 to June 15, 2018)
- Mentors evaluate me and I evaluate mentors of official coding period phase 1.
- Deliver Minimum-cost flow implementation.
- Deliver full documentation and tests for Minimum-cost flow implementation.
Official Coding Period Phase 2 (June 11 to July 8, 2018)
Week 5 (June 11 to June 17, 2018)
- Prepare basic code and test framework for directed ChPP implementation.
Week 6 to 8 (June 18 to July 8, 2018)
- Implement pgr_directedChPP.
Second evaluation period (July 9 to July 13, 2018)
- Mentors evaluate me and I evaluate mentors of officail coding period phase 2.
- Deliver the directed ChPP implementation.
Official Coding Period Phase 3 (July 9 to August 5, 2018)
Week 9 to 10 (July 9 to July 22, 2018)
- Create documentation for the directed ChPP implementation.
- Create unit tests and documentation tests for the directed ChPP implementation.
Week 11 (July 23 to July 29, 2018)
- Fix bugs and documentation details.
- If time permits, implement pgr_directedChPP_Cost.
Week 12 (July 30 to August 5, 2018)
- Prepare for final delivery.
Final evaluation period (August 6 to August 14, 2018)
- Wrap up my projects and submit final evaluation of my mentors.
Prepare for final delivery
- Double confirm that everything are goes well.
- Fix documentation.
- Write a google presentation about this project.
- Merge my branch to develop.
- Make this project compiled with C++7.
Documentation for directedChPP
- Family page.
- pgr_directedChPP page.
- pgr_directedChPP_Cost page.
Tests for pgr_directedChPP
- Documentation tests.
- pgTAP tests.
Fix bugs and improve code
- Fixed compile errors.
- Fixed issue when the graph is not connected.
Implementation of pgr_directedChPP
- Implement Fleury algorithm.
- Fix bugs.
- basic tests.
Implementation of pgr_directedChPP_Cost
- Fixed compiled errors.
- Fixed runtime errors.
Get ready for full implementation of pgr_directedChPP
Basic code for directed ChPP implementation
- Fixed SQL.
- Fixed Documentation.
pgTAP tests for new functions
- InnerQuery for both functions.
Improve and fix
- Fix bugs in the graph generation part.
- Fix warnings.
- Lint the code.
- Create queries.
- Cost flow family.
Full implementation of pgr_minCostMaxFlow
- One to one version.
- One to many version.
- Many to one version.
Fix components license
- Change developers name & email address.
Implememt pgr_minCostMaxFlow basic code
- Create sql files.
Hand written copy of OSGeo mail
- “Route inspection problem - Wikipedia” https://en.wikipedia.org/wiki/Route_inspection_problem
- “Minimum-cost flow problem - Wikipedia” https://en.wikipedia.org/wiki/Minimum-cost_flow_problem
- “Minimum Cost Flows | Optimization | Google Developers” https://developers.google.com/optimization/flow/mincostflow
- “Efficient Algorithms for Finding Maximum Matching in Graphs” http://www.cs.kent.edu/~dragan/GraphAn/p23-galil.pdf
- “The Chinese Postman Problem” http://staff.ustc.edu.cn/~xujm/Graph16.pdf
- “Route Inspection (Chinese postman problem)” http://www.ucl.ac.uk/~ucahbtw/docs/d1lesson3/route_inspection_notes.pdf
- “Chinese postman problem” http://www.suffolkmaths.co.uk/pages/Maths%20Projects/Projects/Topology%20and%20Graph%20Theory/Chinese%20Postman%20Problem.pdf
- “successive_shortest_path_nonnegative_weights” http://www.boost.org/doc/libs/1_66_0/libs/graph/doc/successive_shortest_path_nonnegative_weights.html