Discussion :

[Brila54]

Bonjour,
Dans le cadre d'un exercice je souhaiterai charger un graphe depuis un fichier text sous le format suivant :

Code :

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

1
2
3
4
5
6
7
8
9
 
ordre
num
num
…
taille
num1num2 poids
num1num2 poids
......

J'aimerai faire une classe graphe et une classe sommet, ce que j'avais fait dans un précédent exercice mais cette fois, je n'arrive pas à visualiser comment enregistrer l'information sur les arrêtes et les poids.
J'avais précédemment fait une classe graphe possédant un vecteur de pointeurs sur sommet, et dans la classe sommet, un vecteur de sommet (pour la liste des sommets adjacents). Mais maintenant avec les poids je n'arrive vraiment pas trop à voir quoi en faire. Si quelqu'un aurait une petite piste... merci d'avance

[LittleWhite]

Bonjour,

On peut imaginer une structure Lien qui contient le lien (un pointeur vers la destination, et un entier pour le poids) et ce Lien serait instancié dans chaque nœud (Il faut une structure Noeud aussi ).

[foetus]

Je n'ai plus de souvenirs mais il me semble qu'1 graphe c'est une liste de sommets et une liste d'arêtes.

Un sommet c'est un couple (x, y, z)/ autre chose (avec en +, 1 identifiant qui est quand même recommandé) et une arête, 2 sommets et 1 poids (Édit : l'orientation est juste une contrainte en respectant l'origine (le sommet qui s'appelle soit from soit start soit src soit begin) et la destination (l'autre sommet soit to soit end soit dest))

Là où je bloque c'est comment trouver toutes les arêtes d'1 sommet ?
Mettre dans 1 sommet, 1 liste d'arêtes (les siennes cela va de soi, même pointeur) c'est lourd
Faire la recherche dans la liste d'arêtes du graphe, c'est lourd

[CedricMocquillon]

Il y a plusieurs manières de représenter un graphe.

S'il est dense (c'est à dire que de nombreux sommets sont connectés les uns aux autres) on peut représenter le graphe sous la forme d'une matrice (autant de lignes et de colonnes que de sommets), l'élément Mat[i][j] représente les données liées à l'arc entre i et j. cf matrice d'adjacence

Si le graphe est peu dense on peut partir d'une liste de sommets et à chaque sommet on associe une liste des arcs sortants cf liste d'adjacence

Après il y a de nombreuse variantes (par exemple si le graphe est orienté ou non, s'il existe plusieurs arcs entre deux sommets, etc...)

[koala01]

Salut,

En fait, l'idéal est toujours de respecter le SRP, cela permet de se sortir des situations les plus complexes

D'un coté, on a la notion de graphe, qui représente "des points reliés entre eux" selon une logique 0...N (un point peut être relié à 0 autre points... ou plus)

La "liaison" ne se fait que "de un point vers un autre" peut -- potentiellement -- être orientée (je relie spécifiquement le premier point au deuxième, ou l'inverse... ou bien le sens n'a aucun intérêt) et est appelée arrête.

L'arrête peut -- accessoirement -- présenter un poids: une valeur (quelque soit l'unité choisie) permettant d'évaluer "ce que cela nous coûte" de passer d'un point à l'autre.

En outre, l'arrête peut éventuellement présenter des restrictions (par exemple, la vitesse maximale autorisée si notre graphe représente des portions de la voie publique) ... ou pas

A priori, n'importe quel point peut être relié à n'importe quel autre: il n'y a strictement rien qui interdise d'avoir une arrête qui traverserait l'intégralité d'un graphe pour relier l'un des premiers points qui le composent à l'un des derniers.

Enfin, à la notion de poids, à la base, elle correspond à n'importe quel type de donnée utilisable dans un référentiel donné et la valeur associée devra -- le plus souvent -- être évaluée (quitte à être mise en cache pour ne pas devoir être recalculée en permanence)

Il nous faut donc au moins trois structures "de base", et potentiellement une quatrième:
la structure point, qui pourrait la forme de

Code :

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

1
2
3
4
5
6
7
8
struct point{
    int id; // c'est plus facile pour déterminer de quel point on parle par la suite
             // ce serait sans doute l'indice du point dans la liste maintenue par le
             // graphe
    TYPE x;
    TYPE y;
   // TYPE z;
};

la structure arrete qui pourrait prendre la forme de

Code :

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

1
2
3
4
5
6
struct arrete{
    int a; // représente l'id du premier point
    int b; // l'id du deuxième point
    // direction sens; (direction étant sans doute une simple énumération)
    // type restriction
};

ou la forme de

Code :

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

1
2
3
4
5
6
struct arrete{
    point & a;   // parce que je préfère les références, mais un pointeur pourrait faire l'affaire :D
    point & b;
    // direction sens; (direction étant sans doute une simple énumération)
    // type restriction
};

et une structure grpahe qui permettra de maintenir la liste des points et la liste des arrête et qui pourrait ressembler à quelque chose comme

Code :

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

1
2
3
4
5
struct graphe{
    std::vector<point> points;
    std::vector<arrete> arretes;
    // some_type poids_des_arrêtes; // les poids mis en cache :D
};

Tout cela étant dit, lorsqu'il s'agit de charger un graphe existant, le plus facile est très certainement de travailler "avec ordre et méthode": comme une arrête ne peut exister que si elle relie effectivement deux points entre eux autant commencer par charger l'ensemble des points qui composent le graphe, ce qui implique que le fichier devrait sans doute commencer par quelque chose comme

Code :

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

1
2
3
4
5
N // le nombre de points à charger
x1, y1, z1
x2, y2, z2
...
xN, yN, zN

où N (le nombre de points) permettra essentiellement de faciliter la logique permettant de charger les différents points

Ensuite, nous pourrons charger les différentes arrêtes. Mais, comme on ne peut pas garantir que les différents points se trouveront à la même adresse mémoire au travers des différents exécutions, il est préférable d'utiliser une donnée qui a peu de chance de varier pour représenter le point: l'indice du point lors de la lecture du graphe.

Le fichier continuera donc sans doute sous une forme proche de

Code :

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

1
2
3
4
5
M // le nombre d'arrête
point1_a, point1_b
point2_a, point2_b
...
pointM_a, pointM_b

(pour sa forme la plus simple) , voire, sous la forme de

Code :

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

1
2
3
4
5
M // le nombre d'arrête
point1_a, point1_b, direction1, restriction1
point2_a, point2_b, direction2, restriction2
...
pointM_a, pointM_b, direction1, restriction1

en fonction des données disponible au niveau des arrêtes

Le cas échéant, on pourrait aussi envisager de charger les poids mis en cache, mais cela dépendra forcément de ce qu'ils représentent et de la manière dont ils sont représentés.

Ensuite, les choses pourront évoluer en fonction des besoins que l'on associe à chaque terme (par exemple : un noeud doit pouvoir la liste de toutes les arrêtes qui en partent) et la manière de mettre les différentes notions en relations les unes avec les autres dépendra très certainement de ces besoins plus "spécifiques"