Virtual subgraph by attributes of nodes

Neo4j Graph Platform Procedures & APOC
1

Hello together,
i have a small graph like the following. A network of objects(nodes) with weight and forces as (relations black edges) nodes(objects) might have alternatives these are represented by a "alternative" relation (blue edges).

image
image1253×933 44.7 KB

how can I query the subgraph containing the N4_ node with the maximum/minimum/... weight?

the resulting graph should look like the following:
(the resulting graph could be a virtual graph)

image
image971×534 21.9 KB

I hope my idea is clear enough.

Regards
Thomas

an alternative base model could be the model below with different "Alternatives" Labeled Node N4_ . Not sure about if this makes things simpler

image
image1042×743 46 KB

2

You're looking for weigthed shortest path algorithms. APOC library does have Djikstra and A* algorithms aboard, see https://neo4j.com/labs/apoc/4.1/overview/apoc.algo/apoc.algo.dijkstra/. You need to first lookup start and end node via a normal match and feed them into the procedure call.

The graph data science library does have these algorithms as well (plus many more), see Path finding - Neo4j Graph Data Science.

3

Hi Stefan,
first of all, thank you very much for you reply. If I understand right the Dijkstra,A* are shortest path algorithms. They are aggregate based, this is not what i look for.

How would you filter
a-b-c(w=1)-d
a-b-c'(w=3)-d
a-b-c''(w=2)-d
a-b-e(w=2)-d
a-b-e'(w=4)-d

to return
a-b-c'-d
a-b-e'-d

in the above example if weight of N2=30 and weight of N7=1 Shortest Path (N1-N5) would be N1-N2-N5 since 30>11+1 , 30>10+1 ,30>8+1

am i right or do i missunderstand / miss anything?

regards
Thomas

4

my idea is kind of get

  1. all paths starting from Node a as treepaths
  2. extract the nodes of treepath nodes(treepaths)
  3. cycle trough each alternative chain c-c'-c'' retain the maximum/minimum node by weight in a filtertednodes collection
  4. cycle trough each path and construct only the paths that have all nodes in the filterednodes collection

as you can see this approach is different

5

Assuming:

  • All nodes have the label :Node
  • N4_ nodes have the label :Option
  • "weight" is a property on :Option.weight
  • "forces" are relationships with the label :FORCE

Part of the trouble in helping you define a solution, is that your diagram is a bit unclear. Where are the weights? How do you really want to query this graph (via :ALTERNATIVE relations)?

MATCH (n:Option)
WITH n ORDER BY n.weight DESC LIMIT 1
MATCH p=(n)-[]-(a:Node)
MATCH p2=(a)-[]-(:Node)-[]-(:Node)
RETURN p, p2

Source Data:

CREATE (n1:Node {name:"N1"}), (n2:Node {name:"N2"}), (n3:Node {name:"N3"}), (n5:Node {name:"N5"}), (n6:Node {name:"N6"}), (n7:Node {name:"N7"}), 
(o4A:Node:Option {name:"N4a", weight:10}), (o4B:Node:Option {name:"N4b", weight:8}), (o4C:Node:Option {name:"N4c", weight:11})
CREATE
(n1)-[:FORCE]->(n2),
(n1)-[:FORCE]->(n3),
(n2)-[:FORCE]->(n5),
(n6)-[:FORCE]->(n5),
(n7)-[:FORCE]->(n5),

(n3)-[:ALT]->(o4A),
(n3)-[:ALT]->(o4B),
(n3)-[:ALT]->(o4C),
(o4A)-[:FORCE]->(n2),
(o4A)-[:FORCE]->(n5),
(o4B)-[:FORCE]->(n6),
(o4C)-[:FORCE]->(n7)
6

Hi Tony,
all nodes are Bodies the weights are on the nodes. See picture and table of my database. Thats the first variant i asked for.

n.name n.weight r.type m.name m.weight
"N1" 1 force "N2" 1
"N1" 1 force "N3" 1
"N2" 1 force "N5" 1
"N3" 1 force "N4a" 10
"N4a" 10 alternative "N4b" 8
"N4a" 10 force "N5" 1
"N4b" 8 alternative "N4c" 11
"N4b" 8 force "N6" 1
"N4c" 11 force "N7" 1
"N6" 1 force "N5" 1
"N7" 1 force "N5" 1

grafik
grafik1122×991 39.7 KB

the graphs represents actualy an acyclic tree with paths
n1
n1-n2
n1-n2-n5
n1-n2-n3
n1-n2-n3-n4a
n1-n2-n3-n4a-n5
n1-n2-n3-n4a-n4b
n1-n2-n3-n4a-n4b-n6
n1-n2-n3-n4a-n4b-n6-n5
n1-n2-n3-n4a-n4b-n4c (alternative) n4b-n4c
n1-n2-n3-n4a-n4b-n4c-n7
n1-n2-n3-n4a-n4b-n4c-n7-n5

i want to get back
n1
n1-n2
n1-n2-n5
n1-n3
n1-n3-n4c
n1-n3-n4c-n7
n1-n3-n4c-n7-n5

remark this is the first model the relation n3-n4c does not exist persistantly

the second model replaces the n4a-n4b-n4c alternative chain by a star representation
with an option node N4_ and 3 Body nodes N4a,N4b,N4c

last remark for clarification. The example has only one node with alternatives, but other nodes could also have alternatives e.g N5_ N5a,N6b ...

I hope I got it nailed down now

create (n1:Body {name:"N1",weight:1}) ,
(n2:Body {name:"N2",weight:1}),
(n3:Body {name:"N3",weight:1}),
(n4:Body {name:"N4",weight:1}),
(n4a:Body {name:"N4a",weight:10}),
(n4b:Body {name:"N4b",weight:8}),
(n4c:Body {name:"N4c",weight:11}),
(n5:Body {name:"N5",weight:1}),
(n6:Body {name:"N6",weight:1}),
(n7:Body {name:"N7",weight:1}),
(n1)-[:force]->(n2),
(n2)-[:force]->(n5),
(n1)-[:force]->(n3),
(n3)-[:force]->(n4a),
(n4a)-[:alternative]->(n4b),
(n4b)-[:alternative]->(n4c),
(n4a)-[:force]->(n5),
(n4b)-[:force]->(n6),
(n6)-[:force]->(n5),
(n4c)-[:force]->(n7),
(n7)-[:force]->(n5) return n1,n2,n3,n4a,n4b,n4c,n5,n6,n7

And many thanks for your help
l!!!!

7

Hi,
I've changed the model back to a "star" like structure. You have a node N4. If there's alternatives behind, you create a N4a, N4b, N4c node for the alternatives. The alternative nodes do get a secondary label Alt:

create (n1:Body {name:"N1",weight:1}) ,
(n2:Body {name:"N2",weight:1}),
(n3:Body {name:"N3",weight:1}),
(n4:Body {name:"N4",weight:0}),
(n4a:Body:Alt {name:"N4a",weight:10}),
(n4b:Body:Alt {name:"N4b",weight:8}),
(n4c:Body:Alt {name:"N4c",weight:11}),
(n5:Body {name:"N5",weight:1}),
(n6:Body {name:"N6",weight:1}),
(n7:Body {name:"N7",weight:1}),
(n1)-[:force]->(n2),
(n2)-[:force]->(n5),
(n1)-[:force]->(n3),
(n3)-[:force]->(n4),
(n4)-[:alternative]->(n4a),
(n4)-[:alternative]->(n4b),
(n4)-[:alternative]->(n4c),
(n4a)-[:force]->(n5),
(n4b)-[:force]->(n6),
(n6)-[:force]->(n5),
(n4c)-[:force]->(n7),
(n7)-[:force]->(n5) return *

It's my understanding that when a traversal arrives at node N4, you only pick the largest out of [N4a, N4b, N4c] - that would be N4cand disregard the paths continuing inN4aandN4B`.

To implement this the java traversal API is the way to go:
You need a custom expander that returns only the one alternative relationship pointing to the end node with highest weight. If you know how to do it, implementing this is a task of less than 30 mins.

1 Like
8

Hi Stefan,
thank you for the link. I was not aware of the java traversal api. I'l try to get this done.
There is a deprecation warning on the page. Is this correct?
regards
Thomas

9

The deprecation warning is very unfortunate. It basically means that in the next major Neo4j version 5.x we will change it something having feature parity but with an different API. Since that replacement is not yet defined, you shouldn't care about the deprecation warning.

1 Like
10

Hi Stefan,
thank you very much for your help, i got it working.
Even without the extra node i was able to write a procedure capable to get near to the data i want.

I really appreciate your help.

regards
Thomas

1 Like
11

Thanks for the update. Great to hear you got things sorted.

12

Upate or lessons learned,

please corect me if i am wrong.

  • I am not sure, but the order adding expanders,evaluators,branchorder, uniqueness seems to be important.

  • do not confuse evaluator vs filtering. An evaluator can only decide on the current path. It is the current path that is included and or pruned. At evaluation time not all potential paths are avaiable. => Filtering on global subgraph node / relation properties must be done during traversal.

  • writing custom expanders might be helpful espacialy for performance reasons. In my case out of the box relation expanders where good enough.

  • let's hope that the replacement of the traversal api will be slik.

  • Working with the traversal api, i began to understand a bit more some behavioral aspekts of some apoc provedures.