使用图库/节点网络库还是自己写？

Question

我正在尝试在预先制作的图形/节点网络库之间做出决定,或者自己动手.

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

我不知道该怎么做的原因是我不确定预制的定制是否比首先制作我自己的更加昂贵/麻烦.我也很好奇,但不那么重要的是性能权衡.

有没有人有使用其中一个库的直接经验,并根据成功或失败的故事提出建议？我想听到最坏的情况,所以无论我选择什么,我都知道自己要进入什么.

到目前为止,我在搜索中找到的只有两个:Boost Graph Library(BGL)和GOBLIN.其中任何一方的具体建议或对他人的建议也非常受欢迎.BGL似乎非常奥术.值得挣扎吗？

Answer 1

我或许可以就BGL提供一些指导.

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

不幸的是,增强文档完全倾斜,仅提供完整复杂性的描述,而不暗示事情的简单性.

("任何足够先进的技术都与魔法无法区分"--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的语法,这样你就可以看到你的编码.

有时无法删除复杂的语法.(或者我可能没有注意到潜在的事实).然后我通常使用一个小实用程序函数来封装复杂性abd远离我正在处理的算法.

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

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.它可以简化为简单的事情,但是一旦你学会了使用它,只要你需要它就可以获得所有巨大的灵活性.

Answer 2

"需要对节点和/或边缘的类结构进行一些重要的定制."

你看过BGL的"捆绑属性"功能了吗？

http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/bundles.html

这既强大又不是最不重要的.

您可以为边和顶点定义类

class cMyVertex
{
…
};
class cMyEdge
{
…
};

现在,您定义将使用您的类的图表类型

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    cMyVertex, cMyEdge > graph_t;

现在,您可以创建此类型的图形,这些图形将使用您的类,无论它们是什么,用于顶点和边.

您可以以完全自然的方式访问类的属性和方法

Graph_t g(10)       // create a graph with 10 vertices
g[1].setA1( “alpha” );  // invoke an accessor on node #1

Answer 3

我最近给了提升图库一个Dijkstras最短路径问题的试验.结果:

• 非常高的性能

• 只需很少的代码

• 非常灵活和可扩展

• 难以理解或调试

建议:使用它但在此之前阅读 Boost Graph Library:用户指南和参考手册

Answer 4

我认为如果你可以利用图遍历算法,那么值得使用Boost Graph.创建和使用自定义顶点非常简单.BGL中包含的示例对于学习如何使用它非常有用.

我同意Clifford,我使用GraphViz来帮助在开发过程中可视化图形,并发现它非常有用.

Answer 5

您也可以尝试使用LEMON图库.

从配置文件中读取图形后,我可以用它来执行Dijsktra最短路径搜索.

新版本刚刚问世.