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).
Additional Information: Please use the current Rocs version from GIT master. For details how to obtain this, see http://techbase.kde.org/Projects/Edu/Rocs.
Contact: For any questions, please search me on irc.freenode.net in #kde-edu or #kde-soc. My time zone is UTC+1.