cypher query to find paths of fixed length

[Akhil]

Is there a way to get paths of fixed length in cypher quickly. Using a
query like Match n-[*4..4]-m between nodes n to m takes a long time to
complete. I have close to 8000 nodes and 16000 relationships.

Akhil

[Wes Freeman]

Are you specifying what n and m are? Or are you doing node(*) and finding all of the paths to any m 4 levels away?

It shouldn't be too bad if you do 

start n=..., m=... 

match p=n-[*4]-m 

return p

On Thu, Nov 29, 2012 at 1:08 PM, Akhil <azk...@psu.edu> wrote:

Is there a way to get paths of fixed length in cypher quickly. Using a query like Match n-[*4..4]-m between nodes n to m takes a long time to complete. I have close to 8000 nodes and 16000 relationships.

Akhil

--

[Akhil]

--
 
 

nope, this takes an extremely long time and i am also using indexes. Works immediately if it is under 4. The gremlin query seemed to work quickly tho ... I am however not satisfied with the way i have to write that query for now.

Akhil

[Michael Hunger]

It should be much faster if you spell out the relationships, can you please try it?

n--()--()--()--m

Should make 4 :)

Cypher should do this internally too, can you raise an github issue for that?

Thanks

Michael

--
 
 

[Akhil]

nope

MATCH p = s--()--()--()--e  RETURN p,length(p)                          

hangs ...  I tried something similar in gremlin

g.v(1).out.out.out ....

which works quickly and i still cause i am new

I am using Neo4j - Graph Database Kernel 1.8.M06

Akhil

--
 
 

[Wes Freeman]

Performance is likely better in 1.9-M01... if you wouldn't mind testing it out.

Wes

--
 
 

[Akhil]

Sorry .... Says invalid query ... Do yo guys want any files from me ?

Akhil

--
 
 

[Peter Neubauer]

Well,

MATCH p = s--()--()--()--e RETURN p,length(p)

is looking at both directions, see http://console.neo4j.org/r/meifp8
and of course tends to explode in complexity and number of returned
paths.

You probably want

start s=node(*)
MATCH p = s-->()-->()-->()-->e
RETURN p,length(p)

like http://console.neo4j.org/r/fjle2s ?

/peter

Cheers,

/peter neubauer

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

Neo4j 1.8 GA - http://www.dzone.com/links/neo4j_18_release_fluent_graph_literacy.html

> --
>
>

[Akhil]

Oh sorry, i just pasted the match part, the whole query was something like

START s=node:nodeIdx(name='abc'),
e = node:nodeIdx(name='xyz')

MATCH p = s--()--()--()--e
RETURN p,length(p)

i dont understand why its said invalid query

Akhil

[Michael Hunger]

can you try as peter said (and as you do in gremlin), make the relationship-patterns directed:

> START s=node:nodeIdx(name='abc'),
> e = node:nodeIdx(name='xyz')

> MATCH p = s-->()-->()-->()-->e
> RETURN p,length(p)

> --
>
>

[Akhil]

It still doesnt help me too much. It works when i add this direction for
4 but runs forever for 6. I know there are paths that exist for greater
than 10 for vertices i am querying for. I used the all shortest paths
along with certain constraints to get that path of length 10.

MATCH p = s-->()-->()-->()-->()-->()-->e ... fails ...


Akhil

[Michael Hunger]

Which is more sensible anyway as it uses a bidirectional algorithm with cutoff,

why would you have cypher do a explosive search instead over r^10 rels and nodes (n being the avg #of rels per node) using the shortest-path algorithm?

Michael

> --
>
>

[Akhil Kumar]

Then I don't understand how I could get a result with paths of fixed length, all shortest paths would give me the paths with the shortest lengths and I am looking for an exhaustive list for paths of a certain length
Akhil Kumar
Bioinformatics and Genomics @
The Huck institutes of the life sciences,
Pennsylvania state university

--

[Akhil Kumar]

[Akhil Kumar]

[Michael Hunger]

Can you try to use a more recent version of Neo4j, there have been some improvements in the cypher pattern machers?

E.g. 1.9.M01

Imho you can pass a limit to the shortest-path, perhaps that helps you.

MATCH p = shortestPath(s-[*..4]->e)

MATCH p = allShortestPaths(s-[*..4]->e)

> --
>
>

[Akhil Kumar]

I used 1.9 and I ran the query and j still don't get the path of the length I want, it still gives me paths with shortest length, I put in the upper limit of 10 and it gives me all the paths of length 5. I am able to dictate this with multiple '.out' in gremlin but I can't do the same with Cypher here :-(

--

[Akhil Kumar]

[Michael Hunger]

Did you use 1.9 also with the MATCH p = s-->()-->()-->()-->()-->()-->e ?

Any chance to share your dataset and your concrete query?

Cheers

Michael

> --
>
>

[Peter Neubauer]

Akhil,
also, how many records are you getting back, if you gradually increase
the length of the path?

START s=node:nodeIdx(name='abc'),
e = node:nodeIdx(name='xyz')

MATCH p = s-->()-->e
RETURN p,length(p)

START s=node:nodeIdx(name='abc'),
e = node:nodeIdx(name='xyz')

MATCH p = s-->()-->()-->e
RETURN p,length(p)

START s=node:nodeIdx(name='abc'),
e = node:nodeIdx(name='xyz')
MATCH p = s-->()-->()-->()-->e
RETURN p,length(p)

Cheers,

/peter neubauer

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

Neo4j 1.8 GA - http://www.dzone.com/links/neo4j_18_release_fluent_graph_literacy.html

> --
>
>

[Akhil]

Hi Peter, Michael,

Please find the dataset attached along with the information you asked
for below.

START s=node:nodeIdx(name='abc'),
e = node:nodeIdx(name='xyz')
MATCH p = s-->()-->e
RETURN p,length(p)

Number of records : 0

START s=node:nodeIdx(name='abc'),
e = node:nodeIdx(name='xyz')
MATCH p = s-->()-->()-->e
RETURN p,length(p)

Number of records : 0

START s=node:nodeIdx(name='abc'),
e = node:nodeIdx(name='xyz')
MATCH p = s-->()-->()-->()-->e
RETURN p,length(p)

Number of records : 0

START s=node:nodeIdx(name='abc'),
e = node:nodeIdx(name='xyz')

MATCH p = s-->()-->()-->()-->()-->e
RETURN p,length(p)

Number of records : 852

The next level fails or does not return results for quite a while.

Akhil

[Michael Hunger]

You forgot to pack the indexes in the subdirectories (zip -r)

> --
>
>
> <graph.db.zip>

[Akhil]

hi Michael,
please find the folder data attached

Akhil