CODEWITHSUNDEEP
pythonnetworkxdirected-graphancestorcyclic
H_H
H_H

Reputation: 17

How to get a predecessors/ancestor list of a node from cyclic directed graph in python?

I have a cyclic-directed graph/network which is obtained by the following dataframe:

import pandas as pd
import networkx as nx
df = pd.DataFrame({ 'from':['A', 'B', 'C','K','J','K','A'], 'to':['C', 'D','D','A','A','J','K']})
network = nx.from_pandas_edgelist(df,source='from',target='to', edge_attr=None, create_using=nx.DiGraph())

I would like to get the predecessor list of a given node and for acyclic cases I obtained it by the following:

def get_predecessors_all(graph, nodes):

    """
    Recursively get all the predecessors of a node or a list of nodes
    :param graph: graph to be transversed
    :param nodes: a single node or a list of nodes for which the list of predecessors is required
    :return: list of predecessor nodes
    """
    
    if not isinstance(nodes, list):
        nodes = [nodes]
    for node in nodes:
        node_predecessors = [graph.predecessors(node)]
        #print(node)
    # get all the immediate predecessors
    node_predecessors = list(chain.from_iterable(node_predecessors))
    if not node_predecessors:   # if reached a root & no more predecessors, stop and return
        return node_predecessors
    else: 
    # otherwise, get the predecessors of the current list of nodes
        return node_predecessors + get_predecessors_all(graph, node_predecessors)
pred_list=get_predecessors_all(network, ['D'])

However, since my network is cyclic, get_predecessors_all gets into an infinite loop. How can I get my pred_list as ['B','C','A','K','J']? Thanks in advance.

Upvotes: 1

Views: 383

Answers (1)

Ben Grossmann
Ben Grossmann

Reputation: 4852

It looks like you're just looking for a list of all ancestors for the nodes in your input list. You should just be able to do the following. For a single node,

node = 'C'
result = list(nx.ancestors(network,node))

For a list of nodes,

nodes = ['B','K']
result = list(set().union(*[nx.ancestors(network,node) for node in nodes]))

Upvotes: 0

Related Questions