cypher: find all longest paths

[Tomas Teicher]

Hi

I have cypher query as follows: 

start a = node(1) MATCH path = a-[r:HAS_PARENT*]->b return path

it returns results as follows: 

Pater -> John -> Maria -> Mike

Peter -> John -> Maria

Peter-> John

I would like to return only longest paths.

I have a graph where every node can have just one relationship of type HAS_PARENT. So when I return only longest paths, I should found all nodes with that relationship

Can anybody help?

thanks

Tomas

[Peter Neubauer]

Tomas,

Taking the Matrix default, you can do something like
http://tinyurl.com/6ralddc or

start n=node(1)
match p = n-[:KNOWS*1..]->m
with n,MAX(length(p)) as l
match p = n-[:KNOWS*1..]->m
where length(p) = l
return p,l

It's a bit lengthy since you first need to find the maxlength, and
then the paths that have this length, but it should work. For a
shorter workaround you could simply just limit the result and return
after the first clause:

start n=node(1) match p = n-[:KNOWS*1..]->m return p,MAX(length(p)) as
l order by l desc limit 1

Cheers,

/peter neubauer

G:  neubauer.peter
S:  peter.neubauer
P:  +46 704 106975
L:   http://www.linkedin.com/in/neubauer
T:   @peterneubauer

If you can write, you can code - @coderdojomalmo
If you can sketch, you can use a graph database - @neo4j

[Tomas Teicher]

thank you

I have found one more way

start n=node(1) match p = n-[:KNOWS*1..]->m WHERE NOT(m-[:KNOWS]->()) return p

last node in path cannot have outgoing KNOWS relationship, so it should return only the longest paths of the relationships.

Dňa pondelok, 30. apríla 2012 9:00:25 UTC+2 Tomas Teicher napísal(-a):

[Tomas Teicher]

In fact, this work only when nodes are in hierarchical structure (so between two nodes is only one possible path), but this sutisfies my use case

thanks for the tips

Tomas

Dňa piatok, 4. mája 2012 22:25:18 UTC+2 Tomas Teicher napísal(-a):

[Alireza Rezaei Mahdiraji]

I want to find all different paths starting from root element, i.e., no prefix paths but
paths can be of different length.
The query you wrote find the maximal length and only returns those.
Best,
Alireza

[Michael Hunger]

start n=node(1) match p = n-[:KNOWS*1..]->m return p

--
You received this message because you are subscribed to the Google Groups "Neo4j" group.
To unsubscribe from this group and stop receiving emails from it, send an email to neo4j+un...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

[Alireza Rezaei Mahdiraji]

This will also return prefix paths of each maximal path.

Like examples above:

Pater -> John -> Maria -> Mike

Peter -> John -> Maria

Peter-> John

Best,
Alireza

[Alireza Rezaei Mahdiraji]

Forgot to write, I do not want that :)
Alireza

[Thomas Fenzl]

You can filter paths where the final nodes still has outgoing
connections like this:

start n=node(1) match p = n-[:KNOWS*1..]->m

where not m -[:KNOWS]->()
return p

Regards,
Thomas

On 2013-05-07 15:55, Alireza Rezaei Mahdiraji wrote:
> This will also return prefix paths of each maximal path.
>
> Like examples above:
>
> Pater -> John -> Maria -> Mike
> Peter -> John -> Maria
> Peter-> John
>
> Best,
> Alireza
>
> On Tuesday, May 7, 2013 3:44:57 PM UTC+2, Michael Hunger wrote:
>> start n=node(1) match p = n-[:KNOWS*1..]->m return p
>>
>> Am 07.05.2013 um 15:28 schrieb Alireza Rezaei Mahdiraji <

>> alire...@gmail.com <javascript:>>:

>> email to neo4j+un...@googlegroups.com <javascript:>.

[Alireza Rezaei Mahdiraji]

OK, here is a little bit more about the type of path I am interested:
I have a graph which has 4 levels of nodes, namely, B, F, E, and V.
All nodes have two properties let say name and dim.  Nodes in set V
are only connected to E, and E only to F and F only to B.

So now, I want to know if all paths starting from B to V (or vice versa) have
the maximum length (here 3). Conceptually, it means that some nodes of types
E might not be connected to any F and instead be connected to some B.
This only happens from V to B direction. Another case, some Nodes from
V may be directly connected to B but not to any E or F.
I hope it is clear enough :)

Now, the question is how I check to see there are paths (at least one) of such type, i.e.,
with length less than maximum (3 here)?

Best,
Alireza

[Lasse Westh-Nielsen]

Alireza,

Are you looking for the number of paths of length 2 or less between B and V:

start b=node({b}), v=node({v}) match p = b-[:KNOWS*1..2]->v

return count(p)

Or did I misunderstand?

 - Lasse

To unsubscribe from this group and stop receiving emails from it, send an email to neo4j+un...@googlegroups.com.

[Alireza Rezaei Mahdiraji]

It seems using your query together with a where clause will get what I want,
I will test it on more cases and report back if it does not.
Thanks a lot :)
Best,
Alireza