Кратчайший путь для каждого узла в коллекции / json Neo4j apoc - PullRequest
Новая
       8

Кратчайший путь для каждого узла в коллекции / json Neo4j apoc

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

Краткое описание задачи: у меня есть документ json, состоящий из набора узлов источника / источника, для каждого из которых мне нужно найти 1-й, 2-й и 3-й кратчайший путь к набору целевых узлов.Ввод json выглядит следующим образом: 

{
    "origin":[
        {"label":"Alcohol drinks",
        "tag":[],
        "type":"string",
        "xpath":[]
        },

        {"label":"Wine",
        "tag":["red","white"],
        "type":"string",
        "xpath":["Alcohol drinks"]
        },

        {"label":"Port wine",
        "tag":["Portugal","sweet","strong"],
        "type":"string",
        "xpath":["Alcohol drinks","Wine"]
        },

        {"label":"Sandeman Cask 33",
        "tag":["red","expensive"],
        "type":"string",
        "xpath":["Alcohol drinks","Wine","Port wine"]
        }
    ],

    "target":[
        {"label":"Drinks",
        "tag":[],
        "type":"string",
        "xpath":[]
        },

        {"label":"Tea",
        "tag":["black", "green"],
        "type":"string",
        "xpath":["Drinks"]
        },

        {"label":"Carbonated water",
        "tag":[],
        "type":"string",
        "xpath":["Drinks","Tea"]
        },

        {
        "label":"Pepsi",
        "tag":["sweet","cheap"],
        "type":"string",
        "xpath":["Drinks","Tea","Carbonated water"]
        }
    ]
}

Узлы уже вставлены в БД и построены соответствующие взаимосвязи.Узлы подключены, поэтому можно построить хотя бы один путь от источника к цели.

Чтобы найти кратчайший путь, я использую следующий запрос Cypher: 

    CALL apoc.load.json("file:///D:/project/neo_proj/input.json") YIELD value 
UNWIND value.origin AS orig UNWIND value.target AS tar 
MATCH(origin:concept{name:orig.label}) 
MATCH(target:concept{name:tar.label}), 
path = shortestPath((origin)-[*1..3]-(target)) RETURN path ORDER BY length(path) ASC LIMIT 4

Этот запрос отображает все исходные узлы на все целевые узлы.Но мне нужно что-то вроде: 

   CALL apoc.load.json("file:///D:/project/neo_proj/input.json") YIELD value
UNWIND value.origin AS orig UNWIND value.target AS tar 
MATCH(origin:concept{name:orig.label}) MATCH(target:concept{name:tar.label}) 
FOREACH (x IN orig.label 
| MERGE(origin:concept{name:orig.label}) 
MERGE(target:concept{name:tar.label}) 
path = shortestPath((origin)-[*1..3]-(target))) RETURN path ORDER BY length(path) ASC LIMIT 3

Этот запрос не работает, но идея в том, чтобы иметь возможность использовать цикл foreach, взять метку первого источника и попытаться найти 1-й, 2-й, 3-й кратчайшиепуть к одной из целей, затем 2-й источник, 3-й источник и т. д. Я был бы признателен, если бы вы могли указать мне, как я могу использовать цикл foreach в связи с правильным поиском краткого пути.Заранее спасибо!

1 Ответ

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

Вы не можете использовать FOREACH таким образом.

Вероятно, вам лучше всего использовать процедуры расширения APOC, они могут использовать расширение bfs для кратчайших путей и могут быть ограничены в количестверезультатов на вызов (и вызов будет выполняться для каждой пары строк исходного и целевого), поэтому при правильной процедуре (с использованием spanningTree () здесь, чтобы гарантировать, что мы посетим каждый узел ровно один раз и вернем пути в конце), вы получитеполучить до 3 кратчайших путей на комбинацию источник / цель.

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

CALL apoc.load.json("file:///D:/project/neo_proj/input.json") YIELD value 
UNWIND value.origin AS orig 
MATCH(origin:concept{name:orig.label}) 
WITH value, collect(origin) as origins
UNWIND value.target AS tar 
MATCH(target:concept{name:tar.label})
UNWIND origins as origin
WITH origin, tar
CALL apoc.path.spanningTree(origin, {terminatorNodes:[tar], maxLevel:3, limit:3}) YIELD path
RETURN origin, tar, length(path) as pathLength, path
...