Boost的图形库如何链接顶点和边缘列表容器？ [英] How does Boost's graph library link vertex and out-edge list containers?

问题描述

根据 Boost的文档，顶点有两个主要容器类型及其相应的出边，默认值为两者的向量。

两者之间是否有任何关联，如同一张地图，关键是顶点，而值是一个向外边缘的向量？或者你知道每个顶点指向什么，因为顶点在顶点列表中被存储为一个唯一的int，其中每个顶点将像某种矢量矢量的索引，其中每个矢量都包含该矢量的输出边缘顶点？

基本上，在Boost邻接列表中，如何将顶点链接到其对应的出线边缘列表中？

解决方案

邻接列表中的每个顶点项目，称为 stored_vertex ，都有一个out边的容器，如果是双向的， 。以下是定义 stored_vertex 各种风格的方式：

  // stored_vertex和StoredVertexList 
 typedef typename container_gen< VertexListS，vertex_ptr> :: type 
 SeqStoredVertexList; 
 struct seq_stored_vertex {
 seq_stored_vertex（）{} 
 seq_stored_vertex（const VertexProperty& p）：m_property（p）{} 
 OutEdgeList m_out_edges; 
 VertexProperty m_property; 
 typename SeqStoredVertexList :: iterator m_position; 
}; 
 struct bidir_seq_stored_vertex {
 bidir_seq_stored_vertex（）{} 
 bidir_seq_stored_vertex（const VertexProperty& p）：m_property（p）{} 
 OutEdgeList m_out_edges; 
 InEdgeList m_in_edges; 
 VertexProperty m_property; 
 typename SeqStoredVertexList :: iterator m_position; 
}; 
 struct rand_stored_vertex {
 rand_stored_vertex（）{} 
 rand_stored_vertex（const VertexProperty& p）：m_property（p）{} 
 OutEdgeList m_out_edges; 
 VertexProperty m_property; 
}; 
 struct bidir_rand_stored_vertex {
 bidir_rand_stored_vertex（）{} 
 bidir_rand_stored_vertex（const VertexProperty& p）：m_property（p）{} 
 OutEdgeList m_out_edges; 
 InEdgeList m_in_edges; 
 VertexProperty m_property; 
}; 
 
 //！这将生成基于
 //的实际stored_vertex类型！容器类型。 
 typedef typename mpl :: if_< is_rand_access，
 typename mpl :: if_< BidirectionalT，
 bidir_rand_stored_vertex，rand_stored_vertex> :: type，
 typename mpl :: if_< BidirectionalT，
 bidir_seq_stored_vertex，seq_stored_vertex> :: type 
> :: type StoredVertex; 
 struct stored_vertex：public StoredVertex {
 stored_vertex（）{} 
 stored_vertex（const VertexProperty& p）：StoredVertex（p）{} 
}; 
  

如果顶点的列表类型是随机访问，那么vertex_descriptor类型是std :: size_t并且代表 stored_vertex 实例向量中顶点的索引。如果列表类型是基于节点的序列（如列表），那么vertex_descriptor是 stored_vertex （转换为void *）的内存地址。任何一种情况下都提供从vertex_descriptor到底层的 stored_vertex 的映射，从而提供 O（n）关联的边列表（s ）。

According to Boost's documentation, there are two main container types for vertices and their corresponding outgoing edges, with the defaults being vectors for both.

Is there any linking between the two going on, as with a map, with the key being the vertex and the value being a vector of outgoing edges? Or do you know what each vertex points to due to the fact that vertices are stored as a unique int in a vertex list, where each vertex would be like an index into some kind of vector of vectors, where every vector holds outgoing edges of that vertex?

Basically, how is a vertex linked together to its corresponding list of outgoing edges in a Boost adjacency list?

解决方案

Each vertex item, called a stored_vertex, in the adjacency list has a container of out edges and if bidirectional, in edges. Here is how the various flavors of stored_vertex are defined:

    // stored_vertex and StoredVertexList
    typedef typename container_gen<VertexListS, vertex_ptr>::type
      SeqStoredVertexList;
    struct seq_stored_vertex {
      seq_stored_vertex() { }
      seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
      OutEdgeList m_out_edges;
      VertexProperty m_property;
      typename SeqStoredVertexList::iterator m_position;
    };
    struct bidir_seq_stored_vertex {
      bidir_seq_stored_vertex() { }
      bidir_seq_stored_vertex(const VertexProperty& p) : m_property(p) { }
      OutEdgeList m_out_edges;
      InEdgeList m_in_edges;
      VertexProperty m_property;
      typename SeqStoredVertexList::iterator m_position;
    };
    struct rand_stored_vertex {
      rand_stored_vertex() { }
      rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
      OutEdgeList m_out_edges;
      VertexProperty m_property;
    };
    struct bidir_rand_stored_vertex {
      bidir_rand_stored_vertex() { }
      bidir_rand_stored_vertex(const VertexProperty& p) : m_property(p) { }
      OutEdgeList m_out_edges;
      InEdgeList m_in_edges;
      VertexProperty m_property;
    };

    //! This generates the actual stored_vertex type based on 
    //! the container type.
    typedef typename mpl::if_<is_rand_access,
      typename mpl::if_<BidirectionalT,
        bidir_rand_stored_vertex, rand_stored_vertex>::type,
      typename mpl::if_<BidirectionalT,
        bidir_seq_stored_vertex, seq_stored_vertex>::type
    >::type StoredVertex;
    struct stored_vertex : public StoredVertex {
      stored_vertex() { }
      stored_vertex(const VertexProperty& p) : StoredVertex(p) { }
    };

If the list type for vertices is random access, then the vertex_descriptor type is std::size_t and represents the index of the vertex in the vector of stored_vertex instances. If the list type is a node based sequence (like list), then the vertex_descriptor is the memory address of the stored_vertex (cast to void*). Either case offers O(n) mapping from the vertex_descriptor to the underlying stored_vertex and hence to the associated edge list(s).

这篇关于Boost的图形库如何链接顶点和边缘列表容器？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！