Le dredi sexy, supplanté par le dredi matheux. Voila un petit problème sur lequel je planche et pour lequel je ne refuserais pas un coup de main.
J’ai un graphe, représenté en mémoire par une matrice d’adjacence pondérée, i.e. une valeur non-zero dans la case (m,n) de la matrice indique une arête du noeud m vers le noeud n, avec une valeur entre 0 et 1.
Exemple:
Mon objectif: en supposant qu’il n’y a pas de cycles, trouver un algorithme pour ordonner les noeuds sous forme d’arbre dirigé et, du coup, établir une liste de précédence de calcul de chacun des noeuds.
Dans l’exemple trivial, l’ordre est [1, 2, 3].
Je suis intéressé par toute solution: bout de code, algorithme, librairie externe, litterature matheuse…
1er tiroir:
S’il y a des cycles (et il y en aura), possible de les isoler, et de les insérer dans la liste comme un noeud a calculer a part entiere ?
2eme tiroir:
Si je vous dis “temps réel” ? Le graphe pourra etre édité en temps réel par l’utilisateur. Imaginez des potards a la place des valeurs de la matrice, et vous avez l’idée. Donc, on doit pouvoir recalculer l’ordre rapidement, souvent et pour pas cher.
Toutes les bonnes idées sont acceptées!
EDIT: Le probleme en question s’appelle le Topological sorting. Question principale résolue, ce qui n’empeche pas de continuer a discuter du sujet. Il reste les histoires de cycle…