Rapport: les bases de graphviz

Graphviz est un logiciel libre de représentation de graph. Il permet de représenter des graph à l’aide d’une syntaxe simple, que l’on peut rendre un peu plus complexe afin d’ajouter du style à notre graph (forme des élements, couleurs). On peut ensuite récupérer le rendu de notre travail sous divers formats d’images. Il est également possible de génerer des graph à l’aide de programme codés en C ou en Python. On utilisera alors un interpréteur du langage DOT selon le rendu que l’on désire, afin d’obtenir un graph à partir d’un code. Cet outils est donc assez utile en mathématiques mais également en programmation lorsque l’on souhaite avoir une meilleure idée des opérations qu’effectue notre code.

La conjecture de Syracuse, aussi appelée algorithme ou suite de Syracuse, est un problème mathématique à l’énoncé élémentaire qui défie les chercheurs depuis plus de 80 ans. Elle peut être définie sous forme d’une suite, ou peut être codé dans diverses langages de programmation. On la définie plus généralement de la façon suivante:

∀ n∈ N

Cette conjecture énonce que pour tout les nombres entiers positifs à qui on applique cette suite, leur suite de Syracuse va forcément tomber au bout d’un certain nombre d’opérations sur le cycle 4,2,1 qui se répetera indéfiniement. C’est le cycle trivial.

Le but de l’exercice est le suivant. A l’aide d’un programme en C et de l’outil Graphviz, il faut créer un arbre représentant la suite de Syracuse. Le but est de montrer tout les antécedents de 1 jusqu’à un certain nombre prédéfini, afin d’obtenir un arbre dont les branches et les feuilles correspondent au nombre généré par l’algorithme de la suite de Syracuse. Le tronc de l’arbre sera forcement composé des trois nombres du cycle trivial, et le nombre le plus bas de l’arbre sera donc 1.

Afin de résoudre ce problème j’ai donc programmé un code en C. Il utilise la stratégie suivante:

• n admet forcément un antécedent pair, on l’affiche et le calcul donc à chaque tour de boucle
• Si (n-1)%6 vaut 3, alors n admet également un antécedent impair, on l’affiche et le calcul dès que le programme détecte qu’il existe.

Le fait de code une fonction en dehors du main permet d’utiliser le mécanisme de récursion, essentiel à la réalisation du graph. Enfin, un dernier élement rentre en jeu afin de pouvoir créer le graph. Il faut définir une hauteur permettant au programme de s’arréter et de ne pas créer une boucle infini. Cela permettra également d’équilibrer notre arbre et de le rendre plus agréable à regarder. On réduira la hauteur de 1 à chaque appelle de la fonction. Quand cette variable vaudra 0, alors on arrétera le programme.

Voici ci-dessous le code m’ayant permi de réaliser le graph:

#include<stdio.h>

int syracuse(int n, int hauteur){

  if(hauteur!=0){  // On execute le programme tant que on a pas atteint la hauteur maximale
    printf("%d->%d\n",n*2,n); // Affichage de l'antécédent pair
    syracuse(n*2,hauteur-1);  // Répétition du programme pour l'antécédent pair


  if((n-1)%6==3 && n!=4){ // Si n admet un antécedent impair
    printf("%d->%d\n",(n-1)/3,n); // On l'affiche
    syracuse((n-1)/3,hauteur-1); // Répétition du programme pour l'antécedent impair
  }
  }
  return 0;
}

int main(){
  int hauteur=17;  // Définition de la hauteur de l'arbre
  printf("strict digraph{\n"); // Début du graph
  syracuse(1,hauteur); // Ecriture du graph grace à la fonction Syracuse
  printf("}\n"); // Fin du graph
  return 0;
}

Et maintenant voici le graph obtenu. Il a été légerement modifié avec l’outil Sketchviz, qui permet d’ajouter un style crayonné à nos graph.

Nous allons maintenant nous intéresser à une autre fonction, cette fois ci à deux variables. Cette fonction est définie sous la forme suivante:

Le problème est le suivant, il faut créer un graph qui montrera pour certaines valeurs de i et de j, quels sont les appelles de fonction qui sont généré par ce couple de valeurs. Pour cela nous allons utiliser un programme en C qui générera le graph attendu.

Afin de tracer le graph, on va utiliser un programme en C. Il n’est pas utile de coder ce que renvoi la fonction, puisque l’on souhaite tracer le graphique des appels. On doit seulement se concentrer sur les couples (i,j). On distingue 3 cas:

• Si j vaut 0, on affiche rien car aucun autre appel ne sera généré.
• Si i<j, on trace le couple (i+1,j) relié au couple (i,j). On appelera également notre fonction par récursion avec les valeurs (i+1,j).
• Enfin, dans les autres cas, on tracera les couples (k,j-1) à l’intérieur d’une boucle for, et on appelera la fonction avec ces mêmes couples à l’intérieur de la boucle.

La récursion finira forcément par s’arréter puisque il existe un cas où l’on ne génère aucuns autres couples. De plus, dans la troisième boucle on réduit la valeur de j, ce qui forcera l’arrét de la fonction après un certain nombre d’opérations.

Ci dessous, voici le code que j’ai utiliser pour produire le graph.

#include <stdio.h>

int fonction(int i,int j){

  int k;

  if(j==0){ // Si j=0 rien n'est tracé sur le graph
    return 1;
  }
  else if (i<j) { // Si i<j
    printf("{\"%d, %d\"}->{\"%d, %d\"}",i,j,i+1,j); // On trace le couple i,j et l'appel
                                                    // qu'il génère
    fonction(i+1,j); // On appelle à nouveau notre fonction

  }else{
    for(k=0;k<=i-1;k++){ // On crée une boucle pour obtenir toutes les valeurs de k
      fonction(k,j-1);  // On appelle à nouveau notre fonction
      printf("{\"%d, %d\"}->{\"%d, %d\"}",i,j,k,j-1); // On trace sur le graph
                                          // le couple i,j et les couples qu'il génère
      }}
return 0;
  }


int main(){

  int i=5;
  int j=3;
    printf("digraph{\n"); // Début du graph
    printf("{\"%d, %d\"}",i,j); // Tracé du premier couple
    fonction(i,j); // Tracé du graph grace à la fonction définie plus haut
    printf("}\n"); // Fin du graph

return 0;
  }

Et maintenant, voici le graph de la fonction, avec pour valeur de départ, le couple (5,3). Il a été légerement modifié avec Sketchviz afin de le rendre plus agréable à regarder.

Ce travail m’a permi de comprendre les bases de Graphviz, et de pouvoir m’en servir afin de mieux comprendre le fonctionnement d’un programme. En effet, j’ai également appris à convertir les printf que l’on utilise en C, en des instructions interprété dans un fichier Graphviz. Enfin, j’ai pu découvrir l’outil Sketchviz ain de produire des images plus belles, et présentables dans un document comme celui-ci.