GSoC 2018 Minimum cost flow and ChPP - pgRouting/pgrouting GitHub Wiki
Table of Contents
- Proposal
- Tag
- Slide
- Timeline
- 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)
- Reports
- References
Proposal
Brief Description
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.
Proposal pdf
Tag
https://github.com/pgRouting/pgrouting/tree/gsoc2018-XJTUmg-lw
Slide
https://docs.google.com/presentation/d/1WsnhuOhcsl_SADo3AO8VFO3hIAXuLxIHhrGsAMDfOKY/edit?usp=sharing
Timeline
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.
Reports
Week 12
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-August/001912.html
PR: https://github.com/pgRouting/pgrouting/pull/1077
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.
Week 11
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-July/001907.html
PR: https://github.com/pgRouting/pgrouting/pull/1072
Documentation for directedChPP
- Family page.
- pgr_directedChPP page.
- pgr_directedChPP_Cost page.
Week 10
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-July/001901.html
PR: https://github.com/pgRouting/pgrouting/pull/1067
Tests for pgr_directedChPP
- Documentation tests.
- pgTAP tests.
Week 9
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-July/001898.html
PR: https://github.com/pgRouting/pgrouting/pull/1065
Fix bugs and improve code
- Fixed compile errors.
- Fixed
edge_id
issue. - Fixed issue when the graph is not connected.
Week 8
Report Mail:
PR: https://github.com/pgRouting/pgrouting/pull/1059
Implementation of pgr_directedChPP
- Implement Fleury algorithm.
- Fix bugs.
- basic tests.
Week 7
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-June/001892.html PR: https://github.com/pgRouting/pgrouting/pull/1052
Implementation of pgr_directedChPP_Cost
- Implement
.hpp
fiile. - Fixed compiled errors.
- Fixed runtime errors.
Week 6
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-June/001889.html PR: https://github.com/pgRouting/pgrouting/pull/1048
Get ready for full implementation of pgr_directedChPP
-
directedChPP.c
-
directedChPP_driver.cpp
-
directedChPP_driver.h
-
.sql
files.
Week 5
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-June/001886.html
PR: https://github.com/pgRouting/pgrouting/pull/1045
Basic code for directed ChPP implementation
-
directedChPP.c
-
directedChPP_driver.cpp
-
.hpp
&_driver.h
-
.sql
Week 4
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-June/001882.html
PR: https://github.com/pgRouting/pgrouting/pull/1040
- Fixed SQL.
- Fixed Documentation.
pgTAP tests for new functions
-
pgr_minCostMaxFlow
types check. -
pgr_minCostMaxFlow_Cost
types check. - InnerQuery for both functions.
Week 3
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-June/001878.html
PR: https://github.com/pgRouting/pgrouting/pull/1037
Improve and fix
- Fix bugs in the graph generation part.
- Fix warnings.
- Lint the code.
Documentation Tests
-
pgr_minCostMaxFlow
-
pgr_mimCostMaxFlow_Cost
- Create queries.
Documentation
- Cost flow family.
-
pgr_minCostMaxFlow
-
pgr_mimCostMaxFlow_Cost
Week 2
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-May/001874.html
Full implementation of pgr_minCostMaxFlow
PR: https://github.com/pgRouting/pgrouting/pull/1032
- Create
pgr_costFlowGraph.hpp
file. - Create
pgr_minCostMaxFlow.hpp
file. - Change
id
toedge_id
inpgr_costFlow_t
. - One to one version.
- One to many version.
- Many to one version.
Week 1
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-May/001872.html
Fix components license
PR: https://github.com/pgRouting/pgrouting/pull/1028
- Change developers name & email address.
Implememt pgr_minCostMaxFlow basic code
PR: https://github.com/pgRouting/pgrouting/pull/1022
- Create
minCostMaxFlow.c
&minCostMaxFlow_driver.cpp
files. - Create
minCostMaxFlow_driver.h
file. - Create
pgr_costFlow_t.h
file inc_types
. - Extend
pgr_flow_t
(cost
andreverse_cost
). - Create sql files.
Bonding
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-May/001870.html
Hand written copy of OSGeo mail
References
- “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