GSoC 2018 Minimum cost flow and ChPP

Table of Contents

• Proposal
  • Brief Description
  • State of the project before GSoC
  • Proposal pdf
• Branch
• Timeline
  • Community Bonding Period (April 23 to May 13, 2018)
  • Official Coding Period Phase 1 (May 14 to June 10, 2018)
    • Week 1 (May 14 to May 20, 2018)
    • Week 2 (May 21 to May 27, 2018)
    • Week 3 (May 28 to June 3, 2018)
    • Week 4 (June 4 to June 10, 2018)
  • First evaluation period (June 11 to June 15, 2018)
  • Official Coding Period Phase 2 (June 11 to July 8, 2018)
    • Week 5 (June 11 to June 17, 2018)
    • Week 6 to 8 (June 18 to July 8, 2018)
  • Second evaluation period (July 9 to July 13, 2018)
  • Official Coding Period Phase 3 (July 9 to August 5, 2018)
    • Week 9 to 10 (July 9 to July 22, 2018)
    • Week 11 (July 23 to July 29, 2018)
    • Week 12 (July 30 to August 5, 2018)
  • Final evaluation period (August 6 to August 14, 2018)
• Reports
  • [Week 12)(#week-12)
    • Prepare for final delivery
  • Week 11
    • Documentation for directedChPP
  • Week 10
    • Tests for pgr_directedChPP
  • Week 9
    • Fix bugs and improve code
  • Week 8
    • Implementation of pgr_directedChPP
  • Week 7
    • Implementation of pgr_directedChPP_Cost
  • Week 6
    • Get ready for full implementation of pgr_directedChPP
  • Week 5
    • Basic code for directed ChPP implementation
  • Week 4
    • pgTAP tests for new functions
  • Week 3
    • Improve and fix
    • Documentation tests
    • Documentation
  • Week 2
    • Full implementation of pgr_minCostMaxFlow
  • Week 1
    • Fix components license
    • Implememt pgr_minCostMaxFlow basic code
  • Bonding
    • Hand written copy of OSGeo mail
• 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

Project proposal

Branch

https://github.com/pgRouting/pgrouting/tree/gsoc/ch_postman

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:
PR:

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.

Week 11

Report Mail:
PR: https://github.com/pgRouting/pgrouting/pull/1072

Documentation for directedChPP

• Family page.
• pgr_directedChPP page.
• pgr_directedChPP_Cost page.

Week 10

Report Mail:
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 to edge_id in pgr_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 in c_types.
• Extend pgr_flow_t (cost and reverse_cost).
• Create sql files.

Bonding

Report Mail: https://lists.osgeo.org/pipermail/pgrouting-dev/2018-May/001870.html

Hand written copy of OSGeo mail

• issue: https://github.com/XJTUmg/pgrouting/issues/14

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