CODEWITHSUNDEEP
pythonpython-3.xnetworkx
Greg
Greg

Reputation: 8915

How to analyse and identify directed graph relationships (between nodes) in Python

I want to use Python to solve a graph theory problem (I am a complete novice to graph theory).

The data is in the following format:

edges = [('Child1', 'Parent1'), ('Child2', 'Parent2'), ('Child3', 'Parent1'), 
     ('Child4', 'Parent3'), ('Child2', 'Parent1')]

The relationships I need to analyse include finding that:

What is the best way to find the above listed relationships using Python?

Upvotes: 0

Views: 682

Answers (2)

edo
edo

Reputation: 1869

Since you tagged networkx, here's a solution using that library.

In the code below I create a directional graph and then add the edges from your list. Important: the first node in an edge will be the source node and the second node will be the target node, i.e. the children will point to their parents.

To get the parents of a child I use out_edges and to get the children of a parent I use in_edges. Note that both functions return a list of edges.

import networkx as nx

edges = [('Child1', 'Parent1'), ('Child2', 'Parent2'), ('Child3', 'Parent1'), 
     ('Child4', 'Parent3'), ('Child2', 'Parent1')]

G = nx.DiGraph()
G.add_edges_from(edges)

print(G.out_edges('Child2'))  # parents of Child2
print(G.in_edges('Parent1'))  # children of Parent1

Output:

[('Child2', 'Parent2'), ('Child2', 'Parent1')]
[('Child2', 'Parent1'), ('Child1', 'Parent1'), ('Child3', 'Parent1')]

You can use list comprehension to get lists with individual children or parents.

temp = [edge[1] for edge in G.out_edges('Child2')]
print('Parents of Child2:', temp)

temp = [edge[0] for edge in G.in_edges('Parent1')]
print('Children of Parent1:', temp)

Output:

Parents of Child2: ['Parent2', 'Parent1']
Children of Parent1: ['Child2', 'Child1', 'Child3']

Upvotes: 2

falsetru
falsetru

Reputation: 368904

I would make a mapping between parents and children:

>>> edges = [
...     ('Child1', 'Parent1'), ('Child2', 'Parent2'), ('Child3', 'Parent1'), 
...     ('Child4', 'Parent3'), ('Child2', 'Parent1')
... ]

>>> from collections import defaultdict
>>> parents = defaultdict(list)  # Key: child, value: list of parents
>>> children = defaultdict(list)  # Key: parent, value: list of children
>>> for child, parent in edges:
...     parents[child].append(parent)
...     children[parent].append(child)
... 
>>> parents['Child2']  # Child2's parents are Parent1 and Parent2
['Parent2', 'Parent1']
>>> children['Parent1'] # Parent1 is a parent to Child1, Child2 and Child3.
['Child1', 'Child3', 'Child2']

Upvotes: 0

Related Questions