Find all paths from node without duplicated

Neo4j Graph Platform
,
1

Hello.

I have graph:

CREATE (a:Item {id: "1"}), (b:Item {id: "2"}), (c:Item {id: "3"})

MATCH (a:Item {id: "1"}), (b:Item {id: "2"})
CREATE (a)-[:a]->(b)

MATCH (a:Item {id: "1"}), (b:Item {id: "2"})
CREATE (b)-[:a]->(a)

MATCH (a:Item {id: "2"}), (b:Item {id: "3"})
CREATE (a)-[:b]->(b)

MATCH (a:Item {id: "2"}), (b:Item {id: "3"})
CREATE (b)-[:a]->(a)

I want to get all paths from given node and filter them by relationship. My cypher is:

MATCH paths = (from:Item {id: '1'}) - [relations*] -> (to:Item)
WHERE ALL(r IN relations WHERE type(r) IN ['a', 'b'])
AND ALL(r IN relations WHERE startNode(r) <> to AND endNode(r) <> from) 
AND (to:Item) - [:a|b] -> () 
WITH {end: to.id, components: [i in relationships(paths) | {id: endNode(i).id, rel_type: type(i)}]} AS result 
RETURN result

The result of this cypher is:

[
  {
    "components": [
      {
        "rel_type": "a",
        "id": "2"
      }
    ],
    "end": "2"
  }
  {
    "components": [
      {
        "rel_type": "a",
        "id": "2"
      },
      {
        "rel_type": "b",
        "id": "3"
      }
    ],
    "end": "3"
  }
]

How can I re-write my cypher to avoid first element in array. The correct output, that I want is:

{
  "components": [
    {
      "rel_type": "a",
      "id": "2"
    },
    {
      "rel_type": "b",
      "id": "3"
    }
  ],
  "end": "3"
}
2

I am assuming you don't want a path that is a segment of any other path. If so, the following query filters those segments out. It is the first approach I thought of that seemed straight forward. Not sure how it will scale for large number of long paths, because each path has to be compared against each other path.

MATCH paths = (from:Item {id: '1'}) - [*] -> (to:Item)
WHERE ALL(r IN relationships(paths) WHERE type(r) IN ['a', 'b'])
AND ALL(r IN relationships(paths) WHERE startNode(r) <> to AND endNode(r) <> from) 
AND (to:Item) - [:a|b] -> () 
WITH {end: to.id, components: [i in relationships(paths) | {id: endNode(i).id, rel_type: type(i)}]} as result_map
WITH result_map, [i in result_map.components|i.id] as result_ids
WITH collect({map:result_map, ids:result_ids}) as results
UNWIND results as result
WITH result
WHERE none(y in results where y <> result and all(x in result.ids where x in y.ids)) 
RETURN result.map as result

Screen Shot 2023-02-19 at 11.45.43 PM
Screen Shot 2023-02-19 at 11.45.43 PM784×822 23.9 KB

1 Like
3

Working fine for me. Thanks you

1 Like
4

Can you please explain why none() and all() are nested into one-another? Would the filter be evaluated differently if it was none(...) AND all(...)?

5

It needs to be nested. What it does is to filter out each path that is a segment of another path in the result set that is generated from your query.

Following the third 'with' and 'unwind', each row consists of one result and the result_map collection. The 'where' clause is evaluated for each result, to determine if it should be passed through. The outer 'none' predicate loops through each of the results to make sure 'none' of them meet the inner predicate, which is to test if the current results is a segment of any of the other results. This is determined by the inner 'all' predicate, which tests that the list of 'ids' for the current result being tested is not entirely contained in the list of 'ids' from the result of the current iteration of the outer 'none' predicate.

In summary, for a given 'result', we are looping through all the results to ensure 'none' of them contain 'all' of the 'ids' of the current result being tested.

1 Like