implémentation d'un graphe

Bonjour,
Dans le cadre d'un projet on souhaite réaliser un graphe de ce type en langage C
http://img4.hostingpics.net/pics/874735graphe4sites.jpg

Je vous explique le principe: On a un point de départ, un nombre de tache à réaliser, une arrivée qui est le point de départ.

Sur l'exemple ci dessus, il y a 4 taches à réaliser. Chaque tache doit être finie à une DateF et chaque tache nécessite de la matière première disponible à une DateM. Donc parfois il est préférable d'attendre les ressources pour plusieurs taches, des fois non. Il faut savoir que ces tâches s'effectuent à des distances que l'on prend en compte dans nos calculs.

Le graphe doit nous retourner le chemin ou il y aura le plus petit retard possible sur chaque tâche.

Nous n'arrivons pas à trouver la méthode pour découper les séquences possibles de taches et affecter les contraintes de précédence. De plus ici c'est un exemple de 4 tâches mais notre programme doit fonctionner avec n taches.

Merci de votre aide, je me tiens à votre disposition si je n'ai pas était assez clair ci-dessus ou pas assez précis.

Ca sent les cours d'ordonnancement et/ou de temps réel :aie:

Qu'avez-vous réussi à faire pour le moment ?

C'est très vague ce que tu nous demandes là...

Il suffit simplement d'allouer des tableaux pour chaque état afin d'enregistrer les contraintes.

Après, on part du départ et on continu sur un chemin tant qu'on peut calculer sinon, on prend un autre chemin.

merci on a finalement réussi à faire la fonction pour créer les noeuds possibles. Ici: (1,2,3,4,12,23,34,123,234,1234).

Maintenant on cherche comment implémenter le graphe en c à partir de ces noeuds. Avez-vous des suggestions?

merci

pour ajouter un graphe tu as :

- Tableau ou array d'adjacence (rapide, prend plus d'espace sommet²)
En colonne, tu met le sommet de fin d’arête, en ligne, le sommet de début.
Et sur la cellule, 2 possibilités :
- 0 si n'existe pas 1 si existe
- 0 si n'existe pas n° du sommet si existe

- Liste des successeur -ou prédécesseurs- (moins rapide, prend moins d'espace sommet + arrête)
A chaque sommet, tu associe soit ses successeur soit ses prédécesseurs.

on est parti sur les listes de prédécesseurs et successeurs, merci. Je vous ferai part de l'avancement.

Pour les listes de successeur ou de prédécesseur, c'est soit l'un soit l'autre mais pas les deux (ce serait une redondance de l'information).

Je re-précise car j'ai l'impression que tu vas faire les deux listes^^