[SoC] [GSoC 2018] Final Report - Implement Minimum cost flow and ChPP for pgRouting

Maoguang Wang xjtumg1007 at gmail.com
Sun Aug 19 11:10:24 PDT 2018

 Hi all,

I am Maoguang Wang, and This is my final report for my GSoC project.

*Title:  Implement Minimum-cost flow Algorithm by the Boost Graph Library
and Chinese Postman Problem for pgRouting *

*Organization: *pgRouting under OSGeo

*Abstract: *

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.

I have added Minimum-cost flow algorithm and directed ChPP algorithms to
pgRouting during this GSoC period.

*Implemented functions:*


* pgr_ChPP*
   - pgr_ChPP_Cost
   - pgr_minCostMaxFlow
   - pgr_minCostMaxFlow_Cost

*State of the art before the project: *pgRouting didn't have above
functionalities before my GSoC.

*Addition that my project brought to pgRouting: *

*The deliverables are code, full documentation, documentation tests, pgTap
of above functions.*

* Future Directions: *

   - Double confirm the documentation.
   - Implement undirected ChPP algorithms.
   - Implement windy or other complex ChPP problems.
   - Test the implementation in real cases.


   - *Wiki: *
   - *Last Pull Request:* https://github.com/pgRouting/pgrouting/pull/1077
   - *Slide: *
   - *Tag:* https://github.com/pgRouting/pgrouting/tree/gsoc2018-XJTUmg-lw

Best Regards,
Maoguang Wang
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20180820/b50c4ad0/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pgRouting Directed Chinese Postman.pdf
Type: application/pdf
Size: 79265 bytes
Desc: not available
URL: <http://lists.osgeo.org/pipermail/soc/attachments/20180820/b50c4ad0/attachment-0001.pdf>

More information about the SoC mailing list