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_CostState 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
pgRouting Directed Chinese Postman.pdf (77.4 KB)