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

Adjacency list implementation of the sequential graph. More...

Public Member Functions
	adjacency_list_graph (size_t size=0)
vertex_iterator	begin ()
const_vertex_iterator	begin () const
vertex_iterator	end ()
const_vertex_iterator	end () const
edge_iterator	edges_begin ()
	Returns an edge iterator to the first edge in the entire adjacency-list.
const_edge_iterator	edges_begin () const
	Returns an edge iterator to the first edge in the adjacency-list.
edge_iterator	edges_end ()
	Returns an edge iterator to one past the last edge in the adjacency-list.
const_edge_iterator	edges_end () const
	Returns an edge iterator to the last edge in the adjacency-list.
size_t	get_num_vertices () const
	Returns the total number of vertices.
size_t	get_max_descriptor () const
	Returns the largest vertex id.
size_t	get_num_edges () const
	Returns the total number of edges.
vertex_descriptor	add_vertex ()
	Adds vertex with the default vertex property. A descriptor is automatically generated for the new vertex. More...
vertex_descriptor	add_vertex (const vertex_property &vp)
	Adds vertex with the specified vertex property. A descriptor is automatically generated for the new vertex. More...
vertex_descriptor	add_vertex (vertex_descriptor vd, const vertex_property &vp)
	Adds vertex to the storage with the given descriptor and property. Useful, for example, when reading the graph from the file or when the user wants to explicitly control the descriptors. More...
edge_descriptor	add_edge (const edge_descriptor &ed)
	Adds an edge with given descriptor and default edge property. More...
edge_descriptor	add_edge (const edge_descriptor &ed, const edge_property &p)
	Adds an edge with given descriptor and edge property. More...
bool	set_edge (const vertex_descriptor &v, const size_t i, const vertex_descriptor &neighbor)
	Sets i-th neighbor of v to the specified neighbor vertex. More...
bool	set_edge (const vertex_descriptor &v, const size_t i, const size_t max, const vertex_descriptor &neighbor)
	Sets i-th neighbor of v to the specified neighbor vertex. Expands the edgelist to the specified max, if current size is smaller. More...
void	clear (void)
	Erases all vertices and edges in the graph.
void	delete_all_edges_to_v (const vertex_descriptor &vd)
	Deletes all edges with the specified vertex as their target. For internal use by delete_vertex. More...
bool	delete_vertex (const vertex_descriptor &vd)
	Deletes the specified vertex and all edges pointing to and from it. More...
bool	delete_edge (const edge_descriptor &ed)
	Deletes the edge with given descriptor. More...
bool	find_edge (const edge_descriptor &ed, vertex_iterator &vi, adj_edge_iterator &ei)
	Finds the edge with the specified descriptor, and sets an iterator to its source vertex and an adj_edge_iterator pointing to the edge. More...
bool	find_edge (const edge_descriptor &ed, const_vertex_iterator &vi, const_adj_edge_iterator &ei) const
	Finds the edge with the specified descriptor, and sets an iterator to its source vertex and an adj_edge_iterator pointing to the edge. More...
const_vertex_iterator	find_vertex (vertex_descriptor const &vd) const
	Finds the vertex with the specified descriptor, and returns a vertex_iterator pointing to it. If not found, the end of the graph is returned. More...
vertex_iterator	find_vertex (vertex_descriptor const &vd)
	Finds the vertex with the specified descriptor, and returns a vertex_iterator pointing to it. If not found, the end of the graph is returned. More...
void	update_descriptor (vertex_descriptor &vd, vertex_iterator &vi)
	Updates given descriptor's version info, provided the iterator is valid. If iterator is not valid, it is updated with a call to find(). More...

Public Types
typedef Traits::vertex_descriptor	vertex_descriptor
typedef Traits::simple_vertex_descriptor	simple_vertex_descriptor
typedef Traits::edge_descriptor	edge_descriptor
typedef Traits::vertex_property	vertex_property
typedef Traits::edge_property	edge_property
typedef select_vertex_iterator< typename vertex_set_type::iterator, vertex_property >::type	vertex_iterator
typedef select_const_vertex_iterator< typename vertex_set_type::const_iterator, vertex_property >::type	const_vertex_iterator
typedef vertex_iterator	iterator
typedef const_vertex_iterator	const_iterator
typedef edgelist_type::iterator	adj_edge_iterator
	Iterator over adjacent edges of a vertex.
typedef edgelist_type::const_iterator	const_adj_edge_iterator
	Const iterator over adjacent edges of a vertex.
typedef edge_iterator_adaptor< vertex_iterator >	edge_iterator
	Edge iterator over all edges in the graph.
typedef edge_iterator_adaptor< const_vertex_iterator >	const_edge_iterator
	Const edge iterator over all edges in the graph.

Protected Types
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 Traits::storage_type	vertex_set_type
	Vertex storage type.

Protected Attributes
vertex_set_type	m_vertices
	Set of vertices.
size_t	m_ne
	Number of edges.
size_t	m_eid
	Used to generate unique edge ids.

Friends
void	add_internal_edge (this_type &g, const edge_descriptor &ed, const edge_property &p)
	Adds an edge with the given edge_descriptor. The edge_descriptor provided must have the id field assigned prior to the call to this method. This is used by the undirected graph to add sibling edges which share the same edge id. More...
edge_descriptor	add_edge_pair (this_type &g, const edge_descriptor &edr, const edge_property &epy)
	Adds two edges: one from source to target of the specified descriptor and the other from the target to source. Adds first to the vertex with the smaller id of source() and target(). This will generate the id of the edge and this id will be the same in the second (sibling) edge added. This is important to match the edges when there are duplicates. Uses add_internal_edge to add the sibling edge. More...

Detailed Description

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

Adjacency list implementation of the sequential graph.

Template Parameters

Traits

Traits class which specifies types of descriptors, storage, etc.

This is a base class and it implements the following graph concepts: adjacency_graph, static_graph, dynamic_graph. Other graph concepts, such as directed, undirected, multiedges, and non-multiedges are implemented as derived classes.

Constructor & Destructor Documentation

adjacency_list_graph()

template<class Traits >

stapl::sequential::adjacency_list_graph< Traits >::adjacency_list_graph

(

size_t

size = 0

)

Parameters

size	Number of vertices in the new graph.

Member Function Documentation

add_vertex() [1/3]

template<class Traits >

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

(

void

)

Adds vertex with the default vertex property. A descriptor is automatically generated for the new vertex.

Returns

The descriptor of the added vertex.

add_vertex() [2/3]

template<class Traits >

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

(

const vertex_property &

vp

)

Adds vertex with the specified vertex property. A descriptor is automatically generated for the new vertex.

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::adjacency_list_graph< Traits >::add_vertex	(	vertex_descriptor	vd,
		const vertex_property &	vp
	)

Adds vertex to the storage with the given descriptor and property. Useful, for example, when reading the graph from the file or when the user wants to explicitly control the descriptors.

Parameters

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

Returns

The descriptor of the added vertex.

add_edge() [1/2]

template<class Traits >

edge_descriptor stapl::sequential::adjacency_list_graph< Traits >::add_edge

(

const edge_descriptor &

ed

)

Adds an edge with given descriptor and default edge property.

Parameters

ed	Descriptor of the desired edge.

Returns

edge_descriptor of the added edge. edge_descriptor.id() is set to numeric_limits<size_t>::max() if edge was not added.

add_edge() [2/2]

template<class Traits >

edge_descriptor stapl::sequential::adjacency_list_graph< Traits >::add_edge	(	const edge_descriptor &	ed,
		const edge_property &	p
	)

Adds an edge with given descriptor and edge property.

Parameters

ed	Descriptor of the desired edge.
p	Property of the edge.

Returns

edge_descriptor of the added edge. edge_descriptor.id() is set to numeric_limits<size_t>::max() if edge was not added.

set_edge() [1/2]

template<class Traits >

bool stapl::sequential::adjacency_list_graph< Traits >::set_edge	(	const vertex_descriptor &	v,
		const size_t	i,
		const vertex_descriptor &	neighbor
	)

Sets i-th neighbor of v to the specified neighbor vertex.

Parameters

v	Descriptor of the source vertex.
i	The index of the target neighbor vertex.
neighbor	The descriptor of the target neighbor vertex.

Returns

True if the vertex and edge exist, False otherwise.

set_edge() [2/2]

template<class Traits >

bool stapl::sequential::adjacency_list_graph< Traits >::set_edge	(	const vertex_descriptor &	v,
		const size_t	i,
		const size_t	max,
		const vertex_descriptor &	neighbor
	)

Sets i-th neighbor of v to the specified neighbor vertex. Expands the edgelist to the specified max, if current size is smaller.

Parameters

v	Descriptor of the source vertex.
i	The index of the target neighbor vertex.
max	The maximum size to expand the edgelist to.
neighbor	The descriptor of the target neighbor vertex.

Returns

True if the vertex exists, False otherwise.

delete_all_edges_to_v()

template<class Traits >

void stapl::sequential::adjacency_list_graph< Traits >::delete_all_edges_to_v

(

const vertex_descriptor &

vd

)

Deletes all edges with the specified vertex as their target. For internal use by delete_vertex.

Parameters

vd	The descriptor of the vertex.

delete_vertex()

template<class Traits >

bool stapl::sequential::adjacency_list_graph< Traits >::delete_vertex

(

const vertex_descriptor &

vd

)

Deletes the specified vertex and all edges pointing to and from it.

Parameters

vd	The descriptor of the vertex.

Returns

Whether or not the vertex was successfully deleted.

delete_edge()

template<class Traits >

bool stapl::sequential::adjacency_list_graph< Traits >::delete_edge

(

const edge_descriptor &

ed

)

Deletes the edge with given descriptor.

Parameters

ed	Descriptor of the desired edge.

Returns

Whether or not the edge was successfully deleted.

find_edge() [1/2]

template<class Traits >

bool stapl::sequential::adjacency_list_graph< Traits >::find_edge	(	const edge_descriptor &	ed,
		vertex_iterator &	vi,
		adj_edge_iterator &	ei
	)

Finds the edge with the specified descriptor, and sets an iterator to its source vertex and an adj_edge_iterator pointing to the edge.

Parameters

ed	Descriptor of the edge.
vi	vertex_iterator pointing to the source vertex of the edge, populated by the method.
aei	adj_edge_iterator pointing to the specified edge, populated by the method.

Returns

Whether or not the edge was found.

find_edge() [2/2]

template<class Traits >

bool stapl::sequential::adjacency_list_graph< Traits >::find_edge	(	const edge_descriptor &	ed,
		const_vertex_iterator &	vi,
		const_adj_edge_iterator &	ei
	)		const

Finds the edge with the specified descriptor, and sets an iterator to its source vertex and an adj_edge_iterator pointing to the edge.

Parameters

ed	Descriptor of the edge.
vi	vertex_iterator pointing to the source vertex of the edge, populated by the method.
aei	adj_edge_iterator pointing to the specified edge, populated by the method.

Returns

Whether or not the edge was found.

find_vertex() [1/2]

template<class Traits >

const_vertex_iterator stapl::sequential::adjacency_list_graph< Traits >::find_vertex

(

vertex_descriptor const &

vd

)

const

Finds the vertex with the specified descriptor, and returns a vertex_iterator pointing to it. If not found, the end of the graph is returned.

Parameters

vd	Descriptor of the vertex.

Returns

A vertex_iterator to the specified vertex, if found, or a vertex_iterator to the end of the graph otherwise.

find_vertex() [2/2]

template<class Traits >

vertex_iterator stapl::sequential::adjacency_list_graph< Traits >::find_vertex

(

vertex_descriptor const &

vd

)

Finds the vertex with the specified descriptor, and returns a vertex_iterator pointing to it. If not found, the end of the graph is returned.

Parameters

vd	Descriptor of the vertex.

Returns

A vertex_iterator to the specified vertex, if found, or a vertex_iterator to the end of the graph otherwise.

update_descriptor()

template<class Traits >

void stapl::sequential::adjacency_list_graph< Traits >::update_descriptor	(	vertex_descriptor &	vd,
		vertex_iterator &	vi
	)

Updates given descriptor's version info, provided the iterator is valid. If iterator is not valid, it is updated with a call to find().

Parameters

vd	Descriptor of the edge.
vi	A vertex_iterator pointing to the specified vertex.

Friends And Related Function Documentation

add_internal_edge

template<class Traits >

void add_internal_edge ( this_type &  g, const edge_descriptor &  ed, const edge_property &  p  )

friend

Adds an edge with the given edge_descriptor. The edge_descriptor provided must have the id field assigned prior to the call to this method. This is used by the undirected graph to add sibling edges which share the same edge id.

Parameters

g	The graph to which the edge will be added.
ed	The descriptor of the edge to be added. Id of the descriptor must have been externally assigned.
p	The property of the edge being added.

add_edge_pair

template<class Traits >

edge_descriptor add_edge_pair ( this_type &  g, const edge_descriptor &  edr, const edge_property &  epy  )

friend

Adds two edges: one from source to target of the specified descriptor and the other from the target to source. Adds first to the vertex with the smaller id of source() and target(). This will generate the id of the edge and this id will be the same in the second (sibling) edge added. This is important to match the edges when there are duplicates. Uses add_internal_edge to add the sibling edge.

Parameters

g	The graph to which the edge will be added.
edr	The descriptor of the edge to be added. Id of the descriptor must have been externally assigned.
epy	The property of the edge being added.

---

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

• adj_list_vertex_edge.h
• adjacency_list_core_graph.h