Boîte à outils

Compilation

Pour un fichier A.cpp

make A

La commande officielle est :

g++ -w -O2 -pipe -std=gnu++0x A.cpp -o A

Tests

Pour exécuter un fichier de tests :

./A < A.in

Pour exécuter un tas de fichiers de tests :

for x in *in; do ./A < $x; done
cat *out # Pour comparer

Graphviz

Pour visualiser un graphe, la syntaxe est la suivante :

digraph G {
    rankdir=LR;
    s -> 1 [label=1];
    s -> 2;
    1 -> 3;
    1 -> 4 [label=1];
    2 -> 4;
    3 -> t;
    4 -> t [label=1];
}

Et la commande :

dot -Tpng graph.dot > graph.png

Donne le graphe suivant :

Par exemple, ce code C++ peut faire l’affaire :

void graphviz() {
    cout << "digraph G {" << endl;
    int v;
    for(int u = 0; u < 2 * n + 2; ++u) {
        for(int i = 0; i < graph[u].size(); ++i) {
            v = graph[u][i];
            cout << u << " -> " << v << "[label=" << flow[u * SIZE + v] << "];" << endl;
        }
    }
    cout << "}" << endl;
}

En remplaçant éventuellement flow par capacity.

Version OCaml

Merci à Clémence Réda pour cette version.

(* La fonction prend en argument un graphe non orienté sous forme de liste *)
(* d'adjacence et affiche le graphe correspondant sous forme d'un code DOT *)

type graphe = int*int list array;;

let print = Printf.printf;;

let grapheno g = 
  let n=Array.length g in
  print "graph g { \n";
  for i=0 to (n-1) do
     let rec affiche liste = match liste with
      |[] -> ()
      |(b,c)::q -> print "%d -- %d [label=%d]; \n" i b c;affiche q
     in affiche g.(i);
  done;print " } \n";;

(* version orientée *)

let grapheo g = 
  let n=Array.length g in
  print "digraph g { \n";
  for i=0 to (n-1) do
     let rec affiche liste = match liste with
      |[] -> ()
      |(b,c)::q -> print "%d -> %d [label=%d]; \n" i b c;affiche q
     in affiche g.(i);
  done; print " } \n";;

(* version avec liste d'arêtes, non orienté *)

let graphelno g =
   print "graph g { \n";
   let rec affiche liste = match liste with
     |[] -> print " } \n"
     |(i,j,poids)::q -> print "%d -- %d [label=%d]; \n" i j poids;affiche q
   in affiche g;;

(* version avec liste d'arêtes, orienté *)

let graphelo g =
   print "digraph g { \n";
   let rec affiche liste = match liste with
     |[] -> print " } \n"
     |(i,j,poids)::q -> print "%d -> %d [label=%d]; \n" i j poids;affiche q
   in affiche g;;

let graphe = [(1,2,0);(3,1,0);(4,5,0);(4,8,0);(1,7,0);(1,4,0);(7,1,0);(2,4,0)];;
graphelno graphe;;