Neo4j cypher query display tree-like subgraph star

Question

I want to Display a tree-like subgraph showing all paths starting from a single node. Most connections are bidirectional(2 edges at the moment probably change to 1 edge instead for better performance) and I have different types of relationships. But theres one special sequence of nodes and relations leading into even more loops and this sequence shouldn't be displayed in the resulting graph.

MATCH p=(n)-[r*0..4]-(m) WHERE n.CAT='a1' RETURN p

This Query is nearly solving the problem, but I couldnt find/create the correct query to leave the sequence out of the graph. The depth is still limited because with depth [r*0..9] neo4j web app stopped responding (not the main problem! I already know how to improve/fix this) and it took a while to stop the database. The Sequence is creating the most unwanted permutations and tons of possible paths and loops. There is no way to change the relations(except using 1 edge instead of 2, practically its bidirectional but as far as i know the operation should still be the same and less complex, correct me know if I'm wrong) between the nodes because with another starting node the relation is potentially needed.

Sequence:

(x)-[:relation2]-(y)-[:relation2]-(z)

and x,y,z all having the same propertie value at CAT='variable'. It's always the same relation and the same propertie. The values and the nodes vary.

All nodes are potential starting nodes.

Also the query has to be very very fast dealing with long paths(different lenghts) splitting sometimes. Most splits will be ignored with the sequence exlcuded. The depth has to be unlimited. The resulting paths will always end as soon the query ignores the sequence and doesnt "go" this path.

To prevent misunderstanding:

x,y,z1 and z3 are sharing the same property CAT(category)='a'and z2.CAT='b' for example.

display dont display and stop

(x)-[:relation2]-(y)-[:relation2]-(z1)

(x)-[:relation2]-(y)-[:relation2]-(z2)

(x)-[:relation2]-(y)-[:relation1]-(z3)

x.CAT = y.CAT = z1.CAT = z3.CAT != z2.CAT

Performance of the query is very important and the reason for me doing this, but first I need "simple" solution to progress on this project.

Thanks a lot in advance.

Answer 1

For this you should create a custom traversal. There is an API for that in Neo4j, take a look at the documentation : https://neo4j.com/docs/java-reference/current/#tutorial-traversal

To not traverse twice a node, you should use the NODE_PATH as uniqueness rule (in cypher, it's a RELATIONSHIP_PATH uniqueness to avoid graph cycle).

Cheers

Answer 2

For this you should create a custom traversal. There is an API for that in Neo4j, take a look at the documentation : https://neo4j.com/docs/java-reference/current/#tutorial-traversal

To not traverse twice a node, you should use the NODE_PATH as uniqueness rule (in cypher, it's a RELATIONSHIP_PATH uniqueness to avoid graph cycle).

As @Tezra and @logisima pointed out the Traversal API is the key. But its not done with uniqueness or anything this complex. This finally printed out the results i was looking for:

TraversalDescription td = graphDb.traversalDescription()
.depthFirst()
.uniqueness(Uniqueness.RELATIONSHIP_GLOBAL)
.evaluator( new Evaluator()
{
    @Override
    public Evaluation evaluate( final Path path )
    {
        Node parent=null,grandParent =null;
        Relationship rel1=null,rel2=null;
        int nCount=0,rCount=0;

        if(path.length()>=2)
        {
            for(Node node : path.reverseNodes())
            {
                if(nCount==1)
                    parent = node;
                if(nCount==2)
                    grandParent=node;
                if(nCount>2)
                    break;
                nCount++;
            }
            for(Relationship rel : path.reverseRelationships())
            {
                if(rCount==0)
                    rel1 = rel;
                if(rCount==1)
                    rel2=rel;
                if(rCount>1)
                    break;
                rCount++;
            }
        }
        if(path.length()<2)
        {
            return Evaluation.INCLUDE_AND_CONTINUE;
        }
        else if (path.length()>=2 
                && rel1.isType(relType)
                && rel2.isType(relType)
                && path.endNode().getProperty("CATEGORY").toString().equals(parent.getProperty("CATEGORY").toString())
                && path.endNode().getProperty("CATEGORY").toString().equals(grandParent.getProperty("CATEGORY").toString()))
        {
            return Evaluation.EXCLUDE_AND_PRUNE;
        }
        else
        {
            return Evaluation.INCLUDE_AND_CONTINUE;
        }
    }
});
try ( Transaction tx = graphDb.beginTx() )
{
    Traverser traverser = td.traverse(graphDb.getNodeById(id));
    for ( Path path : traverser)
    {
        System.out.println(path.toString());
                }
    tx.success();
}

(special thanks to @Tezra bringing me on the right track on time)

A solution with apoc should also be possible and also avoid the problem of getting the graph back into neo4j.