<div dir="ltr">
<font size="2" face="arial, helvetica, sans-serif"><div>Hi all,<br></div></font><div><font size="2" face="arial, helvetica, sans-serif"><br></font><div><font size="2" face="arial, helvetica, sans-serif">I am Maoguang Wang, and This is my final report for my GSoC project.</font></div><div><font size="2"><br></font></div><div><font size="2" face="arial, helvetica, sans-serif"><b>Title: 
<span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap" id="gmail-docs-internal-guid-ce3b366b-7fff-f94b-0de5-788435d8c5b6">Implement Minimum-cost flow Algorithm by the Boost Graph Library and Chinese Postman Problem for pgRouting</span><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:700;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap"> </span>

</b></font></div><div><font size="2" face="arial, helvetica, sans-serif"><br></font></div><div><font size="2" face="arial, helvetica, sans-serif"><b>Organization:<span> </span></b>pgRouting under OSGeo</font></div><div><font size="2"><b><font face="arial, helvetica, sans-serif"><br></font></b></font></div><div><font size="2" face="arial, helvetica, sans-serif"><b>Abstract: 
</b></font><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt" id="gmail-docs-internal-guid-c3d0922e-7fff-e644-74aa-8763e10d8d18"><font size="2"><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">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.</span></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font size="2"><span style="font-family:Arial;color:rgb(0,0,0);background-color:transparent;font-weight:400;font-style:normal;font-variant:normal;text-decoration:none;vertical-align:baseline;white-space:pre-wrap">I have added Minimum-cost flow algorithm and directed ChPP algorithms to pgRouting during this GSoC period.</span></font></p>

</div><div><font size="2" face="arial, helvetica, sans-serif"><br></font></div><div><font size="2" face="arial, helvetica, sans-serif"><b><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);display:inline">Implemented functions</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-weight:400;display:inline">:</p><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-weight:400;display:inline"><br></p></b></font><ul><li><font size="2" face="arial, helvetica, sans-serif"><b><p style="box-sizing:border-box;margin-top:0px;margin-bottom:16px;color:rgb(36,41,46);font-weight:400;display:inline">pgr_ChPP</p></b></font></li><li><font size="2" face="arial, helvetica, sans-serif">pgr_ChPP_Cost</font></li><li><font size="2" face="arial, helvetica, sans-serif">pgr_minCostMaxFlow</font></li><li><font size="2" face="arial, helvetica, sans-serif">pgr_minCostMaxFlow_Cost<br></font></li></ul></div><div><font size="2"><b><font face="arial, helvetica, sans-serif"><br></font></b></font></div><div><font size="2" face="arial, helvetica, sans-serif"><b>State of the art before the project:<span> </span></b>pgRouting didn't have above functionalities before my GSoC. </font></div><div><font size="2"><b><pre style="white-space:pre-wrap;color:rgb(0,0,0);font-weight:400;display:inline"><font face="arial, helvetica, sans-serif"><br></font></pre></b></font></div><div><font size="2"><b><pre style="white-space:pre-wrap;color:rgb(0,0,0);display:inline"><font face="arial, helvetica, sans-serif">Addition that my project brought to pgRouting: </font></pre></b><b><pre style="white-space:pre-wrap;color:rgb(0,0,0);display:inline"><pre style="white-space:pre-wrap;font-weight:400;display:inline"><font face="arial, helvetica, sans-serif">The deliverables are code, full documentation, documentation tests, pgTap of above functions.</font></pre></pre></b><b><pre style="white-space:pre-wrap;color:rgb(0,0,0);display:inline"><font face="arial, helvetica, sans-serif"><br></font><font face="arial, helvetica, sans-serif"><span style="font-weight:400">
</span>Future Directions:<span style="font-weight:400"> </span></font><br></pre></b></font></div><div><ul style="color:rgb(34,34,34);font-family:arial,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><li><font size="2">Double confirm the documentation.</font></li><li><font size="2">Implement undirected<font face="arial, helvetica, sans-serif"><b> </b>ChPP algorithms.</font></font></li><li><font size="2"><font face="arial, helvetica, sans-serif">Implement windy or other complex ChPP problems.</font></font></li><li><font size="2"><font face="arial, helvetica, sans-serif">Test the implementation in real cases.<br></font></font></li></ul><div><div><font size="2" face="arial, helvetica, sans-serif" color="#000000"><span style="white-space:pre-wrap"><b>Links:</b></span></font></div></div><div><ul style="color:rgb(34,34,34);font-family:arial,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><li style="margin-left:15px"><font size="2"><b>Wiki: </b><a href="https://github.com/pgRouting/pgrouting/wiki/GSoC-2018-Minimum-cost-flow-and-ChPP" style="color:rgb(17,85,204)" target="_blank">https://github.com/pgRouting/pgrouting/wiki/GSoC-2018-Minimum-cost-flow-and-ChPP</a></font></li><li style="margin-left:15px"><font size="2"><b>Last Pull Request:</b> <a href="https://github.com/pgRouting/pgrouting/pull/1077" style="color:rgb(17,85,204)" target="_blank">https://github.com/pgRouting/pgrouting/pull/1077</a><br></font></li><li style="margin-left:15px"><font size="2"><b>Slide: </b><a href="https://docs.google.com/presentation/d/1WsnhuOhcsl_SADo3AO8VFO3hIAXuLxIHhrGsAMDfOKY/edit?usp=sharing" style="color:rgb(17,85,204)" target="_blank">https://docs.google.com/presentation/d/1WsnhuOhcsl_SADo3AO8VFO3hIAXuLxIHhrGsAMDfOKY/edit?usp=sharing</a></font></li><li style="margin-left:15px"><font size="2"><b>Tag:</b> <a href="https://github.com/pgRouting/pgrouting/tree/gsoc2018-XJTUmg-lw" style="color:rgb(17,85,204)" target="_blank">https://github.com/pgRouting/pgrouting/tree/gsoc2018-XJTUmg-lw</a></font></li></ul><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><font size="2"><br></font></div><div style="color:rgb(34,34,34);font-family:arial,sans-serif;font-style:normal;font-variant-ligatures:normal;font-variant-caps:normal;font-weight:400;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;background-color:rgb(255,255,255);text-decoration-style:initial;text-decoration-color:initial"><font size="2">Best Regards,</font></div><font size="2">Maoguang Wang</font><br></div></div></div>

</div>