Comment puis-je détecter circulaire de la logique ou de la récursivité dans un multi-niveaux de références et dépendances
J'ai un graphique de la multi-niveau avec des dépendances de ce genre, et j'ai besoin de détecter toute référence circulaire dans ce graphique.
A = B
B = C
C = [D, B]
D = [C, A]
Quelqu'un avez un problème de ce genre?
Toute solution???
Merci et désolé en anglais.
========= mise à jour ==========
J'ai eu une autre situation.
1
2 = 1
3 = 2
4 = [2, 3]
5 = 4
Dans ce cas, mon récursive code itérer deux fois dans le "4" de référence, mais cette référence n'est pas de générer une boucle infinie. Mon problème est de savoir quand la fonction itérer plusieurs fois une référence et n'est pas une boucle infinie et quand est une boucle infinie, à en informer l'utilisateur.
1 = 4
2 = 1
3 = 2
4 = [2, 3]
5 = 4
Ce cas est un peu différent à partir de la 2ème exemple. Cela génère une boucle infinie. comment puis-je savoir quand cas, de générer une boucle infinie ou pas?
- voir: stackoverflow.com/questions/546655/finding-all-cycles-in-graph
- pas du tout ce que l'OP (et moi) est à la recherche pour.
Vous devez vous connecter pour publier un commentaire.
Le tri topologique. La description sur Wikipédia est clair et fonctionne pour tous vos exemples.
Fondamentalement, vous commencez avec un nœud qui n'a pas de dépendances, le mettre dans une liste triée des nœuds, puis supprimer la dépendance à partir de chaque nœud. Pour vous le deuxième exemple, qui signifie que vous commencez avec 1. Une fois que vous supprimez toutes les dépendances sur 1, vous êtes de gauche avec les 2. Vous vous retrouvez en les triant 1,2,3,4,5 et de voir qu'il n'y a pas de cycle.
Pour votre troisième exemple, chaque nœud a un lien de dépendance, donc il n'y a nulle part où commencer. Un tel graphique doit contenir au moins un cycle.
De garder une liste de identifié de manière unique les nœuds. Essayez d' de la boucle à travers l'ensemble de l'arbre, mais de garder le contrôle de nœuds dans la liste jusqu'à ce que vous obtenez un nœud d'être désigné comme un enfant qui est déjà dans la liste unique - à partir de là (la poignée de la boucle ou simplement l'ignorer en fonction de vos besoins)