Most elegant way to find node's predecessors with networkX

Question

I'm working on a graphical model project with python using NetworkX. NetworkX provides simple and good functionality using dictionaries:

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

I want to use directed graphs because I am coding dependencies that have directions (in the above example I have the closed form for 'b' conditional on 'a', not the other way around).

For a given node, I want to find the predecessors of that node. For the above example, par('b') should return ['a']. NetworkX does have a successor function, which finds the children of any node. Obviously, by going through all the nodes and finding those that have 'b' as a child will work, but it will be Ω(n) in the number of nodes (which will be too expensive for my application).

I cannot imagine that something this simple would be left out of this well-made package, but can't find anything.

One efficient option is to store a directed and an undirected version of the graph; all undirected edges are essentially implemented by adding both directed edges, and so it would be possible to take the set-wise difference between the adjacent nodes and the children (which would be the predecessor).

The trouble is I'm not sure of the most pythonic way to wrap the existing networkx DiGraph and Graph class to accomplish this. Really I just want to end up with a class PGraph that behaves exactly like the networkx DiGraph class but has a predecessors(node) function in addition to the successors(node) function.

Should PGraph inherit from DiGraph and encapsulate Graph (for use in the predecessors function)? How then should I force all nodes and edges to be added to both the directed and undirected graphs that it contains? Should I just reimplement the functions for adding and removing nodes and edges in PGraph (so that they are added and removed from both the directed and undirected version)? I worry that if I miss something obscure I'll be in for a headache later, which may not imply good design.

Or (and please let this be True) is there simply an easy way to get a node's predecessors in a networkx.DiGraph and I've completely missed it?

Thanks a lot for your help.

---

EDIT:

I think this does the job. PGraph inherits from DiGraph and encapsulates another DiGraph (this one reversed). I've overridden the methods to add & remove nodes & edges.

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)

What do you think about this solution? It might double the memory usage, but I think that's acceptable. Is it too complicated? Is this good design?

Garnettgarnette

Answer 1

There is a predecessor (and predecessor_iter) method: http://networkx.lanl.gov/reference/generated/networkx.DiGraph.predecessors.html#networkx.DiGraph.predecessors

Also there is nothing stopping you from accessing the data structure directly as 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': {}}

Nims

Thanks for posting this-- I found pred[...] not long ago. I didn't have them before and then installed networkx on a different computer. Maybe they weren't in the version I used to have? Or maybe I'd just made a typpppo the first time? – Garnettgarnette

I have not predecessors available in my networkx but I do have pred – Softwood

Answer 2

Another way to implement this can be as follows:

Creating the basic graph

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()

Finding Downstream Edges

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

Finding Upstream Edges

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

More details in this blog

Infrequent

Answer 3

A graph is not always a tree, so the notion of "parent" often makes no sense. Therefore, I assume that this is not implemented.

To implement what you need, inherit from DiGraph and overload all methods which allow to add nodes. Build the tree data structure from that information.

Inflationism

Ah, sorry about that. More formally, predecessor is a better description of what I want. I'm definitely working with general graphs, not just trees. I worry that I'll also need to overload methods for removing nodes, because I'll need to keep the same node set in the directed and the undirected graph. And then there are methods that add nodes en masse. Furthermore, I'm not sure where these are called "under the hood," so I worry I'll miss something important even if I am not calling it myself. – Garnettgarnette

I doubt that any methods in DiGraph will add or remove nodes unless you tell them to do so. That said, just look at the source of the class. This is Python after all. The code is probably simple enough to understand. Maybe all calls converge to 2-3 methods which you need to overload. – Inflationism

Thanks for your help-- I've posted the code corresponding to that solution. What do you think? I had to override 8 functions from DiGraph. After seeing it, do you think this is good design? – Garnettgarnette

@starghost: I like the solution. It's simple, obvious, compact. Don't worry about performance or memory until it becomes an issue. – Inflationism

Answer 4

If G is an instance of nx.DiGraph() and node is the source node whose predecessors you search, the following gives you a list of predecessor nodes:

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

Pulling

Nice. With + [node], this was a good one liner for an exception. – Pharisaic

Answer 5

In general, if you're trying to create a directed graph where the edge directions are reversed compared to an existing graph (what you did with your PGraph class), transposing the adjacency matrix should do the trick.

Specifically, in NetworkX, one can use the DiGraph.reverse method for this.

(If for some reason you're forced to use a very old version of NetworkX that didn't have predecessors or pred - reverse the graph and use successors.)

Kob