pythonnetworkxdigraphs

networkx: identify instances where a node is both an ancestor and descendant of another node

I'm not sure if specific terminology exists for this, but I'm looking to identify paths in a directed network in which case the directionality goes both ways. I'm building a network with a bunch of provided data and by accident stumbled on some artifacts where nodes A and B are both parents/children of each other.

In looking to identify these, I stumbled on the term "self loop". This is what I want, just for paths longer than a single edge.

import networkx as nx
g = nx.DiGraph()
g.add_edges_from([(0, 1), (0, 2), (0, 3), (1, 3), (3, 0), (3, 3), (2, 0), (1, 2), (2, 1)])
nx.draw_networkx(g, arrows=True, with_labels=True, width=0.2, edge_color='#AAAAAA', arrowsize=20,
                     node_size=2)

enter image description here

networkx has a function to identify nodes with self loops, but I only get node 3 as a result.

list(nx.nodes_with_selfloops(g))
[3]

Only node 3 is identified, but in this case I'd be looking to identify that 1/2 and 0/1 have arrows going both ways. It's not a single edge self loop, but allows 2 > 0 > 1 > 2 and 1 > 3 > 0 > 2 > 1. I start and end at the same node, just with other nodes between.

Is there an efficient way to identify "what nodes that have bi-directional arrows to the same node"? I have not identified enough of these cases to know if the cause will always be a single double sided arrow or something like 2+ multi-edge paths that start/stop with the same node.

The real world data is like process flows, so there should not be cases where somehow A flows to B and B also flows into A, so these are the data inconsistencies I'm looking to quickly identify.

Solution

  • One easy way would be to compute a set intersection of the edges with their reversed counterpart (with reverse and &):

    g.edges & nx.reverse(g).edges

    Output:

    {(0, 2), (0, 3), (1, 2), (2, 0), (2, 1), (3, 0), (3, 3)}

    If you want a more compact version you could further combine the (a,b)/(b,a) pairs into a single (a,b) and (a,a) into (a,) with:

    set(tuple(frozenset(e)) for e in g.edges & nx.reverse(g).edges)

    Output:

    {(0, 2), (0, 3), (1, 2), (3,)}

    Graph:

    enter image description here