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

查看:35
本文介绍了使用 neo4j 对有序树建模的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我刚刚开始使用 neo4j,我了解图形和关系的原理,但是我在想要建模的某些结构上遇到了一些麻烦.我想在编程语言项目中使用它,并存储解析源文件的 AST.从那里开始,我计划向节点添加大量额外数据和关系以帮助分析和工具,但基础 AST 仍然有点困难.

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

我想到了两种基本方法.一种是为每个 CHILD 关系添加一个索引/序数属性.另一种是对第一个孩子有一个 FIRST 关系,每个孩子之间有一个 NEXT 关系,以这种方式维持秩序.

对于这两种方法中的任何一种,它似乎仍然没有任何开箱即用的东西可以用来以正确的顺序遍历它.我想如果我先/下一个,只要我强制 neo4j 总是先遍历 FIRST 并进行深度优先搜索,我就可以获得正确的顺序.那行得通吗?有没有更好的办法?这似乎应该更容易处理.

更新

最终我决定使用我的两个想法.子节点与索引属性具有 CHILD 关系.第一个孩子也有 FIRST_CHILD 关系.兄弟节点有一个 NEXT_SIBLING 关系来给出正确的排序.之后,遍历就很容易了:

//可重用的遍历描述最终私有 TraversalDescription AST_TRAVERSAL = Traversal.description().深度优先().expand(new OrderedByTypeExpander().add(RelType.FIRST_CHILD, Direction.OUTGOING).add(RelType.NEXT_SIBLING, Direction.OUTGOING));

然后当我真的需要走那棵树时,我就可以了

for(Path path : AST_TRAVERSAL.traverse(astRoot)){//在这里做事}

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

如果我确实研究了一些更易变的东西,我可能会尝试 Peter Neubauer 建议的集合,并且可能只会创建一个 OrderedTreeNode 类,指向一个节点并为孩子使用 List 集合.

解决方案

Russel,我们正在做这样的事情,在工作中有一个有序的时间树,它的结构很大程度上遵循不同的 YEAR-2012->MONTH-01->DAY-21->VALUE123 并且可能会有 NEXT 关系,例如同年的 MONTH.

否则,如果您这样做,请考虑贡献它或调查 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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆