cancel
Showing results forΒ
Did you mean:Β

## How to sort a subgraph by weakest link in weighted graph

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]

4 REPLIES 4
Ninja

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``````

@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})``````

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