STAPL API Reference          
Overview   Containers   Algorithms   Views   Skeletons   Run-Time System
Modules     Classes    
List of all members | Public Member Functions | Public Types | Static Public Attributes | Protected Attributes
stapl::sequential::directed_preds_graph< M, VertexP, EdgeP > Class Template Reference

Class implementing a directed graph with predecessors.A directed predecessor graph extends the graph hierarchy with methods to maintain predecessors. Methods like add/delete vertex/edges add some overhead. The directed with predecessors graph is an extension of the STAPL graph. The property associated with each vertex is an extended property where one of the fields is the list of predecessors. The directed with predecessors graph will overload add/delete vertex/edge to update this field. The vertex property is wrapped inside an internal property that is used to track predecessors info. For most part this is invisible to the user. More...

Public Member Functions

 directed_preds_graph (size_t sz=0)
 Create a graph with the specified number of vertices. More...
 
size_t get_in_degree (vertex_descriptor const &vd) const
 Returns the number of incident edges on the specified vertex.
 
size_t get_predecessors (vertex_descriptor const &vd, std::vector< vertex_descriptor > &preds) const
 Returns the predecessors of the specified vertex. More...
 
edge_descriptor add_edge (edge_descriptor const &ed)
 Adds the specified edge to the graph. More...
 
edge_descriptor add_edge (edge_descriptor const &ed, edge_property const &p)
 Adds the specified edge with the given property to the graph. More...
 
edge_descriptor add_edge (vertex_descriptor const &source, vertex_descriptor const &target)
 Adds the edge with the specified source and target, with a default property to the graph. More...
 
edge_descriptor add_edge (vertex_descriptor const &source, vertex_descriptor const &target, edge_property const &p)
 Adds the edge with the specified source and target, with the given property to the graph. More...
 
bool delete_edge (edge_descriptor const &ed)
 Deletes the specified edge, while maintaining predecessors info. More...
 
bool delete_edge (vertex_descriptor const &source, vertex_descriptor const &target)
 Deletes the specified edge identified by its source and target, while maintaining predecessors info. If there are multiple edges available, one of them (unspecified) will be removed. More...
 
bool delete_vertex (vertex_descriptor const &vd)
 Deletes the specified vertex and all edges pointing to it and from it, while maintaining predecessors info. More...
 
void set_lazy_update (bool f)
 Set the graph in the lazy/non lazy update mode. More...
 
void set_predecessors (void)
 
bool is_edge (vertex_descriptor const &source, vertex_descriptor const &target) const
 Checks if an edge exists between specified source and destination vertices.
 
size_t get_degree (vertex_descriptor const &vd) const
 Returns the number of adjacent edges (out_degree) of the specified vertex.
 
size_t get_adjacent_vertices (vertex_descriptor const &vd, std::vector< vertex_descriptor > &adj) const
 Returns the list and number of adjacents of the specified vertex,. More...
 

Public Types

typedef base_type::vertex_descriptor vertex_descriptor
 
typedef base_type::edge_descriptor edge_descriptor
 
typedef base_type::vertex_iterator vertex_iterator
 
typedef base_type::const_vertex_iterator const_vertex_iterator
 
typedef base_type::adj_edge_iterator adj_edge_iterator
 
typedef base_type::const_adj_edge_iterator const_adj_edge_iterator
 
typedef base_type::edge_property edge_property
 
typedef preds_property< size_t, VertexP > vertex_property
 
typedef vertex_property::predlist_type::iterator preds_iterator
 
typedef vertex_property::predlist_type::const_iterator const_preds_iterator
 
typedef core_base_type::edge_iterator edge_iterator
 
typedef core_base_type::const_edge_iterator const_edge_iterator
 
typedef vertex_iterator::value_type vertex_reference
 
typedef const_vertex_iterator::value_type const_vertex_reference
 
typedef vertex_iterator::value_type reference
 
typedef const_vertex_iterator::value_type const_reference
 
typedef edge_iterator::value_type edge_reference
 
typedef const_edge_iterator::value_type const_edge_reference
 
typedef adj_edge_iterator::value_type adj_edge_reference
 
typedef const_adj_edge_iterator::value_type const_adj_edge_reference
 

Static Public Attributes

static const graph_attributes d_type
 
static const graph_attributes m_type
 

Protected Attributes

bool m_lazy_update
 When set true the methods are not updating the predecessors info.
 
bool m_needs_update
 Flag specifying if the predecessors info is not updated.
 

Detailed Description

template<graph_attributes M, class VertexP = properties::no_property, class EdgeP = properties::no_property>
class stapl::sequential::directed_preds_graph< M, VertexP, EdgeP >

Class implementing a directed graph with predecessors.

A directed predecessor graph extends the graph hierarchy with methods to maintain predecessors. Methods like add/delete vertex/edges add some overhead. The directed with predecessors graph is an extension of the STAPL graph. The property associated with each vertex is an extended property where one of the fields is the list of predecessors. The directed with predecessors graph will overload add/delete vertex/edge to update this field. The vertex property is wrapped inside an internal property that is used to track predecessors info. For most part this is invisible to the user.

Template Parameters
Mgraph-attribute specifying Multiedge. (MULTIEDGES/NONMULTIEDGES).
VertexPtype of property for the vertex. Default is no_property. Must be default assignable, copyable and assignable.
EdgePtype of property for the edge. Default is no_property. Must be default assignable, copyable and assignable.
TraitsA traits class that defines customizable components of graph, such as the descriptor, model, storage, etc. The default traits class is adj_graph_traits.

Constructor & Destructor Documentation

◆ directed_preds_graph()

template<graph_attributes M, class VertexP = properties::no_property, class EdgeP = properties::no_property>
stapl::sequential::directed_preds_graph< M, VertexP, EdgeP >::directed_preds_graph ( size_t  sz = 0)

Create a graph with the specified number of vertices.

Lazy updating of predecessor-info is disabled by default.

Member Function Documentation

◆ get_predecessors()

template<graph_attributes M, class VertexP = properties::no_property, class EdgeP = properties::no_property>
size_t stapl::sequential::directed_preds_graph< M, VertexP, EdgeP >::get_predecessors ( vertex_descriptor const &  vd,
std::vector< vertex_descriptor > &  preds 
) const

Returns the predecessors of the specified vertex.

Parameters
vdThe specified vertex.
predsThe output list of predecessors.
Returns
The number of predecessors.

◆ add_edge() [1/4]

template<graph_attributes M, class VertexP = properties::no_property, class EdgeP = properties::no_property>
edge_descriptor stapl::sequential::directed_preds_graph< M, VertexP, EdgeP >::add_edge ( edge_descriptor const &  ed)

Adds the specified edge to the graph.

This is specialized to add the proper predecessors info as well.

Parameters
edThe descriptor of the edge to be added.
Returns
The edge descriptor of the added edge. If successful, the id() of the descriptor is populated with the actual edge's id, otherwise set to std::numeric_limits<size_t>::max().
Note
If lazy update is set to true, the predecessor-info is not updated, but the m_needs_update flag is set, so this can be updated later in batch.

◆ add_edge() [2/4]

template<graph_attributes M, class VertexP = properties::no_property, class EdgeP = properties::no_property>
edge_descriptor stapl::sequential::directed_preds_graph< M, VertexP, EdgeP >::add_edge ( edge_descriptor const &  ed,
edge_property const &  p 
)

Adds the specified edge with the given property to the graph.

This is specialized to add the proper predecessors info as well.

Parameters
edThe descriptor of the edge to be added.
pThe edge property.
Returns
The edge descriptor of the added edge. If successful, the id() of the descriptor is populated with the actual edge's id, otherwise set to std::numeric_limits<size_t>::max().
Note
If lazy update is set to true, the predecessor-info is not updated, but the m_needs_update flag is set, so this can be updated later in batch.

◆ add_edge() [3/4]

template<graph_attributes M, class VertexP = properties::no_property, class EdgeP = properties::no_property>
edge_descriptor stapl::sequential::directed_preds_graph< M, VertexP, EdgeP >::add_edge ( vertex_descriptor const &  source,
vertex_descriptor const &  target 
)

Adds the edge with the specified source and target, with a default property to the graph.

This is specialized to add the proper predecessors info as well.

Parameters
sourceThe vertex descriptor of the source of the edge to be added.
targetThe vertex descriptor of the target of the edge to be added.
Returns
The edge descriptor of the added edge. If successful, the id() of the descriptor is populated with the actual edge's id, otherwise set to std::numeric_limits<size_t>::max().
Note
If lazy update is set to true, the predecessor-info is not updated, but the m_needs_update flag is set, so this can be updated later in batch.

◆ add_edge() [4/4]

template<graph_attributes M, class VertexP = properties::no_property, class EdgeP = properties::no_property>
edge_descriptor stapl::sequential::directed_preds_graph< M, VertexP, EdgeP >::add_edge ( vertex_descriptor const &  source,
vertex_descriptor const &  target,
edge_property const &  p 
)

Adds the edge with the specified source and target, with the given property to the graph.

This is specialized to add the proper predecessors info as well.

Parameters
sourceThe vertex descriptor of the source of the edge to be added.
targetThe vertex descriptor of the target of the edge to be added.
pThe edge property.
Returns
The edge descriptor of the added edge. If successful, the id() of the descriptor is populated with the actual edge's id, otherwise set to std::numeric_limits<size_t>::max().
Note
If lazy update is set to true, the predecessor-info is not updated, but the m_needs_update flag is set, so this can be updated later in batch.

◆ delete_edge() [1/2]

template<graph_attributes M, class VertexP = properties::no_property, class EdgeP = properties::no_property>
bool stapl::sequential::directed_preds_graph< M, VertexP, EdgeP >::delete_edge ( edge_descriptor const &  ed)

Deletes the specified edge, while maintaining predecessors info.

Returns
True if the delete was successful, or false otherwise.

◆ delete_edge() [2/2]

template<graph_attributes M, class VertexP = properties::no_property, class EdgeP = properties::no_property>
bool stapl::sequential::directed_preds_graph< M, VertexP, EdgeP >::delete_edge ( vertex_descriptor const &  source,
vertex_descriptor const &  target 
)

Deletes the specified edge identified by its source and target, while maintaining predecessors info. If there are multiple edges available, one of them (unspecified) will be removed.

Returns
True if the delete was successful, or false otherwise.

◆ delete_vertex()

template<graph_attributes M, class VertexP = properties::no_property, class EdgeP = properties::no_property>
bool stapl::sequential::directed_preds_graph< M, VertexP, EdgeP >::delete_vertex ( vertex_descriptor const &  vd)

Deletes the specified vertex and all edges pointing to it and from it, while maintaining predecessors info.

Returns
True if vertex was deleted, or false otherwise.

◆ set_lazy_update()

template<graph_attributes M, class VertexP = properties::no_property, class EdgeP = properties::no_property>
void stapl::sequential::directed_preds_graph< M, VertexP, EdgeP >::set_lazy_update ( bool  f)

Set the graph in the lazy/non lazy update mode.

If lazy update is not set, graph operations will keep the predecessor information up-to-date with each operation. If lazy update is set, graph operations will not update the predecessor information, instead relying on the user to call the set_predecessors() method to update all predecessor information at once, before use.

◆ set_predecessors()

template<graph_attributes M, class VertexP = properties::no_property, class EdgeP = properties::no_property>
void stapl::sequential::directed_preds_graph< M, VertexP, EdgeP >::set_predecessors ( void  )

When in the lazy update mode this method should be called to update all predecessors at once.

◆ get_adjacent_vertices()

size_t stapl::sequential::graph< D, M, preds_property< size_t, VertexP > , EdgeP, adj_graph_traits< DIRECTED, M, preds_property< size_t, VertexP >, EdgeP > >::get_adjacent_vertices ( vertex_descriptor const &  vd,
std::vector< vertex_descriptor > &  adj 
) const
inherited

Returns the list and number of adjacents of the specified vertex,.

Parameters
vdThe specified vertex.
adjThe output vector of the descriptors of the adjacent vertices.
Returns
The number of adjacent edges (out_degree) of the specified vertex.

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