GSoC/GCI Archive
Google Code-in 2012 KDE

KDE Edu (Rocs): Create Example Implementation of the Ford-Fulkerson Algorithm

completed by: Andromeda Galaxy

mentors: Andreas Cord-Landwehr

Rocs is a Graph Theory IDE for everybody interested in designing and analyzing graph algorithms. (For more information please refer to the Rocs handbook or the website). In this task, you have to implement the famous "Ford-Fulkerson" algorithm that solves the maximum-flow problem for networks.

The Task in Detail: The steps to complete your task are the following:

  • Understand how the Ford-Fulkerson Algorithm works (especially if you never saw it before!) and understand what problem it solves.
  • Create a project in Rocs (You must either use Rocs from the master branch or the Project Neon nightly build packages! If you want to use Rocs from GIT master, instructions can be found at the link at the end of this description.)
  • Create a meaningful graph for a flow network and assign values to the edges.
  • Implement the algorithm and check that it works.
  • Add interrupts at the algorithm (see the handbook) at meaningful positions (e.g., when an "augmenting path" is computed; such a path can also be visualized by colors to show how the algorithm works).
The goal for this task is that a student, who previously did not know the Ford-Fulkerson algorithm, can understand how it works, only be reading the text in the journal and by executing the algorithm step by step. This means that you should explain the algorithm's idea in the journal and tell the student how to execute the algorithm to see the acting of the algorithm.

Additional Information: Please use the current Rocs version from GIT master. For details how to obtain this, see

Contact: For any questions, please search me on in #kde-edu or #kde-soc. My time zone is UTC+1.