GSoC 2016 Flow - pgRouting/pgrouting GitHub Wiki

GSoC 2016: Flow Algorithms

tag: https://github.com/pgRouting/pgrouting/releases/tag/gsoc%2Fflow-lw

Abstract

This project aims to add functionality in order to solve the maximum flow problem in pgRouting.

A flow network is a directed graph where each edge has a capacity and a flow. The flow through an edge must not exceed the capacity of the edge. Additionally, the incoming and outgoing flow of a node must be equal except the for source which only has outgoing flow, and the destination(sink) which only has incoming flow.

Flow algorithms have several other applications in network routing, delivery & transportation, circulation and more.

For more info, please contact me!

End of work summary

Scroll down for Week 12 report for more info.
Copying links here so that they're immediately available:
Commits - https://github.com/pgrouting/pgrouting/commits/gsoc-flow?author=Illedran
Pull requests - https://github.com/pgRouting/pgrouting/pulls?utf8=%E2%9C%93&q=is%3Apr%20author%3AIlledran
Demo slides - https://docs.google.com/presentation/d/1Gbmfhzixhwit0AcfWEbNhMKQlL3fgdxqoqDzL-xvEE8/pub?start=false&loop=true&delayms=3000

Table of Contents

Reports

Week 12

The goal of my project was adding functionality to solve maximum flow problems to the pgRouting library.
Maximum flow problems involve routing the maximum amount of a commodity from a single source S to a single sink T. Previously, there were no such functions in the library.

With my work this summer, I added three algorithms that solve this problem and example applications that utilize them:

  • Edge disjoint paths
  • Maximum cardinality matching
  • Multiple sources/sinks flow

Additionally, tests and documentation was produced for everything that was coded.

I worked on my fork of the repository on the branch gsoc-flow and made pull requests weekly.
List of pull requests and commits.
My work is part of the 2.3.0 release of pgrouting.

If you want to test my code, you can build the library for yourself following the guidelines here: http://docs.pgrouting.org/dev/en/doc/src/installation/build.html

Demo slides: https://docs.google.com/presentation/d/1Gbmfhzixhwit0AcfWEbNhMKQlL3fgdxqoqDzL-xvEE8/pub?start=false&loop=true&delayms=3000

Week 11

  1. What did you get done this week?

As said in the last report, this week I was on holiday and could not work.

  1. What do you plan on doing next week?

The release of pgRouting 2.3 is imminent. As such, I will mostly focus on completing all the user and developer documentation by adding more examples, tests and improving the sample data.

  1. Are you blocked on anything?

No.

Week 10

  1. What did you get done this week?

This week I did the code improvements I mentioned last week. All of the functions now have an additional return value that represents the ID of the original edge in the graph. This meant I had to refactor docs and tests. For the remainder of the week, a lot of work went into making sure the project builds correctly on Travis and Appveyor, with the tests included.

  1. What do you plan on doing next week?

Next week I am going to be on holiday, so I will not be able to work.

  1. Are you blocked on anything?

No.

Week 9

  1. What did you get done this week?

This week I started studying the algorithm in the paper I linked last week. It is quite complicated and requires knowledge of a lot of other algorithms (it is made up of different sub-algorithms with better complexities it can fall back to). I started prototyping these in Python. For the rest of the week I implemented a way for the edge_disjoint_paths function to actually return the paths and not just their number.

  1. What do you plan on doing next week?

Next week I plan to do several things:

  • Continue studying additional max_flow implementations.
  • Finish up all the possible signatures for the new edge_disjoint_paths function.
  • While working this week, I realized that there are a lot of small things I can add and improve through the codebase, in regards to both functionality and efficiency.
  1. Are you blocked on anything?

No.

Week 8

  1. What did you get done this week?

This week I finished writing most part of the documentation, tests, and examples. PgTAP unit tests were written to test all the signatures&parameters of the max flow functions and error handling was added where it was required. I also refactored the signature of maximum cardinality matching and edge disjoint paths after discussion with the mentors. Edge-disjoint paths now also works with multiple sources/destinations.

  1. What do you plan on doing next week?

Next week I plan to do several things:

  • Add more PgTAP tests covering other functions and checking of the actual results.
  • Expand the pgr_edgedisjointpaths function in order to list all the actual paths and not just the number.
  • Feasibility study on implementing other possible implementations of maxflow that offer even better complexities. Discussion with mentors on this topic.
  1. Are you blocked on anything?

No.

Week 7

  1. What did you get done this week?

This week I wrote some documentation and examples for some of the signatures I mentioned last week. I also added another application that calculates the number of edge disjoint paths between two vertices. Currently, this only calculates the number of paths and not all the edges of the paths through the graph. This is a possible addition I am looking into. I also refactored the signature of the maximum cardinality matching function to include a parameter for directed/undirected graphs.

  1. What do you plan on doing next week?

Now that the majority of the code is written, I want to focus on the documentation, a lot of which is still missing. I am also interested in looking into automating tests using PgTAP.

  1. Are you blocked on anything?

No.

Week 6

  1. What did you get done this week?

I created all the possible signatures for one to one, one to many, many to one and many to many versions of the maximum flow algorithms. Additionally, some major internal code revision happened which led to a lot less code duplication, more clarity and higher maintainability. I added an additional function from boost that calculated the maximum cardinality matching in a graph.

  1. What do you plan on doing next week?

Due to the code changes, some of the documentation will have to change. Additionally, I need to write some more for the new function and also write tests for all of this: I plan to work on this next week.

  1. Are you blocked on anything?

No.

Week 5

  1. What did you get done this week?

This week I created some additional sample data in order to better show off the functionality of flow algorithms. I also started to try writing some PgTAP tests but I am going to need help to check exactly what I need to test, how, etc... I also created a function that calculates the max flow for multiple sources/sinks.

  1. What do you plan on doing next week?

While creating the multiple source/sink version I realized that maybe the current function signatures I have planned have not been so good. I want to discuss this with my mentors and possibly have only one function with the implementation as a parameter. Once that is done, I can move on to writing the documentation and other implementations.

  1. Are you blocked on anything?

I am going to ask for help about writing the PgTAP tests in this coming week.

Week 4

  1. What did you get done this week?

This week was spent adding the code for the last implementation for maximum flow (Boykov-Kolmogorov) offered by Boost and refactoring a bit some of the code after some discussions with my mentors. The rest of the time was spent adding documentation.

  1. What do you plan on doing next week?

Now that all the implementations and the base of the documentation is down, I can actually start writing some applications. I also think it could be useful to have some more different sample data in order to show off the algorithms.

  1. Are you blocked on anything?

No.

Week 3

  1. What did you get done this week?

As said in my last report, I did not have time to work as much due to my finals. I managed to add the code for the last maximum flow implementation but I still have to fix some details in the PostgreSQL functions.

  1. What do you plan on doing next week?

Next week will be the last one before the mid term assessments. I plan to fix what I said above, finish the documentation and discuss with my mentors about any improvement to the code, tests, etc...

  1. Are you blocked on anything?

No.

Week 2

  1. What did you get done this week?

I implemented an additional wrapper using Boost and wrote some tests. I cleaned up/refactored some of the code, in particular the common library between all the implementations(the one that handles creating the graph and returning the results).

  1. What do you plan on doing next week?

As written in my application, next week I won't be able to work as much due to finals at my university. However, I think I can manage to add the last implementation from Boost.

  1. Are you blocked on anything?

No, but I need to learn how to write the documentation more efficiently.

Week 1

  1. What did you get done this week?

I created a working example using the sample data using an implementation from Boost. I also started working on documentation, but that is a still a work in progress.

  1. What do you plan on doing next week?

Clean code, continue the documentation and possibly add different implementations offered from Boost.

  1. Are you blocked on anything?

Nope.

Plans

August 10

  • Plan date: August 10
  • overall STATUS:
  • Completed Date: August 13
Task Status
Expanded PgTAP tests: type-checking DONE
Automated example queries for documentation DONE
Updated documentation DONE
Getting ready for pgRouting 2.3 DONE

July 31

  • Plan date: July 31
  • overall STATUS: PENDING
  • Completed Date:
Task Status
Expanded edge disjoint paths function for routes DONE
Added PgTAP tests for max flow applications DONE
Expanded all function signatures with edge_id DONE
Building on Travis & Appveyor DONE
Tests on Travis & Appveyor DONE

July 12

  • Plan date: July 12
  • overall STATUS: DONE
  • Completed Date: July 24
Task Status
Write docs DONE
Discuss "basic" edge for function signatues DONE
Refactor maximum cardinality matching DONE
Added edge disjoint paths function DONE
Edge disjoint paths one/many to many/one DONE
Write automated tests with PgTAP DONE

June 26

  • Plan date: June 26
  • overall STATUS: Pending
  • Completed Date:
Task Status
Do sample application with multi source/sink DONE
Discuss function signatures with mentors DONE

June 17

  • Plan date: June 17
  • overall STATUS: Done
  • Completed Date: June 26
Task Status
Split SQL files into one for each implementation DONE
Add tests for 3rd implementation DONE
Camel case function names DONE
Merge develop and Windows branches DONE

June 5

  • Plan date: June 5
  • overall STATUS: Done
  • Completed Date: June 17
Task Status
Code refactoring DONE
Create implementation #3 (boykov-kolmogorov) DONE
Create implementation #2 (edmonds-karp) DONE
Work on docs... DONE
Default maxflow implementation in SQL DONE
Create tests DONE

May 16

  • Plan date: May 16
  • overall STATUS: DONE
  • Completed Date: June 5
Task Status
Flow function signatures DONE
Created implementation #1 (push-relabel) DONE
Real data example DONE(using sample data)
Create initial documentation DONE
Code template DONE
Create example DONE

May 11

  • Plan date: May 11
  • overall STATUS: DONE
  • Completed Date: May 16
Task Status
Find a way to visualize input & results DONE
Update branches DONE

April 29

  • Plan date: April 29
  • overall STATUS: DONE
  • Completed Date: May 11
Task Status
Test genrmf DONE
Work on issue #555 DONE
Created issue #559 DONE
Issue 555 Status
Create branch hotFix/issue555 DONE
Modify documentation file: pgr_analyzeGraph.rst DONE
Push & pull request DONE
Wait for merge DONE
Generate updated documentation DONE
Update documentation on gh_pages DONE

April 24

  • Plan date: April 24
  • overall STATUS: DONE
  • Completed Date: May 2
Task Status
Reorganizing dev environment & my workstation DONE
Watch videos (see below) DONE
Write report on videos DONE
Read docs of Boost Graph Library DONE
Reproduce examples DONE
Rewrite abstract DONE

The max flow algorithms in Boost follow the DIMACS max flow problem specification. I reproduced the examples found here, scroll down to max_flow.

Also found this for generating input data: genrmf

Calendar

Important dates

(see application for tentative task description)

Day(s) -
Apr 25 Liberation Day (National holiday) - no coding
May 23 - Jun 05 Coding starts - Task 1
Jun 02 Republic Day (National holiday) - no coding
Jun 06 - Jun 12 Finals week - no coding
Jun 13 - Jun 20 Finishing up Task 1
Jun 20 - Jun 27 Midterm evaluation
Jun 28 - Jul 12 Task 2
Jul 13 - Jul 31 Task 3
Aug 01 - Aug 07 Holidays (also, birthday on the 1st) - no coding
Aug 08 - Aug 14 Writing tests, fixing bugs...
Aug 15 - Aug 23 Submissions
Aug 23 - Aug 29 Final evaluation

Reports

Mini-report/thoughts on C++ videos:

Lots of very interesting things in the STL one. The partial_sort vs nth_element + sort example got me thinking: I studied the quickselect implementation to solve the problem and was curious whether the STL actually uses it. Turns out it actually uses introselect which switches between the good average performance algorithm and the best worst performance algorithm.

Other stuff: Move constructors

References