blocks|key|1226862|text|我认为如果您能够利用图遍历算法，那么使用Boost+Graph是值得的。创建和使用自定义顶点非常简单。BGL附带的示例对于学习如何使用它很有用。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1226863|我同意Clifford的观点，我在开发过程中使用了GraphViz来帮助可视化图形，并且发现它非常有用。|1226864|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

I think if you can leverage the graph traversal algorithms, it is worth using the Boost Graph. Creating and using custom vertices is pretty easy. The examples included with BGL were useful for learning how to use it.

I agree with Clifford, I've used GraphViz to help visualize the graph during development and found it very useful.

blocks|key|1441820|text|也许我可以提供一些关于BGL的指导。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1441821|这个库非常灵活。这样做的代价是，为了适应所有的可能性，语法可以非常巴洛克风格。然而，它是足够灵活的，简单的事情可以简单地做。|1441822|不幸的是，boost文档全力以赴，只提供了完整的复杂性描述，而没有暗示事情有多简单。|1441823|(“任何足够先进的技术都无法与魔法区分开来”--亚瑟·C·克拉克。他应该说的是“任何先进的技术，只要有足够糟糕的文档，都无法与魔法区分开来”。|1441824|考虑一下：|1441825|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;+%2B%2Bvp.first)+{
+++std::cout+<<+index[*vp.first]+<<++"+";
}|code-block|syntax|javascript|1441826|这就是“快速浏览”建议我们打印出图形顶点列表的方式。然而，少量的研究表明，顶点只不过是一个整数索引，代码可以大大简化为|1441827|for+(int+v+=+*vertices(g).first;+v+!=+*vertices(g).second;+%2B%2Bv)
++++std::cout+<<+v+<<+"+";|1441828|也许有一些神奇的事情是不能用这个简化的代码实现的，但每天都要合理地修剪包含BGL的语法，这样你就可以看到你在写什么了。|1441829|有时复杂的语法是无法删除的。(也许我只是没有注意到潜在的事实)。然后，我通常使用一个小的实用函数来封装复杂性，并使其远离我正在研究的算法。|1441830|例如，我经常需要遍历顶点的子节点。|1441831|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;+%2B%2B(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+)|1441832|底线是:继续使用BGL。它可以简化为做简单的事情，但是一旦你学会了使用它，所有巨大的灵活性都将在你真正需要它的时候可用。|1441833|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|14|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|15|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|16|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|17|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|18|8|@]|9|@]|A|$]]|$1|J|3|K|5|L|7|19|8|@]|9|@]|A|$M|N]]|$1|O|3|P|5|6|7|1A|8|@]|9|@]|A|$]]|$1|Q|3|R|5|L|7|1B|8|@]|9|@]|A|$M|N]]|$1|S|3|T|5|6|7|1C|8|@]|9|@]|A|$]]|$1|U|3|V|5|6|7|1D|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|1E|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|L|7|1F|8|@]|9|@]|A|$M|N]]|$1|10|3|11|5|6|7|1G|8|@]|9|@]|A|$]]|$1|12|3|-4|5|6|7|1H|8|@]|9|@]|A|$]]]|13|$]]

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.

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.

( "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 )

Consider:

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

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

<pre><code>for (int v = *vertices(g).first; v != *vertices(g).second; ++v)
 std::cout &lt;&lt; v &lt;&lt; " ";
</code></pre>

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

<pre><code>vector&lt;int&gt; getVertexChildren( int v )
{
 vector&lt;int&gt; vc;
 typedef std::pair&lt;graph_traits&lt;graph_t&gt;::out_edge_iterator, graph_traits&lt;graph_t&gt;::out_edge_iterator&gt; 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&lt;int&gt; vc=getVertexChildren(v); BOOST_FOR_EACH( int child, vc )
</code></pre>

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.

blocks|key|1441870|text|“需要对节点和/或边的类结构进行一些重要的自定义。”|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1441871|您看过BGL的“捆绑属性”特性吗？|1441872|http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/bundles.html|offset|length|1441873|这既是强大的，也是一点也不令人费解的。|1441874|您可以为边和折点定义类|1441875|class+cMyVertex
{
…
};
class+cMyEdge
{
…
};|code-block|syntax|javascript|1441876|现在，定义一个将使用您的类的图类型|1441877|typedef+boost::adjacency_list<
++++boost::listS,+boost::vecS,+boost::bidirectionalS,
++++cMyVertex,+cMyEdge+>+graph_t;|1441878|现在，您可以创建这种类型的图，它将使用您的类，无论它们是什么，用于顶点和边。|1441879|您可以以一种非常自然的方式访问类的属性和方法|1441880|Graph_t+g(10)+++++++//+create+a+graph+with+10+vertices
g[1].setA1(+“alpha”+);++//+invoke+an+accessor+on+node+#1|1441881|entityMap|0|LINK|mutability|MUTABLE|url^0|0|0|0|1S|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|17|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|18|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|19|8|@]|9|@$F|1A|G|1B|1|1C]]|A|$]]|$1|H|3|I|5|6|7|1D|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|1E|8|@]|9|@]|A|$]]|$1|L|3|M|5|N|7|1F|8|@]|9|@]|A|$O|P]]|$1|Q|3|R|5|6|7|1G|8|@]|9|@]|A|$]]|$1|S|3|T|5|N|7|1H|8|@]|9|@]|A|$O|P]]|$1|U|3|V|5|6|7|1I|8|@]|9|@]|A|$]]|$1|W|3|X|5|6|7|1J|8|@]|9|@]|A|$]]|$1|Y|3|Z|5|N|7|1K|8|@]|9|@]|A|$O|P]]|$1|10|3|-4|5|6|7|1L|8|@]|9|@]|A|$]]]|11|$12|$5|13|14|15|A|$16|E]]]]

“require some significant customization to the class structure of the node and/or edges.”

Have you looked at the “bundled properties” feature of the BGL?

<a href="http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/bundles.html" rel="noreferrer">http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/bundles.html</a>

This is both powerful and not the least bit acrcane.

You define a classes for your edges and your vertices

<pre><code>class cMyVertex
{
…
};
class cMyEdge
{
…
};
</code></pre>

Now you define a graph type which will use your classes

<pre><code>typedef boost::adjacency_list&lt;
 boost::listS, boost::vecS, boost::bidirectionalS,
 cMyVertex, cMyEdge &gt; graph_t;
</code></pre>

Now you can create graphs of this type that will use your classes, whatever they are, for the vertices and edges.

You can access the attributes and methods of your classes in a perfectly natural way

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

blocks|key|1441951|text|我自己也做了。你不应该遵循这个例子，除非你绝对确定你需要这样做。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1441952|尽管如此，如果你的图论已经生疏，这仍然是一次很好的学习经历。|1441953|我用EBNF运算符组合有向图，做epsilon消除和基于Hopcroft的最小化，有很多“乐趣”。特别是在最小化的情况下，如果你可以拼命寻找有用的信息，并弄清楚它是如何工作的，那就“有趣”了:-(|1441954|如果你有自己的想法，我建议将高级操作从低级有向图数据结构中分离出来-不同的类，而不仅仅是不同的方法。我没有-很快我就会因为那个糟糕的决定而进行大量的重构。|1441955|一些图形注释节点，一些注释边，一些两者都有。有时两个注释很有用，即使它们只是一些外部数据的外键。例如，在有限状态机中，可以用输入和输出对边进行注释。您可能会对确定性WRT输入而不是输出感兴趣，所以将它们都隐藏在单个ID后面是一件很痛苦的事情-而且这还不包括用于执行这个ID引用的查找的辅助容器的整个问题。|1441956|此外，有时你只想处理那些没有明确设计为有向图IYSWIM的东西--例如，一堆相互链接的数据结构节点。|1441957|当然，如果能够插入不同的有向图表示，但仍然使用相同的高级工具进行许多操作，这是很有用的。|1441958|我写了一个“树工具”类，它可以按照树视图的顺序和XML元素的标签顺序进行迭代和下标。底层的树表示是可插入的(基于策略的模板)。对于有向图，我搞砸了。|1441959|无论如何，我不知道Boost或其他图形库实际上提供了什么，但如果它提供了您需要的东西，我建议您使用它。这会省去很多麻烦。|1441960|entityMap^0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|T|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|U|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|V|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|W|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|X|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|Y|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|Z|8|@]|9|@]|A|$]]|$1|N|3|O|5|6|7|10|8|@]|9|@]|A|$]]|$1|P|3|Q|5|6|7|11|8|@]|9|@]|A|$]]|$1|R|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|S|$]]

I rolled my own. You shouldn't follow that example, unless you're absolutely certain you need to.

Still, it's a great learning experience, if you're graph theory is rusty.

I had lots of "fun" with combining digraphs using EBNF operators, and doing epsilon elimination and Hopcroft-based minimisation. Especially with the minimisation, if you can call desperately trying to find good information and figure out how it works "fun" :-(

If you do roll your own, I recommend separating high level operations from the low level digraph data structures - different classes, not just different methods. I didn't - and pretty soon I'll be refactoring heavily because of that poor decision.

Some graphs annotate nodes, some annotate edges, some both. Sometimes two annotations are useful, even if they're just foreign keys for some external data. For example in finite state machines, an edge may be annotated with an input and an output. You're likely to be interested in determinism WRT the input but not the output, so having them both hidden behind a single ID is a pain - and that's besides the whole issue of secondary containers for the what-does-this-ID-refer-to lookups.

Also, sometimes you just want to work with things that weren't designed explicitly as a digraph IYSWIM - e.g. a bunch of data structure nodes that link to each other.

IOW, it's useful to be able to plug in different digraph representations, yet still use the same high-level tools for many operations.

IMO I got it right when I wrote a 'tree tool' class which does things like iterating and subscripting in treeview order and XML element tag order. The underlying tree representation is pluggable (policy based template). With digraphs, I messed up.

Anyway, I don't know what Boost or any other graph library actually provides, but if it provides what you need I say use it. It'll save a lot of headaches.

blocks|key|1227077|text|您也可以尝试使用LEMON图形库。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1227078|在从配置文件中读取图形后，我可以使用它来执行Dijsktra最短路径搜索。|1227079|一个新版本刚刚问世。|1227080|entityMap|0|LINK|mutability|MUTABLE|url|http://lemon.cs.elte.hu/trac/lemon/^0|8|5|0|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@$A|Q|B|R|1|S]]|C|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@]|C|$]]|$1|H|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|I|$J|$5|K|L|M|C|$N|O]]]]

You may also take a try with <a href="http://lemon.cs.elte.hu/trac/lemon/" rel="noreferrer">LEMON</a> graph library.

I could use it to perform Dijsktra shortest path search after reading the graph from a configuration file.

A new version has just come out.

blocks|key|1227119|text|在决定构建自己的图形库之前，我会先好好看看igraph+(http://igraph.sourceforge.net/)。它是用C语言编写的，速度非常快，提供了更广泛的基本和高级图形算法(包括可视化)。此外，它有一个用于快速编码的python包装器，所以我认为这个解决方案结合了编码速度和执行速度。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1227120|entityMap|0|LINK|mutability|MUTABLE|url|http://igraph.sourceforge.net/^0|T|U|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

Before deciding to build your own graph library, I would have a good look at igraph (<a href="http://igraph.sourceforge.net/" rel="nofollow noreferrer">http://igraph.sourceforge.net/</a>). It is written in C and is extremely fast and offers a wider range of basic and advanced graph algorithms (including visualization). In addition, it has a python wrapper for fast coding so I think this solution combines speed of coding and speed of execution.

blocks|key|1227197|text|我经常使用BGL，但让我困扰的是BGL缺乏基本的算法，比如边和顶点连通性，最小代价流，以及通用的最大权重完美匹配，这些都是我最怀念的。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1227198|LEMON提供了所有这些功能，而且语法也更简单，让我对LEMON感到困扰的是WINDOWS平台上的安装和编译问题，但我可能会改用LEMON，尽管存在这些问题。|1227199|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

I use the BGL very much, but what disturbs me with BGL is the lack of basic algorithms like edge and vertex connectivity, min cost flow and, general maximum weight perfect matching, just to name those which I miss the most.

LEMON offers all of that and also has a simpler syntax, what bugs me with LEMON is the installation and compilation problems on WINDOWS platforms, but I will probably switch to LEMON despite those problems.

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.

There are only two that I've found in my search so far: <a href="http://www.boost.org/doc/libs/1_40_0/libs/graph/doc/index.html" rel="noreferrer">The Boost Graph Library (BGL)</a> and <a href="http://goblin2.sourceforge.net/" rel="noreferrer">GOBLIN</a>. 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?

Use a Graph Library/Node Network Library or Write My Own?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我正在尝试决定是使用预制的图/节点网络库，还是使用自己的网络库。我正在实现一些图搜索算法，这可能需要对节点和/或边的类结构进行一些重要的定制。我不确定该做什么的原因是，我不确定定制一个预先制作的产品是否会比一开始自己做一个更昂贵/更麻烦。我对性能的权衡也很好奇，但不是很好奇。有没有人有使用这些库的直接经验，并有基于成功...

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

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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