c++ - 使用图形库/节点网络库还是自己编写？

Question

我正在尝试决定是使用预制的图形/节点网络库还是自己动手。

我正在实现一些图形搜索算法，这些算法可能需要对节点和/或边的类结构进行一些重要的自定义。

我不确定该怎么做的原因是，我不确定定制预制件是否会比自己制作更昂贵/更麻烦。我也很好奇，但不太关心性能权衡。

有没有人有使用其中一个库的直接经验，并根据成功或失败的故事提出建议？我想听听最坏的情况，这样无论我选择什么，我都知道我要做什么。

到目前为止，我在搜索中只找到了两个:The Boost Graph Library (BGL)和 GOBLIN .对其中任何一个的具体建议或对其他人的建议也非常感谢。 BGL 看起来非常神秘。值得挣扎吗？

Answer 1

我或许可以提供一些关于 BGL 的指导。

图书馆非常灵活。这样做的代价是语法可能非常巴洛克，以适应所有可能性。但是，它足够灵活，可以简单地完成简单的事情。

不幸的是，boost 文档完全倾斜，只提供了完整复杂性的描述，没有暗示事情有多简单。

(“任何足够先进的技术都无法与魔法区分开来” - Arthur C. Clarke。他应该说的是“任何先进的技术，如果记录得不够充分，就无法与魔法区分开来)

考虑:

typedef property_map<Graph, vertex_index_t>::type IndexMap;
IndexMap index = get(vertex_index, g);
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = vertices(g); vp.first != vp.second; ++vp.first) {
   std::cout << index[*vp.first] <<  " ";
}

这就是“快速浏览”建议我们打印出图顶点列表的方式。但是一点研究表明，一个顶点不过是一个整数索引，代码可以大大简化为

for (int v = *vertices(g).first; v != *vertices(g).second; ++v)
    std::cout << v << " ";

也许有一些神奇的事情不能用这个简化的代码来实现，但是每天使用它来合理地大幅修剪包裹 BGL 的语法，这样你就可以看到你在编码什么。

有时无法删除复杂的语法。 (或者也许我只是没有注意到潜在的真相)。然后我通常会使用一些实用函数来封装复杂性，并使其远离我正在研究的算法。

例如，我经常需要遍历一个顶点的子节点

vector<int> getVertexChildren( int v )
{
    vector<int> vc;
    typedef std::pair<graph_traits<graph_t>::out_edge_iterator, graph_traits<graph_t>::out_edge_iterator> out_edge_iter_pair_t;
    for( out_edge_iter_pair_t ep = out_edges(v,m_tree);
        ep.first != ep.second; ++(ep.first))
    {
        vc.push_back( target( *ep.first, m_tree ) );
    }
    return vc;
}
#define FOR_ALL_CHILDREN( v ) vector<int> vc=getVertexChildren(v); BOOST_FOR_EACH( int child, vc )

底线是:继续使用 BGL。它可以简化为做简单的事情，但一旦你学会使用它，所有巨大的灵 active 将在你需要时随时可用。