python - Most elegant way to find node's predecessors with networkX -

python - Most elegant way to find node's predecessors with networkX -

i'm working on graphical model project python using networkx. networkx provides simple , functionality using dictionaries:

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

i want utilize directed graphs because coding dependencies have directions (in above illustration have closed form 'b' conditional on 'a', not other way around).

for given node, want find predecessors of node. above example, par('b') should homecoming ['a']. networkx have successor function, finds children of node. obviously, going through nodes , finding have 'b' kid work, Ω(n) in number of nodes (which expensive application).

i cannot imagine simple left out of well-made package, can't find anything.

one efficient alternative store directed , undirected version of graph; undirected edges implemented adding both directed edges, , possible take set-wise difference between adjacent nodes , children (which predecessor).

the problem i'm not sure of pythonic way wrap existing networkx digraph , graph class accomplish this. want end class pgraph behaves networkx digraph class has predecessors(node) function in add-on successors(node) function.

should pgraph inherit digraph , encapsulate graph (for utilize in predecessors function)? how should forcefulness nodes , edges added both directed , undirected graphs contains? should reimplement functions adding , removing nodes , edges in pgraph (so added , removed both directed , undirected version)? worry if miss obscure i'll in headache later, may not imply design.

or (and please allow true) there easy way node's predecessors in networkx.digraph , i've missed it?

thanks lot help.

edit:

i think job. pgraph inherits digraph , encapsulates digraph (this 1 reversed). i've overridden methods add together & remove nodes & edges.

import networkx 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) a,b in es]) # predecessors function wanted def predecessors(self, n): homecoming self.reversed_graph.successors(n)

what think solution? might double memory usage, think that's acceptable. complicated? design?

there predecessor (and predecessor_iter) method: http://networkx.lanl.gov/reference/generated/networkx.digraph.predecessors.html#networkx.digraph.predecessors

also there nil stopping accessing info construction straight g.pred

in [1]: import networkx nx in [2]: g = nx.digraph() # 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': {}}

python networkx parents