用neo4j建模有序树 [英] Modeling an ordered tree with neo4j

问题描述

我刚开始使用neo4j，我了解图形和关系的原理，但是对于要建模的某些结构，我有点麻烦.我想在编程语言项目上使用它，并存储已解析源文件的AST.从那里开始，我计划在节点上添加很多其他数据和关系，以帮助进行分析和处理工具，但是基本的AST仍然有些困难.

制作树的天真的方法是简单地遍历AST并将树中的每个节点复制到neo4j中的节点，使用属性来跟踪令牌数据等，然后使用CHILD关系来指向子节点.问题是，当我以后要遍历树时，我需要能够按照原始AST的正确顺序进行操作，但是开箱即用时，我不确定这样做的最佳方法.

我正在考虑两种基本方法.一种是只向每个CHILD关系添加索引/普通属性.另一种是与第一个孩子建立FIRST关系，每个孩子之间保持NEXT关系，以保持这种顺序.

对于这两种方法中的任何一种，似乎都没有开箱即用的东西，我可以用它以正确的顺序遍历.我认为如果执行FIRST/NEXT，只要我强制neo4j始终始终先行FIRST并进行深度优先搜索，就可以获得正确的顺序.那行得通吗?有没有更好的办法?似乎应该在开箱即用时更轻松地进行处理.

更新

我最终决定同时使用我的两个想法.子节点与索引属性具有CHILD关系.第一个孩子也有FIRST_CHILD关系.同级节点具有NEXT_SIBLING关系以给出正确的顺序.之后，遍历很容易:

//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));

然后当我真正需要走树的时候我就可以做

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

对于我的用例，在创建后我实际上并没有修改树结构本身-我只是执行分析并添加更多的关系和属性，因此易于维护.如果必须进行更多修改，可能会需要一点点工作，特别是如果我想维护子关系的索引号时.因此，对于处于类似情况的其他人来说，这可能是要考虑的事情.

如果确实遇到了更多可变的问题，我可能会尝试Peter Neubauer建议的集合，并且可能只是创建一个指向节点的OrderedTreeNode类，并为孩子使用List集合.

解决方案

Russel， 我们正在从事类似的工作，在作品中安排一个有序的时间树，该时间树的结构与YEAR-2012-> MONTH-01-> DAY-21-> VALUE123不同，并且在诸如同年的月份.

否则，如果您这样做，请考虑贡献它或调查 https://github.com中的内容/neo4j/graph-collections ，在那里的贡献和测试受到高度赞赏！

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.

解决方案

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!

这篇关于用neo4j建模有序树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！