使用图形库/节点网络库还是自己编写?

2021-12-24 00:00:00 graph templates c++ boost boost-graph

我正在尝试决定是使用预先制作的图形/节点网络库还是自己推出.

I'm trying to decide between going with a pre-made graph/node network library or to roll my own.

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

I'm implementing some graph search algorithms which might require some significant customization to the class structure of the node and/or edges.

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

The reason I'm not sure what to do is that I'm unsure if customization of a pre-made might be more expensive/trouble than making my own in the first place. I'm also curious, but less so, of the performance trade-offs.

有没有人有直接使用其中一个库的经验并根据成功或失败的故事提出建议?我想听到最坏的结果,这样无论我选择什么,我都知道自己在做什么.

Is there anyone out there have direct experience with using one of the libraries out there and have advice based on a success or failure story? I want to hear the worst so that whatever I chose, I know what I'm getting into.

到目前为止,我在搜索中只找到了两个:Boost 图库 (BGL) 和 GOBLIN.对其中任何一个的具体建议或对其他人的建议也非常感谢.BGL 看起来非常该死的神秘.值得努力吗?

There are only two that I've found in my search so far: The Boost Graph Library (BGL) and GOBLIN. Specific advice on either of these, or suggestions for others is greatly appreciated as well. BGL seems pretty damn arcane. Is it worth struggling through?

推荐答案

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

I can perhaps provide a little guidance on the BGL.

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

The library is very flexible. The cost of this is that the syntax can be very baroque, in order to accommodate all the possibilities. However, it is sufficiently flexible that simple things can be done simply.

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

Unfortunately the boost documentation goes at things full tilt, providing a description only of the full complexity, without a hint of how simple things can be.

(任何足够先进的技术都无法与魔法区分开来" - Arthur C. Clarke.他应该说的是任何先进的技术,只要有足够的记录,都无法与魔法区分开来)

( "Any sufficiently advanced technology is indistinguishable from magic" - Arthur C. Clarke. What he should have said is "Any advanced technology, sufficiently badly documented, is indistinguishable from magic )

考虑:

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] <<  " ";
}

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

This is how the "quick tour" suggests we print out a list of the graph vertices. However, a little study shows that a vertex is no more than an integer index, and the code can be greatly simplified to

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

也许有一些神奇的事情是用这个简化的代码无法实现的,但每天都可以合理地使用它来彻底修剪包含 BGL 的语法,这样你就可以看到你在编码什么.

Perhaps there are some magical things that cannot be achieved with this simplified code, but for every day use it reasonable to drastically prune the syntax that encrust BGL so you can see what your are coding.

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

Sometimes the elaborate syntax cannot be removed. ( Or perhaps I have just not noticed the underlying truth ). Then I usually use a little utility function to encapsulate the complexity abd keep it away from the algorithm I am working on.

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

For example, I often need to loop over the children of a vertex

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.它可以简化为做简单的事情,但是一旦您学会了使用它,所有巨大的灵活性将在您需要时随时可用.

The bottom line is: go ahead and use BGL. It can be simplified to do simple things, but once you have learned to use it, all the immense flexibility will be available whenever you do need it.

相关文章