Valid XHTML     Valid CSS2    

Production Automatisée de

Graphiques, Statistiques et Documents

                     gilles.hunault "at" univ-angers.fr

 

-- partie 1 sur 5 : arbres et graphes

 

Table des matières cliquable

  1. Exemple élémentaire de tracé d'un arbre avec DOT

  2. Théorème des quatre carrés de Lagrange en DOT via PHP

  3. Calcul de la matrice d'adjacence d'un graphe et tracé via DOT

  4. Tracés DOT en ligne

  5. Tracé d'un échiquier en SVG via PHP

  6. Canviz, Javascript et conversions de formats de graphes

  7. Tracé de l'arbre d'un document XHTML valide

  8. Animation Javascript d'un graphe défini en XML

  9. Graphiques en barres

10. Méthodologie du développement

 

Il est possible d'afficher toutes les solutions via ?solutions=1 et de toutes les masquer avec ?solutions=0.

 

1. Exemple élémentaire de tracé d'un arbre avec DOT

Ecrire un graphe en langage DOT pour décrire la structure classique de XHTML : "html, head and body, title est dans le head". On générera un fichier PNG. Comment le visualiser rapidement à partir de la ligne de commandes ? On devra obtenir un graphe identique au graphe ci-dessous.

               non su

Reprendre le graphe en utilisant des boites rectangulaires pour chaque noeud comme dans le graphe ci-dessous.

               non su

Peut-on faire des cadres emboités avec DOT, comme ci-dessous ?

               non su

Comment produire le graphe ci-dessous avec DOT ? Est-ce un arbre ?

               non su

Solution :  

 

2. Théorème des quatre carrés de Lagrange en DOT via PHP

Le théorème des quatre carrés de Lagrange dit que tout entier positif ou nul peut se décomposer en au moins une somme de 4 carrés.


           ∀n≥0, ∃a,b,c,d tels que n = a2 + b2 + c2 + d2
 

Voici quelques exemples de décomposition :

n a b c d
10 3 1 0 0
583 23 7 2 1
342 18 4 1 1
263 15 6 1 1
772 27 5 3 3
839 27 10 3 1
27 5 1 1 0
347 17 7 3 0

Ecrire un programme PHP qui donne l'arbre des décompositions d'un entier n passé en paramètre, arbre obtenu en décomposant chacune des décompositions à son tour, comme ci-dessous pour n=839.

               non su

On pourra utiliser le sous-programme suivant quatrecarres.php -- archive du code php -- pour obtenir une décomposition :


     <?php
     
     ######################################################################################
     
     function ds4c($nombre) {  # décomposition en somme de 4 carrés
     
     ######################################################################################
     
     $dbg = 0 ; # 0 en standard, 1 pour debug
     
     # valeur limite : la racine carrée du nombre
     
     $racine = round(sqrt($nombre)) ;
     
     $n1 = $racine ;
     
     # on boucle sur n1, n2 et n3 seulement,
     # n4 s'en déduira
     # comme il peut y avoir plusieurs solutions,
     # on renvoie ce qu'on a trouvé le plus tot possible
     
     while ($n1>=0) {
       $cn1 = $n1*$n1 ;
       $n2  = $racine ;
       while ($n2>=0) {
         $cn2 = $n2*$n2 ;
         $n3  = $racine ;
         while ($n3>=0) {
           $cn3 = $n3*$n3 ;
           $cn4 = $nombre - ($cn1+$cn2+$cn3) ;
           if ($dbg==1) {
             echo " n1 $n1 n2 $n2 n3 $n3 cn4 $cn4 \n" ;
           } # fin si
           if ($cn4>=0) {
             $n4 = sqrt($cn4) ;
             if ($dbg==1) {
               echo "   n4 possible $n4 \n" ;
             } # fin si
             if (round($n4)==$n4) {
               return( array($n1,$n2,$n3,$n4) ) ;
             } ; # fin si
           } ; # fin si
           $n3-- ;
         } # fin tant que sur n3
         $n2-- ;
       } # fin tant que sur n2
       $n1-- ;
     } # fin tant que sur n1
     
     return( array("?","?","?","?") ) ;
     
     } # fin fonction ds4c
     
     ?>
     

Solution :  

 

3. Calcul de la matrice d'adjacence d'un graphe et tracé via DOT

On suppose qu'on dispose des listes d'adjacence d'un graphe dans un fichier texte. Ecrire un programme PHP qui construit la matrice d'adjacence du graphe puis qui utilise DOT pour fournir une visualisation du graphe. On commencera par écrire un programme en CLI (ligne de commandes) avant de fournir une page Web qui lit les listes d'adjacence dans un <textarea>.

Voici un exemple d'entrée (fichier listeadj.txt) :


     0 1 4
     1 2 6
     2
     3 2 6
     4
     5 0 2
     6
     7 6
     

Et de sortie :


     
     
     Matrice d'adjacence d'un graphe dont on connait les listes d'adjacence.
     
      sommet numéro  1 : 0
      sommet numéro  2 : 1
      sommet numéro  3 : 2
      sommet numéro  4 : 3
      sommet numéro  5 : 4
      sommet numéro  6 : 5
      sommet numéro  7 : 6
      sommet numéro  8 : 7
     
     Voici la matrice d'adjacence associée au fichier listeadj.txt :
     
     num nom     1  2  3  4  5  6  7  8
       1 0       0  1  0  0  1  0  0  0
       2 1       0  0  1  0  0  0  1  0
       3 2       0  0  0  0  0  0  0  0
       4 3       0  0  1  0  0  0  1  0
       5 4       0  0  0  0  0  0  0  0
       6 5       1  0  1  0  0  0  0  0
       7 6       0  0  0  0  0  0  0  0
       8 7       0  0  0  0  0  0  1  0
     
      -- fin normale de matadj.php
     
     
               non su

Solution :  

 

4. Tracés DOT en ligne

A la réflexion, écrire du code DOT sous éditeur, le sauvegarder puis taper une commande dot -T png ... en ligne de commandes est un peu "fastidieux". Y a-t-il des pages Web qui interprètent du code DOT ?

Solution :  

 

5. Tracé d'un échiquier en SVG via PHP

Ecrire une page Web avec un programme PHP qui produit un échiquier en SVG de taille nxnn est passé en paramètre.

Expliquer ce que produit le code SVG suivant :


     <?xml version="1.0" encoding="UTF-8"?>
     <svg xmlns="http://www.w3.org/2000/svg" width="810" height="810" viewBox="-.05 -.05 8.1 8.1">
       <rect x="-.5" y="-.5" width="9" height="9" />
       <path fill="#FFF" d="M0,0H8v1H0zm0,2H8v1H0zm0,2H8v1H0zm0,2H8v1H0zM1,0V8h1V0zm2,0V8h1V0zm20V8h1V0zm2,0V8h1V0z"/>
     </svg>
     

Solution :  

 

6. Canviz, Javascript et conversions de formats de graphes

Qu'est-ce que Canviz ?

Ecrire une page PHP dont le rendu est XHTML strict valide avec tout le code Javascript externalisé qui reprend la page Canviz demo. On utilisera les fonctions de std.php.

Peut-on convertir facilement des fichiers PNG de graphes en SVG ? Et réciproquement ?

Solution :  

 

7. Tracé de l'arbre d'un document XHTML valide

Ecrire un programme PHP qui affiche l'arbre des éléments XHTML d'une URL donnée mais sans les contenus textuels. On produira l'arbre en SVG.

Comment afficher aussi les attributs ? Et le début des contenus textuels ?

Solution :  

 

8. Animation Javascript d'un graphe défini en XML

Réaliser dans une page Web un affichage progressif d'un graphe à raison d'un arc par seconde (durée paramétrable). On utilisera SVG. Le graphe sera écrit en XML au format GraphML ou DOTML. On pourra utiliser les fichiers suivants pour tester la page Web : xhtml.graphml, triangle.graphml, xhtml.dotml et triangle.dotml.

Au passage, comment tester qu'un fichier définissant un graphe est "valide" ?

Solution :  

 

9. Graphiques en barres

Question 9.1

Quelle est la différence entre un histogramme de classes et un histogramme de fréquences ?

Quelle est la méthode la plus rapide (moins d'une minute) pour produire un histogramme de fréquences en PNG si on connait le titre, les modalités et les effectifs correspondant ?

Comment trace-t-on ces deux types d'histogrammes avec le logiciel R ? On viendra bien sûr ajouter le nom des modalités et le titre de la figure dans le cas d'un histogramme de fréquences.

Quelles précautions faut-il prendre si on veut pouvoir comparer plusieurs histogrammes de fréquences ?

Question 9.2

Modifier la page de jphistopct pour qu'on dispose d'un paramètre supplémentaire nommé couleur et rédiger la documentation associée dans la page Web de présentation.

Ecrire ensuite un formulaire Web pour interfacer la nouvelle page de jphistopct y compris avec une liste de sélection pour la couleur. On s'arrangera pour gérer une liste quelconque de modalités et le titre éventuellement accentué. On affichera le graphique sous le formulaire.

Question 9.3

Ecrire une version PHP en ligne de commandes qui utilise un seul paramètre, le nom d'un fichier-texte. Ce fichier peut contenir plusieurs séries de données à tracer. Chaque série contient un titre, la liste des modalités puis la liste des valeurs. Ce fichier pourra être au format CSV, JSON, ou XML. On fournira un help via les paramètres -h et --help. On basera le nom du fichier de sortie PNG sur le nom du fichier d'entrée.

Exemples possibles (mais non imposés) de tels fichiers (archive hfreq.zip) :

hfreqXmp.xml       hfreqXmp.csv       hfreqXmp.json       

Que pourrait-on ajouter à ces fichiers de données ?

On pourra suivre le plan suivant afin d'avoir un programme assez complet et testé :


     ## 1. test des paramètres
     
        # si pas assez de paramètres, affichage de l'aide
        # si trop de paramètres, on le dit et on arrete
        # si le paramètre est -h ou --help, affichage de l'aide
     
     ## 2. vérifications sur le fichier
     
       # il doit y avoir un point dans l'identifiant du fichier
       # le nom du fichier (partie avant le point) ne doit pas être vide
       # le type du fichier doit être CSV JSON ou XML
       # il faut que le fichier existe
     
     ## 3. traitement des données
     
       # si le fichier est de type csv,  utiliser le sous-programme correspondant
       # si le fichier est de type json, utiliser le sous-programme correspondant
       # si le fichier est de type xml,  utiliser le sous-programme correspondant
     
       # dans tous les cas, renvoyer
       #  - le tableau des titres,
       #  - le tableau des modalités,
       #  - le tableau des effectifs
     
       # produire les png à l'aide ces trois tableaux
     

Solution :  

 

10. Méthodologie du développement

Nous avons vu avec la décomposition de Lagrange (archive de la solution lagrange.zip) et avec la matrice d'adjacence d'un graphe (archive de la solution matadj.zip) qu'il y a une méthode pour écrire du PHP afin d'aboutir progressivement à une page Web compléte utilisable sans rechargement de la page. Détailler cette méthode.

Quelles sont les contraintes supplémentaires rajoutées par le fait qu'on utilise un exécutable en ligne de commandes qui produit une image ?

Solution :  

 

Code-source de cette page ;  fichiers inclus : pagsd_inc.php et pagsd.js.

 

 

retour gH    Retour à la page principale de   (gH)