Graphes

**Premium** · 14/05/2006, 11h45

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** · 15/05/2006, 11h07

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** · 15/05/2006, 11h11

Envoyé par FrancisSourd

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** · 15/05/2006, 11h42

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** · 15/05/2006, 14h09

Envoyé par Jean-Marc.Bourguet

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** · 15/05/2006, 15h00

Envoyé par FrancisSourd

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** · 15/05/2006, 18h50

Envoyé par Premium

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...

**Premium** · 16/05/2006, 07h15

Envoyé par FrancisSourd

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...

Pour la structure de graphe, que proposerais-tu ?
Par exemple, si j'utilise une matrice, je ne vois pas très bien comment représenter les sommets du graphe qui sont des adresses IP

**FrancisSourd** · 16/05/2006, 10h46

Si tu as besoin de rajouter des noeuds, ce n'est pas très pratique d'utiliser une matrice car il faudrait redimensionner la matrice à chaque ajout.

Utilise plutôt des listes de noeuds et des listes d'adjacence, c'est parfait pour les parcours, les ajouts de noeuds et d'arcs.

**Premium** · 18/05/2006, 12h15

Envoyé par FrancisSourd

Si tu as besoin de rajouter des noeuds, ce n'est pas très pratique d'utiliser une matrice car il faudrait redimensionner la matrice à chaque ajout.

Utilise plutôt des listes de noeuds et des listes d'adjacence, c'est parfait pour les parcours, les ajouts de noeuds et d'arcs.

Bonjour,

est-ce que dans le traceroute, le graphe doit être orienté ?

voici les différentes fonctions que j'ai crée pour ajouter des sommets et des arcs en vue de construire mon graphe en supposant que le graphe est orienté :

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
 
#include <stdio.h>
#include <stdlib.h>
 
 
typedef struct cellule{
  int val;
  struct cellule *next;
}Cellule;
typedef Cellule *Liste;
 
 
 
typedef struct graphe{
  int size;
  Liste *adj;
}Graphe;
 
 
 
Cellule *CreerCellule(int val){
  Cellule *c = (Cellule*)malloc(sizeof(Cellule));
  if(c == NULL)
    return NULL;
 
  c->val = val;
  c->next = NULL;
 
  return c;
}
 
 
Liste consListe(int val, Liste liste)
{
  Liste parcours ;
  Cellule* c = CreerCellule(val);
 
  if (!c) return NULL ;
 
  if ( liste == NULL )
    {
      c->next = NULL ; 
      return c ;
    }
 
  for(parcours=liste; parcours->next; parcours=parcours->next ) ;
 
  parcours->next = c ;
  return liste;
}
 
 
Graphe *consGraph(int size){
  int i;
 
  Graphe *g = (Graphe*)malloc(sizeof(Graphe));
  if(g == NULL)
    return NULL;
 
  g->size = size;
 
  if(size > 0)
    g->adj = (Liste*)malloc(size*sizeof(Liste));
  else
    g->adj = NULL;
 
  for(i=0; i<size; i++)
    g->adj[i] = NULL;
 
  return g;
}
 
void addEdge(Graphe *g, int source, int dest){
  g->adj[source] = consListe(dest, g->adj[source]);
}
 
int main(void)
{
  int i ; Liste parcours ;
  Graphe *g = NULL;
  g = consGraph(3);
 
  addEdge(g,0,1);
  addEdge(g,0,2);
  addEdge(g,1,2);
 
  for( i=0; i<g->size; i++ )
    {
      printf( "Sommet %d :", i );
      for( parcours=g->adj[i]; parcours; parcours=parcours->next )
    printf( " %d", parcours->val ) ;
      printf ("\n" ) ;
    }
  return 0;
}

J'avais codé mes fonctions, en utilisant des int.
J'ai donc crée une structure Adresse_ip, me permettant de stocker des IP

Code :

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

1
2
3
4
5
6
7
typedef struct
{
  int a;
  int b;
  int c;
  int d;
}Adresse_ip;

Mon problème est dans le cas de la fonction :

Code :

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

1
2
3
void addEdge(Graphe *g, int source, int dest){
 g->adj[source] = consListe(dest, g->adj[source]);
}

ce ne sera pas possible de prendre les sommets ip_source et ip_dest de type adresse_ip et les considérer comme des indices d'un tableau.

Je voudrais savoir si vous pouviez m'aider pour résoudre cela car ma représentation du graphe impose que tous les sommets soient numérotés entre 0 et size-1

Merci d'avance

**je®ome** · 18/05/2006, 12h53

Pourquoi ne pas utiliser les matrices d'adjacences de ces graphes ??

Où est le problème de redimmensionner la matrice à chaque ajout de noeud ?

**fearyourself** · 18/05/2006, 13h35

Envoyé par Premium

Bonjour,

est-ce que dans le traceroute, le graphe doit être orienté ?

Décision algorithmique, cela dépend de ce que tu veux en faire.

J'avais codé mes fonctions, en utilisant des int.
J'ai donc crée une structure Adresse_ip, me permettant de stocker des IP

Code :

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

1
2
3
4
5
6
7
typedef struct
{
  int a;
  int b;
  int c;
  int d;
}Adresse_ip;

Mon problème est dans le cas de la fonction :

Code :

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

1
2
3
void addEdge(Graphe *g, int source, int dest){
 g->adj[source] = consListe(dest, g->adj[source]);
}

ce ne sera pas possible de prendre les sommets ip_source et ip_dest de type adresse_ip et les considérer comme des indices d'un tableau.

Problème de nouveau algorithmique. Pourquoi ne pas avoir un tableau mesIP dans lequel tu as les différents ip. Les numéros des sommets du graphes seront donc les indices de ce tableau...

Ou mieux, change ton code pour prendre en compte cette nouvelle structure.

Jc

Graphes

C

Discussions similaires

Partager

Partager