Doing a DFS on a neo4j graph

1.1k views Asked by At

I have a database with the following structure. enter image description here

The property node is of the type

 create (A:Property {value:"abc"})

How to do a dfs so that it will be able to print all the values in the graph.In the order A->B->E->F->C->G->H->D->I->J

The relationship r is in the downward direction(single direction) with no properties.I have tried this link but looks complex to me.

Is there an easier way to do a simple dfc on an already existing Neo4j database

1

There are 1 answers

1
dkatzel On

The link you linked to is very verbose to cover all the different things you can do with Neo4j's powerful Traversal API.

I think all you have to do is this:

TraversalDescription traversalDescription = graphDb.traversalDescription()
            .depthFirst()
            .relationships(YourRelationShipTypeR, Direction.OUTGOING);

    Node a = ... // however you find your node A

    try(ResourceIterator<Node> nodes =traversalDescription.traverse(a)
                                                       .nodes()
                                                       .iterator()){
        while(nodes.hasNext()){
            Node n = nodes.next();
            //or whatever property name you use to get your names for nodes
            System.out.print(n.getProperty("id") + "->");
        }

    }

Should print A->B->E->F->C->G->H->D->I->J->

You can make the print statement smarter by not appending the arrow at the last node but I'll leave that up to you

EDIT

After trying the code myself I got a depth first search but the iterator order was out of order. It seemed it arbitrarily picked which child node to walk first. So I got output like A->D->J->I->C->H->G->B->F->E->.

So you have to sort the returned Paths of the TraversalDescription which has a sort(Comparator<Path> ) method.

To match the traversal you want, I sorted the paths by the node property that gives the node its name, which I called "id". Here's my updated traversal code:

 TraversalDescription traversalDescription = graphDb.traversalDescription()
            .depthFirst()
            .sort(new PathComparatorByName())
            .relationships(YourRelationShipTypeR, Direction.OUTGOING);

Where PathComparatorByName is a comparator I wrote that sorts Paths based on the nodes traversed in the path lexigraphically sorted by name:

private class PathComparatorByName implements Comparator<Path>{

    @Override
    public int compare(Path o1, Path o2) {
        Iterator<Node> iter1 = o1.nodes().iterator();
        Iterator<Node> iter2 = o2.nodes().iterator();


        while(iter1.hasNext()){
            if(!iter2.hasNext()){
                //return shorter path?
                return 1;
            }

            Node n1 = iter1.next();
            Node n2 = iter2.next();
            int nodeCmp = compareByNodeName(n1, n2);
            if(nodeCmp !=0){
                return nodeCmp;
            }

        }
        if(iter2.hasNext()){
            //return shorter path?
            return -1;
        }
        return 0;
    }

    private int compareByNodeName(Node node1, Node node2) {
        String name1 = (String)node1.getProperty("id");

         String name2 = (String)node2.getProperty("id");

        return name1.compareTo(name2);
    }

}

Rerunning it now with the comparator will output:

A->B->E->F->C->G->H->D->I->J->