STAPL API Reference          
Overview   Containers   Algorithms   Views   Skeletons   Run-Time System
Modules     Classes    
List of all members | Public Member Functions | Public Types | Protected Attributes | Friends
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 >

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.

Template Parameters
TraitsThe 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_vdThe starting descriptor of the vertices.
num_vdsThe number of vertices to be initially stored.
default_valueThe 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
edDescriptor 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
edDescriptor of the desired edge.
epProperty 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
edDescriptor of the desired edge.
epProperty 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
edDescriptor 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
predA 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
edDescriptor of the edge.
vivertex_iterator pointing to the source vertex of the edge, populated by the method.
aeiadj_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
edDescriptor of the edge.
vivertex_iterator pointing to the source vertex of the edge, populated by the method.
aeiadj_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
vdDescriptor 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
vdDescriptor 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
gThe graph to which the edge will be added.
edThe descriptor of the edge to be added. Id of the descriptor must have been externally assigned.
pThe property of the edge being added.

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