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).
