[Algo]Graphe

Premium · Le 14/05/2006, à 17:43

Bonjour,

je dois lancer plusieurs traceroute et construire un graphe avec les IP trouvées.Dans mon problème seules les IP comptent.
Les lettres correspondent à des adresses IP

Par exmple :
je lance

traceroute X
A
B
C
X

Mon graphe sera donc comme suit
A - B - C - X
 
Puis on le complète...
 
traceroute Y
A
B
E
G
Y
 
A - B - C - X
     |

     E - G - Y



puis on le complete
 
traceroute Z
A
B
C
H
Z
 
A - B - C - X
     |    |

     |    H - Z

     E - G - Y

Je voudrais savoir comment faire pour créer le graphe aux fur et à mesure que des adresses IP sont ajoutées

Une fois le graphe crée, il faudrait pouvoir donner les plus distances minimales à la source .
Par exemple dans le graphe suivant on aurait en considérant la source en A

B,1
E,2
C,2
G,3
etc...

ainsi que les couples de sommets
par exemple dans le graphe, de G on peut atteindre E et Y:
G,E
G,Y
etc...

Si quelqu'un pouvait m'aider?

Merci par avance

Dernière modification par Premium (Le 14/05/2006, à 17:46)

Black_pignouf · Le 14/05/2006, à 18:03

Regarde du côté de graphviz, qui va vite devenir ton ami:
http://www.graphviz.org/

En particulier, dot devrait t'être le plus utile.

Voilà un exemple de fichier dot qui correspond à ton exemple:

digraph G {
A -> B;
B -> C;
B -> E;
C -> X;
E -> G;
G -> Y;
}

Plus simple, ce serait dur non?
Après tu enregistres ce fichier en test.dot
puis

dot -Tps test.dot -o test.ps

et tu obtiens un joli graphe en postscript, prêt à être imprimé ou converti en pdf.

Maintenant, pour convertir la sortie de traceroute en un fichier .dot, un coup de script (Ruby, shell, Perl ou autres...) et le tour est joué. Si tu n'en connais aucun, ca risque d'être dur par contre...

Bon courage!

Premium · Le 14/05/2006, à 18:34

Merci pour le lien mais il me faudrait des algos pour les retranscrire en C.

Dernière modification par Premium (Le 14/05/2006, à 18:36)

gene69 · Le 14/05/2006, à 20:10

pour dessiner je ne sais pas MAIS pour la structure pour stocker tu as le choix.
Soit une matrice avec des IP sur les lignes et les colonnes avec un boolean pour representer une connection OU un entier qui reprensente la distance en ms entre les IP. Attention à ne pas mettre 0 là ou il n'y a pas de lien...

Complexité spaciale: n2

Sinon tu fais des listes de colision un peu comme les tables de hachages.

Maintenant pour l'utiliser c'est simple:
traceroute>>fichier.txt
apres
IP = ip @eth0
graphe = nouveau_graphe;
ouvrir fichier
tant qu'il reste des lignes
x = lire_une_ligne
temp = IP_parse(x)
ajouter_à (graphe, IP, temp , DistanceParse(x));
IP=temp;
fin tant que;

Dernière modification par gene69 (Le 14/05/2006, à 20:10)

Premium · Le 15/05/2006, à 16:34

gene69 a écrit :

pour dessiner je ne sais pas MAIS pour la structure pour stocker tu as le choix.
Soit une matrice avec des IP sur les lignes et les colonnes avec un boolean pour representer une connection OU un entier qui reprensente la distance en ms entre les IP. Attention à ne pas mettre 0 là ou il n'y a pas de lien...
Complexité spaciale: n2
Sinon tu fais des listes de colision un peu comme les tables de hachages.
Maintenant pour l'utiliser c'est simple:
traceroute>>fichier.txt
apres
IP = ip @eth0
graphe = nouveau_graphe;
ouvrir fichier
tant qu'il reste des lignes
x = lire_une_ligne
temp = IP_parse(x)
ajouter_à (graphe, IP, temp , DistanceParse(x));
IP=temp;
fin tant que;

Je crois qu'il y a une incompréhension.
Je ne cherche pas à dessiner un graphe. Le dessin était juste pour illustrer la manière dont il fallait faire.

Concernant la structure de données que tu proposes pour le tableau : Comment sera t'on quelle est l'adresse IP d'une ligne ou d'une colonne donné ?

Pourrais-tu si ça ne te déranges pas me détailler un peu plus l'algo?

Merci par avance

gene69 · Le 15/05/2006, à 22:16

ben si tu fait un tableau à 2 entrée chaque IP doit se trouver titre de colonne et titre de ligne, d'ou la complexitée spaciale détestable.

moi j'aurai plutot mis une liste de colision avec un savant mélange de table de hachage... ok le tableau est plus simple.

Pour l'algo bennn sais pas quoi te dire de plus...

tu crees ton fichier texte

traceroute jerikojerk.over-blog.net
traceroute to jerikojerk.over-blog.net (62.233.38.227), 30 hops max, 38 byte pac kets
1 * * *
2 10.224.48.XX (10.224.48.XX) 59.159 ms 63.934 ms 63.977 ms
3 pos4-1.nrlyo202.Lyon.francetelecom.net (193.252.103.198) 63.992 ms 63.960 ms 63.981 ms
4 pos12-0.ntsta302.Paris.francetelecom.net (193.252.103.110) 63.976 ms 63.96 2 ms 63.979 ms
5 pos10-0.ntsta202.Paris.francetelecom.net (193.251.126.69) 175.989 ms 95.98 3 ms 192.001 ms

tu initialises l'ip de départ:
IP_depart = @moi
tu ajoutes cette adresse dans ton graphe (une ligne + une colonne dans le cas du tableau)

(debut boucle)

et apres tu lis ligne par lignes

2 10.224.48.XX (10.224.48.XX) 59.159 ms 63.934 ms 63.977 ms

pour chaque ligne tu extrais la distance moyenne
63 ms = distanceParse(" ");
et l'ip
ip_lue = 198.168.2.55 = IP_parse(" ");

tu connais l'IP précédante (PI_depart)
si IP_lue n'existe pas dans le graphe, alors tu l'ajoute dans le graphe.
tu completes le graphe (le croisement entre la ligne IP_depart et de la colonne ip_lue avec la mesure de la distance en ms) [tu peux par ex remplir uniquement le triangle supérieur du tableau pour eviter la redondance...]

pis tu boucles tant que tu as autre chose à lire.

NicoA380 · Le 15/05/2006, à 22:21

Pour le plus court chemin, recherche l'algorithme de Dijkstra.
Je dois l'avoir en C++, c'était un exo l'année dernière à l'IUT. Le truc, c'est que mon PC est HS

Mathieu147 · Le 15/05/2006, à 23:03

Mon cours de «Structures de données et algorithmes», va voir les chapitres sur les graphes, ça peut t'aider: http://www.montefiore.ulg.ac.be/~piater/Cours/INFO0902/plan.php

Premium · Le 16/05/2006, à 15:26

Salut,

Alors avant de m'attaquer à la création de mon graphe, il me faut faire le parsing des valeurs de traceroute

IL faut que je parse un fichier pour ne garder que les adresses IP

j'ai fait le parsing de cette manière

Mon fichier pour le teste est le suivant :

 1  192.168.0.1  9.754 ms  9.461 ms  8.046 ms
 2  195.6.244.14  60.885 ms  48.924 ms  90.517 ms
 3  194.206.126.244  50.503 ms  48.97 ms  120.122 ms
 4  194.206.126.2  55.655 ms  52.213 ms  58.908 ms
 5  208.213.229.130  588.303 ms  589.843 ms  589.611 ms
 6  208.213.229.129  599.564 ms  599.763 ms  600.749 ms
 7  208.213.229.226  629.167 ms  599.284 ms  599.383 ms
 8  195.10.40.34  599.152 ms  599.289 ms  631.011 ms
 9  157.130.34.217  642.326 ms  715.072 ms  653.724 ms
10  146.188.160.62  595.143 ms  590.433 ms  659.247 ms
11  146.188.160.181  649.863 ms  700.901 ms  617.067 ms
12  137.39.253.86  600.835 ms  599.379 ms  590.867 ms
13  192.48.96.9  607.071 ms  589.221 ms  603.156 ms

et en sortie, j'obtiens ceci :

1
  195.6.244.14
  194.206.126.244
  194.206.126.2
  208.213.229.130
  208.213.229.129
  208.213.229.226
  195.10.40.34
  157.130.34.217
  146.188.160.62
  146.188.160.181
  137.39.253.86
  192.48.96.9

Il y a un problème au niveau de la première ligne

ESt-ce que quelqu'un saurait comment remédier à ce problème?

Je voudrais également savoir comment faire pour ignorer les adresses IP suivantes :

10.0.0.0 à 10.255.255.255
172.16.0.0 à 172.31.255.255
192.168.0.0 à 192.168.255.255
224.0.0.0 à 239.255.255.255
240.0.0.0 à 255.255.255.255

et les * * * qui apparaissent parfois dans les traceroute.

Merci

Voici mon code :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void){
  FILE * file = fopen("fichier","r");
  char buffer[BUFSIZ];
  int a,b,c,d;
  char *espace;

  if(file == NULL){
    perror("erreur de lecture");
    exit(-1);
  }
  
  while(fgets(buffer, sizeof buffer, file) != NULL){
    espace = strtok(buffer, " ");
    if(espace == NULL)
      {
	perror("strtok");
	exit(-1);
      }
    
    fscanf(file, "%d.%d.%d.%d", &a, &b, &c, &d);
    printf("%s\n",buffer);
  }
  
  return 0;
}

Dernière modification par Premium (Le 16/05/2006, à 16:28)

Black_pignouf · Le 16/05/2006, à 17:06

Salut! Une solution pourrait être de lancer ça:

traceroute forum.ubuntu-fr.org | sed -re 's/(^ *[0-9]+)[^(]*\(([0-9\.]*).*/\1 \2/g' > toto

Voilà le contenu du fichier toto après :

1 * * *
2 217.0.64.66
3 62.154.46.182
4 62.156.138.178
5 195.122.132.178
6 212.187.128.34
7 212.73.240.39
8 212.73.204.70
9 193.24.212.83
10 80.82.17.133

Le * * * vient d'un bug de je ne sais pas quoi je ne sais où dans la requête de traceroute.
Tu peux enlever les lignes contenant un * en utilisant:

traceroute forum.ubuntu-fr.org | sed -re 's/(^ *[0-9]+)[^(]*\(([0-9\.]*).*/\1 \2/g' | grep -v '\*'> toto

après, ton fichier toto devient :

2 217.0.64.66
3 62.154.46.182
4 62.156.138.178
5 195.122.132.178
6 212.187.128.34
7 212.73.240.83
8 212.73.204.70
9 193.24.212.83
10 80.82.17.133

Enjoy!

Modif: Ah! Je viens de voir tes autres souhaits...
je n'ai pas cherché les expressions régulières pour

172.16.0.0 à 172.31.255.255
224.0.0.0 à 239.255.255.255

c'est un peu trop lourd...

La fonction devient:

traceroute forum.ubuntu-fr.org | sed -re 's/(^ *[0-9]+)[^(]*\(([0-9\.]*).*/\1 \2/g' | grep -v '\*' | grep -Ev '10(\.[0-9]+){3,3}' | grep -Ev '2[4-5][0-9](\.[0-9]+){3,3}' | grep -Ev '192.168(\.[0-9]+){2,2}'

Ouf!!!

Dernière modification par Black_pignouf (Le 16/05/2006, à 17:25)

Premium · Le 16/05/2006, à 17:32

Salut,

Je ne peux pas utiliser le shell.
Tout ce que je dois faire doit être écrit en langage C.

Concernant les résultats de traceroute, je les mets effectivement dans un fichier que je parse ensuite.

Connais-tu le C, tu pourrais peut-être m'aider ?

Black_pignouf · Le 16/05/2006, à 17:38

Ben tu dois bien lancer traceroute pour avoir ces résultats, non?
Alors pourquoi ne pas économiser un peu de temps en rajoutant des sed et des grep?

T'en fais pas, il te restera du boulot pour créer ton graphe après!
Et non, je ne connais pas trop le C, désolé...

C'est très rapide mais je trouve la syntaxe moche au possible, surtout depuis que je connais Ruby.

Bon courage!

Premium · Le 16/05/2006, à 17:58

Black_pignouf a écrit :

Ben tu dois bien lancer traceroute pour avoir ces résultats, non?
Alors pourquoi ne pas économiser un peu de temps en rajoutant des sed et des grep?
T'en fais pas, il te restera du boulot pour créer ton graphe après!
Et non, je ne connais pas trop le C, désolé...
C'est très rapide mais je trouve la syntaxe moche au possible, surtout depuis que je connais Ruby.
Bon courage!

C'est vrai que ta commande est très pratique mais je ne peux utiliser que l'option -n du traceroute et me débrouiller pour le reste

Dernière modification par Premium (Le 16/05/2006, à 17:59)

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#1 Le 14/05/2006, à 17:43

[Algo]Graphe

#2 Le 14/05/2006, à 18:03

Re : [Algo]Graphe

#3 Le 14/05/2006, à 18:34

Re : [Algo]Graphe

#4 Le 14/05/2006, à 20:10

Re : [Algo]Graphe

#5 Le 15/05/2006, à 16:34

Re : [Algo]Graphe

#6 Le 15/05/2006, à 22:16

Re : [Algo]Graphe

#7 Le 15/05/2006, à 22:21

Re : [Algo]Graphe

#8 Le 15/05/2006, à 23:03

Re : [Algo]Graphe

#9 Le 16/05/2006, à 15:26

Re : [Algo]Graphe

#10 Le 16/05/2006, à 17:06

Re : [Algo]Graphe

#11 Le 16/05/2006, à 17:32

Re : [Algo]Graphe

#12 Le 16/05/2006, à 17:38

Re : [Algo]Graphe

#13 Le 16/05/2006, à 17:58

Re : [Algo]Graphe

Pied de page des forums