Ограничения отношений на взвешенном кратчайшем пути в neo4j-шифре - PullRequest
Новая
       66

Ограничения отношений на взвешенном кратчайшем пути в neo4j-шифре

0 голосов
/ 18 февраля 2020

Я экспериментирую с neo4j. У меня есть такой график. enter image description here

Запрос на создание приведенного выше графика: 

merge (:node{name : '1'});
merge (:node{name : '2'});
merge (:node{name : '3'});
merge (:node{name : '4'});
merge (:node{name : '5'});
merge (:node{name : '6'});
merge (:node{name : '7'});
merge (:node{name : '8'});

match (n1:node{name : '1'}), (n2:node{name : '2'}) merge (n1) -[:edge{cost : 100, Property1:'P1', Property2: 'P2'}]-> (n2)
match (n1:node{name : '2'}), (n2:node{name : '3'}) merge (n1) -[:edge{cost : 100, Property1:'P1', Property2: 'P2'}]-> (n2)
match (n1:node{name : '3'}), (n2:node{name : '4'}) merge (n1) -[:edge{cost : 200, Property1:'P1', Property2: 'P2'}]-> (n2)
match (n1:node{name : '1'}), (n2:node{name : '5'}) merge (n1) -[:edge{cost : 40, Property1:'P1'}]-> (n2)
match (n1:node{name : '5'}), (n2:node{name : '6'}) merge (n1) -[:edge{cost : 50, Property1:'P1'}]-> (n2)
match (n1:node{name : '6'}), (n2:node{name : '4'}) merge (n1) -[:edge{cost : 60, Property1:'P1'}]-> (n2)
match (n1:node{name : '1'}), (n2:node{name : '7'}) merge (n1) -[:edge{cost : 60, Property2: 'P2'}]-> (n2)
match (n1:node{name : '7'}), (n2:node{name : '8'}) merge (n1) -[:edge{cost : 60, Property2: 'P2'}]-> (n2)
match (n1:node{name : '6'}), (n2:node{name : '8'}) merge (n1) -[:edge{cost : 20, Property1:'P1'}]-> (n2)
match (n1:node{name : '8'}), (n2:node{name : '4'}) merge (n1) -[:edge{cost : 20, Property2: 'P2'}]-> (n2)

Я хочу получить ответ на следующие запросы.

  1. Кратчайший путь от 1 до 4, где свойство отношения: Property1 = 'P1' и свойство отношения: Property2 = 'P2' (Стоимость: 400, 1 -> 2 -> 3 -> 4)

  2. Кратчайший путь от 1 до 4, где свойство отношения: Property1 = 'P1' (Стоимость: 150, 1 -> 5 -> 6 -> 4). Здесь путь (1 -> 2 -> 3 -> 4) также действителен, но поскольку его стоимость велика, это не ответ.

  3. Кратчайший путь от 1 до 4, где свойство отношения: Property2 = 'P2' (Стоимость: 140, 1 -> 7 -> 8 -> 4). Опять же, здесь путь (1 -> 2 -> 3 -> 4) также действителен, но поскольку его стоимость велика, это не ответ.

  4. Кратчайший путь от 1 до 4, где свойство отношения: Property1 = 'P1' или свойство отношения: Property2 = 'P2' (Стоимость: 130, 1 -> 5 -> 6 -> 8 -> 4). Здесь любой путь действителен, но указанный выше путь является оптимальным.

  5. Кратчайший путь от 1 до 4, где свойство отношения: Property1! = 'P1'. (Стоимость: 140, 1 -> 7 -> 8 -> 4).

Здесь Property1 может быть чем угодно, а Property2 также может быть чем угодно (необязательно «P1» и «P2» соответственно.). Во всех случаях, если существует ребро, у которого свойство отношения Property1 = 'P3', то это ребро должно рассматриваться для оптимального пути.

Предположим, что если я хочу фильтровать по условию узла (например, узел, имеющий свойство = 'P5') вместе с условием отношения, это можно сделать?

Использую язык запросов шифрования.

Хороший поиск по целому rnet дает только ограничения на невзвешенный граф ( Cypher: Кратчайший путь с ограничением )

1 Ответ

1 голос
/ 20 февраля 2020

Попробуйте библиотеку алгоритмов графа. https://neo4j.com/docs/graph-algorithms/current/labs-algorithms/shortest-path/

//1.
MATCH (start:node {name: '1'}), (end:node {name: '4'})
CALL algo.shortestPath.stream(start, end, 'cost', {
  nodeQuery:'MATCH (n:node) RETURN id(n) as id',
  relationshipQuery:'MATCH (n:node)-[r:edge]->(m:node) WHERE r.Property1="P1" and r.Property2="P2" RETURN id(n) AS source, id(m) AS target, r.cost AS weight',
    graph: 'cypher', duplicateRelationships: 'min'})
YIELD nodeId, cost
RETURN algo.asNode(nodeId).name AS name, cost;

//2.
MATCH (start:node {name: '1'}), (end:node {name: '4'})
CALL algo.shortestPath.stream(start, end, 'cost', {
  nodeQuery:'MATCH (n:node) RETURN id(n) as id',
  relationshipQuery:'MATCH (n:node)-[r:edge]->(m:node) WHERE r.Property1="P1" RETURN id(n) AS source, id(m) AS target, r.cost AS weight',
    graph: 'cypher', duplicateRelationships: 'min'})
YIELD nodeId, cost
RETURN algo.asNode(nodeId).name AS name, cost;

//3.
MATCH (start:node {name: '1'}), (end:node {name: '4'})
CALL algo.shortestPath.stream(start, end, 'cost', {
  nodeQuery:'MATCH (n:node) RETURN id(n) as id',
  relationshipQuery:'MATCH (n:node)-[r:edge]->(m:node) WHERE r.Property2="P2" RETURN id(n) AS source, id(m) AS target, r.cost AS weight',
    graph: 'cypher', duplicateRelationships: 'min'})
YIELD nodeId, cost
RETURN algo.asNode(nodeId).name AS name, cost;

//4.
MATCH (start:node {name: '1'}), (end:node {name: '4'})
CALL algo.shortestPath.stream(start, end, 'cost', {
  nodeQuery:'MATCH (n:node) RETURN id(n) as id',
  relationshipQuery:'MATCH (n:node)-[r:edge]->(m:node) WHERE r.Property1="P1" or r.Property2 = "P2" RETURN id(n) AS source, id(m) AS target, r.cost AS weight',
    graph: 'cypher', duplicateRelationships: 'min'})
YIELD nodeId, cost
RETURN algo.asNode(nodeId).name AS name, cost;

//5.
MATCH (start:node {name: '1'}), (end:node {name: '4'})
CALL algo.shortestPath.stream(start, end, 'cost', {
  nodeQuery:'MATCH (n:node) RETURN id(n) as id',
  relationshipQuery:'MATCH (n:node)-[r:edge]->(m:node) WHERE  coalesce(r.Property1, "P2")<>"P1" RETURN id(n) AS source, id(m) AS target, r.cost AS weight',
    graph: 'cypher', duplicateRelationships: 'min'})
YIELD nodeId, cost
RETURN algo.asNode(nodeId).name AS name, cost;
...