Discussion :

[Premium]

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
 
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 si quelqu'un pouvait m'indiquer un algo pour créer le graphe aux fur et à mesure que des adresses IP sont ajoutées


Merci par avance

[FrancisSourd]

Ta structure est un arbre. Tu dois donc être capable de bien manipuler de telle stuctures algorithmiques dans ton langage.

Quand tu dois rajouter une nouvelle route X=(A,X_1,X_2,X_3..., X_n) tu descends dans l'arbre en suivant X: si X_1 est un descendant de la racine A de l'arbre, tu y vas. Si X_2 est un descendant de X_1, tu y vas. Tu continues ainsi jusqu'à X_i tel que X_i+1 n'est pas un descendan de X_i dans l'arbre.
Tu ajoutes alors la branche X_i+1,....X_n en dessous de X_i dans l'arbre.

[Jean-Marc.Bourguet]

Ta structure est un arbre.

Non. C'est un graphe: rien n'interdit d'avoir pour resultat de traceroute X
une fois
ABCX
et une fois
ACBX
bien que generalement on suive toujours la meme route. Ce qui est plus courant c'est que le routage soit asymetrique (cad que le chemin a de A a X n'est pas l'inverse du chemin de X a A).

[Premium]

Bonjour,

est-ce que vous auriez un algo à me proposer pour pouvoir construire le graphe au fur et à mesure que des adresses IP sont ajoutées.

Merci

[FrancisSourd]

Non. C'est un graphe: rien n'interdit d'avoir pour resultat de traceroute X
une fois
ABCX
et une fois
ACBX

Effectivement. Mais un graphe n'est pas la structure naturelle pour stocker un ensemble de chemins possibles: Si tu stockes ABCX et ACBX par les arcs utilisés dans ces chemins, tu crées du même coup les chemins ABX et ACX.

Premium, il faudrait mieux formaliser ce que tu veux faire quand tu as 2 chemins différents entre A et X.

Dans un message quasi identique sur le forum C, tu parles de plus court chemin. Veux tu dire que si tu as deux chemins tu gardes le plus court?

[Premium]

Effectivement. Mais un graphe n'est pas la structure naturelle pour stocker un ensemble de chemins possibles: Si tu stockes ABCX et ACBX par les arcs utilisés dans ces chemins, tu crées du même coup les chemins ABX et ACX.

Premium, il faudrait mieux formaliser ce que tu veux faire quand tu as 2 chemins différents entre A et X.

Dans un message quasi identique sur le forum C, tu parles de plus court chemin. Veux tu dire que si tu as deux chemins tu gardes le plus court?

Je vais essayer d'être plus clair.

Le graphe n'est pas forcément un graphe idéal, et les chemins ne seront pas forcément les meilleurs ou les plus court. Le graphe ne doit pas non plus être figé, ni déterministe car un même traceroute peut donner des résultats différents d'un moment à l'autre

Pour chaque noeud du graphe(son adresse IP), il faut pouvoir connaitres ses voisins, ainsi que sa distance minimale à l'origine (la distance n'est pas forcément constante, par exemple entre un noeud A et un noeud B, un noeud X peut apparaitre en 3è position et le même neoud X peut apparaitre en 6ème position entre le noeud A et le noeud C)

[FrancisSourd]

Pour chaque noeud du graphe(son adresse IP), il faut pouvoir connaitres ses voisins, ainsi que sa distance minimale à l'origine (la distance n'est pas forcément constante, par exemple entre un noeud A et un noeud B, un noeud X peut apparaitre en 3è position et le même neoud X peut apparaitre en 6ème position entre le noeud A et le noeud C)

Si je comprends bien, tu veux faire un cartographie d'internet.

Dans ce cas, lorsque tu découvres un chemin AXYZT, il faut rajouter à ton graphe les noeuds non existants et les arcs (ou arêtes) AX, XY, YZ et ZT qui n'existent pas.

Pour calculer le plus court chemin (en nombre d'arcs jusqu'à un sommet Z), il suffit de faire un parcours en largeur d'abord. Je sais qu'il existe des moyens de maintenir un peu plus efficacement tous les plus courts chemins mais c'est du raffinement algorithmique pas facile à comprendre...

A priori donc, tu n'as donc besoin que d'une structure graphe sur laquelle tu peux ajouter des arcs et effectuer un parcours en largeur.

Si c'est pour un projet "réel", il est possible que tu tombes sur de très grands graphes...