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

M	graph-attribute specifying Multiedge. (MULTIEDGES/NONMULTIEDGES).
VertexP	type of property for the vertex. Default is no_property. Must be default assignable, copyable and assignable.
EdgeP	type of property for the edge. Default is no_property. Must be default assignable, copyable and assignable.
Traits	A 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

vd	The specified vertex.
preds	The 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

ed	The 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

ed	The descriptor of the edge to be added.
p	The 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

source	The vertex descriptor of the source of the edge to be added.
target	The 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

source	The vertex descriptor of the source of the edge to be added.
target	The vertex descriptor of the target of the edge to be added.
p	The 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

vd	The specified vertex.
adj	The 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:

• directed_preds_graph.h