c++ 如何在boost图库中对图形进行版本控制

enxuqcxy  于 2022-12-24  发布在  其他
关注(0)|答案(2)|浏览(168)

我使用boost graph library来表示图形数据,算法和序列化都得到了很好的支持,文档也很完整。
话虽如此,我已经到了需要“版本化我的图表”的地步,却找不到任何相关的教程或示例。

  • 在图中有效地记录版本信息,例如v1.0v1.1等,并提供简洁的方式来处理图的特定版本。
  • 处理序列化和信息检索。例如,我如何存储版本化的图形,我可以产生两个版本之间的“相对差异”吗?
    我想知道是否有一种广泛接受的算法方法或BGL特定配方适用于我的情况。

作为一个最小的示例,您可以考虑family tree example

#include <boost/config.hpp>
#include <iostream>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/tuple/tuple.hpp>
enum family
{
    Jeanie,
    Debbie,
    Rick,
    John,
    Amanda,
    Margaret,
    Benjamin,
    N
};
int main()
{
    using namespace boost;
    const char* name[] = { "Jeanie", "Debbie", "Rick", "John", "Amanda",
        "Margaret", "Benjamin" };

    adjacency_list<> g(N);
    // 1. How do I extend the graph accounting for versions?
    add_edge(Jeanie, Debbie, g);
    add_edge(Jeanie, Rick, g);
    add_edge(Jeanie, John, g);
    add_edge(Debbie, Amanda, g);
    add_edge(Rick, Margaret, g);
    add_edge(John, Benjamin, g);

    graph_traits< adjacency_list<> >::vertex_iterator i, end;
    graph_traits< adjacency_list<> >::adjacency_iterator ai, a_end;
    property_map< adjacency_list<>, vertex_index_t >::type index_map
        = get(vertex_index, g);

    // 2. How do I iterate the graph based on versions?
    for (boost::tie(i, end) = vertices(g); i != end; ++i)
    {
        std::cout << name[get(index_map, *i)];
        boost::tie(ai, a_end) = adjacent_vertices(*i, g);
        if (ai == a_end)
            std::cout << " has no children";
        else
            std::cout << " is the parent of ";
        for (; ai != a_end; ++ai)
        {
            std::cout << name[get(index_map, *ai)];
            if (boost::next(ai) != a_end)
                std::cout << ", ";
        }
        std::cout << std::endl;
    }
    return EXIT_SUCCESS;
}

我的问题带来了三个问题,我在代码中对此进行了注解:
1.如果家族树中有一个90年代的家族版本和一个2010年代的家族版本,我如何考虑v1990v2010来扩展图呢?
1.在使用特定版本时,我可以在计算中隔离或专门使用该版本的数据吗?
1.如何影响序列化?

f4t66c6m

f4t66c6m1#

看起来你想在图论库内部做版本控制。恕我直言,这超出了图论库的范围。
建议:将图形配置(节点、边和它们的属性)存储在一个文本文件中,该文件的格式应易于读入库和从库中写出。然后使用版本控制软件(例如GIT)来管理文本文件的版本。
关于"有意义的"差异,这取决于你认为什么是有意义的。然而,如果你仔细选择你的文本文件格式,你可以对差异的外观进行一些控制。
例如,一个有两个节点和一条边的图(我的例子没有属性--通常我把它们的值附加到节点或边线的末尾)

n a
n b

e a b

现在添加一个结点和一条边

n a
n b
n c

e a b
e b c

会给你一个如下的比较(取决于你使用的比较工具和选项)

对我来说,这似乎是合理的"意义"。
正如您所描述的,您的用例似乎不需要比这更复杂的东西。
这是你的描述
1.如果家族树有一个1990年代的家族版本和一个2010年代的家族版本,我如何扩展图来考虑v1990和v2010?
1.在使用特定版本时,我可以在计算中隔离或专门使用该版本的数据吗?
1.如何影响序列化?
在我的提议中:
1.图形没有扩展,版本控制由版本控制包(如GIT)完成
1.从版本控制包中 checkout 所需的版本
1.您需要仔细设计序列化格式,以便差异对您最有意义。您可以尝试使用库提供的序列化函数,但可能需要编写自己的函数以获得最大的"意义"。
如果您有比这些更多的要求,需要更复杂的东西,那么您将需要在您的问题中指定它们

2guxujil

2guxujil2#

我确实认为你正在寻找的数据结构是一个版本树。例如,一个节点可以被共享的树。
我不知道boost库中有这样的东西。
但是你可以创建你自己的数据结构来拥有这些属性。我之前已经为这个答案创建了一个:在C++中转换树(查找CowTree)。
现在我很乐意起草一些东西。但是,你的要求对选择是必不可少的。

  • 你需要能够表示什么树?我的意思是,家谱应该是严格的DAG吗?这应该是一个安全的假设,为生物家庭关系,但一旦你包括非生物关系,你可能需要更多的灵活性。
  • 从Tree到Tree存在什么样的突变?如果它们是可加的(同样,就像生物关系的历史一样),那么你可能能够利用图适配器:
  • 子图,其中以前的版本是以后版本的子图(开销将随版本数线性增长)
  • filtered_graph,其中您可以对树中的每个节点使用“版本时间戳”值;这样,版本(t)的图就可以是针对timestamp <= t过滤的最新版本的视图,最大的好处是开销是恒定的,与版本数无关。

我有许多在现有的StackOverflow答案中使用这两种适配器的例子,如果您想获得更多灵感的话。
我会在做晚餐的时候穆尔这些选择,如果我想到任何一种方法的有用的演示,我会在今晚添加它。

* 已添加 *

我刚刚想到了把图表示为一个只添加边的列表的想法;如果关系需要随时间被版本化、关系从不(或很少)消失并且顶点本身的 * 内容 * 不需要被版本化,则这将是良好的匹配。
正如您所看到的,对于示例代码来说,这可能是一个很好的匹配,这可能取决于某些算法的效率要求。为了将来的安全起见,我不会跳到这个方法,但它可能是迄今为止最有价值的。

相关问题