How to sort a subgraph by weakest link in weighted graph

Neo4j Graph Platform
,
1

I have a weighted graph and I'd like to know the most efficient way to return all the nodes connected to one node, sorted by the weakest link in the path it took to get to that node. (in my case the 'weights' would be signified by the name of the relationship type. But I could also have a 'weight' property on the relationships)

The only way I know how to do that is to make separate apoc.path.subgraphAll() queries with different relationships in the 'relationshipFilter' field and then programmatically subtracting the nodes from the query result with a stricter filter from the nodes from the query result with the less strict filter.

For example, here is a graph shown 4 different times to highlight what would be returned based on different queries.

The first example is what would be returned with a 'relationshipFilter' of 'STRONG' the next one with 'STRONG|MEDIUM', the third with 'STRONG|MEDIUM|WEAK'. And the last example represents what I want returned. Something like (where the numbers in the arrays would be objects that represent the nodes with those labels in the example graph):

{
  STRONG: [1, 2, 3],
  MEDIUM: [4, 5, 6, 7],
  WEAK: [8, 9, 10]
}

The return value wouldn't have to look exactly like that, but something similar enough, that wouldn't require making a bunch of separate queries and then iterating through the results would be nice.

[ps: I'm using the javascript driver]

2

I think I understand the requirements. Try this. It orders all the paths based on the weakest relationship type. You could convert it to work with a property too. I did not create test data to test it, but it runs. You can output whatever info you want since you have access to the path, so you have all the nodes and relationships along the path.

match(n:ROOT{id:0})
match p=(n)-[*]-(m)
with p, m, relationships(p) as rels
with p, m, 
any(r in rels where type(r) = 'STRONG') as strong,
any(r in rels where type(r) = 'MEDIUM') as medium,
any(r in rels where type(r) = 'WEAK') as weak
with p, m, case
	when weak then 0
	when medium and not weak then 1
	when not medium and not weak then 2
end as order
return p, m
order by order
3

wow thank you @glilienfield ! I haven't used some of those keywords, I never would have thought of that strategy. Now I just have to try to understand what it's doing!

4

@glilienfield I tweaked your suggestion to get it closer to what I was thinking of:

MATCH(n:Test {appId: 1})
MATCH p=(n)-[*]-(m)
WHERE NOT m.appId = 1
WITH m, relationships(p) AS rels
WITH m, 
any(r IN rels WHERE type(r) = 'MEDIUM') AS medium,
any(r IN rels WHERE type(r) = 'WEAK') AS weak
WITH m, CASE
  WHEN weak THEN "WEAK"
  WHEN medium AND NOT weak THEN "MEDIUM"
  WHEN NOT medium AND NOT weak THEN "STRONG"
END AS weight
RETURN collect(m.appId), weight

Here are some of the paths it returns:

1-3

1-3-2

1-4

1-3-2-1-4

The last path is unnecessary. If I can get from 1-4 directly, I don't care if I can also get there by adding a bunch of other hops and coming back to 1 to go directly to 4.

How do I exclude paths that return to the start node?

Generate the sample data I'm playing with:

CREATE (n3:Test {appId: 3})<-[:MEDIUM]-(n0:START:Test {appId: 1})-[:WEAK]->(:Test {appId: 2})-[:STRONG]->(n3),
(n0)-[:STRONG]->(:Test {appId: 4})-[:STRONG]->(n4:Test {appId: 5})-[:WEAK]->(:Test {appId: 6})-[:MEDIUM]->(:Test {appId: 8}),
(n4)-[:MEDIUM]->(n11:Test {appId: 7})-[:STRONG]->(:Test {appId: 9}),
(n11)-[:WEAK]->(:Test {appId: 10})
5

I answered the question in your other post. Glad you got it to work.