5ca782e8b1
git-svn-id: https://websvn.glenux.net/svn/Upoc/alobe/trunk@1348 eaee96b3-f302-0410-b096-c6cfd47f7835
358 lines
12 KiB
HTML
358 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é</h1>
|
|
<h2><a name="1._Description"></a>1.
|
|
<a name="Description"></a>Description</h2>
|
|
<p>Alobé est
|
|
un logiciel libres 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
|
|
filtrage du graphe pour l'extraction d'un sous-ensemble
|
|
(exercice 2).</li>
|
|
<li>Il implémente le
|
|
calcul des degrés (exercice 3)</li>
|
|
<li>Il implémente les
|
|
statistiques sur le calcul des degrés (degré
|
|
moyen, degré maximum, densité du graphe)
|
|
(exercice 5)</li>
|
|
<li>Il implémente le
|
|
stockage des données de façon contigüe
|
|
en mémoire (en un unique tableau) (exercice 4).</li>
|
|
<li>Il implémente le
|
|
calcul des composantes connexes de façon efficace (exercice
|
|
5). </li>
|
|
<li>Il implémente une
|
|
méthode de calcul alternatif des composantes connexes
|
|
(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.1.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.1</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>-F, --filter</dt>
|
|
<dd>Filtrage du fichier
|
|
d'entrée pour extraire un sous-graphe.</dd>
|
|
<dt> -D, --degree </dt>
|
|
<dd>Calcul du degré
|
|
des noeuds du graphe pris en entrée.</dd>
|
|
<dt>-S, --store</dt>
|
|
<dd>Stockage et remplissage du
|
|
tableau représentant le graphe en mémoire.</dd>
|
|
<dt>-A, --average</dt>
|
|
<dd>Calcul des statistiques sur
|
|
les noeuds du graphe d'entrée (degré moyen,
|
|
degré max, densité).</dd>
|
|
<dt>-C, --connexity</dt>
|
|
<dd>Calcul des composantes
|
|
connexes par la méthode du tableau unique.</dd>
|
|
<dt>-E, --defi</dt>
|
|
<dd>Calcul des composantes
|
|
connexes par ensembles d'intervalles de noeuds.</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>
|
|
<dt>-s, --size <entier></dt>
|
|
<dd>Taille du filtre</dd>
|
|
<dt>-t, --offset <entier></dt>
|
|
<dd>Offset du filtre</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>
|
|
</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>
|
|
<br>
|
|
<h4>5.2.2. Exercice 2</h4>
|
|
<p>Il est possible de filtrer le
|
|
graphe d'entrée pour extraire un sous ensemble de noeuds de
|
|
la façon suivante :</p>
|
|
<p class="code">./src/alobe -F -t 0 -s 60 -i ../web.data.gz -c 701654</p>
|
|
<p class="">Ce qui
|
|
produit en sortie</p>
|
|
<p class="code">Command -> FILTER<br>
|
|
Offset -> 0<br>
|
|
Size -> 30<br>
|
|
Input Data -> ../web.data.gz<br>
|
|
Input Index -> 701654<br>
|
|
Filtering between [ 0 .. 30 ]...<br>
|
|
0 1<br>
|
|
0 2<br>
|
|
1 3<br>
|
|
1 4<br>
|
|
1 5<br>
|
|
1 6<br>
|
|
1 7<br>
|
|
1 8<br>
|
|
1 9<br>
|
|
1 10<br>
|
|
1 11<br>
|
|
1 12<br>
|
|
<br>
|
|
[...]<br>
|
|
<br>
|
|
( uniquement les noeuds x compris entre 0 <= x < 30 )</p>
|
|
<h4>5.2.3. Exercice 3</h4>
|
|
<p>Le calcul du degré des noeuds se fait par la commande
|
|
suivante :</p>
|
|
<p class="code">./src/alobe -D -i ../web.data.gz -c 701654</p>
|
|
<p class="">Ce qui produit (en première colone l'index du noeud
|
|
et en seconde le degré):</p>
|
|
<p class="code">Command -> DEGREE<br>
|
|
Input Data -> ../web.data.gz<br>
|
|
Input Index -> 701654<br>
|
|
Computing degree of each node...<br>
|
|
done<br>
|
|
0 2<br>
|
|
1 1194<br>
|
|
2 77<br>
|
|
3 496<br>
|
|
4 227<br>
|
|
5 339<br>
|
|
6 337<br>
|
|
7 340<br>
|
|
8 337<br>
|
|
9 10<br>
|
|
10 16<br>
|
|
11 31<br>
|
|
12 15<br>
|
|
13 22<br>
|
|
<br>
|
|
[...]</p>
|
|
<p class="">Le calcul du degré est effectué dans un
|
|
tableau de <span style="font-weight: bold;">sizeof(long) * N</span>
|
|
(où N est le nombre de noeuds), initialisé à
|
|
zéro, et où les valeurs des cases sont
|
|
incrémentées à la lecture des arcs.<br>
|
|
</p>
|
|
<h4>5.2.4. Exercice 4</h4>
|
|
<p>Le simple stockage du graphe en mémoire ne produit pas de
|
|
sortie visible, mais s'execute en tapant :</p>
|
|
<p class="code">./src/alobe -S -i ../web.data.gz -c 701654</p>
|
|
Le programme commence par calculer les degrés, puis initialise
|
|
un tableau de taille N (N = nombre de noeuds) pointeurs vers les cases
|
|
d'un tableau de taille <span style="font-weight: bold;">(M + 3) *
|
|
sizeof(long)</span> (où M est la somme des degrés des
|
|
noeuds) destiné à contenir les arcs de chaque noeud. Les
|
|
3 cases supplémentaires ne servent qu'au calcul des composates
|
|
connexes et seront décrites plus loin.<br>
|
|
<h4>5.2.5. Exercice 5</h4>
|
|
<p>Le calcul des statistiques sur les noeuds du graphe se fait de la
|
|
façon suivante:</p>
|
|
<p class="code">./src/alobe -A -i ../web.data.gz -c 701654</p>
|
|
<p class="code">Command -> AVERAGE<br>
|
|
Input Data -> ../web.data.gz<br>
|
|
Input Index -> 701654<br>
|
|
Computing degree of each node...<br>
|
|
done<br>
|
|
Degree average: 5.517015<br>
|
|
Degree maximum: 5331<br>
|
|
Density : 0.000000<br>
|
|
</p>
|
|
<p class="">Cet exercice réutilise la structure de
|
|
données l'éxercice 3, et en la parcourant effectue le
|
|
calcul.</p>
|
|
<h4>5.2.6. Exercice 6</h4>
|
|
<p>Le calcul des composantes connexes se fait de la façon
|
|
suivante :</p>
|
|
<p class="code">./src/alobe -C -i ../web.data.gz -c 701654</p>
|
|
<p class="code">Command -> CONNEXITY<br>
|
|
Input Data -> ../web.data.gz<br>
|
|
Input Index -> 701654<br>
|
|
Computing degree of each node...<br>
|
|
done<br>
|
|
Filling the Big Table...<br>
|
|
done<br>
|
|
Found connex component at 0<br>
|
|
Found connex component at 9484<br>
|
|
Found connex component at 15516<br>
|
|
Found connex component at 17477<br>
|
|
Found connex component at 20073<br>
|
|
Found connex component at 20100<br>
|
|
<br>
|
|
[...]<br>
|
|
<br>
|
|
Found connex component at 699413<br>
|
|
Found connex component at 700568<br>
|
|
Found connex component at 701306<br>
|
|
Found connex component at 701313<br>
|
|
Found 970 connex components</p>
|
|
<p class="">Pour le fichier <span style="font-weight: bold;">IP.data.gz</span>
|
|
on obtient :</p>
|
|
<p class="code">Command -> CONNEXITY<br>
|
|
Input Data -> /home/warbrain/Films/IP.data.gz<br>
|
|
Input Index -> 467273<br>
|
|
Computing degree of each node...<br>
|
|
done<br>
|
|
Filling the Big Table...<br>
|
|
done<br>
|
|
Found connex component at 0<br>
|
|
Found connex component at 324896<br>
|
|
Found 2 connex components</p>
|
|
<p class="">Et pour le fichier <span style="font-weight: bold;">P2P.data.gz</span>
|
|
les machines à ma disposition ne possédaient pas
|
|
suffisament de mémoire...</p>
|
|
<p class="">Le calcul des composantes connexes utilise le même
|
|
tableau que l'exercice 4. Le calcul se fait dans les 3 cases
|
|
supplémentaires :<br>
|
|
</p>
|
|
<ul>
|
|
<li>une case pour le degré du noeud</li>
|
|
<li>une case pour l'offset du noeud traité</li>
|
|
<li>une case pour le noeud "père" dans le parcours en
|
|
profondeur.</li>
|
|
</ul>
|
|
<p class="">Lorsqu'on parcours un noeud x en provenance de y, on
|
|
inscrit la référence du noeud père dans la case 3,
|
|
puis pour chaque noeud adjacent non visité, on indique le
|
|
noeud adjacent parcouru actuellement puis on parcourt
|
|
récursivement le noeud adjacent.</p>
|
|
<p class="">Remarque: jusque là le TP était
|
|
programmé en C++, et pour un éventeuel gain de
|
|
performances il fut réécrit entièrement (en
|
|
conservant les structures de données) en C. Cependant seules 0.3
|
|
secondes furent gagnées sur le graphe <span
|
|
style="font-weight: bold;">web.data.gz</span>... sur un temps de
|
|
calcul total de 14 sec... (sur un iBook G4 1Ghz avec 256 Mo de RAM sous
|
|
GNU/Linux).</p>
|
|
<h4>5.2.7. Défi</h4>
|
|
<p class="">On suppose que dans le graphe du web, les noeud adjacents
|
|
ont de fortes chances d'appartenir à la même composante
|
|
connexe. <br>
|
|
Ainsi, pour décrire en mémoire une composante regroupant
|
|
les noeuds <span style="font-weight: bold;">{0, 1, 2 ,3 ,4, 5, 6, 7,
|
|
8, 9, 10, 14,15,16, 17, 19, 20}</span> null besoin de stocker en
|
|
mémoire autre chose que les ensembles d'intervalles suivants: <span
|
|
style="font-weight: bold;">[0 .. 10] U [14 .. 17] U [19 .. 20] </span>...</p>
|
|
<p class="">Cependant, les fusions d'ensembles nécessitent de
|
|
nombreuses recopies de données et d'allocations de
|
|
mémoire. L'algorithme s'en trouve par conséquent fort
|
|
ralenti...</p>
|
|
<p class="">On peut lancer le défi en tapant :</p>
|
|
<p class="code">./src/alobe -E -i ../web.data.gz -c 701654</p>
|
|
<p class="">..et admirer les résultats (s'il apparaissent, car
|
|
il y a encore pas mal de soucis de pointeurs se baladant librement...)</p>
|
|
</div>
|
|
</body>
|
|
</html>
|