Как эффективно найти самые короткие и самые длинные пути между типами узлов в dgraph? ⇐ Python

[Anonymous]

Я пытаюсь найти самый короткий и самый длинный путь между двумя типами узлов по всему графику в dgraph , аналогично тому, как это делается с использованием apoc in neo4j . />

Код: Выделить всё

MATCH (start: `ntype1`)
CALL apoc.path.expandConfig(start, {
labelFilter: '>ntype2',
minLevel: 1,
uniqueness: 'NODE_GLOBAL'
})
YIELD path
RETURN min(length(path)) as min, max(length(path)) as max
< /code>
Это эффективно возвращает самые короткие и длинные длины пути между любыми узлами типа ntype1 < /code> к ntype2 < /code> в одном и типы целевых узлов, а затем зацикливаться на комбинациях для запуска нескольких самых коротких 

запросов:

Код: Выделить всё

combined_query = f"""
{{
sources(func: type({ntype1})) {{ uid  RELATED_TO{{uid}} ~RELATED_TO{{uid}} }}
targets(func: type({ntype2})) {{ uid  RELATED_TO{{uid}} ~RELATED_TO{{uid}} }}
}}
"""
result = dgraphManager.query(combined_query)

source_uids = [x['uid'] for x in result['sources'] if 'RELATED_TO' in x or '~RELATED_TO' in x]
target_uids = [x['uid'] for x in result['targets'] if 'RELATED_TO' in x or '~RELATED_TO' in x]

uid_list = [{"from": s, "to": t} for s in source_uids for t in target_uids]

query_parts = []
result_parts = []
for i, item in enumerate(uid_list, 1):
query_parts.append(f"""
var(func: uid({item['from']})) {{
start{i} as uid
}}
var(func: uid({item['to']})) {{
end{i} as uid
}}
path{i} as shortest(from: uid(start{i}), to: uid(end{i})) {{ RELATED_TO ~RELATED_TO }}
""")
result_parts.append(f"result{i}(func: uid(path{i})) {{ uid }}")

final_query = "{\n" + "\n".join(query_parts) + "\n" + "\n".join(result_parts) + "\n}"
data = dgraphManager.query(final_query)

path_lengths = [len(val) for key, val in data.items() if val]
< /code>
 Проблема: < /h3>
Этот подход работает, но он очень неэффективен при обработке многочисленных узлов. Например, если ntype1 

имеет 100 узлов, а ntype2 имеет 50 узлов, это приводит к выполнению 5000 запросов - просто для определения длины пути между двумя типами. Sometimes, it causes errors related to query timeout.

Question:
Is there a more efficient way in Dgraph to compute:

• The shortest path between any node of type A to Любой узел типа B
• самый длинный такой путь

в идеале, как Apoc работает в Neo4j, с одним запросом.
Любое персонажи или оптимизации будут высоко ценится!>

Подробнее здесь: https://stackoverflow.com/questions/797 ... -in-dgraph