STAPL: stapl::adjacency_list_model< Traits

This model describes operations on a graph that is modeled as an adjacency-list. Adjacency-lists store a list of vertices where each vertex has a list of edges to its adjacents. More...

Public Member Functions
	adjacency_list_model (size_t const &start_vd, size_t const &num_vds, value_type const &default_value=value_type())
	Constructs an adjacency-list with the given number of vertices starting from the specified descriptor, with the given default value. Vertices have contiguous descriptors. More...

	adjacency_list_model (adjacency_list_model const &other)

vertex_iterator	begin (void)

vertex_iterator	end (void)

const_vertex_iterator	begin (void) const

const_vertex_iterator	end (void) const

vertex_descriptor	next_free_descriptor ()

edge_iterator	edges_begin (void)
	Returns an edge iterator to the first edge in the entire adjacency-list.

const_edge_iterator	edges_begin (void) const
	Returns an edge iterator to the first edge in the adjacency-list.

edge_iterator	edges_end (void)
	Returns an edge iterator to one past the last edge in the adjacency-list.

const_edge_iterator	edges_end (void) const
	Returns an edge iterator to the last edge in the adjacency-list.

size_t	num_vertices (void) const
	Returns the total number of vertices.

size_t	size (void) const
	Returns the total number of vertices.

size_t	get_max_descriptor (void)
	Returns the current max descriptor.

void	update_next_descriptor (vertex_descriptor const &vd)
	Updates the vertex descriptor generator with the next free descriptor.

size_t	num_edges (void) const
	Returns the total number of edges.

size_t	num_self_edges (void) const
	Returns the total number of self edges.

void	reserve_adjacency (vertex_descriptor const &vd, size_t num_adjacents)
	Reserves space for storing specified number of edges in the specified vertex. More...

vertex_descriptor	add_vertex (void)
	Adds vertex with the default vertex property. A descriptor is automatically generated for the new vertex. More...

vertex_descriptor	add_vertex (vertex_property const &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, vertex_property const &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 (edge_descriptor const &ed)
	Adds an edge with given descriptor and default edge property. More...

edge_descriptor	add_edge (edge_descriptor const &ed, edge_property const &p)
	Adds an edge with given descriptor and edge property. More...

template<typename Comp >
edge_descriptor	insert_edge (edge_descriptor const &ed, edge_property const &p, Comp const &comp)
	Inserts an edge with given descriptor and edge property. More...

edge_descriptor	check_add_edge (edge_descriptor const &ed, edge_property const &ep)
	Checks and adds an edge with given descriptor and property. The method checks if the edge exists before adding it. If it doesn't, the edge is added, otherwise it is discarded. More...

edge_descriptor	check_add_edge (edge_descriptor const &ed)
	Checks and adds an edge with given descriptor and default property. The method checks if the edge exists before adding it. If it doesn't, the edge is added, otherwise it is discarded. More...

bool	set_edge (vertex_descriptor const &v, const size_t i, vertex_descriptor const &neighbor)
	Sets i-th neighbor of v to the specified neighbor vertex. More...

bool	set_edge (vertex_descriptor const &v, const size_t i, const size_t max, vertex_descriptor const &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	clear_edges (void)
	Erases all edges in the graph.

void	delete_all_edges_to_v (vertex_descriptor const &vd)
	Deletes all edges with the specified vertex as their target. For internal use by delete_vertex. More...

bool	delete_vertex (vertex_descriptor const &vd)
	Deletes the specified vertex and all edges pointing to and from it. More...

bool	suspend_vertex (vertex_descriptor const &vd)
	Deletes the specified vertex, but preserves all edges pointing to it. Used by migration. More...

bool	delete_edge (edge_descriptor const &ed)
	Deletes the edge with given descriptor. More...

template<typename Pred >
void	erase_edges_if (Pred &&pred)
	Erases all edges that match a user-defined predicate. More...

bool	find_edge (edge_descriptor const &ed, vertex_iterator &vi, adj_edge_iterator &ei)
	Finds the edge with the specified descriptor, and returns an iterator to its source vertex and an adj_edge_iterator pointing to the edge. More...

bool	find_edge (edge_descriptor const &ed, const_vertex_iterator &vi, const_adj_edge_iterator &ei) const
	Finds the edge with the specified descriptor, and returns an iterator to its source vertex and an adj_edge_iterator pointing to the edge. More...

bool	find_local_edge (edge_descriptor const &ed, vertex_iterator &vi, adj_edge_iterator &ei)
	Finds a local edge with the specified descriptor, and returns an iterator to its source vertex and an adj_edge_iterator pointing to the edge. More...

bool	find_local_edge (edge_descriptor const &ed, const_vertex_iterator &vi, const_adj_edge_iterator &ei) const
	Finds a local edge with the specified descriptor, and returns an iterator to its source vertex and an adj_edge_iterator pointing to the edge. More...

const_vertex_iterator	find_vertex (vertex_descriptor &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...

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

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

vertex_iterator	find (vertex_descriptor const &vd)
	Same as find_vertex, provided for compatibility.

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

template<typename Comp >
void	sort_edges (Comp const &comp)
	Sorts edges of each vertex according to provided comparator. More...

void	remove_duplicate_edges ()
	Removes all duplicate edges with the same (source, target) pair.

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 Traits::edge_type	edge_type
	The type of the edge.

typedef Traits::storage_type	vertex_set_type
	The type of storage for vertices.

typedef Traits::edgelist_type	edgelist_type
	The type of storage for edges on a vertex.

typedef Traits::vertex_impl_type	vertex_impl_type
	The type of the vertex.

typedef vertex_impl_type	value_type

typedef vertex_set_type::iterator	iterator

typedef vertex_set_type::const_iterator	const_iterator

typedef iterator	vertex_iterator

typedef const_iterator	const_vertex_iterator

typedef edgelist_type::iterator	adj_edge_iterator
	Type of the iterator over adjacent edges of a vertex.

typedef edgelist_type::const_iterator	const_adj_edge_iterator

typedef sequential::edge_iterator_adaptor< vertex_iterator >	edge_iterator
	Type of the edge iterator over all edges stored in the adjacency-list.

typedef sequential::edge_iterator_adaptor< const_vertex_iterator >	const_edge_iterator

Protected Attributes
vertex_set_type	m_vertices
	The container for storing the vertices.

size_t	m_ne
	The number of edges in this adjacency-list, excluding self edges.

size_t	m_se

size_t	m_eid
	The number to keep track of unique edge-descriptors generated.

Friends
void	add_internal_edge (adjacency_list_model &g, edge_descriptor const &ed, edge_property const &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 (adjacency_list_model &g, edge_descriptor const &ed, edge_property const &p)
	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::adjacency_list_model< Traits >

This model describes operations on a graph that is modeled as an adjacency-list. Adjacency-lists store a list of vertices where each vertex has a list of edges to its adjacents.

Template Parameters

Traits The traits class for specifying the types of descriptors, storages, edges and vertices, etc.

Methods like find_vertex, find_edge are optimized for this particular storage.

Constructor & Destructor Documentation

◆ adjacency_list_model()

template<class Traits >

stapl::adjacency_list_model< Traits >::adjacency_list_model	(	size_t const &	start_vd,
		size_t const &	num_vds,
		value_type const &	default_value = `value_type()`
	)

Constructs an adjacency-list with the given number of vertices starting from the specified descriptor, with the given default value. Vertices have contiguous descriptors.

Parameters

start_vd	The starting descriptor of the vertices.
num_vds	The number of vertices to be initially stored.
default_value	The default value for the vertices.

Member Function Documentation

◆ reserve_adjacency()

template<class Traits >

void stapl::adjacency_list_model< Traits >::reserve_adjacency	(	vertex_descriptor const &	vd,
		size_t	num_adjacents
	)

Reserves space for storing specified number of edges in the specified vertex.

Parameters

vd	The descriptor of the vertex.
num_adjacents	The number of adjacents to be stored.

◆ add_vertex() [1/3]

template<class Traits >

vertex_descriptor stapl::adjacency_list_model< 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::adjacency_list_model< Traits >::add_vertex ( vertex_property const & 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::adjacency_list_model< Traits >::add_vertex	(	vertex_descriptor	vd,
		vertex_property const &	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::adjacency_list_model< Traits >::add_edge ( edge_descriptor const & 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::adjacency_list_model< Traits >::add_edge	(	edge_descriptor const &	ed,
		edge_property const &	p
	)

Adds an edge with given descriptor and edge property.

Parameters

ed	Descriptor of the desired edge.
ep	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.

◆ insert_edge()

template<class Traits >

template<typename Comp >

edge_descriptor stapl::adjacency_list_model< Traits >::insert_edge	(	edge_descriptor const &	ed,
		edge_property const &	p,
		Comp const &	comp
	)

Inserts an edge with given descriptor and edge property.

Parameters

ed	Descriptor of the desired edge.
ep	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.

◆ check_add_edge() [1/2]

template<class Traits >

edge_descriptor stapl::adjacency_list_model< Traits >::check_add_edge	(	edge_descriptor const &	ed,
		edge_property const &	ep
	)

Checks and adds an edge with given descriptor and property. The method checks if the edge exists before adding it. If it doesn't, the edge is added, otherwise it is discarded.

Parameters

ed	Descriptor of the desired edge.
ep	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.

◆ check_add_edge() [2/2]

template<class Traits >

edge_descriptor stapl::adjacency_list_model< Traits >::check_add_edge ( edge_descriptor const & ed )

Checks and adds an edge with given descriptor and default property. The method checks if the edge exists before adding it. If it doesn't, the edge is added, otherwise it is discarded.

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.

◆ set_edge() [1/2]

template<class Traits >

bool stapl::adjacency_list_model< Traits >::set_edge	(	vertex_descriptor const &	v,
		const size_t	i,
		vertex_descriptor const &	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::adjacency_list_model< Traits >::set_edge	(	vertex_descriptor const &	v,
		const size_t	i,
		const size_t	max,
		vertex_descriptor const &	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::adjacency_list_model< Traits >::delete_all_edges_to_v ( vertex_descriptor const & 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::adjacency_list_model< Traits >::delete_vertex ( vertex_descriptor const & 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.

◆ suspend_vertex()

template<class Traits >

bool stapl::adjacency_list_model< Traits >::suspend_vertex ( vertex_descriptor const & vd )

Deletes the specified vertex, but preserves all edges pointing to it. Used by migration.

Parameters

vd	The descriptor of the vertex.

Returns: Whether or not the vertex was successfully deleted.

◆ delete_edge()

template<class Traits >

bool stapl::adjacency_list_model< Traits >::delete_edge ( edge_descriptor const & ed )

Deletes the edge with given descriptor.

Parameters

ed	Descriptor of the desired edge.

Returns: Whether or not the edge was successfully deleted.

◆ erase_edges_if()

template<class Traits >

template<typename Pred >

void stapl::adjacency_list_model< Traits >::erase_edges_if ( Pred && pred )

Erases all edges that match a user-defined predicate.

Parameters

pred	A unary predicate that receives a single edge

◆ find_edge() [1/2]

template<class Traits >

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

Finds the edge with the specified descriptor, and returns 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::adjacency_list_model< Traits >::find_edge	(	edge_descriptor const &	ed,
		const_vertex_iterator &	vi,
		const_adj_edge_iterator &	ei
	)		const

Finds the edge with the specified descriptor, and returns 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_local_edge() [1/2]

template<class Traits >

bool stapl::adjacency_list_model< Traits >::find_local_edge	(	edge_descriptor const &	ed,
		vertex_iterator &	vi,
		adj_edge_iterator &	ei
	)

Finds a local edge with the specified descriptor, and returns 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_local_edge() [2/2]

template<class Traits >

bool stapl::adjacency_list_model< Traits >::find_local_edge	(	edge_descriptor const &	ed,
		const_vertex_iterator &	vi,
		const_adj_edge_iterator &	ei
	)		const

Finds a local edge with the specified descriptor, and returns 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/4]

template<class Traits >

const_vertex_iterator stapl::adjacency_list_model< Traits >::find_vertex ( vertex_descriptor & 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/4]

template<class Traits >

const_vertex_iterator stapl::adjacency_list_model< 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() [3/4]

template<class Traits >

vertex_iterator stapl::adjacency_list_model< Traits >::find_vertex ( vertex_descriptor & 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.

◆ find_vertex() [4/4]

template<class Traits >

vertex_iterator stapl::adjacency_list_model< 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::adjacency_list_model< 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.

◆ sort_edges()

template<class Traits >

template<typename Comp >

void stapl::adjacency_list_model< Traits >::sort_edges ( Comp const & comp )

Sorts edges of each vertex according to provided comparator.

Parameters

comp	The comparator for sorting edges of a vertex.

Friends And Related Function Documentation

◆ add_internal_edge

template<class Traits >

void add_internal_edge	(	adjacency_list_model< Traits > &	g,
		edge_descriptor const &	ed,
		edge_property const &	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	(	adjacency_list_model< Traits > &	g,
		edge_descriptor const &	ed,
		edge_property const &	p
	)

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

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

graph_storage.h

Public Member Functions

Public Types

Protected Attributes

Friends

Detailed Description

template<class Traits> class stapl::adjacency_list_model< Traits >

Constructor & Destructor Documentation

◆ adjacency_list_model()

Member Function Documentation

◆ reserve_adjacency()

◆ add_vertex() [1/3]

◆ add_vertex() [2/3]

◆ add_vertex() [3/3]

◆ add_edge() [1/2]

◆ add_edge() [2/2]

◆ insert_edge()

◆ check_add_edge() [1/2]

◆ check_add_edge() [2/2]

◆ set_edge() [1/2]

◆ set_edge() [2/2]

◆ delete_all_edges_to_v()

◆ delete_vertex()

◆ suspend_vertex()

◆ delete_edge()

◆ erase_edges_if()

◆ find_edge() [1/2]

◆ find_edge() [2/2]

◆ find_local_edge() [1/2]

◆ find_local_edge() [2/2]

◆ find_vertex() [1/4]

◆ find_vertex() [2/4]

◆ find_vertex() [3/4]

◆ find_vertex() [4/4]

◆ update_descriptor()

◆ sort_edges()

Friends And Related Function Documentation

◆ add_internal_edge

◆ add_edge_pair

template<class Traits>
class stapl::adjacency_list_model< Traits >