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

[Maoguang Wang]

 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.

*Links:*

   - *Wiki: *
   https://github.com/pgRouting/pgrouting/wiki/GSoC-2018-Minimum-cost-flow-and-ChPP
   - *Last Pull Request:* https://github.com/pgRouting/pgrouting/pull/1077
   - *Slide: *
   https://docs.google.com/presentation/d/1WsnhuOhcsl_SADo3AO8VFO3hIAXuLxIHhrGsAMDfOKY/edit?usp=sharing
   - *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>