IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Graphes


Sujet :

C

  1. #1
    Membre éclairé
    Inscrit en
    Septembre 2005
    Messages
    747
    Détails du profil
    Informations forums :
    Inscription : Septembre 2005
    Messages : 747
    Par défaut Graphes
    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

  2. #2
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut Arbre de traceroute
    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.

  3. #3
    Expert confirmé

    Inscrit en
    Novembre 2005
    Messages
    5 145
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 5 145
    Par défaut
    Citation 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).

  4. #4
    Membre éclairé
    Inscrit en
    Septembre 2005
    Messages
    747
    Détails du profil
    Informations forums :
    Inscription : Septembre 2005
    Messages : 747
    Par défaut
    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

  5. #5
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut
    Citation 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?

  6. #6
    Membre éclairé
    Inscrit en
    Septembre 2005
    Messages
    747
    Détails du profil
    Informations forums :
    Inscription : Septembre 2005
    Messages : 747
    Par défaut
    Citation 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)

  7. #7
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut
    Citation 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...

  8. #8
    Membre éclairé
    Inscrit en
    Septembre 2005
    Messages
    747
    Détails du profil
    Informations forums :
    Inscription : Septembre 2005
    Messages : 747
    Par défaut
    Citation 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

  9. #9
    Membre chevronné
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 52
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Par défaut
    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.

  10. #10
    Membre éclairé
    Inscrit en
    Septembre 2005
    Messages
    747
    Détails du profil
    Informations forums :
    Inscription : Septembre 2005
    Messages : 747
    Par défaut
    Citation 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

  11. #11
    Membre éclairé Avatar de je®ome
    Inscrit en
    Octobre 2005
    Messages
    285
    Détails du profil
    Informations forums :
    Inscription : Octobre 2005
    Messages : 285
    Par défaut
    Pourquoi ne pas utiliser les matrices d'adjacences de ces graphes ??

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

  12. #12
    Expert confirmé

    Avatar de fearyourself
    Homme Profil pro
    Ingénieur Informaticien Senior
    Inscrit en
    Décembre 2005
    Messages
    5 121
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 44
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Ingénieur Informaticien Senior
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2005
    Messages : 5 121
    Par défaut
    Citation 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

Discussions similaires

  1. Classe pour la création d'un graphe xy
    Par Bob dans le forum MFC
    Réponses: 24
    Dernier message: 03/12/2009, 17h20
  2. [Turbo Pascal] [Windows XP] Problème avec l'unité GRAPH
    Par themofleur dans le forum Turbo Pascal
    Réponses: 22
    Dernier message: 29/03/2003, 22h43
  3. Perl & Graphes
    Par makram9999 dans le forum Modules
    Réponses: 4
    Dernier message: 24/03/2003, 11h24
  4. [] [Excel] Exporter un graphe MSChart vers Excel
    Par Gonzo dans le forum Macros et VBA Excel
    Réponses: 4
    Dernier message: 18/12/2002, 17h49
  5. Concerne les graphes
    Par mcr dans le forum Algorithmes et structures de données
    Réponses: 10
    Dernier message: 12/11/2002, 11h02

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo