我一直在尝试制作功能图。我正在制作的图形没有循环，因此它有点像一棵树，其中某些节点可以有多个父节点。
问题是在更新时。用树的通常方法是遍历到要更新的节点，此方法的每个步骤都创建一个新节点，该节点更改为指向新的子节点，直到到达要修改的实际节点为止，然后才是实际数据改变了。
当某些节点的父节点不止一个时，采用这种方法会因为您最终基本上“ split ”了该节点。在两个父节点之间共享的节点变为两个节点，每个节点都有一个父节点，一个节点(您遍历的到达该节点的路径)具有新值，另一个父节点保留有旧值的 child 。
因此，我改为尝试将父节点存储在每个节点内，即节点知道其父节点是谁。
这行得通，但是有问题。如果更新节点，则必须更新其父节点。但是，对于其每个父节点，我不仅需要更新其父节点，还需要更新其子节点，因为其子节点存储了其父节点，并且该父节点现在已更改。
因此，要更新一个节点值，我必须更新图中的每个节点。
我的另一个想法是，不是在每个节点中存储父节点，而是在每个节点中存储到父节点的“路径”。这样，我不必更新父级的子级，因为父级的“路径”没有更改(即使节点本身也已更改)。
但是，也许有更好的方法来构建功能图？有任何想法吗？我不介意它是否不能处理带有循环的图形。我正在用Haskell进行编码，但是非编程语言的描述也可以。
最佳答案
可悲的是，您必须接受这一事实。这基本上就是为什么您不能实现有效的功能图的原因。所有允许在不遍历整个图的情况下进行更新的解决方案均基于表和索引的模型作为引用。想法如下:将所有节点存储在索引表和边缘中，而不是直接引用存储其索引的节点。有一些变体，它们具有不同的好处，但是基本上这就是整个想法。
但是，对上述内容进行更深入的思考，无非就是对内存指针实际作用的模拟。因此，基本上，您最终会重新实现一个低级的东西，而同时又大大降低了性能。因此，说实话，我建议考虑对可变图进行分割，该可变图不会共享任何这些问题。
我一直在研究graph-db项目一段时间，该项目尚未发布。但是，我发布了一些代码。我认为this mutable graph implementation可能对您有用。
关于haskell - 功能图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21350075/