Comment puis-je trouver tous les arcs/arêtes entrants d'un certain nœud dans ce graphique simple

Je lisais https://www.python.org/doc/essays/graphs/ sur la façon de mettre en œuvre des graphiques. La chose est, je suis un peu confus sur la façon de trouver tous les arcs entrants à un certain nœud de la manière la plus rapide possible. Je sais que le nœud C a des arcs provenant du nœud A, B, D, F dirigés vers lui. Le problème est: comment puis-je vérifier les nœuds A, B, D, F sans entrer dans chaque liste dans le dictionnaire de clés pour voir si elle contient C. Y at-il une meilleure façon de le faire ou un graphique et une méthode plus efficace? Quelqu'un peut-il me diriger dans la bonne direction, merci d'avance.Comment puis-je trouver tous les arcs/arêtes entrants d'un certain nœud dans ce graphique simple

Source

2016-05-13 DST

La bonne structure de données pour votre problème est une * matrice d'adjacence *, plutôt qu'une liste d'adjacence. Je crois que pour les graphes dirigés, cela s'appelle une «matrice d'incidence». Il est plus rapide de vérifier des arcs spécifiques, mais beaucoup moins d'espace, en particulier avec un graphe clairsemé. –

@machineyearning Connaissez-vous des sites qui enseignent la matrice d'adjacence pour python et son implémentation que vous pouvez partager? Ce sera très utile, merci d'avance. Quelle est la différence entre la matrice d'adjacence et la liste d'adjacence? – DST

Vous pouvez également améliorer vos performances en implémentant vos listes d'adjacence en tant que structures de données 'set'. Ensuite, vous pouvez vérifier l'appartenance à un ensemble comme [pointsFrom for (pointsFrom, pointsTo) dans graph.items() si target dans pointsTo] '. Cela vous donnerait des performances d'ordre n où n est le nombre de nœuds dans votre graphique. –

Vous pouvez obtenir quelque chose de similaire à une matrice de contiguïté en utilisant simplement set structures

graph = {'A': {'B', 'C'}, # If you're using python 2.7+ you can initalize a set like this 
     'B': {'C', 'D'}, 
     'C': {'D'}, 
     'D': {'C'}, 
     'E': set(['F']), # Set initialization pre-2.7 
     'F': set()}  # Empty set initialization, can't use {}

Ensuite, vous pouvez vérifier les noeuds incident à target comme:

[pointsFrom for (pointsFrom, pointsTo) in graph.items() if target in pointsTo]

Cela aura un temps de fonctionnement linéaire dans le nombre de nœuds dans votre graphique.

Source

2016-05-13 09:49:49

Pouvez-vous expliquer comment '[pointsFrom for (pointsFrom, pointsTo) dans graph.items() si la cible dans pointsTo]' travail? Je sais que les ensembles permettent de comparer l'élément à l'intérieur de l'ensemble, mais comment ce code fonctionne en termes simples, merci d'avance. – DST

C'est une très bonne syntaxe pour être familier avec python, appelé [list comprehension] (https://docs.python.org/2/tutorial/datastructures.html#list-comprehensions). C'est essentiellement un raccourci pour déclarer une liste, itérer à travers quelque chose, filtrer les éléments et les transformer avant de les ajouter à votre liste déclarée. Vous pouvez le lire comme pour chaque paire (pointsFrom, pointsTo) dans graph.items(), si la cible est dans le set pointsTo, mettez les pointsFrom dans ma liste de résultats'. Ces expressions sont ** super utiles ** et peuvent être utilisées pour créer des listes, des dictionnaires ou n'importe quel type de structure itérable. –

Dans le cas général, ceci s'appelle un (Generator Expression) [https://www.python.org/dev/peps/pep-0289/] et produit un itérable qui ne prend pas la mémoire, en générant un élément à un le temps et le «céder» à une fonction qui consomme un itérable. Par exemple, le placer dans un constructeur 'list' vous donne une' list', même chose avec un constructeur 'dict' ou' set'. Étudiez-les et pratiquez-les en les utilisant, cela aidera à garder votre code propre, très efficace et idiomatique. (edit: je ne sais pas pourquoi le lien markdown ne fonctionne pas ci-dessus) –

Comment puis-je trouver tous les arcs/arêtes entrants d'un certain nœud dans ce graphique simple

Répondre

Questions connexes