Modeling an ordered tree with neo4j

Question

I'm just getting started with neo4j, and I understand the principles of the graph and relationships, but I'm having a little bit of trouble with certain structures I want to model. I wanted to use it on a programming language project, and store the AST of a parsed source file. From there, I plan on adding a lot of additional data and relationships to the nodes to help with analysis and tooling, but the fundamental AST is still a little difficult.

The naive way of making a tree would be to simply walk the AST and copy every node in the tree to a node in neo4j, using properties to keep track of token data, etc. and then using a CHILD relationship to point to the child nodes. The problem is that when I later want to traverse the tree, I need to be able to do it in the correct order of the original AST, but out of the box I'm not quite sure the best way to do that.

I have two basic approaches I'm thinking of off the top of my head. One is to just add an index/ordinal property to each CHILD relationship. The other is to have a FIRST relationship to the first child and a NEXT relationship between each child to maintain order that way.

For either of these approaches it still doesn't seem like there's anything out of the box I can use to traverse this in the correct order. I think if I do FIRST/NEXT, I can get the correct order as long as I force neo4j to always traverse FIRST first and do a depth first search. Would that work? Is there a better way? This seems like something that should be handled easier out of the box.

UPDATE

Ultimately I decided to use both of my ideas. Child nodes have a CHILD relationship with an index property. The first child also has FIRST_CHILD relationship. Sibling nodes have a NEXT_SIBLING relationship to give the correct ordering. After that, the traversal was easy:

//reusable traversal description
final private TraversalDescription AST_TRAVERSAL = Traversal.description()
    .depthFirst()
    .expand(new OrderedByTypeExpander()
        .add(RelType.FIRST_CHILD, Direction.OUTGOING)
        .add(RelType.NEXT_SIBLING, Direction.OUTGOING));

and then when I actually needed to walk the tree I could just do

for(Path path : AST_TRAVERSAL.traverse(astRoot)){
    //do stuff here
}

For my use case, I don't actually modify the tree structure itself after creation - I just perform analysis and add more relationships and properties, so this is easy to maintain. If I had to do more modification, it might be a little bit of work, especially if I want to maintain the index numbers on child relations. So that might be something to consider for someone else in a similar situation.

If I did get into something more mutable, I would likely try out the collections Peter Neubauer suggested, and would probably just create a OrderedTreeNode class pointing to a node and using the List collection for children.

Answer 1

Russel, we are working on things like that, have a ordered time tree in the works that is structured much along the lines of different YEAR-2012->MONTH-01->DAY-21->VALUE123 and will probably have NEXT relationships between e.g. MONTHs of the same year.

Otherwise, if you do this, consider contributing it or investigating the stuff in https://github.com/neo4j/graph-collections, contribution and testing there is highly appreciated!

Answer 2

For the benefit of anyone finding this more than 2 years later, there finally is a library that supports time trees out of the box (disclaimer: I'm one of the authors):

https://github.com/graphaware/neo4j-timetree