STAPL: stapl::csr_model< Traits > Class Template Reference

This model describes operations on a graph that is modeled as a Compressed Sparse-Row (CSR) graph. CSRs store a list of vertices and a separate list of edges. Each vertex points to its adjacent edges in the list of edges. More...

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

	csr_model (csr_model const &other)

vertex_iterator	begin ()

vertex_iterator	end ()

const_vertex_iterator	begin () const

const_vertex_iterator	end () const

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

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

size_t	get_max_descriptor ()
	Returns the current max descriptor.

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

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

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

edge_descriptor	check_add_edge (edge_descriptor const &ed, edge_property const &ep)
	Unconditionally adds the edge. Duplicate edges will be handled in the commit phase, if required. More...

edge_descriptor	check_add_edge (edge_descriptor const &ed)
	Unconditionally adds the edge. Duplicate edges will be handled in the commit phase, if required. More...

void	clear (void)
	Erases all vertices and edges in the graph.

void	commit (void)
	Freezes the CSR graph so that no further addition of edges is possible. More...

void	uncommit (void)
	Uncommit the CSR graph. More...

template<typename Comp >
void	sort_edges (Comp &&cmp)
	Sorts edges of each vertex by user-defined comparison function. More...

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

void	remove_duplicate_edges ()
	Removes all duplicate edges with the same (source, target) pair. 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...

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

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

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

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

size_t	m_se
	The number of self edges in this CSR.

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

Friends
edge_descriptor	add_edge_pair (csr_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::csr_model< Traits >

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

◆ csr_model()

template<class Traits >

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

Constructs a CSR 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

◆ add_edge() [1/2]

template<class Traits >

edge_descriptor stapl::csr_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::csr_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.

◆ check_add_edge() [1/2]

template<class Traits >

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

Unconditionally adds the edge. Duplicate edges will be handled in the commit phase, if required.

Parameters

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

Returns: edge_descriptor of the added edge.

◆ check_add_edge() [2/2]

template<class Traits >

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

Unconditionally adds the edge. Duplicate edges will be handled in the commit phase, if required.

Parameters

ed	Descriptor of the desired edge.

Returns: edge_descriptor of the added edge.

◆ commit()

template<class Traits >

void stapl::csr_model< Traits >::commit ( void )

Freezes the CSR graph so that no further addition of edges is possible.

Note: This method must be called before using the CSR graph, and only after all edges have been added to it. Edges may only be added to the CSR as long as it is unfrozen. Once it has been frozen by calling commit(), no further addition of edges is allowed. The CSR may only be committed once, and may not be uncommitted thereafter.

The CSR graph starts off in an unfrozen state. Freezing it internally sorts and copies the edges to the CSR format and updates the vertices accordingly to point to their adjacent sections in the edgelist.

◆ uncommit()

template<class Traits >

void stapl::csr_model< Traits >::uncommit ( void )

Uncommit the CSR graph.

Place the graph in a state so that edges can be added. While the graph is uncommited, it is not possible to access its edges.

◆ sort_edges()

template<class Traits >

template<typename Comp >

void stapl::csr_model< Traits >::sort_edges ( Comp && cmp )

Sorts edges of each vertex by user-defined comparison function.

Note: The graph must be committed in order to sort its edges

◆ erase_edges_if()

template<class Traits >

template<typename Pred >

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

Erases all edges that match a user-defined predicate.

Note: The graph must be not committed

Parameters

pred	A unary predicate that receives a single edge

◆ remove_duplicate_edges()

template<class Traits >

void stapl::csr_model< Traits >::remove_duplicate_edges ( )

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

Note: The graph must be not committed

◆ find_edge() [1/2]

template<class Traits >

bool stapl::csr_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::csr_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_vertex() [1/2]

template<class Traits >

const_vertex_iterator stapl::csr_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() [2/2]

template<class Traits >

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

Friends And Related Function Documentation

◆ add_edge_pair

template<class Traits >

edge_descriptor add_edge_pair	(	csr_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:

csr_storage.hpp

Public Member Functions

Public Types

Protected Attributes

Friends

Detailed Description

template<class Traits> class stapl::csr_model< Traits >

Constructor & Destructor Documentation

◆ csr_model()

Member Function Documentation

◆ add_edge() [1/2]

◆ add_edge() [2/2]

◆ check_add_edge() [1/2]

◆ check_add_edge() [2/2]

◆ commit()

◆ uncommit()

◆ sort_edges()

◆ erase_edges_if()

◆ remove_duplicate_edges()

◆ find_edge() [1/2]

◆ find_edge() [2/2]

◆ find_vertex() [1/2]

◆ find_vertex() [2/2]

Friends And Related Function Documentation

◆ add_edge_pair

template<class Traits>
class stapl::csr_model< Traits >