-
-
Notifications
You must be signed in to change notification settings - Fork 370
GSoC 2018 Minimum cost flow and ChPP
- Proposal
- Branch
-
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
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.
Previously there is no functionality which calculates Minimum-cost flow or ChPP in the library.
https://github.com/pgRouting/pgrouting/tree/gsoc/ch_postman
- 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.
- 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.
- Implement Minimum-cost flow algorithm by the BGL.
- If needed, copy the needed BGL header file to pgRouting.
- Write full documentation for Minimum-cost flow implementation.
- Create unit tests and documentation tests for Minimum-cost flow implementation.
- 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.
- Prepare basic code and test framework for directed ChPP implementation.
- Implement pgr_directedChPP.
- Mentors evaluate me and I evaluate mentors of officail coding period phase 2.
- Deliver the directed ChPP implementation.
- Create documentation for the directed ChPP implementation.
- Create unit tests and documentation tests for the directed ChPP implementation.
- Fix bugs and documentation details.
- If time permits, implement pgr_directedChPP_Cost.
- Prepare for final delivery.
- Wrap up my projects and submit final evaluation of my mentors.
Report Mail: PR: https://github.com/pgRouting/pgrouting/pull/1040
- Fixed SQL.
- Fixed Documentation.
-
pgr_minCostMaxFlow
types check. -
pgr_minCostMaxFlow_Cost
types check. - InnerQuery for both functions.
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-June/001878.html
PR: https://github.com/pgRouting/pgrouting/pull/1037
- Fix bugs in the graph generation part.
- Fix warnings.
- Lint the code.
-
pgr_minCostMaxFlow
-
pgr_mimCostMaxFlow_Cost
- Create queries.
- Cost flow family.
-
pgr_minCostMaxFlow
-
pgr_mimCostMaxFlow_Cost
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-May/001874.html
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.
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-May/001872.html
PR: https://github.com/pgRouting/pgrouting/pull/1028
- Change developers name & email address.
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.
Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-May/001870.html
- “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