Re: Is Neo4J A good choice for these requirements

[Niels Hoogeveen]

The data you are using, is that static or does it change over time? If you need update facilities, then having a graph database is certainly not overkill (ACID properties). If however you have a never changing set of 3000 nodes, you may as well load them from a text file into datastructures of your own.

On Saturday, September 22, 2012 4:00:27 PM UTC+2, Rehan wrote:

Hi 

I have a very basic Graph requirement ,  as show in  attached example image. 

I have few questions here:

• is Neo4J not an over kill for this purpose? as I have nodes less that 3000.
  
• do Neo4J supports finding short test path between two given nodes while specifying criteria for a property of relationship to be met.  if yes can someone give a java example for this.
  

Would be great help if some one can illustrate a a small java class for attached graph as an example. 

Thanks in advance. 

Rehan

[Michael Hunger]

Rehan,

your graph should be easy to create using cypher or the java API:

http://docs.neo4j.org/chunked/snapshot/tutorials-java-embedded.html

cypher create: http://docs.neo4j.org/chunked/snapshot/query-create.html

cheat sheet: neo4j.org/resources/cypher

for your query, in cypher:

start n=node(1),m=node(2)

match p=allShortestPaths(n-[*]-m)

where all(r in rels(p) : r.value >= 200)

return p

Am 22.09.2012 um 16:00 schrieb Rehan Azher:

Hi 

I have a very basic Graph requirement ,  as show in  attached example image. 

I have few questions here:

• is Neo4J not an over kill for this purpose? as I have nodes less that 3000.
  
• do Neo4J supports finding short test path between two given nodes while specifying criteria for a property of relationship to be met.  if yes can someone give a java example for this.
  

Would be great help if some one can illustrate a a small java class for attached graph as an example. 

Thanks in advance. 

Rehan

--
 
 

[Rehan]

Hi Micheal, 

Yes I have created the graph already.... will look into cypher query

Thanks and best regards, 

Rehan. 

[Rehan]

this is dynamic data, but every time we will refresh the whole database . Our goal  is to find the shortest paths keeping in mind efficiency while filtering those based on given properties.

[Michael Hunger]

Cool, please share your results

Please use cypher parameters for query caching.

Aka n=node({startNode})

Etc

Sent from mobile device

--
 
 

[Rehan]

Hi Micheal, 

please see the attached for implementation of example graph but I am getting an exception on Cypher query: 

expected where

"start n=node(1),m=node(13) match p=allShortestPaths(n-[*]-m) where all(r in rels(p) :  r.value>=200) return p "

                                                                                                                                    ^

at org.neo4j.cypher.internal.parser.v1_8.CypherParserImpl.parse(CypherParserImpl.scala:44)

at org.neo4j.cypher.CypherParser.parse(CypherParser.scala:44)

at org.neo4j.cypher.ExecutionEngine$$anonfun$prepare$1.apply(ExecutionEngine.scala:61)

at org.neo4j.cypher.ExecutionEngine$$anonfun$prepare$1.apply(ExecutionEngine.scala:61)

at org.neo4j.cypher.internal.LRUCache.getOrElseUpdate(LRUCache.scala:31)

at org.neo4j.cypher.ExecutionEngine.prepare(ExecutionEngine.scala:61)

at org.neo4j.cypher.ExecutionEngine.execute(ExecutionEngine.scala:55)

at org.neo4j.cypher.ExecutionEngine.execute(ExecutionEngine.scala:52)

at com.fastwire.carriere.grpah.GaphGeneratorImplTest.initializeGraphDB(GaphGeneratorImplTest.java:95)

Any idea how can I resole this issue. 

Thanks in advance. 

best regards, 

Rehan

[Rehan]

Hi All, 

I can find all paths between A-M for attached image graph , now how can I add a filter condition to Relationship where value<=200. Below is my snippet for finding all paths:

PathFinder<Path> finder = GraphAlgoFactory.allPaths(Traversal.expanderForTypes(relType.CONNECTED, Direction.BOTH),100);
Iterable<Path> paths = finder.findAllPaths(A, M);

Iterator<Path> pIterator = paths.iterator();
while (pIterator.hasNext()){
 Path path = pIterator.next();
 System.out.println(Traversal.simplePathToString(path));
}

best regards, 

Rehan

[Daniel Kuppitz]

Just a little syntax error. Try the following:

 START n=node(1), m=node(13)

 MATCH p=allShortestPaths(n-[*]-m)

 WHERE ALL(r in RELS(p) WHERE r.value >= 200)

RETURN p

Example: http://console.neo4j.org/r/iayhgi

Cheers,

Daniel

[Rehan]

Hi Daniel, 

Thanks for the response, Error is gone now . but I am getting an Empty iterator . 

Initially type of value property was string , so i got exception "Don't know how to compare" , tested with type as Long now no  exception but empty iterator.

Below is my code and response as well of running this example, any idea for this.: 

import java.util.Iterator;
import org.neo4j.cypher.ExecutionEngine;
import org.neo4j.cypher.ExecutionResult;
import org.neo4j.graphalgo.GraphAlgoFactory;
import org.neo4j.graphalgo.PathFinder;
import org.neo4j.graphdb.Direction;
import org.neo4j.graphdb.GraphDatabaseService;
import org.neo4j.graphdb.Node;
import org.neo4j.graphdb.Path;
import org.neo4j.graphdb.PathExpander;
import org.neo4j.graphdb.Relationship;
import org.neo4j.graphdb.RelationshipType;
import org.neo4j.graphdb.Transaction;
import org.neo4j.graphdb.index.Index;
import org.neo4j.graphdb.traversal.Evaluation;
import org.neo4j.graphdb.traversal.Evaluator;
import org.neo4j.graphdb.traversal.Evaluators;
import org.neo4j.graphdb.traversal.TraversalDescription;
import org.neo4j.kernel.Traversal;
import org.testng.annotations.Test;


public class GaphGeneratorImplTest {
 
 private Index<Node> indexService;
 private GraphDatabaseService graphDB ;
 public enum relType implements RelationshipType
 {
     CONNECTED
 }
 @Test
 public void f() {
 initializeGraphDB();
 }
 
 //GraphDatabase Object Initializer  
 private GraphDatabaseService getUniqueGraphDB(){
 if (graphDB==null){
 GraphDB gDB = new GraphDB();
 graphDB = gDB.getGraphDB();
 indexService = graphDB.index().forNodes("name");
 }
 return graphDB;
 }
 
 //Initialize Graph Class
 public Boolean initializeGraphDB() {
 
 if (graphDB==null){
 getUniqueGraphDB();
 }
 Transaction tx = graphDB.beginTx();
 try {
 Node A = getOrCreateNode("A");


 Node B = getOrCreateNode("B");
 Node C = getOrCreateNode("C");
 Node D = getOrCreateNode("D");
 Node E = getOrCreateNode("E");
 Node F = getOrCreateNode("F");
 Node G = getOrCreateNode("G");
 Node H = getOrCreateNode("H");
 Node I = getOrCreateNode("I");
 Node J = getOrCreateNode("J");
 Node K = getOrCreateNode("K");
 Node L = getOrCreateNode("L");
 Node M = getOrCreateNode("M");
 System.out.println("Nodes Created");
 getOrCreateRelationShip(A, B, (long) 400);
 getOrCreateRelationShip(A, C, (long) 200);
 getOrCreateRelationShip(B, M, (long) 10);
 getOrCreateRelationShip(C, D, (long) 1000);
 getOrCreateRelationShip(C, E, (long) 1000);
 getOrCreateRelationShip(C, F, (long) 300);
 getOrCreateRelationShip(D, I, (long) 1000);
 getOrCreateRelationShip(E, H, (long) 1000);
 getOrCreateRelationShip(E, G, (long) 500);
 getOrCreateRelationShip(F, G, (long) 500);
 getOrCreateRelationShip(G, J, (long) 1000);
 getOrCreateRelationShip(H, J, (long) 0);
 getOrCreateRelationShip(I, L, (long) 500);
 getOrCreateRelationShip(J, K, (long) 200);
 getOrCreateRelationShip(J, M, (long) 1000);
 getOrCreateRelationShip(K, L, (long) 500);
 getOrCreateRelationShip(L, M, (long) 800);
 
 tx.success();
 long aID = A.getId();
 long mID = M.getId();
 /*
 Evaluator e = new Evaluator() {
 @Override
            public Evaluation evaluate(Path arg0) {
             if(Long.valueOf(arg0.endNode().getSingleRelationship(relType.CONNECTED, Direction.BOTH).getProperty("value").toString())>=200){
                    return Evaluation.INCLUDE_AND_CONTINUE;
                }else{
                    return Evaluation.EXCLUDE_AND_CONTINUE;
                }
            }
        };


        TraversalDescription td = Traversal.description()
                .breadthFirst()
                .relationships(relType.CONNECTED)
                .evaluator( Evaluators.excludeStartPosition()).evaluator(Evaluators.atDepth(1)).evaluator(e);


       
 
 
 PathFinder<Path> finder = GraphAlgoFactory.allSimplePaths(Traversal.expanderForTypes(relType.CONNECTED, Direction.BOTH),100);

 
 Iterable<Path> paths = finder.findAllPaths(A, M);
 Iterator<Path> pIterator = paths.iterator();
 while (pIterator.hasNext()){
 Path path = pIterator.next();
 System.out.println(Traversal.simplePathToString(path));
 }

 */
 ExecutionEngine exEngine = new ExecutionEngine(graphDB);
 ExecutionResult eReuslt = exEngine.execute("START n=node("+aID+"), m=node("+mID+") MATCH p=allShortestPaths(n-[*]-m) WHERE ALL(r in RELS(p) WHERE r.value >= 200) RETURN p");
 //ExecutionResult eReuslt = exEngine.execute("start n=node("+aID+"),m=node("+mID+") match p=allShortestPaths(n-[*]-m) return p ");
 System.out.println(eReuslt);
 } catch (Exception e) {
 // TODO Auto-generated catch block
 e.printStackTrace();
 }finally{
 tx.finish();
 graphDB.shutdown();
 }
 return true;
 }
 /* Get or Create Node
 * Return Node if already exists
 * Else create a New node
 *
 * */
 private Node getOrCreateNode( String neName){
 if (graphDB==null)
 getUniqueGraphDB();
 Node node = indexService.get( "name", neName).getSingle();
        if ( node == null ){
        System.out.println("Creating Node: "+neName);
        node = graphDB.createNode();
        node.setProperty("name", neName);
            indexService.add( node, "name", node);
        }
        return node;
    }
 /* Get or Create Relationship
 * Return Relationship if already exists
 * Else create a New Relationship
 *
 * */
 private Relationship getOrCreateRelationShip(Node sourceNode, Node targetNode, Long value){
 if (graphDB==null){
 getUniqueGraphDB();
 }
 // Check if Already Connected
 Relationship rel = isRelated(sourceNode, targetNode, relType.CONNECTED);
 //if (rel!=null){
 Relationship relationship = sourceNode.createRelationshipTo(targetNode, relType.CONNECTED);
 System.out.println("Created Relationship between :"+sourceNode.getProperty("name")+" to "+targetNode.getProperty("name"));
 relationship.setProperty("value", value);
 return relationship;
 //}
 
 //return rel;
 }
 /* Check if Relationship Exists
 * Return Relationship if already exists
 * */
 private Relationship isRelated(Node a, Node b, RelationshipType type) {
 if (a.hasRelationship()){
 Iterable<Relationship> rels = a.getRelationships();
 if (rels!=null){
   for(Relationship r : rels) {
      if (r.getType().equals(type)){
         if (r.getStartNode() == b || r.getEndNode()==b){
         return r;
         }
      }
   }
 }
 }
 return null;


 }
}

Response: 

Creating Node: A
Creating Node: B
Creating Node: C
Creating Node: D
Creating Node: E
Creating Node: F
Creating Node: G
Creating Node: H
Creating Node: I
Creating Node: J
Creating Node: K
Creating Node: L
Creating Node: M
Nodes Created
Created Relationship between :A to B
Created Relationship between :A to C
Created Relationship between :B to M
Created Relationship between :C to D
Created Relationship between :C to E
Created Relationship between :C to F
Created Relationship between :D to I
Created Relationship between :E to H
Created Relationship between :E to G
Created Relationship between :F to G
Created Relationship between :G to J
Created Relationship between :H to J
Created Relationship between :I to L
Created Relationship between :J to K
Created Relationship between :J to M
Created Relationship between :K to L
Created Relationship between :L to M
empty iterator
PASSED: f

[Daniel Kuppitz]

I see. The problem is, that the allShortestPaths function is evaluated at first and then the WHERE clause. None of the shortest paths met the conditions => empty iterator. As far as I know, there's no way to inject filters in the shortestPath functions, but here's a workaround:

 START a=node:node_auto_index(name="A")

     , m=node:node_auto_index(name="M")

 MATCH p=a-[*]-m

 WHERE ALL(r in RELS(p) WHERE r.value >= 200)

  WITH a, m, MIN(LENGTH(p)) AS l

 MATCH p=a-[*]-m

 WHERE ALL(r in RELS(p) WHERE r.value >= 200)

   AND LENGTH(p)=l

RETURN p

Example: http://console.neo4j.org/?id=qizlc2

Cheers,

Daniel

[Rehan]

Hi Daniel, 

thanks for the support again. If i use below query it gives me exception:  

org.neo4j.cypher.MissingIndexException: Index `node_auto_index` does not exist


I can understand auto indexing on my database is not enabled , so I tried to do following : 

graphDB = new GraphDatabaseFactory().newEmbeddedDatabaseBuilder(DB_PATH).
    setConfig( GraphDatabaseSettings.relationship_keys_indexable, "value" ).
    setConfig( GraphDatabaseSettings.node_auto_indexing, true).
    setConfig( GraphDatabaseSettings.relationship_auto_indexing, true).
    newGraphDatabase();

but get an error on GraphDatabaseSettings.node_auto_indexing is not applicable for setConfig(String , String ) or setConfig(Setting, String). 

Any hint on this please. 

thanks again. 

Rehan

[Rehan]

graphDB = new GraphDatabaseFactory().newEmbeddedDatabaseBuilder(DB_PATH).
    setConfig( GraphDatabaseSettings.relationship_keys_indexable, "value" ).
    setConfig( GraphDatabaseSettings.node_auto_indexing, "true").
    setConfig( GraphDatabaseSettings.relationship_auto_indexing, "true").
    newGraphDatabase();

above works, ture need to be passed as string not boolean i.e. "true";

But i have notices that new query has caused a degradation in performance. Any hints on this to improve this. 

thanks .

[Michael Hunger]

Instead of: Traversal.expanderForTypes(relType.CONNECTED, Direction.BOTH)

A custom implementation of the relationship-expander interface that not only looks at rel-type and direction but also on

rel.getProperty("value",0) >= 200

Michael

--
 
 

[Michael Hunger]

Rehan,

if you get an empty response for the condition, what do you get if you leave off the where clause?

Michael

--
 
 

[Michael Hunger]

Ok, right if none of the shortest path's contained the (all rels do have to have the minimum value of 200) then they are filtered out.

You can shorten the query imho to:

 START a=node:node_auto_index(name="A")

     , m=node:node_auto_index(name="M")

 MATCH p=a-[*]-m

 WHERE ALL(r in RELS(p) WHERE r.value >= 200)

  WITH MIN(LENGTH(p)) AS l, collect(p) as paths

RETURN filter(p in paths : length(p) = l)

or

RETURN head(filter(p in paths : length(p) = l))

--
 
 

[Rehan]

Hi Michael , 

I only get one Path when removed the where clause. Please see the response below.

Relationship Already Exists
+-------------------------------------------------------------------------------------------------------------+
| p                                                                                                           |
+-------------------------------------------------------------------------------------------------------------+
| [Node[1]{name:"A"},:CONNECTED[0] {value:400},Node[2]{name:"B"},:CONNECTED[2] {value:10},Node[13]{name:"M"}] |
+-------------------------------------------------------------------------------------------------------------+
1 row
125 ms

PASSED: f

[Rehan]

Hi Michael , 

Thanks for the query and great help. this query gives  only one result , requirement is to get at least two possible paths if available. 

Thanks and Best Regards, 

Rehan

[Michael Hunger]

But then there seems only be one result between the two nodes?

--
 
 

[Rehan]

+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| p                                                                                                                                                                                                                                                      |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| [Node[1]{name:"A"},:CONNECTED[1] {value:200},Node[3]{name:"C"},:CONNECTED[3] {value:1000},Node[4]{name:"D"},:CONNECTED[6] {value:1000},Node[9]{name:"I"},:CONNECTED[12] {value:500},Node[12]{name:"L"},:CONNECTED[16] {value:800},Node[13]{name:"M"}]  |
| [Node[1]{name:"A"},:CONNECTED[1] {value:200},Node[3]{name:"C"},:CONNECTED[4] {value:1000},Node[5]{name:"E"},:CONNECTED[8] {value:500},Node[7]{name:"G"},:CONNECTED[10] {value:1000},Node[10]{name:"J"},:CONNECTED[14] {value:1000},Node[13]{name:"M"}] |
| [Node[1]{name:"A"},:CONNECTED[1] {value:200},Node[3]{name:"C"},:CONNECTED[5] {value:300},Node[6]{name:"F"},:CONNECTED[9] {value:500},Node[7]{name:"G"},:CONNECTED[10] {value:1000},Node[10]{name:"J"},:CONNECTED[14] {value:1000},Node[13]{name:"M"}]  |
+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
3 rows
297 ms

Above are three possible paths, returned by Daniel provided query and which are correct as well. 

br. 

Rehan

[Michael Hunger]

Then you're perhaps interested in all paths.

 START a=node:node_auto_index(name="A")

     , m=node:node_auto_index(name="M")

 MATCH p=a-[*]-m

 WHERE ALL(r in RELS(p) WHERE r.value >= 200)

RETURN p

ORDER BY length(p) desc limit 5

Am 24.09.2012 um 02:49 schrieb Rehan:

--
 
 

[Rehan]

Thanks Michael , 

I will test it and get back to you , from my understanding on a glance this query  will get all possible paths and then limit the result to 5 shortest paths.

Br, 

Rehan 

[Michael Hunger]

Yup.

But my previous query should have been equivalent to Daniels.

It just returns the paths as a collection (or with head() only the first)

Michael

--
 
 

[Rehan]

Hi Micheal , 

In case If  two node have multiple relationship of same type with different attributes. Can we define a query to select the two different relationships  between same  nodes .For Example as in below image: 

Currently I am using the query as provided by Michael  which gets all results and then limit those to 5 shortest paths.

START a=node:node_auto_index(name="A") , m=node:node_auto_index(name="M")  MATCH p=a-[*]-m  WHERE ALL(r in RELS(p) WHERE r.value >= 200) RETURN p ORDER BY length(p) desc limit 5

Thanks and best Regards, 

Rehan Azher

[Michael Hunger]

It should return all rels regardless of their properties in two paths.

You can also specify

START a=node:node_auto_index(name="B") , m=node:node_auto_index(name="M")  MATCH p=b-[*]-m, a-[:CONNECTED]-b  WHERE ALL(r in RELS(p) WHERE r.value >= 200) RETURN p ORDER BY length(p) desc limit 5




Sent from mobile device

[Rehan]

Hi Michael , 

correct, It do works as you told.  Is it possible to get the paths using different relationships where possible.  taking a scenario form IP Equipment networks scenario where two devices can have connection to each other over multiple interfaces and in case one would like to have  path diversity. For Example a graph would like be  

A------CONNECTED[interfaceA:100.2.33.209, InterfaceB:100.2.33.210]----------B    

A------CONNECTED[interfaceA:192.16.0.111,InterfaceB:192.16.0.112]----------B  

and so B-------------CONNECTED-------------------C  and onwards until it reached  Node G. 

One would like to have path pair  include  A----CONNECTED-----B with both relationships i.e. first contains relationship 1 with interfaces like 100 and other path contains relation like 192.

Since the data is dynamic so these interface value may change and are not fixed and are not always the possibility 

Hope I was able to explain it in easily  readable manner.   Also below is more simple example with similar kind of structure may be can help to understand the problem more easily:

Thanks for the helps.

Best Regards,

Rehan Azher

[Rehan]

Hi Micheal, 

the below query returns the path with loops (My nodes have multiple relationships) , can we get the only simple paths i.e. without loops.

Thanks and Best Regards, 

Rehan

On Monday, 1 October 2012 16:44:42 UTC+8, Michael Hunger wrote: