首页 文章

在分析boost :: graph时，是否会对顶点和边描述符或它们的迭代器进行操作？

提问于
浏览 次
1

使用BOOST图库时，我有一个完全初始化的图形实例 - 结构现在是静态的 . 我需要根据图表进行一些处理 .

我不清楚我是否应该使用顶点和边的迭代器类型，或顶点和边类型本身？

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, VertexProperty, EdgeProperty > GraphType;

typedef typename boost::graph_traits< GraphType >::vertex_descriptor VertexType;
typedef typename boost::graph_traits<GraphType>::vertex_iterator VertexIterator;

typedef typename boost::graph_traits< GraphType >::edge_descriptor   EdgeType;
typedef typename boost::graph_traits<GraphType>::out_edge_iterator EdgeIterator;

我有一个算法，我需要检查两条边是否“相同” . （最强烈的意义 . 假设图形具有连接E1（S1，T2）和E2（S1，T2）的两个平行边缘 . 边缘只能与其中一个边缘“相同” .

What's the difference between (edge_descriptor == edge_descriptor) 和 (edge_iterator == edge_iterator) ? 顶点相同的问题 .

大多数图形函数返回迭代器而不是边/顶点类型本身 .

我还需要存储一组边 . Not sure whether I should be storing EdgeType 或 EdgeIterator ?

std::vector<EdgeType>  processedEdges;
std::vector<EdgeIterator>  processedEdges;

vit = std::find( processedEdges.begin(), processedEdges.end(), anotherEdgeRef )
if ( vit == processedEdges.end() )
    doSomethingBasedOnEdgeProperty(*vit);

参考：http://www.boost.org/doc/libs/1_64_0/libs/graph/doc/adjacency_list.html

c++ boost graph iterator

1 回答

  • 2

    您应该存储描述符，而不是迭代器 .

    迭代器与逻辑范围有关，而不是图 . 迭代器可能在同一图的不同范围之间无效：

    auto range1 = out_edges(vertex1, g);
auto range2 = out_edges(vertex2, g);

assert(range1.first != range2.first); // unspecified or undefined

    相反，描述符是图形范围的 . 根据图模型，描述符可能更稳定：如果操作使迭代器无效，则它不一定使对应于相同图元素的描述符无效 .

    换句话说，这使得描述符更适用于顶点或边缘"ID" - 或者，如Boost Graph所称，它可以称为 vertex_index 或 edge_index 属性 .

    我认为这与你的问题非常接近 .

    一个警告：即便如此，描述符可能并不总是稳定的！例如：adjacency_list <vecS，vecS，directedS>
    导致顶点描述符在追加时是稳定的，但在删除时则不然 . adjacency_list <setS，listS，directedS>
    另一方面，导致顶点描述符在插入和移除时都是稳定的 . 请参阅文档部分“迭代器和描述符稳定性/失效”

    如果您需要为图元素提供完全稳定的标识，则可能需要添加一个作为（捆绑）属性 .

    回复于

相关问题