361 lines
12 KiB
HTML
361 lines
12 KiB
HTML
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
|
||
|
|
<html lang="fr-fr">
|
||
|
|
<head>
|
||
|
|
<meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
|
||
|
|
<link rel="stylesheet" type="text/css" href="index.css">
|
||
|
|
<title>Alobé</title>
|
||
|
|
<meta content="Glenn ROLLAND" name="author">
|
||
|
|
</head>
|
||
|
|
<body style="direction: ltr;">
|
||
|
|
<div style="text-align: justify;" class="page">
|
||
|
|
<h1>Alobé (TP2)</h1>
|
||
|
|
<h2><a name="1._Description"></a>1.
|
||
|
|
<a name="Description"></a>Description</h2>
|
||
|
|
<p>Alobé est
|
||
|
|
un logiciel libre permettant de manipuler de grands graphes
|
||
|
|
non-orientés décrits par la liste de leurs
|
||
|
|
arrêtes. Il possède les
|
||
|
|
caractéristiques
|
||
|
|
suivantes :</p>
|
||
|
|
<ul>
|
||
|
|
<li>Il est distribué
|
||
|
|
sous la licence <a href="http://www.gnu.org/copyleft/gpl.html">GNU
|
||
|
|
General Public License</a></li>
|
||
|
|
<li>Il est
|
||
|
|
écrit en C (bien qu'écrit au départ en
|
||
|
|
C++, comme en témoigne le dépôt
|
||
|
|
subversion) et possède une interface en ligne
|
||
|
|
de
|
||
|
|
commande,</li>
|
||
|
|
<li>Il implémente le
|
||
|
|
calcul de la distance d'un noeud à tous les autres
|
||
|
|
(exercice 1).</li>
|
||
|
|
<li>Il fournit en sortie des
|
||
|
|
données permettant de tracer la
|
||
|
|
distribution des distance à un noeud donné
|
||
|
|
(exercice 2)</li>
|
||
|
|
<li>Il fournit en sortie les
|
||
|
|
données permettant de tracer
|
||
|
|
l'évolution de l'estimation de la distance moyenne en
|
||
|
|
fonction
|
||
|
|
du nombre de parcours effectués.
|
||
|
|
(exercice 3)</li>
|
||
|
|
<li>Il implémente le
|
||
|
|
calcul de la borne inférieure du
|
||
|
|
diamètre, en prenant la distance maximale d'un noeud
|
||
|
|
donné à tous les autres (exercice 4).</li>
|
||
|
|
<li>Il implémente le
|
||
|
|
calcul de la borne supérieure du diamètre, en
|
||
|
|
prenant la
|
||
|
|
distance maximale dans l'arbre du parcours en largeur (exercice
|
||
|
|
5). </li>
|
||
|
|
<li>Il fournit en sortie des
|
||
|
|
données permettant de tracer les
|
||
|
|
courbes des meilleurs bornes inférieures et
|
||
|
|
supérieure en
|
||
|
|
fonction du nombre de parcours effectués.
|
||
|
|
(exercice 6 - défi).</li>
|
||
|
|
</ul>
|
||
|
|
<h3>1.1.
|
||
|
|
Auteurs</h3>
|
||
|
|
<p>Alobé a
|
||
|
|
été entièrement
|
||
|
|
réalisé par Glenn ROLLAND <<a
|
||
|
|
href="mailto:glenux@fr.st">glenux@fr.st</a>>
|
||
|
|
à l'occasion de travaux pratiques du cours de <span
|
||
|
|
style="font-style: italic;">Grand Réseaux</span>
|
||
|
|
du Master 2 Ingénierie Informatique
|
||
|
|
-
|
||
|
|
Systèmes, Réseaux et Internet.</p>
|
||
|
|
<h2><a99 name="2._Pré-requis">2.
|
||
|
|
Pré-requis</a99></h2>
|
||
|
|
<p>Alobé
|
||
|
|
ne nécessite pas de bibliothèques de
|
||
|
|
fonctions
|
||
|
|
particulières pour fonctionnner.</p>
|
||
|
|
<h2>3.
|
||
|
|
Se procurer Alobé</h2>
|
||
|
|
Vous
|
||
|
|
pouvez télécharger la dernière archive
|
||
|
|
des
|
||
|
|
sources, ou bien directement la version la plus récente du
|
||
|
|
projet sur le dépôt Subversion du projet.<br>
|
||
|
|
<h3>3.1. L'archive des sources</h3>
|
||
|
|
Elle est disponible à l'adresse : <br>
|
||
|
|
<a href="http://glenux2.free.fr/pub/projets/Alobe/archives/">http://glenux2.free.fr/pub/projets/Alobe/archives/</a><br>
|
||
|
|
<h3>3.2. Le
|
||
|
|
dépôt Subversion</h3>
|
||
|
|
<p>Afin d'obtenir les sources les
|
||
|
|
plus à jour, vous pouvez utiliser le logiciel de
|
||
|
|
contrôle de sources Subversion </p>
|
||
|
|
<p class="code">$ svn
|
||
|
|
checkout http://repository.glenux.ath.cx/svn/Cours/M2/Grand_Reseaux/TP1/</p>
|
||
|
|
<p>Il n'y a pas de mot de passe,
|
||
|
|
il suffit donc de presser la touche
|
||
|
|
"Entrée" pour l'utilisateur "anonymous", si ce dernier vous
|
||
|
|
est
|
||
|
|
demandé.</p>
|
||
|
|
<h2><a name="4._Utiliser_Alobé"></a>4.
|
||
|
|
Utiliser Alobé</h2>
|
||
|
|
<h3><a name="4.1._Compilation"></a>4.1.
|
||
|
|
Compilation</h3>
|
||
|
|
<p>Commencez par
|
||
|
|
décompressez l'archive.</p>
|
||
|
|
<p class="code">$ tar -xzvf
|
||
|
|
alobe-0.2.tar.gz</p>
|
||
|
|
<p>Rendez vous ensuite dans le
|
||
|
|
dossier qui vient d'être créé lors de
|
||
|
|
la décompression.</p>
|
||
|
|
<p class="code">$ cd
|
||
|
|
alobe-0.2</p>
|
||
|
|
<p>Puis lancez
|
||
|
|
l'auto-configuration du logiciel, puis la compilation.</p>
|
||
|
|
<p class="code">$ ./autogen<br>
|
||
|
|
$ ./configure<br>
|
||
|
|
$ make</p>
|
||
|
|
<p>Le binaire produits se trouve
|
||
|
|
dans le dossier :</p>
|
||
|
|
<ul>
|
||
|
|
<li> <span class="code">src/alobe</span></li>
|
||
|
|
</ul>
|
||
|
|
<h3><a name="4.2._Utilisation"></a>4.2.
|
||
|
|
Utilisation</h3>
|
||
|
|
<div style="text-align: justify;">Les
|
||
|
|
binaires de Alobé doivent être appelés
|
||
|
|
avec la syntaxe suivante:<br>
|
||
|
|
</div>
|
||
|
|
<p class="code">Usage:
|
||
|
|
alobe <commande> <parametres_obligatoires>
|
||
|
|
[options]<br>
|
||
|
|
</p>
|
||
|
|
<p>Les commandes sont
|
||
|
|
les suivants:</p>
|
||
|
|
<dl>
|
||
|
|
<dt>-I, --tp2distance</dt>
|
||
|
|
<dd>Calcule les distances
|
||
|
|
à partir du noeud donné.</dd>
|
||
|
|
<dt> -J, --tp2distanceplot </dt>
|
||
|
|
<dd>Donne la distribution des
|
||
|
|
distances à partir du noeud donné.</dd>
|
||
|
|
<dt>-L, --tp2distevolution</dt>
|
||
|
|
<dd>Donne l'évolution
|
||
|
|
de l'estimation de la distance moyenne.pour un noeud donné,
|
||
|
|
ou au hasard, en fonction du nombre d'itérations.</dd>
|
||
|
|
<dt>-M, --tp2limitinf</dt>
|
||
|
|
<dd>Calcule la borne
|
||
|
|
inférieure du diamètre pour un noeud
|
||
|
|
donné ou au hasard, en fonction du nombre
|
||
|
|
d'itérations.</dd>
|
||
|
|
<dt>-N, --tp2limitsup</dt>
|
||
|
|
<dd>Calcule la borne
|
||
|
|
supérieure du diamètre pour un noeud
|
||
|
|
donné ou au hasard, en fonction du nombre
|
||
|
|
d'itérations.</dd>
|
||
|
|
<dt>-O, --tp2defi</dt>
|
||
|
|
<dd>Fournit les
|
||
|
|
données permettant de tracer les courbes de meilleures
|
||
|
|
bornes inférieures et supérieures du
|
||
|
|
diamètre en fonction du nombre d'itération.</dd>
|
||
|
|
</dl>
|
||
|
|
<ul>
|
||
|
|
</ul>
|
||
|
|
<p>Les paramètres
|
||
|
|
obligatoires sont les suivants:</p>
|
||
|
|
<dl>
|
||
|
|
<dt>-c, --count
|
||
|
|
<entier> <fichier> </fichier></dt>
|
||
|
|
<dd>Nombre de noeuds du fichier
|
||
|
|
d'entrée.</dd>
|
||
|
|
</dl>
|
||
|
|
<p>Les parames optionnels sont les
|
||
|
|
suivants:</p>
|
||
|
|
<dl>
|
||
|
|
<dt>-i, --input
|
||
|
|
<fichier></dt>
|
||
|
|
<dd> Le fichier
|
||
|
|
d'entrée, "-" désignant l'entrée
|
||
|
|
standard,</dd>
|
||
|
|
<dt>-o, --output
|
||
|
|
<fichier></dt>
|
||
|
|
<dd>Le fichier de sorftie, "-"
|
||
|
|
désignant la sortie standard.</dd>
|
||
|
|
<dt>-v, --verbose</dt>
|
||
|
|
<dd> Passe l'affichage en mode
|
||
|
|
verbeux.e
|
||
|
|
numéro du noeud à lire et afficher à
|
||
|
|
partir du
|
||
|
|
fichier
|
||
|
|
compressé</dd>
|
||
|
|
<dt>-r, --root
|
||
|
|
<entier></dt>
|
||
|
|
<dd>Noeur servant de racine
|
||
|
|
à la première itération.</dd>
|
||
|
|
<dt>-n, --iterations
|
||
|
|
<entier></dt>
|
||
|
|
<dd>Nombre
|
||
|
|
d'itérations a effectuer.</dd>
|
||
|
|
</dl>
|
||
|
|
<h2><a name="5._Documentation"></a>5.
|
||
|
|
Documentation</h2>
|
||
|
|
<h3>5.1. Code</h3>
|
||
|
|
<p>Vous pouvez trouver la
|
||
|
|
documentation de Alobé dans le dossier <span class="code">doc/html</span>
|
||
|
|
de l'application, ou en suivant <a href="html/index.html">ce lien</a>.</p>
|
||
|
|
<h3>5.2. Remarques sur les
|
||
|
|
différents exercices</h3>
|
||
|
|
<h4>5.2.1. Exercice 1</h4>
|
||
|
|
<p>On calcule la distance d'un
|
||
|
|
noeud (le 24 par exemple) à tous les autres, ainsi que la
|
||
|
|
moyenne de toutes ses distances, par la commande suivante:</p>
|
||
|
|
<p class="code"> ./alobe
|
||
|
|
-I -i web.data.gz -o result.txt -c 701654 -r 24</p>
|
||
|
|
<p class="">Ce qui produit
|
||
|
|
le fichier result.txt suivant :</p>
|
||
|
|
<p class="code">Maximum
|
||
|
|
distance : 1<br>
|
||
|
|
Average distance : 0.666667</p>
|
||
|
|
<h4>5.2.2. Exercice 2</h4>
|
||
|
|
<p>On obtient la distribution des
|
||
|
|
distances pour un noeud donné (le 24 par exemple) de la
|
||
|
|
façon suivante:</p>
|
||
|
|
<p class="code">$ ./alobe
|
||
|
|
-J -i web.data.gz -o result.txt -c 701654 -r 24<br>
|
||
|
|
</p>
|
||
|
|
<p class="">Ce qui
|
||
|
|
produit en sortie</p>
|
||
|
|
<p class="code">0 1<br>
|
||
|
|
1 336<br>
|
||
|
|
2 3017<br>
|
||
|
|
3 21100<br>
|
||
|
|
4 89398<br>
|
||
|
|
5 146225<br>
|
||
|
|
6 145567<br>
|
||
|
|
7 118491<br>
|
||
|
|
8 77830<br>
|
||
|
|
9 47189<br>
|
||
|
|
10 21247<br>
|
||
|
|
11 8628<br>
|
||
|
|
12 1550<br>
|
||
|
|
13 532<br>
|
||
|
|
14 112<br>
|
||
|
|
15 7<br>
|
||
|
|
16 4</p>
|
||
|
|
<p class="">Soit le
|
||
|
|
graphique suivant :<br>
|
||
|
|
<img src="exercice2.png" alt="exercice 2 plot"></p>
|
||
|
|
<h4>5.2.3. Exercice 3</h4>
|
||
|
|
<p>On trace l'évolution
|
||
|
|
de l'estimation de la distance moyenne (en fonction du nombre
|
||
|
|
d'itération) par la commande suivante:</p>
|
||
|
|
<p class="code"> ./alobe
|
||
|
|
-L -i web.data.gz -o result.txt -c 701654 -n 100 -r 24<br>
|
||
|
|
</p>
|
||
|
|
<p class="">Ce qui produit
|
||
|
|
en sortie: </p>
|
||
|
|
<p class="code">0 6.228710<br>
|
||
|
|
1 7.560919<br>
|
||
|
|
2 9.514071<br>
|
||
|
|
3 9.537433<br>
|
||
|
|
4 9.504442<br>
|
||
|
|
5 9.567365<br>
|
||
|
|
6 9.542382<br>
|
||
|
|
7 9.429151<br>
|
||
|
|
8 9.426282<br>
|
||
|
|
9 9.566440<br>
|
||
|
|
10 9.583777<br>
|
||
|
|
11 9.450484<br>
|
||
|
|
12 9.548250<br>
|
||
|
|
13 9.503499<br>
|
||
|
|
14 9.508191<br>
|
||
|
|
15 9.475249<br>
|
||
|
|
16 9.297400<br>
|
||
|
|
17 9.210398<br>
|
||
|
|
[...]</p>
|
||
|
|
<p>Soit sous forme graphique
|
||
|
|
:<br>
|
||
|
|
<img src="exercice3.png" alt="exo 3 plot"></p>
|
||
|
|
<br>
|
||
|
|
<h4>5.2.4. Exercice 4</h4>
|
||
|
|
<p>Pour calculer la borne
|
||
|
|
inférieure, on fera:</p>
|
||
|
|
<p class="code">./alobe -M
|
||
|
|
-i web.data.gz -o result.txt -c 701654 -n 5 -r 24</p>
|
||
|
|
<p class="code">Iteration 0
|
||
|
|
-- choosing root 24<br>
|
||
|
|
|
||
|
|
-- borne inférieure 17<br>
|
||
|
|
Iteration 1 -- choosing root 60401<br>
|
||
|
|
|
||
|
|
-- borne inférieure 18<br>
|
||
|
|
Iteration 2 -- choosing root 700018<br>
|
||
|
|
|
||
|
|
-- borne inférieure 24<br>
|
||
|
|
Iteration 3 -- choosing root 77852<br>
|
||
|
|
|
||
|
|
-- borne inférieure 24<br>
|
||
|
|
Iteration 4 -- choosing root 45944<br>
|
||
|
|
|
||
|
|
-- borne inférieure 24<br>
|
||
|
|
</p>
|
||
|
|
<br>
|
||
|
|
<h4>5.2.5. Exercice 5</h4>
|
||
|
|
<p>Pour le calcul de la borne
|
||
|
|
supérieure, on fait :</p>
|
||
|
|
<p class="code">./alobe -N
|
||
|
|
-i ~/web.data.gz -o result.txt -c 701654 -n 10 -r 24</p>
|
||
|
|
<p class="code">Iteration 0
|
||
|
|
-- choosing root 24<br>
|
||
|
|
|
||
|
|
-- borne supérieure 33<br>
|
||
|
|
Iteration 1 -- choosing root 96542<br>
|
||
|
|
|
||
|
|
-- borne supérieure 33<br>
|
||
|
|
Iteration 2 -- choosing root 49208<br>
|
||
|
|
|
||
|
|
-- borne supérieure 33<br>
|
||
|
|
Iteration 3 -- choosing root 436498<br>
|
||
|
|
|
||
|
|
-- borne supérieure 33<br>
|
||
|
|
Iteration 4 -- choosing root 309990<br>
|
||
|
|
|
||
|
|
-- borne supérieure 32<br>
|
||
|
|
Iteration 5 -- choosing root 538890<br>
|
||
|
|
|
||
|
|
-- borne supérieure 32<br>
|
||
|
|
Iteration 6 -- choosing root 266656<br>
|
||
|
|
|
||
|
|
-- borne supérieure 32<br>
|
||
|
|
Iteration 7 -- choosing root 529998<br>
|
||
|
|
|
||
|
|
-- borne supérieure 32<br>
|
||
|
|
Iteration 8 -- choosing root 140145<br>
|
||
|
|
|
||
|
|
-- borne supérieure 32<br>
|
||
|
|
Iteration 9 -- choosing root 640316<br>
|
||
|
|
|
||
|
|
-- borne supérieure 32<br>
|
||
|
|
<br>
|
||
|
|
</p>
|
||
|
|
<h4>5.2.6. Exercice 6 - Défi</h4>
|
||
|
|
<p>Le cumul des courbes
|
||
|
|
précédentes se fait par :</p>
|
||
|
|
<p class="code">$ ./alobe
|
||
|
|
-O -i web.data.gz -o result.txt -c 701654 -n 100 -r 24</p>
|
||
|
|
<p>Puis :</p>
|
||
|
|
<p class="code">$
|
||
|
|
./defiplot.sh result.txt</p>
|
||
|
|
<p class="">Pour obtenir :
|
||
|
|
<img src="defi.png" alt="defi plot"></p>
|
||
|
|
<p class="">Remarque:
|
||
|
|
pour le défi, il aurait fallu en plus utiliser une
|
||
|
|
heuristique de choix des noeuds permettant de faire converger les deux
|
||
|
|
courbes bornant le diamètre au plus vite. Par exemple,
|
||
|
|
choisir les noeuds par degré décroissant dans la
|
||
|
|
composante connexe, en supposant qu'un noeud a fort degré
|
||
|
|
comme racine donne un arbre plus plat et donc la borne
|
||
|
|
suppérieure par la même occasion...</p>
|
||
|
|
<br>
|
||
|
|
</div>
|
||
|
|
</body>
|
||
|
|
</html>
|