8
votes

Trouver le compte accumulateur pour tous les sommets d'un dag

J'essaie de trouver un algorithme rapide avec des exigences d'espace modestes pour résoudre le problème suivant.

Pour chaque sommet d'un Dag, trouvez la somme de son degré et de son degré dans la fermeture transitive de la DAG .
donné ce DAG:

Je m'attends au résultat suivant: xxx
Il me semble que cela devrait être possible sans construire la fermeture transitive. Je n'ai pas pu trouver quoi que ce soit sur le net décrit exactement ce problème. J'ai des idées sur la façon de faire cela, mais je voulais voir ce que la foule pourrait venir avec.

algorithm directed-acyclic-graphs graph-theory

5 commentaires

En tant que sommet 7, dans la fermeture transitive, a du degré de degré et de degré 5, comment obtenez-vous ce "6" "Compte accessibles"? De même pour Vertex 5 (comment obtenez-vous 4 au lieu de 3), tandis que pour le sommet 3, le 3 que vous voulez semble tout à fait juste (identique au sommet 5). Veuillez expliquer en détail comment ces chiffres étranges sont censés être obtenus (quel entier et à quels nœuds et à quels nœuds; quels sont les nœuds et à quels nœuds), avant de pouvoir obtenir de plus en plus profondément dans vos fonctions.

Vertex 7 est une faute de frappe, la conduite ... Vertex 5 a (11, 2, 9, 10) sous forme de successeurs de la TC. Vertex 3 a (8, 9, 10) comme successeurs de la TC.

J'ai ajouté l'ensemble Vertex accessible pour chaque Source Vertex à l'exemple.

Pourriez-vous clarifier sur vos besoins: à savoir pourquoi avez-vous besoin de la petite condition d'espace? Votre Dag est-il représenté implicitement? Ou est-ce rare mais avec une fermeture transitive dense? (Parce que, autrement, vous feriez de toute façon stocker le DAG et l'algorithme de fermeture transitive standard ne changerait pas l'espace asymptotique)

Ma mise en œuvre actuelle construit en effet la fermeture transitive complète et j'essaie de l'améliorer à la fois dans le temps et dans l'espace. Je ne fais pas mal pour la mémoire, mais j'aimerais utiliser moins. De nombreuses instances de mon Dag seront relativement rares mais avec une fermeture transitive dense. Le processus qui produit les données Les modèles DAG disposent d'un biais vers des Dags hautement chaînés et connectés.

5 Réponses :

0
votes

omg c'est faux! Désolé!
Je vais laisser cela jusqu'à une bonne alternative disponible. Cw-ed alors n'hésitez pas à discuter et à étendre à ce sujet si possible. P>
Utilisez la programmation dynamique. P>
for each vertex V count[V] = UNKNOWN for each vertex V getCount(V) function getCount(V) if count[V] == UNKNOWN count[V] = 0 for each edge (V, V2) count[V] += getCount(V2) + 1 return count[V]

6 commentaires

Cela compte-t-il aussi la confidentialité? Par exemple, le DAG A -> B -> C doit donner le résultat 2 pour tous les 3 nœuds.
Abordé cela. S'il vous plaît vérifier (je monte cela comme je vais). Je ne suis pas sûr que votre estimation de la complexité est exacte. L'appel récursif de GetCount () n'implique-t-il pas que les sommets peuvent être visités plus d'une fois s'ils disposent d'un diplôme> 1. Abordé cela. S'il vous plaît vérifier (je monte cela comme je vais). Ahh oui, j'ai négligé la mémoisation. Cet algorithme est incorrect. Sur un graphique diamant A -> B, A -> C, B -> D, C -> D Retourne getcount (a) = 4, alors que la réponse correcte est 3.
1 votes Pour chaque nœud, utilisez BFS ou DFS pour trouver la défavorabilité. Faites-le à nouveau pour la direction inversée pour trouver l'inaccessibilité. Complexité du temps: O (mn + N ^{2 ), complexité de l'espace: O (m + n).} 0 commentaires 0 votes Je suppose que vous avez une liste de tous les sommets, et que chaque sommet a un ID et une liste de sommets que vous pouvez contacter directement à partir de celui-ci. Vous pouvez ensuite ajouter un autre champ (ou si vous le représentez) qui détiennent les sommets que vous pouvez également atteindre indirectement. Je ferais cela dans une première recherche de profondeur récursive, en indiquant les résultats dans le domaine des nœuds atteints respectifs. En tant que structure de données pour cela, vous utiliseriez peut-être une sorte d'arbre qui permet une suppression efficace des doublons. La mise en accessibilité peut être effectuée séparément en ajoutant les liaisons inverse, mais elle peut également être effectuée dans le même passage que la sortie hors accès, en accumulant les nœuds actuellement externes et en les ajoutant aux champs correspondants de la atteint les nœuds. 3 commentaires C'était ma première mise en œuvre. Cette technique fonctionne, mais elle construit la fermeture transitive complète du DAG sous-jacent. Eh bien, vous avez besoin d'un moyen d'éliminer les doublons. Vrai, mais il peut ne pas être nécessaire de stocker la fermeture complète à la fois. Je pense qu'il devrait être possible d'obtenir une réponse pour certains sommets avant que toute la fermeture ne soit construite et jetez la portée de la portée des sommets terminés avant la compéquence de l'ensemble de la travertielle. 2 votes Pour une réponse exacte, je pense que ça va être difficile de battre l'algorithme de Kennytm. Si vous êtes prêt à vous contenter d'une approximation, la méthode de comptage de réservoir ( http://www.guardian.co.uk/world/2006/jul/20/secondworldwar.tvandradio ) peut aider. Attribuez chaque vertex un nombre aléatoire dans la plage [0, 1). Utilisez un programme dynamique de temps linéaire, tels que les polygénelubrançants pour calculer chaque vertex V le nombre minimal MINREHCH (V) accessible à partir de v. Évitez ensuite le nombre de sommets accessibles de V comme 1 / minreach (V) - 1. Pour une meilleure précision, répéter plusieurs fois et prenez une médiane de moyens à chaque sommet. 2 commentaires Bien que je cherche une réponse exacte, j'aime votre message. Merci pour l'article, c'était très intéressant et la méthode de comptage des réservoirs est bonne à être consciente. +1 pour penser en dehors de la boîte. @ user287792 Je ne pense pas que cela fonctionne. Prenez l'exemple d'un sommet. Si x $ x $ est distribué aléatoirement dans [0,1], puis 1 / x $ doit avoir une valeur attendue non définie, même si votre méthode suppose qu'il aurait dû attendre la valeur de deux. 1 votes J'ai construit une solution viable à cette question. Je base ma solution sur une modification du Tri topologique algorithme. L'algorithme ci-dessous ne calcule que le titre dans la fermeture transitive. Le out-degré peut être calculé de la même manière avec des bords inversés et les deux chefs de comptabilisation de chaque sommet résumé pour déterminer le dernier dénombrement de "nombre d'accessibilité". xxx supposant que les opérations définies sont O ( 1), cet algorithme fonctionne dans O (| V | + | e |). Il est toutefois plus probable que l'opération de l'Union définie prédécesseurs [v2] .add (prédécesseurs [V]) le rend quelque peu pire. Les étapes supplémentaires requises par les syndicats définies dépend de la forme du DAG. Je crois que le pire des cas est O (| v | ^ 2 + | e |). Dans mes tests, cet algorithme a montré de meilleures performances que tout autre que j'ai essayé jusqu'à présent. En outre, en éliminant des ensembles prédécesseurs pour des sommets entièrement traités, cet algorithme utilisera généralement moins de mémoire que la plupart des alternatives. Il est toutefois vrai que la pire consommation de mémoire de la mémoire de l'algorithme ci-dessus correspond à celle de la construction de la fermeture transitive, mais qui ne sera pas vraie pour la plupart des DAG. 0 commentaires

Articles qui pourrait vous intéresser : Calculer la différence dans l'échelle d'évaluation alphabétique Complexité de Trouver tous les multiples de 3 et 5 entre 1 et 10 000 000 Ma vérification pour savoir si un graphique est un arbre binaire renvoie toujours faux Comment trouver le nombre d'itérations de l'algorithme de recherche binaire?