Как анализировать и идентифицировать связанные отношения графа (между узлами) в Python

Question

Я хочу использовать Python для решения проблемы теории графов (я полный новичок в теории графов).

данные в следующем формате:

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

Взаимосвязи мне нужно проанализировать, включают заключая, что:

• родители Child2 являются Parent1 и Parent2
• Parent1 является родителем ребенка1 , Child2 и Child3.

Каков наилучший способ найти приведенные выше отношения с помощью Python?

Answer 1

Поскольку вы помечено networkx, вот решение с помощью этой библиотеки.

В приведенном ниже коде я создаю диаграмму направленности, а затем добавляю ребра из вашего списка. Важно: первым узлом в ребрах будет исходный узел, а второй узел будет целевым узлом, то есть дети укажут на своих родителей.

Чтобы получить родителей ребенка, я использую out_edges, а для получения детей от родителей я использую in_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 

Выход:

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

Вы можете использовать список понимание, чтобы получить списки с отдельными детьми или родителями.

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) 

Выход:

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

Answer 2

Я хотел бы сделать отображение между родителями и детьми:

>>> 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']