Find the length of longest path using cypher query

mic...@vinasource.com

unread,

Jan 28, 2013, 4:22:06 AM1/28/13

to ne...@googlegroups.com

Hello,

I'm having a neo4j of 40 millions node and 500 millions relationship of a kind.

I wanna see what is the length of the longest path of my dataset (so-called the depth of graph) using Cypher query.

Could you please help me with this?

Thanks in advance.

Michael

Peter Neubauer

unread,

Jan 28, 2013, 6:29:15 AM1/28/13

to Neo4j User

Well,

that is quite an expensive query, but you could do it like

start n=node(1)

match p=n-[:KNOWS*]-m

return p, length(p) as length

order by length(p) desc

limit 2

If you are starting at e.g. node 1

For better efficiency, can you limit you starting points, or execute several queries, starting at a range of the potential starting points, against parallel neo4j instances, e.g. in a HA cluster?

/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

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

Michael Tran

unread,

Jan 28, 2013, 6:31:18 AM1/28/13

to ne...@googlegroups.com

Thanks Peter.
But I'm not sure which node is the beginning of longest path.
n=node(1) doesn't help here.

To unsubscribe from this group, send email to neo4j+un...@googlegroups.com.

Peter Neubauer

unread,

Jan 28, 2013, 6:44:29 AM1/28/13

to Neo4j User

Then I would do with a range of 1..10 for the nodes

start n=node(1,2,3,4,5)

match p=n-[:KNOWS*]-m

return p

order by length(p) desc

limit 1

on one cluster node,

start n=node(6,7,8,9,10)

match p=n-[:KNOWS*]-m

return p

order by length(p) desc

limit 1

on the other, and then merge the results in your client. Would that work?

/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

Michael Hunger

unread,

Jan 28, 2013, 6:48:35 AM1/28/13

to ne...@googlegroups.com

it's probably too expensive to compute via cypher

for paging across all nodes you can also use

start n=node(*)

with n

skip {offset} limit {pageSize}

match p=n-[:KNOWS*]-m
return p
order by length(p) desc
limit 1

Michael Tran

unread,

Jan 29, 2013, 5:42:17 AM1/29/13

to ne...@googlegroups.com

I ran the query that Peter suggested and got the exception:

Jan 29, 2013 9:30:41 AM com.sun.jersey.spi.container.ContainerResponse mapMappableContainerException
SEVERE: The exception contained within MappableContainerException could not be mapped to a response, re-throwing to the HTTP container
java.lang.OutOfMemoryError: Java heap space

Michael, can you please explain it to me? I even can't query a simple cypher, the CPU usage is always 99% (8 cores). Is it because my dataset too large?
FYI, here is information of my current machine:

68.4 GiB of memory
26 EC2 Compute Units (8 virtual cores with 3.25 EC2 Compute Units each)
1690 GB of instance storage
64-bit platform
I/O Performance: High
EBS-Optimized Available: 1000 Mbps
API name: m2.4xlarge

Thanks for your kind support.
Michael Tran

mic...@vinasource.com

unread,

Jan 29, 2013, 5:50:45 AM1/29/13

to ne...@googlegroups.com

Here is the detailed exception in log file:

Jan 29, 2013 8:28:32 AM com.sun.jersey.spi.container.ContainerResponse mapMappableContainerException

SEVERE: The exception contained within MappableContainerException could not be mapped to a response, re-throwing to the HTTP container

java.lang.OutOfMemoryError: GC overhead limit exceeded

at java.lang.Long.valueOf(Long.java:577)

at org.neo4j.kernel.impl.cache.SoftLruCache.get(SoftLruCache.java:71)

at org.neo4j.kernel.impl.core.NodeManager.receiveRelationships(NodeManager.java:641)

at org.neo4j.kernel.impl.core.NodeManager.getMoreRelationships(NodeManager.java:625)

at org.neo4j.kernel.impl.core.NodeImpl.loadMoreRelationshipsFromNodeManager(NodeImpl.java:564)

at org.neo4j.kernel.impl.core.NodeImpl.getMoreRelationships(NodeImpl.java:527)

at org.neo4j.kernel.impl.core.RelationshipIterator.fetchNextOrNull(RelationshipIterator.java:94)

at org.neo4j.kernel.impl.core.RelationshipIterator.fetchNextOrNull(RelationshipIterator.java:36)

at org.neo4j.helpers.collection.PrefetchingIterator.hasNext(PrefetchingIterator.java:55)

at scala.collection.JavaConversions$JIteratorWrapper.hasNext(JavaConversions.scala:574)

at scala.collection.Iterator$class.foreach(Iterator.scala:660)

at scala.collection.JavaConversions$JIteratorWrapper.foreach(JavaConversions.scala:573)

at scala.collection.IterableLike$class.foreach(IterableLike.scala:73)

at scala.collection.JavaConversions$JIterableWrapper.foreach(JavaConversions.scala:587)

at scala.collection.generic.Growable$class.$plus$plus$eq(Growable.scala:48)

at scala.collection.mutable.ListBuffer.$plus$plus$eq(ListBuffer.scala:128)

at scala.collection.mutable.ListBuffer.$plus$plus$eq(ListBuffer.scala:42)

at scala.collection.TraversableLike$class.$plus$plus(TraversableLike.scala:150)

at scala.collection.JavaConversions$JIterableWrapper.$plus$plus(JavaConversions.scala:587)

at org.neo4j.cypher.internal.pipes.matching.VarLengthStep.expandRecursively$1(VarLengthStep.scala:68)

at org.neo4j.cypher.internal.pipes.matching.VarLengthStep.expand(VarLengthStep.scala:96)

at org.neo4j.cypher.internal.pipes.matching.TraversalPathExpander.expand(TraversalPathExpander.scala:36)

at org.neo4j.kernel.impl.traversal.TraversalBranchWithState.expandRelationshipsWithoutChecks(TraversalBranchWithState.java:70)

at org.neo4j.kernel.impl.traversal.TraversalBranchImpl.expandRelationships(TraversalBranchImpl.java:104)

at org.neo4j.kernel.impl.traversal.TraversalBranchImpl.initialize(TraversalBranchImpl.java:130)

at org.neo4j.kernel.impl.traversal.TraversalBranchWithState.initialize(TraversalBranchWithState.java:32)

at org.neo4j.kernel.impl.traversal.TraversalBranchImpl.next(TraversalBranchImpl.java:150)

at org.neo4j.kernel.impl.traversal.TraversalBranchWithState.next(TraversalBranchWithState.java:32)

at org.neo4j.kernel.PreorderDepthFirstSelector.next(PreorderDepthFirstSelector.java:52)

at org.neo4j.kernel.impl.traversal.TraverserIterator.fetchNextOrNull(TraverserIterator.java:65)

at org.neo4j.kernel.impl.traversal.TraverserIterator.fetchNextOrNull(TraverserIterator.java:34)

at org.neo4j.helpers.collection.PrefetchingIterator.hasNext(PrefetchingIterator.java:55)

Jan 29, 2013 9:30:41 AM com.sun.jersey.spi.container.ContainerResponse mapMappableContainerException

SEVERE: The exception contained within MappableContainerException could not be mapped to a response, re-throwing to the HTTP container

java.lang.OutOfMemoryError: Java heap space

at java.util.Arrays.copyOfRange(Arrays.java:2694)

at java.lang.String.<init>(String.java:203)

at java.lang.StringBuffer.toString(StringBuffer.java:561)

at org.neo4j.server.rest.domain.JsonHelper.createJsonFrom(JsonHelper.java:100)

at org.neo4j.server.rest.repr.formats.JsonFormat.complete(JsonFormat.java:68)

at org.neo4j.server.rest.repr.MappingRepresentation.serialize(MappingRepresentation.java:44)

at org.neo4j.server.rest.repr.OutputFormat.format(OutputFormat.java:182)

at org.neo4j.server.rest.repr.OutputFormat.formatRepresentation(OutputFormat.java:132)

at org.neo4j.server.rest.repr.OutputFormat.response(OutputFormat.java:119)

at org.neo4j.server.rest.repr.OutputFormat.ok(OutputFormat.java:55)

at org.neo4j.server.webadmin.rest.MonitorService.getData(MonitorService.java:118)

at org.neo4j.server.webadmin.rest.MonitorService.getData(MonitorService.java:96)

at sun.reflect.GeneratedMethodAccessor37.invoke(Unknown Source)

at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)

at java.lang.reflect.Method.invoke(Method.java:601)

at com.sun.jersey.spi.container.JavaMethodInvokerFactory$1.invoke(JavaMethodInvokerFactory.java:60)

at com.sun.jersey.server.impl.model.method.dispatch.AbstractResourceMethodDispatchProvider$ResponseOutInvoker._dispatch(AbstractResourceMethodDispatchProvider.java:205)

at com.sun.jersey.server.impl.model.method.dispatch.ResourceJavaMethodDispatcher.dispatch(ResourceJavaMethodDispatcher.java:75)

at com.sun.jersey.server.impl.uri.rules.HttpMethodRule.accept(HttpMethodRule.java:288)

at com.sun.jersey.server.impl.uri.rules.RightHandPathRule.accept(RightHandPathRule.java:147)

at com.sun.jersey.server.impl.uri.rules.ResourceClassRule.accept(ResourceClassRule.java:108)

at com.sun.jersey.server.impl.uri.rules.RightHandPathRule.accept(RightHandPathRule.java:147)

at com.sun.jersey.server.impl.uri.rules.RootResourceClassesRule.accept(RootResourceClassesRule.java:84)

at com.sun.jersey.server.impl.application.WebApplicationImpl._handleRequest(WebApplicationImpl.java:1469)

at com.sun.jersey.server.impl.application.WebApplicationImpl._handleRequest(WebApplicationImpl.java:1400)

at com.sun.jersey.server.impl.application.WebApplicationImpl.handleRequest(WebApplicationImpl.java:1349)

at com.sun.jersey.server.impl.application.WebApplicationImpl.handleRequest(WebApplicationImpl.java:1339)

at com.sun.jersey.spi.container.servlet.WebComponent.service(WebComponent.java:416)

at com.sun.jersey.spi.container.servlet.ServletContainer.service(ServletContainer.java:537)

at com.sun.jersey.spi.container.servlet.ServletContainer.service(ServletContainer.java:699)

at javax.servlet.http.HttpServlet.service(HttpServlet.java:820)

at org.mortbay.jetty.servlet.ServletHolder.handle(ServletHolder.java:511)

Jan 29, 2013 9:54:46 AM com.sun.jersey.spi.container.ContainerResponse mapMappableContainerException

SEVERE: The exception contained within MappableContainerException could not be mapped to a response, re-throwing to the HTTP container

java.lang.OutOfMemoryError: Java heap space

at java.util.Arrays.copyOf(Arrays.java:2367)

at java.lang.AbstractStringBuilder.expandCapacity(AbstractStringBuilder.java:130)

at java.lang.AbstractStringBuilder.ensureCapacityInternal(AbstractStringBuilder.java:114)

at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:535)

at java.lang.StringBuffer.append(StringBuffer.java:322)

at java.io.StringWriter.write(StringWriter.java:94)

at org.codehaus.jackson.impl.WriterBasedGenerator._flushBuffer(WriterBasedGenerator.java:1812)

at org.codehaus.jackson.impl.WriterBasedGenerator.flush(WriterBasedGenerator.java:903)

at org.codehaus.jackson.map.ObjectMapper.writeValue(ObjectMapper.java:1615)

at org.neo4j.server.rest.domain.JsonHelper.createJsonFrom(JsonHelper.java:98)

at org.neo4j.server.rest.repr.formats.JsonFormat.complete(JsonFormat.java:56)

at org.neo4j.server.rest.repr.ListRepresentation.serialize(ListRepresentation.java:53)

at org.neo4j.server.rest.repr.OutputFormat.format(OutputFormat.java:182)

at org.neo4j.server.rest.repr.OutputFormat.formatRepresentation(OutputFormat.java:132)

at org.neo4j.server.rest.repr.OutputFormat.response(OutputFormat.java:119)

at org.neo4j.server.rest.repr.OutputFormat.ok(OutputFormat.java:55)

at org.neo4j.server.webadmin.rest.JmxService.getBean(JmxService.java:127)

at sun.reflect.GeneratedMethodAccessor42.invoke(Unknown Source)