Graphe : problème d'ordonnancement

Salut
Je n'arrive pas démarrer, j'ai besoin d'aide :

La réalisation d’un projet se décompose en 12 tâches notées A, B, C, D, E, F, G, H, I, J, K et L, reliées entre elles par des contraintes de précédence. Les contraintes et les durées, en jours, de ces tâches sont données par le tableau suivant :

Taches	A	B	C	D	E	F	G	H	I	J	K	L
Successeurs	F,K	D	A,D,L		J	G	I	A,C,J		A,G	D,I	B
Durees	2	2	4	1	3	1	2	5	4	6	3	2

Par exemple, la tâche C doit précéder les tâches A, D et L et est de durée 4.

Exemple de commentaire et d’affichage :

Citation:

---

# ceci est le fichier "graphe"
# le graphe a 12 sommets, il est non-oriente 12 non-oriente
# attention : la numérotation des sommets commence à 0 !
# toutes les valuations sont égales a 1
# comme le graphe est non-oriente, on n'indique que les arcs (x,y) avec x < y
0 1 1
0 7 1
1 2 1
1 7 1
1 8 1
2 3 1
3 4 1
3 5 1
3 9 1
4 5 1
5 6 1
5 10 1
6 7 1
7 11 1
8 9 1
8 10 1
8 11 1
9 10 1
9 11 1
10 11 1

---

Travail à faire : réaliser un programme en langage C/C++ permettant de résoudre le problème exposé ci-dessus.

Bonjour,

Le graphe est naturellement orienté puisqu'il y a une notion de successeurs. Il est vraisemblable que le problème ait des développements nécessitant de remonter vers les prédécesseurs d'où le non orienté.

Je ne vais pas résoudre ce problème, juste donner une piste.

A priori, deux structures peuvent servir de base :

• un chaînage composé d'une structure de maillon simple : pointeur sur une tache et pointeur sur le maillon suivant (nul si pas de suivant)
• une structure de tâche : nom, n°, durée, pointeur sur le 1er maillon des successeurs, pointeur ver le premier maillon des prédécesseurs.

Après il faut faire vivre cela (prévoir une fonction de contrôle d'intégrité qui vérifie que les successeurs d'une tâche l'ont bien comme prédécesseur et réciproquement).

Salutations

Merci pour votre aide

Bonjour

Citation:

---

Envoyé par Guesset

A priori, deux structures peuvent servir de base :

• un chaînage composé d'une structure de maillon simple : pointeur sur une tache et pointeur sur le maillon suivant (nul si pas de suivant)
• une structure de tâche : nom, n°, durée, pointeur sur le 1er maillon des successeurs, pointeur ver le premier maillon des prédécesseurs.

---

A mon avis une seule structure peut suffire pour gérer une tâche. Elle contiendra son nom, sa durée et un simple tableau de 13 pointeurs (puisqu'on a 12 tâches et un dernier à NULL comme marqueur de fin) pour gérer les successeurs et idem pour les prédécesseurs.
Gérer les successeurs et prédécesseurs par une seconde structure de liste chainée peut se justifier quand ladite liste évolue (s'agrandit, diminue, que des maillons viennent s'insérer au milieu, ou se supprimer). Mais puisqu'ici elle reste fixée à au maximum 12 et que pour chaque tâche la liste des successeurs et prédecesseurs semble figée...

Bonjour Sve,

Citation:

---

Envoyé par Sve@r

Bonjour

A mon avis une seule structure peut suffire pour gérer une tâche. Elle contiendra son nom, sa durée et un simple tableau de 13 pointeurs (puisqu'on a 12 tâches et un dernier à NULL comme marqueur de fin) pour gérer les successeurs et idem pour les prédécesseurs.

---

Si c'est un exercice, c'est à dire un programme jetable, il n'est effectivement pas nécessaire de faire quelque chose d'adaptable. Dans ce cas, on peut même se contenter d'un tableau de 12 pointeurs (si la fin est avant le 12e, le suivant pointe sur nul, mais si la fin est à 12 ce n'est pas la peine d'aller voir après) sauf si on veut appliquer toujours le même contrôle quitte à avoir un 13e pointeur constant à nul.

Par ailleurs, ils veulent avoir un graphe non orienté (je pense pour pouvoir remonter facilement), il faudrait donc un deuxième tableau (ou deux listes) pour les prédécesseurs si on ne veut pas reparcourir systématiquement les tableaux de prédécesseurs potentiels pour savoir si nous sommes sur l'un de ses successeurs.

Si ce n'est pas un exercice, on a au moins un exemple célèbre où passer de 12 à 13 s'est avéré très problématique :D.

Salutations

Citation:

---

Envoyé par Guesset

Si c'est un exercice, c'est à dire un programme jetable, il n'est effectivement pas nécessaire de faire quelque chose d'adaptable.

---

Oui, c'est l'impression que j'ai eu. D'autant plus que séparer "structure pour la tâche" et "structure pour leur ordonnancement" peut alors devenir complexe pour un débutant (il va avoir des pointeurs, bien souvent doubles, qui se croiseront dans tous les azimuths)...:aie: et s'il ne prend pas de précautions ne serait-ce que pour bien nommer les bases alors :mur:

Ceci dit, j'ai aussi l'impression que le PO a abandonné (impression appuyée par tous les topics qui foisonnent sur ce forum qui commencent toujours de la même façon et sur lesquel le PO ne réapparait plus après le 3° post) :P

Citation:

---

Envoyé par Guesset

Par ailleurs, ils veulent avoir un graphe non orienté (je pense pour pouvoir remonter facilement), il faudrait donc un deuxième tableau (ou deux listes) pour les prédécesseurs

---

Oui, c'était prévu qand j'ai dit "et idem pour les prédecesseurs" ;)

Citation:

---

Envoyé par yacouba zouberou

réaliser un programme en langage C/C++ permettant de résoudre le problème exposé ci-dessus.

---

Le langage C/C++ n'existe pas. Soit c'est du C. Soit c'est du C++ (*). Il faut choisir :)

(*) = (même si une bonne partie de C++ est semblable à C, on n'utilise en général pas cette partie pour faire du C++ car C++ possède des fonctions bien plus avancées et plus pratiques pour résoudre des problèmes).

Bonjour Sve,

Citation:

---

Envoyé par Sve@r

Ceci dit, j'ai aussi l'impression que le PO a abandonné (impression appuyée par tous les topics qui foisonnent sur ce forum qui commencent toujours de la même façon et sur lesquel le PO ne réapparait plus après le 3° post) :P

---

Typique du "Je n'est pas fait mon exercice et je dois le rendre demain" sans doute. Au bout de 3 messages, il est trop tard...

Salut

desolé j'etais deconnecte et merci pour vos suggestion .
voici les structures que j'ai faite

Code:

---

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

struct Arc { int sommet; int valuation; struct Arc *suivant; }; struct sommet { struct Arcs *arc; int id; int duree; };

---

ça fonctione