Cli*_*ton 5 haskell functional-programming graph data-structures
我一直在尝试制作功能图.我正在制作的图形没有循环,所以它有点像树,其中一些节点可以有多个父节点.
问题在于更新时.树的常用方法是遍历到要更新的节点,创建新节点的每一步都被更改为指向新的子节点,直到达到要修改的实际节点然后实际的数据是改变.
当某些节点有多个父节点断开时采用这种方法,因为最终基本上"拆分"节点.在两个父节点之间共享的节点变为两个节点,每个节点具有父节点,一个节点(您遍历到达节点的路径)具有新值,另一个父节点保持具有旧值的子节点.
所以我试着在每个节点内存储父节点,即节点知道他们的父母是谁.
这有效,但有一个问题.如果我更新节点,我必须更新其父节点.但是对于每个父母,我不仅要更新他们的父母,还要更新他们的孩子,因为他们的孩子存储他们的父节点,并且父节点现在已经改变了.
因此,要更新一个节点值,我必须更新图中的每个节点.
我的另一个想法是不是在每个节点中存储父节点,只是将"路径"存储到每个节点中的父节点.这样我就不必更新父节点的子节点,因为父节点的"路径"没有改变(即使节点本身有).
但也许有更好的方法来构建功能图？有任何想法吗？我不介意它是否不处理带循环的图形.我在Haskell编码,但非编程语言描述也可以.
因此,要更新节点值,我必须更新整个图中的每个节点.
可悲的是,你必须接受这个事实.这基本上就是你无法实现高效功能图的原因.所有允许在不遍历整个图形的情况下进行更新的解决方案都基于表格和索引的模型作为参考.其思路如下:将所有节点存储在索引表和边缘中,而不是直接引用存储其索引的节点.有一些变化,有不同的好处,但基本上这是整个想法.
但是想一想上面的内容,它只不过是对内存指针的实际模仿.所以基本上你最终重新实现了低级别的东西,同时性能大大降低.老实说,我建议考虑迭代一个可变图,它不会分享任何这些问题.
我一直在研究graph-db项目已有一段时间了,尚未发布.但是我发布了一些代码.我认为这个可变图形实现可能对您有用,可作为思想的来源.