CODEWITHSUNDEEP
javaalgorithmrandomneo4j
Dinos Mihelis
Dinos Mihelis

Reputation: 21

Random Postorder traversal in neo4j

I'm trying to create an algorithm in Neo4j using the java API. The algorithm is called GRAIL (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.169.1656&rep=rep1&type=pdf) and it assigns labels to a graph for later answering reachability queries.

This algorithm uses postorder depth first search but with random traversal each time (each child of a node is visited randomly in each traversal). In the neo4j java api there is an algorithm doing this (https://github.com/neo4j/neo4j/blob/7f47df8b5d61b0437e39298cd15e840aa1bcfed8/community/kernel/src/main/java/org/neo4j/graphdb/traversal/PostorderDepthFirstSelector.java) without the randomness and i can't seem to find a way to do this.

My code has a traversal description in which i want to add a custom order (BranchOrderingPolicy) in order to achieve the before mentioned algorithm. like this:

 .order(**postorderDepthFirst()**)

Upvotes: 0

Views: 169

Answers (2)

Dinos Mihelis
Dinos Mihelis

Reputation: 21

The answer to my question came rather easy but after a lot of thinking. I just had to alter the path expander (i created my own) which returns the relationhipss that the traversal takes as next and there a simple line of code to randomize the relationships. The code is :

public class customExpander implements PathExpander {

private final RelationshipType relationshipType;
private final Direction direction;
private final Integer times;

public customExpander (RelationshipType relationshipType, Direction direction ,Integer times)
{
    this.relationshipType = relationshipType;
    this.direction = direction;
    this.times=times;
}



@Override
public Iterable<Relationship> expand(Path path, BranchState state)
{
        List<Relationship> results = new ArrayList<Relationship>();
        for ( Relationship r : path.endNode().getRelationships( relationshipType, direction ) )
        {  
           results.add( r ); 
        }
        Collections.shuffle(results);
        }       
    return results;         
    }


@Override
public PathExpander<String> reverse()
{
    return null;
}

}

Upvotes: 1

Mattias Finn&#233;
Mattias Finn&#233;

Reputation: 3054

There's no such ordering by default in neo4j, however it should be possible to write one. TraversalBranch#next gives the next branch and so your implementation could get all or some and pick at random. However state keeping will be slightly tricky and as memory hungry as a breadth first ordering I'd guess. Neo4j keeps relationships in linked lists per node, so there's no easy way to pick one at random without first gathering all of them.

Upvotes: 0

Related Questions