Probleme – Sérialiser une structure relationnelle : le graphe

1. Les deux fonctions.

(* Un graphe orienté : des sommets étiquetés, et pour chacun ses successeurs. *)
type graphe = { noms : string array; arcs : int list array }

(* Écrit g sur le canal : n, les noms, m, puis les m couples (u, v). *)
let ecrire g canal =
  let n = Array.length g.noms in
  output_string canal (string_of_int n ^ "\n");
  output_string canal (String.concat " " (Array.to_list g.noms) ^ "\n");
  let m = Array.fold_left (fun s l -> s + List.length l) 0 g.arcs in
  output_string canal (string_of_int m ^ "\n");
  for u = 0 to n - 1 do
    List.iter (fun v ->
      output_string canal (string_of_int u ^ " " ^ string_of_int v ^ "\n"))
      g.arcs.(u)
  done

exception Format_invalide

(* Relit un graphe écrit par ecrire. Lève Format_invalide sur toute entrée
   incohérente. Complexité : Theta(n + m). *)
let lire canal =
  let n = int_of_string (String.trim (input_line canal)) in
  let noms = Array.of_list (String.split_on_char ' '
                              (String.trim (input_line canal))) in
  if Array.length noms <> n then raise Format_invalide;   (* le compte doit y être *)
  let m = int_of_string (String.trim (input_line canal)) in
  let arcs = Array.make n [] in
  for _ = 1 to m do
    match String.split_on_char ' ' (String.trim (input_line canal)) with
    | [a; b] ->
        let u = int_of_string a and v = int_of_string b in
        if u < 0 || u >= n || v < 0 || v >= n then raise Format_invalide;
        arcs.(u) <- v :: arcs.(u)
    | _ -> raise Format_invalide
  done;
  { noms; arcs = Array.map List.rev arcs }

Mesuré : le fichier produit pour le graphe des trois villes est exactement celui du chapitre —

3
Paris Lyon Nice
4
0 1
1 0
1 2
2 0

et l'aller-retour rend un graphe identique à l'original. Mesuré également sur le graphe cyclique $a\to b\to c\to a$ : l'aller-retour tient. Le cycle n'est pas un cas particulier du format — c'est là tout son intérêt.

2. Pourquoi le parcours au fil de l'eau échoue. Deux raisons, et elles sont distinctes.

• Le cycle : un parcours qui écrirait chaque sommet puis suivrait ses arcs ne terminerait pas sur $a\to b\to c\to a$. Il faudrait marquer les sommets visités — donc tenir un état extérieur à l'écriture.
• Le partage : même sans cycle, un sommet peut être atteint par plusieurs chemins. Le dag $a\to b$, $a\to c$, $b\to d$, $c\to d$ ferait écrire $d$ deux fois ; à la relecture, on obtiendrait deux sommets distincts au lieu d'un. Le parcours perd l'identité des sommets, et c'est précisément ce qu'un graphe encode.

L'arbre échappe aux deux : pas de cycle, et chaque nœud atteint par un unique chemin. La sérialisation d'un arbre peut être un parcours ; celle d'un graphe ne le peut pas. C'est pourquoi le format sépare deux sections — une pour les objets, une pour les liens.

3. Ce qu'il faut refuser. La lecture reçoit un fichier qu'elle n'a pas écrit : elle doit vérifier tout ce que l'écriture garantissait.

• Le nombre de noms doit valoir $n$ ;
• chaque numéro de sommet doit être dans $[0,n[$ — sans ce contrôle, arcs.(u) lèverait une exception d'indice, ou pire, en C, écrirait hors du tableau ;
• chaque ligne d'arc doit compter exactement deux entiers ;
• selon le contrat, on peut aussi refuser les arcs répétés (le programme « n'évoque pas les multi-arcs ») et les boucles.

Un contrôle qui manque au désérialiseur devient une faille, et c'est la voie d'attaque la plus classique qui soit : on envoie au programme un fichier presque valide, dont un champ dépasse.

4. Le lien avec la clé étrangère. Dans le fichier, le lien « Paris va vers Lyon » s'écrit 0 1 : deux valeurs. En mémoire, il s'écrivait comme un indice dans un tableau — et dans une réalisation par pointeurs, comme une adresse. Une adresse n'a de sens que dans le processus qui l'a produite : elle change au relancement, elle ne survit pas à l'écriture sur disque, elle n'a aucun sens sur une autre machine.

Le numéro de sommet est une référence portable : elle ne désigne rien par elle-même, mais elle désigne sans ambiguïté relativement à la table des sommets écrite juste au-dessus. C'est exactement la clé étrangère du chapitre chap:sql : une table Trajet(depart, arrivee) dont les colonnes contiennent des valeurs qui référencent la clé primaire de Ville. Le modèle relationnel a fait de cette contrainte sa règle fondatrice — aucun lien n'est une adresse, tout lien est une valeur —, et c'est ce qui permet à une base de survivre à l'arrêt de la machine, d'être copiée, sauvegardée, jointe à une autre.

Le principe, en une phrase : sérialiser, c'est remplacer chaque adresse par une valeur qui la désigne dans un espace de noms explicitement écrit. Le marqueur # le faisait pour la forme d'un arbre ; les numéros le font pour les liens d'un graphe.