Boost的图库如何链接顶点和外边列表容器？

1 回答

• 1

  邻接列表中的每个顶点项（称为 stored_vertex ）都有一个出边的容器，如果是双向的，则在边上 . 以下是 stored_vertex 的各种风格的定义：

  // 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) { }
      };
  

  如果顶点的列表类型是随机访问，则vertex_descriptor类型是std :: size_t并且表示 stored_vertex instances的向量中的顶点的索引 . 如果列表类型是基于节点的序列（如列表），则vertex_descriptor是 stored_vertex 的内存地址（强制转换为void *） . 这两种情况都提供从vertex_descriptor到底层 stored_vertex 的 O(n) 映射，从而提供到关联的边缘列表 .

  回复于 2024-04-28T15:31:08+08:00