我有一个有向图数据结构,我试图为每个顶点实现单独的版本控制.这会产生一些有趣的场景,我非常感谢你们有任何想法.具体来说,我希望在遇到所述方案时解决系统的默认行为.
请参见下图：Graph versions
场景1：“空指针悖论”
顶点A回滚到1.0版.由于此回滚将级联其子图,因此C将不再指向D.这可能会造成危险.行为应该是：
> 1.1：删除边C – > D,创建一个破碎的图形
> 1.2：删除D,留下E孤儿
> 1.3：删除D和E.
> 1.4：在删除指向D的所有边(在本例中为E – > D)之前拒绝执行回滚
> 1.X：替代解决方案？
场景2：“间接影响”
顶点D已更新,因此以下内容成立：
> D现在是版本1.2
> E现在是1.1版
> C现在是版本1.3
> A现在是版本1.3
顶点A现在回滚到版本1.2,因此以下内容成立：
> A现在是版本1.2
> C现在是1.2版
> D现在是1.1版
默认行为应该是：
解决方法
在我看来,这里有一些关于粒度的混淆.如果您只对单个顶点进行版本而不是图形,则回滚单个顶点不应影响图形的其余部分.如果,OTOH,您希望回滚整个图形,那么您还应该对整个图形进行版本控制.
问题是,如果您只对单个顶点进行版本设置,那么您只能为各个顶点提供完整性保证,但不能对整个图形进行完整性保证.因此,如果你描述它,回滚一个单独的顶点“涟漪”整个图形(或至少连接的子图形),那么你不能保证最终处于一致的状态.
似乎与您正在尝试的最接近的研究是关于XML的版本控制,但是,它仅处理强类型树(IOW退化图),而不是一般图.
