[Algo]Graphe
Hors ligneK@dor Le 14/05/2006 à 19:29 Profil de K@dor Configuration de K@dor

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
Hors ligneInvité Le 14/05/2006 à 20:04 Profil de Invité Configuration de Invité

Bonjour

quel est le langage ? quelle est la structure de donnée ?
en C ça donnerait un :
int idMax;

typedef struct adresse{
int id;
int adresse; //et oui , une adresse, c'est 4 octets...
}

ensuite, tu places les noeuds...

typedef struct noeud{
int id1, id2;
float ping;
}

et pour ajouter une adresse, tu ajoutes au moins un noeud, et une adresse, et tu incrémentes id...

après, pour trouver le chemin le plus court, un djikstra
--
Compte invité - devenez membre pour disposer de votre compte personnalisé !
Hors ligneK@dor Le 14/05/2006 à 20:19 Profil de K@dor Configuration de K@dor

Salut,

c'est à coder en C.

En faite, j'aurais en premier lieu besoin d'aide pour créer le graphe au fur et à mesure que de nouvelles adresses IP sont ajoutées

Je ne sais pas comment gérer un algo qui puisse faire cela
Hors ligneInvité Le 14/05/2006 à 20:32 Profil de Invité Configuration de Invité

mais quel algo ? et quelle est ta structure de donnée ?
--
Compte invité - devenez membre pour disposer de votre compte personnalisé !
Hors ligneAnthony Le 14/05/2006 à 20:43 Profil de Anthony Configuration de Anthony

Fou du volant
Salut,

perso je passerai par un tableau multi-dimensionnel pour faire ça (un arbre en gros). Ca pourrait ressembler à ça :

tableau_ip[0][0] : Adresse IP de la "racine" (si tu en as plusieurs, la deuxième "racine" sera contenue dans tableau_ip[1][0]
tableau_ip[0][1][X][0] : ip (en int) du serveur qui passe par l'ip de la racine [0][0] cat (cette ip sera également dans la clé X)
tableau_ip[0][1][X][1][Y][0] : Y=ip (en int) du "sous serveur" (qui passe par l'ip du [1][X][0] pour être atteint)  (cette IP sera également contenue dans Y)

Bon c'est un exemple, il doit y en avoir de meilleurs, mais son avantage est que tu génères ton tableau sans prise de tête. Ensuite pour le parser c'est pareil ça se fait très facilement ;)
--

Hors ligneK@dor Le 14/05/2006 à 20:47 Profil de K@dor Configuration de K@dor

coucou747 a écrit :
mais quel algo ? et quelle est ta structure de donnée ?

Je ne comprends pas très bien pourquoi tu poses cette question?

L'objet de mon topic est justement d'avoir une aide pour créer un algo qui puisse faire cela.
Hors ligneInvité Le 14/05/2006 à 20:57 Profil de Invité Configuration de Invité

antho, ça ne marche pas pour la simple raison qu'il y a plusieurs chemins pour arriver à un endroit avec traceroute...
et en C, on ne peut pas faire ça de toute façon....
bon, selon moi, la structure de donnée que je t'ai mise en bas est la bonne...

int idMax;

typedef struct {
int id;
int adresse; //et oui , une adresse, c'est 4 octets...
}adresse;

ensuite, tu places les noeuds...

typedef struct {
int id1, id2;
float ping;
}noeud;

ensuite, bah c'est simple, une fonction pour ajouter un noeud, et une pour ajouter une adresse
void addnoeud(int id1, int id2, int ping, noeud * liste);
int addadresse(int id, int adresse, noeud * adresse, int idmax);
--
Compte invité - devenez membre pour disposer de votre compte personnalisé !
Hors ligneAnthony Le 14/05/2006 à 21:03 Profil de Anthony Configuration de Anthony

Fou du volant
Ouais j'y avais pas pensé. Pour le tableau c'est possible de le faire mais ça fera un arbre, bref ça correspond apparemment pas à ce qu'il veut.

Tant pis
--

Hors ligneK@dor Le 14/05/2006 à 21:17 Profil de K@dor Configuration de K@dor

coucou747 a écrit :
antho, ça ne marche pas pour la simple raison qu'il y a plusieurs chemins pour arriver à un endroit avec traceroute...

et en C, on ne peut pas faire ça de toute façon....

bon, selon moi, la structure de donnée que je t'ai mise en bas est la bonne...



int idMax;



typedef struct {

int id;

int adresse; //et oui , une adresse, c'est 4 octets...

}adresse;



ensuite, tu places les noeuds...



typedef struct {

int id1, id2;

float ping;

}noeud;



ensuite, bah c'est simple, une fonction pour ajouter un noeud, et une pour ajouter une adresse

void addnoeud(int id1, int id2, int ping, noeud * liste);

int addadresse(int id, int adresse, noeud * adresse, int idmax);

Merci
Est-ce que tu pourrais m'indiquer à quoi correspond les parametres des structures que tu as mis,

Je ne vois pas treès bien comment un noeud donné pourrait avoir plusieurs successeurs car il me semble que tu proposes une liste chainée simple?

Pourrais-tu me détailler ta pensée ?
Hors ligneInvité Le 14/05/2006 à 21:21 Profil de Invité Configuration de Invité

noeud est un lien entre deux adresses, dans un arbre, les noeuds sont à sens uniques, et t'as qu'un seul chemin pour aller d'un point à un autre...

là c'est différent, avec un traceroute, t'as au moins deux chemins pour pouvoir prévennir les panes...

donc, t'associe un id à chaque adresse (mais bon, ça pourrait être l'adresse en elle même, j'ai mis un id pour que tu puisses ajouter des détails genre protocols ect...)
et ensuite, t'as des coeuds (les chemins...) qui relient deux adresses, donc deux id... avec une certaine vitesse (le ping)
--
Compte invité - devenez membre pour disposer de votre compte personnalisé !
Vous avez résolu votre problème avec VIC ? Faites-le savoir sur les réseaux sociaux !
Vulgarisation-informatique.com
Cours en informatique & tutoriels