La manière la plus élégante de trouver les prédécesseurs de node avec networkX

Je suis en train de travailler sur un modèle graphique du projet avec python à l'aide de NetworkX. NetworkX offre simple et bonne fonctionnalité à l'aide de dictionnaires:

import networkx as nx
G = nx.DiGraph() # a directed graph
G.add_edge('a', 'b')
print G['a'] # prints {'b': {}}
print G['b'] # prints {}

Je veux utiliser les graphes orientés parce que je suis le codage des dépendances qui ont directions (dans l'exemple ci-dessus, j'ai la forme fermée pour 'b' condition 'a', et non pas l'inverse).

Pour un nœud donné, je veux trouver les prédécesseurs de ce nœud. Pour l'exemple ci-dessus, par('b') doit renvoyer ['a']. NetworkX n'ont qu'un successeur de la fonction, qui trouve les enfants de n'importe quel nœud. De toute évidence, en passant par tous les nœuds et trouver ceux qui ont " b " comme un enfant, va travailler, mais elle sera Ω(n) le nombre de nœuds (ce qui sera trop cher pour mon application).

Je ne peux pas imaginer que quelque chose de ce simple serait de gauche de ce paquet, mais ne peut pas trouver quoi que ce soit.

Un efficace option est de conserver une dirigée et non dirigée version du graphique, le tout non orienté, les bords sont mises en œuvre essentiellement par l'ajout de deux arêtes orientées, et il serait donc possible de prendre le sage différence entre les nœuds adjacents et les enfants (ce qui serait le prédécesseur).

Le problème est que je ne suis pas sûr de la plupart des pythonic manière à envelopper l'existant networkx Digraphe et le diagramme de classe pour accomplir cette tâche. Vraiment, je veux juste retrouver avec une classe PGraph qui se comporte exactement comme le networkx Digramme de classe, mais a une predecessors(node) la fonction en plus de la successors(node) fonction.

Devrait PGraph hériter de Digraphe et encapsuler Graphique (pour une utilisation dans le prédécesseurs fonction)? Alors, comment devrais-je la force de tous les nœuds et les arêtes pour être ajouté à la fois orienté et non orienté graphiques qu'il contient? Dois-je viens de ré-écrire les fonctions d'ajout et de suppression de nœuds et d'arêtes dans PGraph (de sorte qu'ils sont ajoutés et supprimés de l'dirigée et non dirigée version)? J'ai peur que si je rate quelque chose d'obscur, je vais avoir un mal de tête plus tard, ce qui peut ne pas impliquer la bonne conception.

Ou (et s'il vous plaît que ce soit True) est-il simplement un moyen facile d'obtenir un nœud prédécesseurs dans un networkx.Le digraphe et j'ai complètement raté?

Merci beaucoup pour votre aide.

---

EDIT:

Je pense que de ce fait le travail. PGraph hérite de Digraphe et encapsule un autre Digraphe (celui-ci est inversé). J'ai remplacé les méthodes pour ajouter & supprimer des nœuds & bords.

import networkx as nx
class PGraph(nx.DiGraph):
def __init__(self):
nx.DiGraph.__init__(self)
self.reversed_graph = nx.DiGraph()
def add_node(self, n, attr_dict=None, **attr):
nx.DiGraph.add_node(self, n, attr_dict, **attr)
self.reversed_graph.add_node(n, attr_dict, **attr)
def add_nodes_from(self, ns, attr_dict=None, **attr):
nx.DiGraph.add_nodes_from(self, ns, attr_dict, **attr)
self.reversed_graph.add_nodes_from(ns, attr_dict, **attr)
def add_edge(self, a, b, attr_dict=None, **attr):
nx.DiGraph.add_edge(self, a, b, attr_dict, **attr)
self.reversed_graph.add_edge(b, a, attr_dict, **attr)
def add_edges_from(self, es, attr_dict=None, **attr):
nx.DiGraph.add_edges_from(self, es, attr_dict, **attr)
self.reversed_graph.add_edges_from(es, attr_dict, **attr)
def remove_node(self, n):
nx.DiGraph.remove_node(self, n)
self.reversed_graph.remove_node(n)
def remove_nodes_from(self, ns):
nx.DiGraph.remove_nodes_from(self, ns)
self.reversed_graph.remove_nodes_from(ns)
def remove_edge(self, a, b):
nx.DiGraph.remove_edge(self, b, a)
self.reversed_graph.remove_edge(a, b)
def remove_edges_from(self, es):
nx.DiGraph.remove_edges_from(self, es)
self.reversed_graph.remove_edges_from([ (b,a) for a,b in es])
# the predecessors function I wanted
def predecessors(self, n):
return self.reversed_graph.successors(n)

Que pensez-vous de cette solution? Il peut doubler l'utilisation de la mémoire, mais je pense que c'est acceptable. Est-il trop compliqué? Est-ce une bonne conception?

source d'informationauteur user