我一直在尝试制作功能图。我正在制作的图表没有循环,所以它有点像一棵树,其中一些节点可以有多个父节点。
问题是更新的时候。树的通常方法是向下遍历要更新的节点,每一步都创建一个新节点,该节点被更改为指向一个新的子节点,直到到达要修改的实际节点,然后实际上是谁的数据改变了。
当某些节点有多个父节点中断时采用这种方法,因为您最终基本上“拆分”了节点。两个父节点之间共享的节点成为两个节点,每个节点都有一个父节点,一个(您遍历到该节点的路径)具有新值,另一个父节点保留一个具有旧值的子节点。
所以我改为尝试将父节点存储在每个节点内,即节点知道他们的 parent 是谁。
这行得通,但有一个问题。如果我更新一个节点,我必须更新它的父节点。但是对于它的每个 parent ,我不仅要更新他们的 parent ,还要更新他们的 child ,因为他们的 child 存储他们的父节点,而那个父节点现在已经改变了。
所以要更新一个节点值,我必须更新图中的每个节点。
我的另一个想法不是将父节点存储在每个节点中,而是将“路径”存储到每个节点中的父节点。这样我就不必更新 parent 的 child ,因为 parent 的“路径”没有改变(即使节点本身已经改变)。
但也许有更好的方法来构建函数图?有任何想法吗?我不介意它是否不处理带有循环的图形。我正在用 Haskell 编码,但非编程语言描述也可以。
最佳答案
So to update on node value I have to update each node in the entire graph.
可悲的是,你必须接受这是一个事实。这基本上就是您无法实现高效功能图的原因。所有允许更新而不遍历整个图的解决方案都是基于表和索引的模型作为引用。想法如下:将所有节点存储在索引表和边中,而不是直接引用存储其索引的节点。有一些变化,它们有不同的好处,但基本上这就是整个想法。
但是对上述内容进行更深入的思考,它只不过是对内存指针实际作用的模拟。所以基本上你最终会重新实现一个低级的东西,同时大大降低性能。所以老实说,我建议考虑迭代一个可变图,它不会共享任何这些问题。
我从事 graph-db 项目已有一段时间了,该项目尚未发布。但是,我发布了一些代码。我认为 this mutable graph implementation作为想法的来源,可能对您有用。
关于haskell - 功能图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21350075/