Как найти путь между 2 узлами на основе значения атрибута промежуточного узла, используя график networkx? - PullRequest
Новая
       4

Как найти путь между 2 узлами на основе значения атрибута промежуточного узла, используя график networkx?

0 голосов
/ 05 февраля 2019

Я могу искать по дереву и получать кратчайший путь между узлами, используя просто: 

nx.shortest_path(G, source=, target=)

Но как мне выбрать путь, проходящий через узел со значением определенного атрибута?

У меня есть простой граф с узлами 

G = nx.Graph()
for token in document:
    G.add_node(token.orth_, item = token.i, tag = token.tag_, dep = token.dep_)

и ребрами: 

for token in document:    
    for child in token.children:
        G.add_edge(token.orth_, child.orth_, pitem = token.i, citem = child.i,
                   ptag = token.tag_, pdep = token.dep_, ctag = child.tag_, cdep = child.dep_)

Могу ли я найти простое решение, потому что сейчас я пытаюсь построить сложную функцию.

РЕДАКТИРОВАТЬ

Идея состоит в том, чтобы иметь такую ​​функцию: (схематично) 

def getPathByNode(betw_word, betw_attr, src_word, src_attr, trg_word, trg_attr):
    nx.shortest_path(G, source=src, source_attr=src_attr, target=trg, target_attr=trg_attr, through=betw_word, through_attr=betw_attr)
    ....

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

source_attr = {'dep_': 'ROOT'}
target_attr = {'tag_': 'NN'}

through = "of" или through = "from" или through_attr = {'tag_': 'IN'}

и так далее.В настоящее время я пытаюсь построить рекурсию, начиная с середины (through='from') и ища соседей, но в той же ситуации - отсутствующие атрибуты.

for i in G.neighbors("from"):
    print(i)

я просто строка.

1 Ответ

0 голосов
/ 06 февраля 2019

Простым решением будет вычисление всех путей от источника к цели.Затем просто отфильтруйте все пути без узла, который имеет желаемое условие, и выберите кратчайший путь из этого набора путей.Предполагая, что у вас есть неориентированный и невзвешенный график, что-то вроде этого должно работать: 

import networkx as nx

# Generate a sample graph:
G = nx.barabasi_albert_graph(10, 3, seed=42)
print(G.edges())

def check_attribute(G, node):
    # Say the condition is node id is 3:
    return node == 3

valid_paths = []
for path in nx.all_simple_paths(G, source=0, target=7):
    cond = False
    for node in path:
        if check_attribute(G, node):
            cond = True
            valid_paths.append(path)
            break

lengths = [len(path) for path in valid_paths]
shortest_path = valid_paths[lengths.index(min(lengths))]
print('valid paths: {}'.format(valid_paths))
print('shortest_path: {}'.format(shortest_path))
...