▸Setup and compilation
- Fork this github project or install a copy on your insa git repository.
(Do not clone it locally, you will not be able to push anything. This is not yours.) - The project contains a Makefile, used only as a menu. You can understand what it does.(Do not believe the official make documentation which pretends that it can be used to compile projects.)
- The build system we use is OCaml's dune
- Try it: make clean, make, make demo
▸Discover the project modules
- You cannot compile the project using ocaml-top. Use any text editor instead, e.g.
emacs(configured as explained at the beginning of OCaml - Lesson 6) or VScode (make edit). - The base project contains two modules and a main program:
- graph.mli and graph.ml which define a module
Graph - gfile.mli and gfile.ml which define a module
Gfile - ftest.ml, the main program.
- graph.mli and graph.ml which define a module
- Look at the interfaces of
Graph(graph.mli) andGfile
All functions are already implemented in graph.ml and gfile.ml
You must not modify the moduleGraph, but you will have to create new modules and to modify Gfile. - Try to understand the graph file format (look at the example graph1 and read quickly gfile.ml)
- To ease the writing of algorithms, write a new module
Tools, with the following signature (the signature must be in file tools.mli) :Interface file
open Graph val clone_nodes: 'a graph -> 'b graph val gmap: 'a graph -> ('a -> 'b) -> 'b graph val add_arc: int graph -> id -> id -> int -> int graphImplementation file
(* Yes, we have to repeat open Graph. *) open Graph (* assert false is of type ∀α.α, so the type-checker is happy. *) let clone_nodes _gr = assert false let gmap _gr _f = assert false (* Replace _gr and _f by gr and f when you start writing the real function. *) ...clone_nodes grreturns a new graph having the same nodes than gr, but no arc. (code : one line)
In order to find your errors more quickly, you may add an annotation :let clone_nodes (gr:'a graph) = ...gmap gr fmaps all arcs of gr by function f. (⩽3 lines)add_arc g id1 id2 nadds n to the value of the arc between id1 and id2. If the arc does not exist, it is created.
- In order to test, you may use an online graph editor, and download your graphs.
- In order to visualize graphs, we will use the famous Graphviz library.
Write a new functionexportinGfilewhich writes a string graph in dot format (the format understood by graphviz). To understand the expected format, you just have to look at this example (click on the picture to get the source file).
To generate an image from a dot file, you can use:dot -Tsvg your-dot-file > some-output-file.svg
▸To be done
- Minimal acceptable project: you should at least implement the Ford-Fulkerson algorithm (in a separate module) and test it on several examples.
- You all remember the 3 MIC lecture on Graphs by Marie-Jo Huguet, and the associated Moodle resources graphes2024
- An interactive presentation of the algorithm.
- A french presentation of flow problems (see "Algorithmes des graphes / Flots").
- Medium project: find a use-case of this algorithm (e.g. network transportation, bandwidth, or bipartite matching) and write a program that solves the problem, given input files easier to write than graph files.
- An example with money sharing.
- Wikipedia offers several examples on its max flow page.
- The cricket elimination problem
- Finding where guests will sleep.
- Bipartite matching
- Object recognition through bipartite matching
- Better project: enhance the medium project by taking into account other constraints - and implementing the max-flow min-cost algorithm.
As an example, your program could be used to match a set of people to a set of ressources (e.g. students to projets tutorés, or future students to universites as in late APB) taking into account people's preferences. Your system should be as fair as possible and avoid biases.
▸Some technical support
Debugging
In order to activate debugging:- In the terminal, set the variable OCAMLRUNPARAM to b (means: backtrace)
export OCAMLRUNPARAM="b"then, you can launch your program.
How to start writing the Ford-Fulkerson algorithm (alert: SPOILER)
If you are stuck, you may start by writing a function which finds a path in a graph:
(* A path is a list of nodes. *)
type path = id list
(* find_path gr forbidden id1 id2
* returns None if no path can be found.
* returns Some p if a path p from id1 to id2 has been found.
*
* forbidden is a list of forbidden nodes (they have already been visited)
*)
find_path: int graph -> id list -> id -> id -> path option