La plupart façon élégante de trouver ses prédécesseurs noeud avec NetworkX

Question

Je travaille sur un projet de modèle graphique avec Python en utilisant NetworkX . NetworkX fournit des fonctionnalités simples et bonnes en utilisant les 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 des graphiques dirigés parce que je suis le codage des dépendances qui ont des directions (dans l'exemple ci-dessus j'ai la forme fermée pour « b » la condition « a », et non l'inverse).

Pour un noeud donné, je veux trouver les prédécesseurs de ce nœud. Pour l'exemple ci-dessus, par ( 'b') devrait revenir [ 'a']. NetworkX fait une fonction successeur, qui trouve les enfants d'un nœud. De toute évidence, en passant par tous les nœuds et de trouver ceux qui ont « b » comme un enfant fonctionnera, mais il sera Ω (n) du nombre de nœuds (qui sera trop cher pour ma demande).

Je ne puis imaginer que quelque chose ce simple serait laissé sur ce paquet bien fait mais ne trouve rien.

Une option efficace consiste à stocker une scène et une version non dirigée du graphe; tous les bords non orientés sont essentiellement mises en oeuvre en ajoutant les deux bords dirigés, et il serait alors possible de prendre la différence de réglage judicieux entre les noeuds adjacents et les enfants (ce qui serait le prédécesseur).

Le problème est que je ne suis pas sûr de la façon la plus pythonique pour envelopper le NetworkX existant DIGRAMME et graphique de classe pour y parvenir. Vraiment, je veux juste finir avec une PGraph de classe qui se comporte exactement comme la classe NetworkX DIGRAMME mais a une fonction de predecessors(node) en plus de la fonction successors(node).

PGraph doit hériter de DIGRAMME et graphique encapsuler (pour une utilisation dans la fonction prédécesseurs)? Comment puis-je forcer tous les nœuds et les arêtes à ajouter aux deux graphes orientés et non orientés qu'il contient? Devrais-je réimplémenter les fonctions d'ajout et de suppression des noeuds et des arêtes dans PGraph (de sorte qu'ils sont ajoutés et supprimés à la fois la version dirigée et non dirigée)? Je crains que, si je manque quelque chose obscure, je serai pour un mal de tête plus tard, qui ne peut impliquer une bonne conception.

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

Merci beaucoup pour votre aide.

---

EDIT:

Je pense que cela fait le travail. PGraph hérite de DIGRAMME et encapsule un autre DIGRAMME (celui-ci inversé). J'ai surchargé les méthodes d'ajouter et de supprimer des nœuds et arêtes.

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 pourrait doubler l'utilisation de la mémoire, mais je pense que c'est acceptable. Est-il trop compliqué? Est-ce un bon design?

Answer 1

Il existe une méthode prédécesseur (et predecessor_iter): http://networkx.lanl.gov/reference /generated/networkx.DiGraph.predecessors.html#networkx.DiGraph.predecessors

En outre il n'y a rien qui vous empêche d'accéder à la structure de données directement G.pred

 In [1]: import networkx as nx
 In [2]: G = nx.DiGraph() # a directed graph
 In [3]: G.add_edge('a', 'b')
 In [4]: G.predecessors('b')
 Out[4]: ['a']
 In [5]: G.pred['b']
 Out[5]: {'a': {}}

Answer 2

Une autre façon de mettre en œuvre ce qui peut être comme suit:

Création du graphique de base

import networkx as nx
import matplotlib.pyplot as plt

G = nx.DiGraph()
G.add_edges_from([('A', 'B'), ('A', 'C'), ('D', 'B'), ('E', 'C'), ('E','F'), ('B', 'H'), ('B', 'G'), ('B', 'F'), ('C', 'G'), ('Q', 'D')])

pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos, cmap=plt.get_cmap('jet'),node_size = 50)
nx.draw_networkx_edges(G, pos, edge_color='r', arrows=True)
nx.draw_networkx_labels(G, pos)
plt.show()

Trouver en aval Arêtes

print("Downstream Edges of 'B' (just example)-->")
print(list(nx.dfs_edges(G,'B')))

Trouver amont Arêtes

print("Upstream Edges of 'B' (just example)-->")
print(list(nx.edge_dfs(G,'B', orientation='reverse')))

Plus de détails dans cette blog

Answer 3

Un graphe est pas toujours un arbre, de sorte que la notion de « parent » fait souvent aucun sens. Par conséquent, je suppose que cela ne soit pas mis en œuvre.

Pour mettre en œuvre ce que vous avez besoin, hériter de DiGraph et de surcharge toutes les méthodes qui permettent d'ajouter des nœuds. Construire la structure de données d'arbre de cette information.

Answer 4

Si G est une instance de nx.DiGraph() et node est le nœud source dont les prédécesseurs vous recherchez, ce qui suit vous donne une liste de nœuds prédécesseur:

predecessors = [pred for pred in G.predecessors(node)]