stapl::sequential::vdg_storage_list< Traits > Class Template Reference

An adjacency list using an std::list for storing vertices. Used inside the adjacency_list_model to store vertices. More...

Public Member Functions
	vdg_storage_list (size_t nv=0)
	Constructs a storage with the given number of vertices starting from zero (0). Vertices have contiguous descriptors. More...
	vdg_storage_list (this_type const &other)
void	resize (size_t nv)
	Resize the internal storage to accommodate specified number of vertices.
iterator	begin ()
const_iterator	begin () const
iterator	end ()
const_iterator	end () const
size_t	size () const
	Returns the number of vertices in the storage; for use in g.num_vertices().
vertex_descriptor	add_vertex (vertex_descriptor &vd)
	Adds vertex to the storage with the given vertex descriptor. More...
vertex_descriptor	add_vertex (vertex_property const &vp)
	Adds vertex to the storage with the given vertex property. The descriptor is assigned automatically using the descriptor generator. More...
vertex_descriptor	add_vertex (vertex_descriptor vd, vertex_property const &vp)
	Adds vertex to the storage with the given descriptor and property. More...
bool	delete_vertex (vertex_descriptor const &vd, iterator const &vi)
	Deletes the vertex pointed to by the specified iterator. More...
void	clear (void)
	Clears the storage container of all vertices and edges, and resets the vertex descriptor generator.
iterator	find_vertex (vertex_descriptor const &vd_input)
	Returns an iterator to the specified vertex, or returns an iterator to this->end() if the vertex does not exist. More...
void	update_descriptor (vertex_descriptor &vd, iterator const &vi)
	Updates a versioning descriptor with the new iterator.
vertex_descriptor	get_max_descriptor () const
	Returns the current max descriptor.

Public Types
typedef Traits::vertex_descriptor	vertex_descriptor
typedef Traits::vertex_property	vertex_property
typedef Traits::edge_type	edge_type
typedef adjacency_descriptor_impl< edge_type >	edgelist_type
typedef select_vertex< vertex_descriptor, vertex_property, edgelist_type >::type	vertex_impl_type
typedef vdg_base_list< vertex_descriptor >	vdg_type
	Type of the vertex descriptor generator.
typedef std::list< vertex_impl_type >	vertex_set_type
	The vertices are stored in an std::list.
typedef vertex_set_type::iterator	iterator
typedef vertex_set_type::const_iterator	const_iterator

Protected Attributes
vdg_type	m_vdg
	The vertex descriptor generator.
vertex_set_type	m_storage
	The container for storing vertices.

Detailed Description

template<class Traits>
class stapl::sequential::vdg_storage_list< Traits >

An adjacency list using an std::list for storing vertices. Used inside the adjacency_list_model to store vertices.

Template Parameters

Traits

The traits class for specifying the types of descriptors, storages, edges and vertices. Contains the physical storage for the Graph, and provides functionality to Add/Delete/Find vertices, and Iterators to access the storage from outside.

Note

This is a versioning storage, i.e., it maintains and supports smart descriptors that can provide faster vertex-lookups if they are reused often.

Constructor & Destructor Documentation

vdg_storage_list()

template<class Traits >

stapl::sequential::vdg_storage_list< Traits >::vdg_storage_list

(

size_t

nv = 0

)

Constructs a storage with the given number of vertices starting from zero (0). Vertices have contiguous descriptors.

Parameters

nv	The number of vertices to be initially stored.

Member Function Documentation

add_vertex() [1/3]

template<class Traits >

vertex_descriptor stapl::sequential::vdg_storage_list< Traits >::add_vertex

(

vertex_descriptor &

vd

)

Adds vertex to the storage with the given vertex descriptor.

Parameters

vd	The vertex descriptor of the added vertex.

Returns

The descriptor of the added vertex.

add_vertex() [2/3]

template<class Traits >

vertex_descriptor stapl::sequential::vdg_storage_list< Traits >::add_vertex

(

vertex_property const &

vp

)

Adds vertex to the storage with the given vertex property. The descriptor is assigned automatically using the descriptor generator.

Parameters

vp	The vertex property of the added vertex.

Returns

The descriptor of the added vertex.

add_vertex() [3/3]

template<class Traits >

vertex_descriptor stapl::sequential::vdg_storage_list< Traits >::add_vertex	(	vertex_descriptor	vd,
		vertex_property const &	vp
	)

Adds vertex to the storage with the given descriptor and property.

Parameters

vd	The explicit descriptor of the added vertex.
vp	The vertex property of the added vertex.

Returns

The descriptor of the added vertex.

delete_vertex()

template<class Traits >

bool stapl::sequential::vdg_storage_list< Traits >::delete_vertex	(	vertex_descriptor const &	vd,
		iterator const &	vi
	)

Deletes the vertex pointed to by the specified iterator.

Parameters

vi	The iterator of the vertex to be deleted.

Returns

Whether or not the vertex was successfully deleted.

find_vertex()

template<class Traits >

iterator stapl::sequential::vdg_storage_list< Traits >::find_vertex

(

vertex_descriptor const &

vd_input

)

Returns an iterator to the specified vertex, or returns an iterator to this->end() if the vertex does not exist.

Note

Checks with VDG_Base if iterator version of given descriptor is valid. Returns VD.Iterator() if valid (O(1)), or searches storage for correct iterator otherwise (O(n)).

---

The documentation for this class was generated from the following file:

• vdg_storage_list.h