Conseil pour implementation d'un graphe

Bonjour a tous,

Je doit implementer un graph a partir d'une image qui a des pixels reprensentant une ville donc un noeud du graph et a partir de 2 fichier txt un qui contient le numeros de la gare et son nom et l'autre où il y a les arc du graph avec le numeros de la gare de depart et celle darrivé. Suite au graph je doit implementer l'algo de dijstra et celui en profondeur...

J'ai pensé à utiliser les listes chaine (comme ca je pourrai rajouter des villes)...
Pour l'instant j'ai fait ca, mais est ce que c'est suffisant...J'ai enormement de mal avec les liste chainée...Si quelqu'un pouvait me conseiller....

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

typedef struct lgare { int id[20]; char NomVille[20]; struct lgare *Suivant; } Gare;   typedef struct lrail { int idGareDep[20]; int idGareDar[20]; int longueur[2000]; struct lrail *Suivant; } Rail;

---

bonjour

pour programmer ce code vous devez utiliser des fonctions permettant de lire un fichier puis recuperer les donner et les parcourirs .j'ai deja fais un programme permettant de parcourir un graphe en profondeur alors si ca vous interesse je peux vous l'envoyer .
merci

Ah oui ca peut m'interesser...Si ca vous derange pas...Je suis un peu bloquer a vrai dire...

J'ai reussi a ajouter des données dans une listes fictive mais quand je veut ajouter les donné du fichier ca marche pas :?

Bonjour,

Dans votre programme, il y a 3 valeurs qu'il ne faut pas confondre.
NbGare: le nombre de gares
NbRail: le nombre de rails
MaxNom: la taille maximale pour la longueur des noms de gare (en ce compris le '\0' terminal)

Alors pour répondre à votre question concernant le concept des listes chaînées, voici un exemple de structure globale

Code:

---

1 2 3 4

struct liste { // Données pour "un" élément de la liste struct liste *Suivant; };

---

auquel il faut ajouter des fonctions pour manipuler la liste
* ajouter un élément
* supprimer un élément
(* accéder au ième élément pour simuler un tableau)
* ...
cfr tutoriel: http://chgi.developpez.com/pile/
Remarque: le nombre d'éléments de la liste apparaît implicitement dans la longueur de la liste chaînée.

Les listes chaînées sont un concept, on peut les implémenter de différentes manières...

Donc les structures lgare et lrail devrait, si vous tenez absolument à faire des listes chaînées, être quelque chose du genre...

Code:

---

1 2 3 4 5 6 7 8 9 10 11

typedef struct lgare { int id; char NomVille[MaxNom]; struct lgare *Suivant; } Gare; typedef struct lrail { int idGareDep; int idGareDar; int longueur; struct lrail *Suivant; } Rail;

---

Donc dans ces structures de base, seul MaxNom est utilisé!
Ici, NbGare et NbRail apparaîtrons implicitement dans la longueur des listes chaînées.
Dans le cas des tableaux, NbGare et NbRail sont utilisés mais ne brulons pas les étapes.

Liste chaînée vs Tableau
Effectivement, les listes chaînées permettent une certaine souplesse dans l'insertion et la suppression d'éléments, c'est le but.
Cependant, dans ce problème, cela ne me semble pas du tout approprié surtout pour la structure lgare.
En effet, pour parcourir le graphe, il faut utiliser le numéro id et la recherche de ce numéro dans une liste va nécessiter de parcourir à chaque fois environ la moitié de la liste.
On sera donc surtout confronté à l'inconvénient majeur d'une liste à savoir la recherche d'un élément. Perte de temps importante dans l'exécution du programme, ce qui peut s'avérer particulièrement sensible lorsque l'on travaille avec des graphes.
Si les numéros id sont les numéros de 1 à NbGare, l'utilisation d'un tableau est hautement recommendée.

Code:

---

1 2 3

Gare gares[NbGare]; gares[i-1]=... //pour la gare dont l'id est i. /* Les indices d'un tableau commencent à 0. */

---

Et dans ce cas, voici ce que devient la structure lgare:

Code:

---

1 2 3

typedef struct gare { char NomVille[MaxNom]; } Gare;

---

Et le reste du code s'en trouvera également simplifié puisqu'il ne faudra pas implémenter la gestion de la liste...

Si NbGare n'est connu qu'en cours de programme, il suffit d'utiliser un pointeur et faire une allocation mémoire.

Code:

---

1 2 3

Gare *gares; NbGare= lire le fichier... gares=malloc(NbGare*sizeof(Gare));

---

NbGare ne doit normalement pas varier en cours de programme puisqu'on lit les informations dans des fichiers qui à priori ne changent pas pendant l'exécution. Mais bien sûr, on peut (pour compliquer la tâche ou par plaisir de faire de la programmation plus avancée ;) ) souhaiter lire les données progressivement une seule fois et donc ne pas connaître NbGare avant la fin...
Si par conséquent NbGare doit varier en cours de programme, j'utiliserais un tableau dont je modifierais dynamiquement la taille (éventuellement par facteur 2). En fonction des préférences du programmeur, une liste chaînée peut dans ce cas, s'avérer plus simple à programmer...

Je propose dans un premier temps d'utiliser les structures suivantes...

Code:

---

1 2 3 4 5 6 7 8

typedef struct gare { char NomVille[MaxNom]; } Gare; typedef struct rail { int idGareDep; int idGareDar; int longueur; } Rail;

---

Les variables globales suivantes...

Code:

---

1 2	struct gare *gares; struct rail *rails;

---

Et le code suivant...

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

// lecture dans les fichiers NbGare=...; NbRail=...;   // allocation mémoire gares=malloc(NbGare*sizeof(Gare)); rails=malloc(NbRail*sizeof(Rail));   // lecture dans les fichiers for(i=0; i<NbGare; i++) gares[i]=...; for(i=0; i<NbRail; i++) rails[i]=...;   // implémentation des algos retournant la longueur des trajets; int profondeur(int idGareDep, int idGareDar); //algo1, celui de Sivine :) int dijkstra(int idGareDep, int idGareDar); //algo2

---

Et vérifier que le programme fonctionne bien!
Cela évitera de cummuler plusieurs difficultés et rendra le code plus simple.
Ensuite, vous aurez toujours l'occasion d'essayer d'implémenter les tableaux sous la forme de listes...

Pour rester le plus proche possible de votre code, on peut aussi faire la chose suivante

Code:

---

1 2 3 4 5 6 7 8 9

typedef struct gares { int id[NbGare]; char NomVille[NbGare][MaxNom]; } Gares; typedef struct rails { int idGareDep[NbRail]; int idGareDar[NbRail]; int longueur[NbRail]; } Rails;

---

gares et rails sont des structures contenant sous forme de tableaux l'ensemble des données.
Ce code bien que correct ne sépare pas la structure de base. Il me semble donc moins intéressant. Aucune gestion raisonnable sous forme de liste n'est possible puisque les tableaux font partie intégrante de la structure.

Une autre possiblité consiste à utiliser les structures suivantes

Code:

---

1 2 3 4 5 6 7 8 9 10 11

struct lvoisine; typedef struct gare { //int id; char NomVille[MaxNom]; struct lvoisine *Premiere; } Gare; struct lvoisine { int id; int longueur; struct lvoisine *Suivante; };

---

Dans ce cas, chaque gare contiendrait son nom et une liste des gares voisines avec la longueur du trajet permettant de s'y rendre.
Cela simplifierait fortement l'écriture des algorithmes qui nécessitent précisément la connaissance des gares voisines. La vitesse d'exécution y gagnerait surement...
Ici, la liste est appropriée car le nombre de gares voisines varie de gare en gare et de plus l'ordre des gares voisines n'a pas d'importance à priori. On ne doit pas accéder à la ième gare voisine mais à toutes...
Pour implémenter ce code, la structure rail ne sert plus à rien. En effet un rail allant de idGareDep à idGareDar est remplacé par une gare voisine pour idGareDep et une gare voisine pour idGareDar.

Pour conclure, je dirais que l'important en définitive n'est pas d'utiliser des listes chaînées ou des tableaux mais d'avoir une idée claire sur la manière dont les données vont être utilisées dans le programme.
Dans le code proposé, on utilise bizarrement des tableaux dans les listes.

Saji.

Citation:

---

Envoyé par lusiole

J'ai reussi a ajouter des données dans une listes fictive mais quand je veut ajouter les donné du fichier ca marche pas :?

---

1. Avez-vous essayé d'imprimer à l'écran les données lues dans le fichier afin de vérifier si les données sont bien lues...
2. Si le résultat à l'écran est correct, essayez de sauvegarder les données dans des variables en affichant le contenu de ces variables
3. Ensuite dans des structures simples
4. Et finalement dans des listes si nécessaire

C'est quoi une liste fictive...
Pour le programme, cela serait intéressant de comencer par implémenter une simple liste de type pile LIFO avec les méthodes

• Ajouter un élément (Push)
• Afficher toute la liste (Display)
• Détruire toute la liste (Delete)

La gestion des pointeurs surtout pour la libération mémoire n'est pas toujours aisée au début!

Je crois que j'ai voulu un peu trop me compliquer la vie en fait, c'est sur qu'un tableau dynamique a l'air beaucoup plus simple a implementer...Je pense que j'aurais un peu moins de diffuculté comme ça.

Par contre si je veut modifier la taille du nombre de gare il faut que je fasse un realloc?

Sinon pour repondre a vos question les donnée de mon fichier sont bien lu. En fait le probleme qui se pose c'est que j'ai créer 2 fonction pour lire les données une qui lit un fichier normal F=fopen.... qui lit ligne par ligne et une autre appelé dans la fonction precedente qui permet de séparer les donnée en 2 variable. Le fichier contenant les gare est du type:
2
0 Toulouse
1 Paris

Je pense que la fonction qui permet de separer les données en 2 variable n'est pas necessaire et que je peut l'inclure dans la premiére. C'est ce que je vais essayer de faire tout a l'heure...

Encore merci de me consacrer un peu de votre temps pour m'aider...

Citation:

---

Envoyé par lusiole

Par contre si je veut modifier la taille du nombre de gare il faut que je fasse un realloc?

---

Oui!

Citation:

---

Envoyé par lusiole

Sinon pour repondre a vos question les donnée de mon fichier sont bien lu. En fait le probleme qui se pose c'est que j'ai créer 2 fonction pour lire les données une qui lit un fichier normal F=fopen.... qui lit ligne par ligne et une autre appelé dans la fonction precedente qui permet de séparer les donnée en 2 variable. Le fichier contenant les gare est du type:
2
0 Toulouse
1 Paris

---

Il ya plusieurs moyens de procéder pour travailler avec les fichiers et le chaînes de carcatères (Il faut regarder la liste des fonctions disponibles et faire son marché... :roll: )
Les fonctions suivantes permettent de résoudre le problème du découpage en lexèmes.

Code:

---

1 2 3 4 5 6 7

fopen // pour ouvrir fclose // pour fermer fgets // pour lire une ligne sscanf // pour décomposer une chaîne malloc // pour allouer de l'espace mémoire free // pour libérer l'espace mémoire

---

pour fopen, fgets, sscanf, malloc: il faut vérifier que l'opération s'est bien déroulée en récupérant le résultat de la fonction.

Citation:

---

Envoyé par lusiole

Je pense que la fonction qui permet de separer les données en 2 variable n'est pas necessaire et que je peut l'inclure dans la premiére. C'est ce que je vais essayer de faire tout a l'heure...

---

Par exemple, pour le fichier "gares.txt", on peut décomposer les lignes grâce à sscanf

Code:

---

1 2 3

sscanf: "%d" // pour récupérer le nombre de gares sscanf: "%d%s" // pour récupérer le ID et le nom de la gare // %s fonctionne si le nom de la gare tient en un mot.

---

Ce qui donne la structure suivante.

Code:

---

1 2 3 4 5 6 7 8

fp=fopen("gares.txt", "r"); fgets(line, MaxLine, fp); sscanf(line, "%d", &NbGares); for(i=0; i<NbGares; i++) { fgets(line, MaxLine, fp); sscanf(line, "%d%s", &id, nom); } fclose(fp);

---

Auquel, il faut ajouter les allocations mémoire et toutes les précautions d'usage pour tester le bon déroulement des opérations.