STAPL: stapl::graph_distribution< Container

Distribution class for the dynamic_graph container. More...

Public Member Functions
	graph_distribution (graph_distribution const &other)

	graph_distribution (partition_type const &partition, mapper_type const &mapper)
	Create a distribution with default constructed elements. More...

	graph_distribution (partition_type const &partition, mapper_type const &mapper, value_type const &default_value)
	Create a distribution with an initial value for elements. More...

	graph_distribution (partition_type const &partition)
	Create a distribution with default constructed elements and a default mapper. More...

bool	is_directed (void) const

void	sort_edges_ascending (void)
	Sorts edges of each vertex in ascending order of target-vertex-id. More...

void	sort_edges_locality (void)
	Sorts edges of each vertex by home-location of target-vertex. More...

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

iterator	begin (void)

const_iterator	begin (void) const

iterator	end (void)

const_iterator	end (void) const

vertex_descriptor	add_vertex (vertex_property const &vp)
	Adds a vertex to the pGraph with the given property. More...

vertex_descriptor	add_vertex (vertex_descriptor const &gid, vertex_property const &vp)
	Adds a vertex to the pGraph with the given property and descriptor. More...

template<typename Functor >
void	add_vertex (vertex_descriptor const &gid, vertex_property const &vp, Functor const &f)
	Adds a vertex to the pGraph with the given property and descriptor, if the vertex does not exist, or applies the given functor to the existing vertex. The vertex is added to the home location, unlike the other add_vertex calls that add the vertex at the current location. More...

vertex_descriptor	add_vertex_uniform (vertex_property const &vp)
	Adds a vertex to the pGraph with the given property to a location based on the vertex descriptor assigned by the graph. This method is asynchronous. This method differs from the typical add_vertex as it inserts the vertex into a potentially remote location, rather than the calling location. More...

void	delete_vertex (vertex_descriptor const &gid)
	Deletes a vertex from the pGraph with the given descriptor. This method is asynchronous. 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.

iterator	find_vertex (vertex_descriptor const &gid)
	Returns a global vertex iterator to the given descriptor. More...

iterator	find (vertex_descriptor const &gid)
	Returns a global vertex iterator to the given descriptor. More...

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

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

void	add_edge_async (edge_descriptor const &ed)
	Adds an edge with given descriptor. More...

void	add_edge_async (edge_descriptor const &ed, edge_property const &ep, bool sibling=false)
	Adds an edge with given descriptor and property. The edge is added asynchronously and method returns immediately. Edge is not guaranteed to be added until after a global synchronization. More...

template<typename Comp >
edge_descriptor	insert_edge (edge_descriptor const &ed, Comp const &comp)

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

template<typename Comp >
void	insert_edge_async (edge_descriptor const &ed, Comp const &comp)
	Inserts an edge with given descriptor. More...

template<typename Comp >
void	insert_edge_async (edge_descriptor const &ed, edge_property const &ep, Comp const &comp, bool sibling=false)

template<typename Cont , typename F >
void	aggregate_apply_async (Cont &&cont, F const &f)
	Applies a functor on this location. More...

template<typename Cont , typename F >
void	aggregate_apply_async (size_t loc, Cont const &cont, F const &f)

template<typename Cont , typename F >
void	guarded_aggregate_apply_async (size_t loc, Cont const &cont, F const &f)

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

void	clear (void)
	Clears the graph. This resets internal counters for vertex-descriptor and edge-id assignments, and clears graph storage. More...

void	clear_edges (void)

size_t	num_local_edges (void) const
	Returns the number of local outgoing edges in the pGraph. This is a blocking method. More...

size_t	num_local_self_edges (void) const
	Returns the number of self edges in the pGraph. This is a blocking method. More...

size_t	num_edges (void) const
	Returns the number of edges in the pGraph. This method is a non-collective version of num_edges. This must be used when not all locations are calling num_edges. More...

size_t	num_self_edges (void) const
	Returns the number of self edges in the pGraph. This must be used when not all locations are calling num_self_edges. For a faster collective, use num_self_edges_collective() below. More...

size_t	num_edges_collective (void) const
	Returns the number of edges in the pGraph. More...

size_t	num_self_edges_collective (void) const
	Returns the number of self edges in the pGraph. More...

template<typename FCont >
void	aggregate_vp_apply_async (FCont const &fcont)
	Applies functors to respective vertex-properties on this location. All elements must be local. For internal use by Aggregators. More...

template<typename FCont >
void	aggregate_vp_apply_async (size_t loc, FCont const &fcont)
	Applies functors to respective vertex-properties on the desired location. For internal use by Aggregators. This method is asynchronous. More...

template<typename Cont , typename F >
void	aggregate_async (Cont const &cont, F const &f)
	Applies a functor on this location. All elements must be local. For internal use by Aggregators. More...

template<typename Cont , typename F >
void	aggregate_async (size_t loc, Cont const &cont, F const &f)
	Applies a functor on the desired location. For internal use by Aggregators. This method is asynchronous. More...

template<typename F >
void	vp_apply_async (vertex_descriptor const &gid, F const &f)
	Applies a function to the property of vertex with given descriptor. This method is asynchronous. More...

template<typename F >
F::result_type	vp_apply (gid_type const &gid, F const &f)
	Applies a function to the property of vertex with given descriptor. More...

template<typename F >
F::result_type	vp_apply (gid_type const &gid, F const &f) const
	Applies a function to the property of vertex with given descriptor. More...

template<typename Functor >
void	ep_apply_async (edge_descriptor const &ed, Functor const &f)
	Applies a function to the property of edge with given descriptor. This method is asynchronous. More...

template<typename Functor >
Functor::result_type	ep_apply (edge_descriptor const &ed, Functor const &f)
	Applies a function to the property of edge with given descriptor. More...

template<typename Functor >
void	ep_apply_promise (edge_descriptor const &ed, Functor const &f, promise< typename Functor::result_type > p)
	Applies a function to the specified edge and populates a promise with the result. Used by ep_apply. More...

template<typename Functor >
bool	ep_find_apply (edge_descriptor const &ed, Functor const &f)
	Applies a functor f on the property of the specified edge, if it exists. More...

template<typename Functor >
void	ep_find_apply_promise (edge_descriptor const &ed, Functor const &f, promise< bool > p)
	Applies the given functor on the property of the specified edge, if it exists. Populates a promise variable with true if the edge was found, or false otherwise. More...

iterator	make_iterator (gid_type const &gid)
	Constructs a vertex iterator to the given descriptor. More...

const_iterator	make_iterator (gid_type const &gid) const
	Constructs a const vertex iterator to the vertex with the specified descriptor. More...

iterator	make_iterator (domain_type const &domain, gid_type const &gid)
	Creates an iterator to the specified gid, which is restricted to the provided domain. More...

const_iterator	make_iterator (domain_type const &domain, gid_type const &gid) const
	Creates an iterator to the specified gid, which is restricted to the provided domain. More...

reference	make_reference (index_type const &gid)
	Constructs a reference to the vertex with the given descriptor. More...

const_reference	make_reference (index_type const &gid) const
	Constructs a reference to the vertex with the given descriptor. More...

gid_type	first (location_type loc) const

gid_type	last (location_type loc) const

gid_type	advance (gid_type const &gid, long long n) const

size_t	local_size (void) const

void	defer_advance (gid_type const &gid, long long n, promise< gid_type > p)
	Advances the GID by the provided value, storing the result in a promise. This allows the advance to be non-blocking. This is needed by the distributed domain.

void	defer_contains (gid_type const &gid, promise< bool > p)
	Checks if the element specified by the GID is stored locally. The result is stored in a promise. This is needed by the distributed domain.

size_t	size (void) const

domain_type const &	domain (void) const

local_return_type	metadata (void)
	Returns the metadata information for the base-containers on this location. More...

size_t	num_base_containers (void)
	Returns the global number of base-containers in this distribution.

template<typename Frontier >
void	set_frontier (Frontier *frontier)
	Set the frontier for the current traversal on this graph.

template<typename Frontier >
Frontier *	get_frontier ()
	Get the frontier for the current traversal on this graph.

future< dom_info_type >	metadata_at (gid_type const &gid)
	Returns the metadata associated with the given `index`. More...

future< bool >	has_edge (vertex_descriptor const &source, vertex_descriptor const &target)
	Determines whether there exists an edge between two vertices. More...

void	aggregate_apply_async (Cont &&cont, F &&f)
	Applies a functor on this location. More...

void	guarded_apply_set (vertex_descriptor const &gid, F &&f)
	Apply a functor to the element at a given GID in a non-concurrent manner. That is, if the graph is already in an apply_set, then this apply_set will be deferred until the one in progress has ended. More...

void	guarded_unordered_apply (vertex_descriptor const &gid, F &&f)
	Apply a functor to the element at a given GID in a non-concurrent manner. That is, if the graph is already in an unordered_apply, then this unordered_apply will be deferred until the one in progress has ended. More...

partition_type &	partition ()

partition_type const &	partition () const

mapper_type &	mapper ()

directory_type &	directory (void)

directory_type const &	directory (void) const

container_manager_type &	container_manager (void)

container_manager_type const &	container_manager (void) const

container_type *	container (void)

container_type const *	container (void) const

bool	is_local (Indices const &... i) const

void	defer_metadata_at (gid_type const &gid, promise< dom_info_type > p)
	Returns the metadata associated with the given `gid` by setting the value of the promise. More...

dom_info_type	metadata_of (cid_type const &cid)
	Return the metadata associated with the specified component. More...

void	redistribute (std::shared_ptr< DistSpecView > dist_view, typename std::enable_if< is_distribution_view< DistSpecView >::value >::type *=0)
	Redistribute data to match the distribution specification provided. More...

void	update (std::vector< std::tuple< std::pair< gid_type, gid_type >, cid_type, location_type >> const &updates)
	Add information on the distribution of elements not yet in the container. Use in dynamic containers with view-based distributions to allow element distribution to be based on computation. More...

void	set_element (gid_type const &gid, value_type const &val)
	Update the element at a GID by replacing it with a given value. More...

void	set_elements (gid_type gid, SourceView &&source_view)
	Update a range of contiguous elements in the container, starting at `gid`. A total of `view.size()` elements will be updated with the values in `view`. More...

void	set_elements (gid_type gid, View &&view)
	Signature of set_elements used when underlying base container is not supported. Fall back to iterative use of set_element.

value_type	get_element (gid_type const &gid) const
	Return a copy of the element at a specific GID. Note that this is a blocking operation. More...

future< value_type >	get_element_split (gid_type const &gid)
	Return a future of the element at a specific GID. This is a non-blocking operation. More...

void	apply_set (gid_type const &gid, Functor const &f)
	Apply a function object to the element with the given GID. More...

void	unordered_apply_set (gid_type const &gid, Functor &&f)
	Apply a function object to the element with the given GID, disregarding RMI causal ordering. More...

void	unordered_apply (gid_type const &gid, Functor &&f)
	Apply a function object to the element with the given GID, passing along the distribution pointer and disregarding RMI causal ordering. More...

boost::result_of< Functor(value_type &)>::type	apply_get (gid_type const &gid, Functor const &f)
	Apply a function object to the element with the given GID and return the result. More...

boost::result_of< Functor(value_type &)>::type	apply_get (gid_type const &gid, Functor const &f) const
	Apply a function object to the element with the given GID and return the result. More...

void	migrate (gid_type const &gid, const location_type destination)
	Migrate a single element with a specific GID to a given location. More...

Public Types
using	base_type = detail::graph_distribution_base< Container, graph_distribution< Container > >

typedef Container	container_type

typedef base_type::directory_type	directory_type

typedef base_type::container_manager_type	container_manager_type

typedef directory_type::partition_type	partition_type

typedef directory_type::mapper_type	mapper_type

typedef container_manager_type::base_container_type	base_container_type

typedef directory_type::key_type	gid_type

typedef gid_type	index_type

typedef graph_distribution_traits< graph_distribution, container_type >::domain_type	domain_type

typedef base_container_type::value_type	value_type

typedef base_container_type::cid_type	cid_type

typedef base_container_type::vertex_descriptor	vertex_descriptor

typedef base_container_type::edge_descriptor	edge_descriptor

typedef container_traits< container_type >::vertex_property	vertex_property

typedef container_traits< container_type >::edge_property	edge_property

typedef base_container_type::edgelist_type	edgelist_type

typedef base_container_type::edge_iterator	edge_iterator

typedef mapper_type::value_type	location_type

typedef graph_accessor< graph_distribution >	accessor_type

typedef proxy< value_type, accessor_type >	reference

typedef const_graph_accessor< graph_distribution >	const_accessor_type

typedef const proxy< value_type, const_accessor_type >	const_reference

typedef graph_metadata< graph_distribution >	loc_dist_metadata

typedef container_iterator< graph_distribution, accessor_type >	iterator

typedef const_container_iterator< graph_distribution, const_accessor_type >	const_iterator

typedef iterator	vertex_iterator

typedef const_iterator	const_vertex_iterator

typedef reference::adj_edge_iterator	adj_edge_iterator

typedef const_reference::const_adj_edge_iterator	const_adj_edge_iterator

typedef graph_distribution_traits< graph_distribution, container_type >::metadata_domain_type	metadata_domain_type

typedef metadata_entry< metadata_domain_type, base_container_type *>	dom_info_type

typedef std::vector< dom_info_type >	local_return_type

typedef mapper_type::domain_type	map_dom_t

Protected Member Functions
template<typename Functor >
void	try_insert (vertex_descriptor const &gid, vertex_property const &vp, Functor const &f)
	Adds a vertex to the pGraph with the given property. More...

void	add_edge_promise (edge_descriptor const &ed, edge_property const &ep, promise< edge_descriptor > p, bool sibling=false)
	used by add_edge method to populate a promise so that the edge descriptor may be returned for the synchronous method. More...

template<typename Comp >
void	insert_edge_promise (edge_descriptor const &ed, edge_property const &ep, Comp const &comp, promise< edge_descriptor > p, bool sibling=false)
	used by insert_edge method to populate a promise so that the edge descriptor may be returned for the synchronous method. More...

void	defer_metadata_at (gid_type const &gid, promise< dom_info_type > p)
	Returns the metadata associated with the given `gid` by setting the value of the promise. More...

void	update_impl (std::vector< std::tuple< std::pair< gid_type, gid_type >, cid_type, location_type >> const &updates)

Protected Types
enum	edge_sortedness { not_sorted, ascending, locality, custom }

Protected Attributes
domain_type	m_domain

edge_sortedness	m_edge_sortedness

void *	m_current_frontier

container_manager_type	m_container_manager
	Manages and owns the base-containers on this location. Base-containers store the actual data. Container manager also handles the mapping from gid to base-container.

Detailed Description

template<typename Container>
struct stapl::graph_distribution< Container >

Distribution class for the dynamic_graph container.

Template Parameters

Container Type of the container that is managing this distribution.

See also: dynamic_graph

Constructor & Destructor Documentation

◆ graph_distribution() [1/3]

template<typename Container >

stapl::graph_distribution< Container >::graph_distribution	(	partition_type const &	partition,
		mapper_type const &	mapper
	)

Create a distribution with default constructed elements.

Parameters

partition	Partition used by the container
mapper	Mapper used by the container

◆ graph_distribution() [2/3]

template<typename Container >

stapl::graph_distribution< Container >::graph_distribution	(	partition_type const &	partition,
		mapper_type const &	mapper,
		value_type const &	default_value
	)

Create a distribution with an initial value for elements.

Parameters

partition	Partition used by the container
mapper	Mapper used by the container
default_value	The value that the elements in this distribution will be initialized with

◆ graph_distribution() [3/3]

template<typename Container >

stapl::graph_distribution< Container >::graph_distribution ( partition_type const & partition )

Create a distribution with default constructed elements and a default mapper.

Parameters

partition Partition used by the container

Member Function Documentation

◆ sort_edges_ascending()

template<typename Container >

void stapl::graph_distribution< Container >::sort_edges_ascending ( void )

Sorts edges of each vertex in ascending order of target-vertex-id.

◆ sort_edges_locality()

template<typename Container >

void stapl::graph_distribution< Container >::sort_edges_locality ( void )

Sorts edges of each vertex by home-location of target-vertex.

◆ sort_edges()

template<typename Container >

template<typename Comp >

void stapl::graph_distribution< Container >::sort_edges ( Comp const & comp )

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

◆ add_vertex() [1/3]

template<typename Container >

vertex_descriptor stapl::graph_distribution< Container >::add_vertex ( vertex_property const & vp )

Adds a vertex to the pGraph with the given property.

Parameters

vp	Property of the vertex.

Returns: vertex_descriptor of the added vertex.

Vertex-descriptor is assigned automatically by the pGraph. This method is asynchronous. The vertex is added at the calling location, which is also the home location for the vertex.

◆ add_vertex() [2/3]

template<typename Container >

vertex_descriptor stapl::graph_distribution< Container >::add_vertex	(	vertex_descriptor const &	gid,
		vertex_property const &	vp
	)

Adds a vertex to the pGraph with the given property and descriptor.

Parameters

gid	descriptor of the vertex.
vp	Property of the vertex.

Returns: vertex_descriptor of the added vertex.

This method is asynchronous. The vertex is added at the calling location. An async is sent to the home-location of the vertex.

◆ try_insert()

template<typename Container >

template<typename Functor >

void stapl::graph_distribution< Container >::try_insert	(	vertex_descriptor const &	gid,
		vertex_property const &	vp,
		Functor const &	f
	)

protected

Adds a vertex to the pGraph with the given property.

This will only be executed on the home location of the gid, as it is at this point that we can make the decision of insertion or application.

Parameters

gid	The gid of the vertex to be added.
vp	The vertex property of the vertex to be added.
f	The functor to apply if the element already exists

◆ add_vertex() [3/3]

template<typename Container >

template<typename Functor >

void stapl::graph_distribution< Container >::add_vertex	(	vertex_descriptor const &	gid,
		vertex_property const &	vp,
		Functor const &	f
	)

Adds a vertex to the pGraph with the given property and descriptor, if the vertex does not exist, or applies the given functor to the existing vertex. The vertex is added to the home location, unlike the other add_vertex calls that add the vertex at the current location.

Parameters

gid	descriptor of the vertex.
vp	Property of the vertex.
f	Function to apply to the vertex if it already exists.

This method is asynchronous. The vertex is added at the home-location.

◆ add_vertex_uniform()

template<typename Container >

vertex_descriptor stapl::graph_distribution< Container >::add_vertex_uniform ( vertex_property const & vp )

Adds a vertex to the pGraph with the given property to a location based on the vertex descriptor assigned by the graph. This method is asynchronous. This method differs from the typical add_vertex as it inserts the vertex into a potentially remote location, rather than the calling location.

Parameters

vp	Property of the vertex.

Returns: vertex_descriptor of the added vertex.

◆ delete_vertex()

template<typename Container >

void stapl::graph_distribution< Container >::delete_vertex ( vertex_descriptor const & gid )

Deletes a vertex from the pGraph with the given descriptor. This method is asynchronous.

Parameters

gid	descriptor of the vertex.

◆ erase_edges_if()

template<typename Container >

template<typename Pred >

void stapl::graph_distribution< Container >::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_vertex()

template<typename Container >

iterator stapl::graph_distribution< Container >::find_vertex ( vertex_descriptor const & gid )

Returns a global vertex iterator to the given descriptor.

Parameters

gid	Descriptor of the desired vertex.

Returns: vertex_iterator to the desired vertex.

Wrapper around make_iterator for compatibility. Does not enforce the existence of the vertex.

◆ find()

template<typename Container >

iterator stapl::graph_distribution< Container >::find ( vertex_descriptor const & gid )

Returns a global vertex iterator to the given descriptor.

Parameters

gid	Descriptor of the desired vertex.

Returns: vertex_iterator to the desired vertex.

Wrapper around make_iterator for compatibility. Does not enforce the existence of the vertex.

◆ add_edge() [1/2]

template<typename Container >

edge_descriptor stapl::graph_distribution< Container >::add_edge ( edge_descriptor const & ed )

Adds an edge with given descriptor and property.

Warning: Synchronous. Edge is added before returning.

Parameters

ed	Descriptor of the desired edge.

Returns: edge_descriptor of the added edge. The id of the edge_descriptor returned is set to numeric_limits<size_t>::max() if the edge was not added.

◆ add_edge() [2/2]

template<typename Container >

edge_descriptor stapl::graph_distribution< Container >::add_edge	(	edge_descriptor const &	ed,
		edge_property const &	ep
	)

Adds an edge with given descriptor and property.

Warning: Synchronous. Edge is added before returning.

Parameters

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

Returns: edge_descriptor of the added edge. The id of the edge_descriptor returned is set to numeric_limits<size_t>::max() if the edge was not added.

◆ add_edge_async() [1/2]

template<typename Container >

void stapl::graph_distribution< Container >::add_edge_async ( edge_descriptor const & ed )

Adds an edge with given descriptor.

The edge is added asynchronously and method returns immediately. Edge is not guaranteed to be added until after a global synchronization.

Parameters

ed	Descriptor of the desired edge.

◆ add_edge_async() [2/2]

template<typename Container >

void stapl::graph_distribution< Container >::add_edge_async	(	edge_descriptor const &	ed,
		edge_property const &	ep,
		bool	sibling = `false`
	)

Adds an edge with given descriptor and property. The edge is added asynchronously and method returns immediately. Edge is not guaranteed to be added until after a global synchronization.

Parameters

ed	Descriptor of the desired edge.
ep	Property of the edge.
sibling	Used to indicate if the edge is the second sibling in an undirected edge-pair.

◆ insert_edge() [1/2]

template<typename Container >

template<typename Comp >

edge_descriptor stapl::graph_distribution< Container >::insert_edge	(	edge_descriptor const &	ed,
		Comp const &	comp
	)

◆ insert_edge() [2/2]

template<typename Container >

template<typename Comp >

edge_descriptor stapl::graph_distribution< Container >::insert_edge	(	edge_descriptor const &	ed,
		edge_property const &	ep,
		Comp const &	comp
	)

Inserts an edge with given descriptor and property.

Warning: Synchronous. Edge is inserted before returning.

Parameters

ed	Descriptor of the desired edge.
ep	Property of the edge.
comp	Comparator workfunction passed to std::lower_bound to determine where to insert the edge.

Returns: edge_descriptor of the added edge. The id of the edge_descriptor returned is set to numeric_limits<size_t>::max() if the edge was not added.

◆ insert_edge_async() [1/2]

template<typename Container >

template<typename Comp >

void stapl::graph_distribution< Container >::insert_edge_async	(	edge_descriptor const &	ed,
		Comp const &	comp
	)

Inserts an edge with given descriptor.

The edge is inserted asynchronously and method returns immediately. Edge is not guaranteed to be added until after a global synchronization.

Parameters

ed	Descriptor of the desired edge.

◆ insert_edge_async() [2/2]

template<typename Container >

template<typename Comp >

void stapl::graph_distribution< Container >::insert_edge_async	(	edge_descriptor const &	ed,
		edge_property const &	ep,
		Comp const &	comp,
		bool	sibling = `false`
	)

Parameters

sibling Used to indicate if the edge is the second sibling in an undirected edge-pair.

◆ aggregate_apply_async() [1/3]

template<typename Container >

template<typename Cont , typename F >

void stapl::graph_distribution< Container >::aggregate_apply_async	(	Cont &&	cont,
		F const &	f
	)

Applies a functor on this location.

All elements must be local. For internal use by Aggregators.

Parameters

v	Container of elements to be passed-in to f.
f	Functor to be applied to each element of v on the desired location. f is passed an element of v.

◆ aggregate_apply_async() [2/3]

template<typename Container >

template<typename Cont , typename F >

void stapl::graph_distribution< Container >::aggregate_apply_async	(	size_t	loc,
		Cont const &	cont,
		F const &	f
	)

◆ guarded_aggregate_apply_async()

template<typename Container >

template<typename Cont , typename F >

void stapl::graph_distribution< Container >::guarded_aggregate_apply_async	(	size_t	loc,
		Cont const &	cont,
		F const &	f
	)

◆ add_edge_promise()

template<typename Container >

void stapl::graph_distribution< Container >::add_edge_promise	(	edge_descriptor const &	ed,
		edge_property const &	ep,
		promise< edge_descriptor >	p,
		bool	sibling = `false`
	)

protected

used by add_edge method to populate a promise so that the edge descriptor may be returned for the synchronous method.

Parameters

ed	The edge descriptor of the edge being added.
ep	The property of the edge being added.
p	The promise object used to return the edge descriptor.
sibling	Used to indicate if the edge is the second sibling in an undirected edge-pair.

◆ insert_edge_promise()

template<typename Container >

template<typename Comp >

void stapl::graph_distribution< Container >::insert_edge_promise	(	edge_descriptor const &	ed,
		edge_property const &	ep,
		Comp const &	comp,
		promise< edge_descriptor >	p,
		bool	sibling = `false`
	)

protected

used by insert_edge method to populate a promise so that the edge descriptor may be returned for the synchronous method.

Parameters

ed	The edge descriptor of the edge being added.
ep	The property of the edge being added.
comp	Passed internal to std::lower_bound to find the spot to insert the new edge.
p	The promise object used to return the edge descriptor.
sibling	Used to indicate if the edge is the second sibling in an undirected edge-pair.

◆ delete_edge()

template<typename Container >

void stapl::graph_distribution< Container >::delete_edge ( edge_descriptor const & ed )

Deletes the edge with given descriptor. Asynchronous.

Parameters

ed	Descriptor of the desired edge.

◆ clear()

template<typename Container >

void stapl::graph_distribution< Container >::clear ( void )

Clears the graph. This resets internal counters for vertex-descriptor and edge-id assignments, and clears graph storage.

Note: This method assumes being called in SPMD (by all locations).

◆ clear_edges()

template<typename Container >

void stapl::graph_distribution< Container >::clear_edges ( void )

Note: This method assumes being called in SPMD (by all locations).

◆ num_local_edges()

template<typename Container >

size_t stapl::graph_distribution< Container >::num_local_edges ( void ) const

Returns the number of local outgoing edges in the pGraph. This is a blocking method.

Returns: size_t total number of outgoing adjacent-edges for all local vertices.

◆ num_local_self_edges()

template<typename Container >

size_t stapl::graph_distribution< Container >::num_local_self_edges ( void ) const

Returns the number of self edges in the pGraph. This is a blocking method.

Returns: size_t total number of self edges for all local vertices.

◆ num_edges()

template<typename Container >

size_t stapl::graph_distribution< Container >::num_edges ( void ) const

Returns the number of edges in the pGraph. This method is a non-collective version of num_edges. This must be used when not all locations are calling num_edges.

For a faster collective, use num_edges_collective() below.

Returns: size_t number of edges in the pGraph.

◆ num_self_edges()

template<typename Container >

size_t stapl::graph_distribution< Container >::num_self_edges ( void ) const

Returns the number of self edges in the pGraph. This must be used when not all locations are calling num_self_edges. For a faster collective, use num_self_edges_collective() below.

Returns: size_t number of self edges in the pGraph.

◆ num_edges_collective()

template<typename Container >

size_t stapl::graph_distribution< Container >::num_edges_collective ( void ) const

Returns the number of edges in the pGraph.

Warning: This method is blocking, collective version of num_edges. Use when calling num-edges from all locations, which is faster than calling num_edges() above.

Returns: size_t number of edges in the pGraph.

◆ num_self_edges_collective()

template<typename Container >

size_t stapl::graph_distribution< Container >::num_self_edges_collective ( void ) const

Returns the number of self edges in the pGraph.

Warning: This method is blocking, collective version of num_self_edges. Use when calling num-edges from all locations, which is faster than calling num_self_edges() above.

Returns: size_t number of self edges in the pGraph.

◆ aggregate_vp_apply_async() [1/2]

template<typename Container >

template<typename FCont >

void stapl::graph_distribution< Container >::aggregate_vp_apply_async ( FCont const & fcont )

Applies functors to respective vertex-properties on this location. All elements must be local. For internal use by Aggregators.

Parameters

fcont Container of functors to be applied. Each element of f should provide a target() method that returns the descriptor of the target vertex. Each element of f is given the property of its corresponding vertex.

◆ aggregate_vp_apply_async() [2/2]

template<typename Container >

template<typename FCont >

void stapl::graph_distribution< Container >::aggregate_vp_apply_async	(	size_t	loc,
		FCont const &	fcont
	)

Applies functors to respective vertex-properties on the desired location. For internal use by Aggregators. This method is asynchronous.

Parameters

loc	Location where functors are to be executed.
fcont	Container of functors to be applied. Each element of fcont should provide a target() method that returns the descriptor of the target vertex. Each element of fcont is given the property of its corresponding vertex.

◆ aggregate_async() [1/2]

template<typename Container >

template<typename Cont , typename F >

void stapl::graph_distribution< Container >::aggregate_async	(	Cont const &	cont,
		F const &	f
	)

Applies a functor on this location. All elements must be local. For internal use by Aggregators.

Parameters

cont	Container of elements to be passed-in to f.
f	Functor to be applied to each element of cont on the desired location. f is passed an element of cont as well as a pointer to the pGraph.

◆ aggregate_async() [2/2]

template<typename Container >

template<typename Cont , typename F >

void stapl::graph_distribution< Container >::aggregate_async	(	size_t	loc,
		Cont const &	cont,
		F const &	f
	)

Applies a functor on the desired location. For internal use by Aggregators. This method is asynchronous.

Parameters

loc	Location where functors are to be executed.
cont	Container of elements to be passed-in to f.
f	Functor to be applied to each element of v on the desired location. f is passed an element of v as well as a pointer to the pGraph.

◆ vp_apply_async()

template<typename Container >

template<typename F >

void stapl::graph_distribution< Container >::vp_apply_async	(	vertex_descriptor const &	gid,
		F const &	f
	)

Applies a function to the property of vertex with given descriptor. This method is asynchronous.

Parameters

gid	Descriptor of the vertex.
f	Functor to be applied to the target vertex's property.

◆ vp_apply() [1/2]

template<typename Container >

template<typename F >

F::result_type stapl::graph_distribution< Container >::vp_apply	(	gid_type const &	gid,
		F const &	f
	)

Applies a function to the property of vertex with given descriptor.

Warning: This method is synchronous.

Parameters

gid	Descriptor of the vertex.
f	Functor to be applied to the target vertex's property.

Returns: The result of applying f to the vertex's property.

◆ vp_apply() [2/2]

template<typename Container >

template<typename F >

F::result_type stapl::graph_distribution< Container >::vp_apply	(	gid_type const &	gid,
		F const &	f
	)		const

Applies a function to the property of vertex with given descriptor.

Warning: This method is synchronous.

Parameters

gid	Descriptor of the vertex.
f	Functor to be applied to the target vertex's property.

Returns: The result of applying f to the vertex's property.

◆ ep_apply_async()

template<typename Container >

template<typename Functor >

void stapl::graph_distribution< Container >::ep_apply_async	(	edge_descriptor const &	ed,
		Functor const &	f
	)

Applies a function to the property of edge with given descriptor. This method is asynchronous.

Parameters

ed	Descriptor of the edge.
f	Functor to be applied to the target edge's property.

◆ ep_apply()

template<typename Container >

template<typename Functor >

Functor::result_type stapl::graph_distribution< Container >::ep_apply	(	edge_descriptor const &	ed,
		Functor const &	f
	)

Applies a function to the property of edge with given descriptor.

Warning: This method is synchronous.

Parameters

ed	Descriptor of the edge.
f	Functor to be applied to the target edge's property.

Returns: The result of applying f to the edge's property.

◆ ep_apply_promise()

template<typename Container >

template<typename Functor >

void stapl::graph_distribution< Container >::ep_apply_promise	(	edge_descriptor const &	ed,
		Functor const &	f,
		promise< typename Functor::result_type >	p
	)

Applies a function to the specified edge and populates a promise with the result. Used by ep_apply.

Parameters

ed	Descriptor of the edge.
f	Functor to be applied to the target edge's property.
p	Promise storing the result of applying f to the edge's property.

◆ ep_find_apply()

template<typename Container >

template<typename Functor >

bool stapl::graph_distribution< Container >::ep_find_apply	(	edge_descriptor const &	ed,
		Functor const &	f
	)

Applies a functor f on the property of the specified edge, if it exists.

Parameters

ed	The descriptor of the edge on which the functor will be applied.
f	The functor to be applied.

Returns: True if the edge exists, False otherwise.

◆ ep_find_apply_promise()

template<typename Container >

template<typename Functor >

void stapl::graph_distribution< Container >::ep_find_apply_promise	(	edge_descriptor const &	ed,
		Functor const &	f,
		promise< bool >	p
	)

Applies the given functor on the property of the specified edge, if it exists. Populates a promise variable with true if the edge was found, or false otherwise.

Parameters

ed	Descriptor of the edge.
f	Functor to be applied to the target edge's property.
p	Promise storing the result of applying f to the edge's property.

◆ make_iterator() [1/4]

template<typename Container >

iterator stapl::graph_distribution< Container >::make_iterator ( gid_type const & gid )

Constructs a vertex iterator to the given descriptor.

Parameters

gid	Descriptor of the desired vertex.

Returns: vertex_iterator to the desired vertex.

◆ make_iterator() [2/4]

template<typename Container >

const_iterator stapl::graph_distribution< Container >::make_iterator ( gid_type const & gid ) const

Constructs a const vertex iterator to the vertex with the specified descriptor.

Parameters

gid	descriptor of the vertex to which the iterator will point.

◆ make_iterator() [3/4]

template<typename Container >

iterator stapl::graph_distribution< Container >::make_iterator	(	domain_type const &	domain,
		gid_type const &	gid
	)

Creates an iterator to the specified gid, which is restricted to the provided domain.

Parameters

domain	The domain to which the iterator will be restricted.
gid	The gid of the vertex to which the iterator will point.

Returns: The iterator pointing to the specified gid, restricted to the given domain.

◆ make_iterator() [4/4]

template<typename Container >

const_iterator stapl::graph_distribution< Container >::make_iterator	(	domain_type const &	domain,
		gid_type const &	gid
	)		const

Creates an iterator to the specified gid, which is restricted to the provided domain.

Parameters

domain	The domain to which the iterator will be restricted.
gid	The gid of the vertex to which the iterator will point.

Returns: The iterator pointing to the specified gid, restricted to the given domain.

◆ make_reference() [1/2]

template<typename Container >

reference stapl::graph_distribution< Container >::make_reference ( index_type const & gid )

Constructs a reference to the vertex with the given descriptor.

Parameters

gid	Descriptor of the desired vertex.

Returns: reference to the desired vertex.

◆ make_reference() [2/2]

template<typename Container >

const_reference stapl::graph_distribution< Container >::make_reference ( index_type const & gid ) const

Constructs a reference to the vertex with the given descriptor.

Parameters

gid	Descriptor of the desired vertex.

Returns: reference to the desired vertex.

◆ metadata()

template<typename Container >

local_return_type stapl::graph_distribution< Container >::metadata ( void )

Returns the metadata information for the base-containers on this location.

See also: metadata_entry.

◆ defer_metadata_at() [1/2]

template<typename Container >

void stapl::graph_distribution< Container >::defer_metadata_at	(	gid_type const &	gid,
		promise< dom_info_type >	p
	)

protected

Returns the metadata associated with the given gid by setting the value of the promise.

Parameters

gid	Id of the element of interest
p	Promise that will return the locality information to the location that invoked the method.

◆ metadata_at()

template<typename Container >

future<dom_info_type> stapl::graph_distribution< Container >::metadata_at ( gid_type const & gid )

Returns the metadata associated with the given index.

◆ has_edge()

future<bool> stapl::detail::graph_distribution_base< Container, graph_distribution< Container > >::has_edge	(	vertex_descriptor const &	source,
		vertex_descriptor const &	target
	)

inherited

Determines whether there exists an edge between two vertices.

Returns: A future representing the answer to this query

◆ aggregate_apply_async() [3/3]

void stapl::detail::graph_distribution_base< Container, graph_distribution< Container > >::aggregate_apply_async	(	Cont &&	cont,
		F &&	f
	)

inherited

Applies a functor on this location.

All elements must be local. For internal use by Aggregators.

Parameters

v	Container of elements to be passed-in to f.
f	Functor to be applied to each element of v on the desired location. f is passed an element of v.

◆ guarded_apply_set()

void stapl::detail::graph_distribution_base< Container, graph_distribution< Container > >::guarded_apply_set	(	vertex_descriptor const &	gid,
		F &&	f
	)

inherited

Apply a functor to the element at a given GID in a non-concurrent manner. That is, if the graph is already in an apply_set, then this apply_set will be deferred until the one in progress has ended.

Parameters

gid	The GID of the vertex
f	The functor to apply

◆ guarded_unordered_apply()

void stapl::detail::graph_distribution_base< Container, graph_distribution< Container > >::guarded_unordered_apply	(	vertex_descriptor const &	gid,
		F &&	f
	)

inherited

Apply a functor to the element at a given GID in a non-concurrent manner. That is, if the graph is already in an unordered_apply, then this unordered_apply will be deferred until the one in progress has ended.

Parameters

gid	The GID of the vertex
f	The functor to apply

◆ is_local()

bool stapl::distribution< Container, detail::nat1 , detail::nat2 , detail::nat3 , detail::nat4 >::is_local ( Indices const &... i ) const

inherited

Returns if the element with the specified gid is stored on this location.

Parameters

i	components of a gid if it is multidimensional, otherwise i is the gid.

◆ defer_metadata_at() [2/2]

void stapl::distribution< Container, detail::nat1 , detail::nat2 , detail::nat3 , detail::nat4 >::defer_metadata_at	(	gid_type const &	gid,
		promise< dom_info_type >	p
	)

inherited

Returns the metadata associated with the given gid by setting the value of the promise.

Parameters

gid	Id of the element of interest
p	Promise that will return the locality information to the location that invoked the method.

◆ metadata_of()

dom_info_type stapl::distribution< Container, detail::nat1 , detail::nat2 , detail::nat3 , detail::nat4 >::metadata_of ( cid_type const & cid )

inherited

Return the metadata associated with the specified component.

Parameters

cid	id of the base container for which metadata is requested.

Returns: Metadata of the base container if it is stored on this location.

◆ redistribute()

void stapl::distribution< Container, detail::nat1 , detail::nat2 , detail::nat3 , detail::nat4 >::redistribute	(	std::shared_ptr< DistSpecView >	dist_view,
		typename std::enable_if< is_distribution_view< DistSpecView >::value >::type *	= `0`
	)

inherited

Redistribute data to match the distribution specification provided.

Parameters

dist_view View-based specification of the distribution that the container elements will match after method completion.

◆ update()

void stapl::distribution< Container, detail::nat1 , detail::nat2 , detail::nat3 , detail::nat4 >::update ( std::vector< std::tuple< std::pair< gid_type, gid_type >, cid_type, location_type >> const & updates )

inherited

Add information on the distribution of elements not yet in the container. Use in dynamic containers with view-based distributions to allow element distribution to be based on computation.

Parameters

updates Explicit mapping information of sets of contiguous GIDs to partition ids and location ids.

◆ set_element()

void stapl::operations::settable< graph_distribution< Container > >::set_element	(	gid_type const &	gid,
		value_type const &	val
	)

inherited

Update the element at a GID by replacing it with a given value.

Parameters

gid	GID of the element to replace
val	The new value for the element

◆ set_elements()

void stapl::operations::settable< graph_distribution< Container > >::set_elements	(	gid_type	gid,
		SourceView &&	source_view
	)

inherited

Update a range of contiguous elements in the container, starting at gid. A total of view.size() elements will be updated with the values in view.

Note: Implementation assumes partition::try_get_domain will not fail if partition::contained_in succeeds.

◆ get_element()

value_type stapl::operations::gettable< graph_distribution< Container > >::get_element ( gid_type const & gid ) const

inherited

Return a copy of the element at a specific GID. Note that this is a blocking operation.

Parameters

gid	GID of the element to retrieve

Returns: Copy of the element at gid

◆ get_element_split()

future<value_type> stapl::operations::gettable< graph_distribution< Container > >::get_element_split ( gid_type const & gid )

inherited

Return a future of the element at a specific GID. This is a non-blocking operation.

Parameters

gid	GID of the element to retrieve

Returns: Future of the element at gid

◆ apply_set()

void stapl::operations::applyable< graph_distribution< Container > >::apply_set	(	gid_type const &	gid,
		Functor const &	f
	)

inherited

Apply a function object to the element with the given GID.

Parameters

gid	GID of the element for which we want to apply the function object.
f	Function object to apply to the element.

Warning: The function operator of f has to be const qualified.

◆ unordered_apply_set()

void stapl::operations::applyable< graph_distribution< Container > >::unordered_apply_set	(	gid_type const &	gid,
		Functor &&	f
	)

inherited

Apply a function object to the element with the given GID, disregarding RMI causal ordering.

Parameters

gid	GID of the element for which we want to apply the function object.
f	Function object to apply to the element.

Warning: The function operator of f has to be const qualified.

◆ unordered_apply()

void stapl::operations::applyable< graph_distribution< Container > >::unordered_apply	(	gid_type const &	gid,
		Functor &&	f
	)

inherited

Apply a function object to the element with the given GID, passing along the distribution pointer and disregarding RMI causal ordering.

Parameters

gid	GID of the element for which we want to apply the function object.
f	Function object to apply to the element.

Warning: The function operator of f has to be const qualified.

◆ apply_get() [1/2]

boost::result_of<Functor(value_type&)>::type stapl::operations::applyable< graph_distribution< Container > >::apply_get	(	gid_type const &	gid,
		Functor const &	f
	)

inherited

Apply a function object to the element with the given GID and return the result.

Parameters

gid	GID of the element for which we want to apply the function object and return the result.
f	Function object to apply to the element.

Returns: The result of applying f to the element.

Warning: This function assumes that the Functor reflects a public type result_type and that the invocation of its function operator returns a value that is convertible to result_type. The function operator of f has to be const qualified.

◆ apply_get() [2/2]

boost::result_of<Functor(value_type&)>::type stapl::operations::applyable< graph_distribution< Container > >::apply_get	(	gid_type const &	gid,
		Functor const &	f
	)		const

inherited

Apply a function object to the element with the given GID and return the result.

Parameters

gid	GID of the element for which we want to apply the function object and return the result.
f	Function object to apply to the element.

Returns: The result of applying f to the element.

Warning: This function assumes that the Functor reflects a public type result_type and that the invocation of its function operator returns a value that is convertible to result_type. The function operator of f has to be const qualified.

◆ migrate()

void stapl::operations::migratable< graph_distribution< Container > >::migrate	(	gid_type const &	gid,
		const location_type	destination
	)

inherited

Migrate a single element with a specific GID to a given location.

This is the first (intent) message in the migration protocol described in LCPC 2012.

Parameters

gid	The GID to migrate
destination	The location to migrate to

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

graph/distribution.hpp

Public Member Functions

Public Types

Protected Member Functions

Protected Types

Protected Attributes

Detailed Description

template<typename Container> struct stapl::graph_distribution< Container >

Constructor & Destructor Documentation

◆ graph_distribution() [1/3]

◆ graph_distribution() [2/3]

◆ graph_distribution() [3/3]

Member Function Documentation

◆ sort_edges_ascending()

◆ sort_edges_locality()

◆ sort_edges()

◆ add_vertex() [1/3]

◆ add_vertex() [2/3]

◆ try_insert()

◆ add_vertex() [3/3]

◆ add_vertex_uniform()

◆ delete_vertex()

◆ erase_edges_if()

◆ find_vertex()

◆ find()

◆ add_edge() [1/2]

◆ add_edge() [2/2]

◆ add_edge_async() [1/2]

◆ add_edge_async() [2/2]

◆ insert_edge() [1/2]

◆ insert_edge() [2/2]

◆ insert_edge_async() [1/2]

◆ insert_edge_async() [2/2]

◆ aggregate_apply_async() [1/3]

◆ aggregate_apply_async() [2/3]

◆ guarded_aggregate_apply_async()

◆ add_edge_promise()

◆ insert_edge_promise()

◆ delete_edge()

◆ clear()

◆ clear_edges()

◆ num_local_edges()

◆ num_local_self_edges()

◆ num_edges()

◆ num_self_edges()

◆ num_edges_collective()

◆ num_self_edges_collective()

◆ aggregate_vp_apply_async() [1/2]

◆ aggregate_vp_apply_async() [2/2]

◆ aggregate_async() [1/2]

◆ aggregate_async() [2/2]

◆ vp_apply_async()

◆ vp_apply() [1/2]

◆ vp_apply() [2/2]

◆ ep_apply_async()

◆ ep_apply()

◆ ep_apply_promise()

◆ ep_find_apply()

◆ ep_find_apply_promise()

◆ make_iterator() [1/4]

◆ make_iterator() [2/4]

◆ make_iterator() [3/4]

◆ make_iterator() [4/4]

◆ make_reference() [1/2]

◆ make_reference() [2/2]

◆ metadata()

◆ defer_metadata_at() [1/2]

◆ metadata_at()

◆ has_edge()

◆ aggregate_apply_async() [3/3]

◆ guarded_apply_set()

◆ guarded_unordered_apply()

◆ is_local()

◆ defer_metadata_at() [2/2]

◆ metadata_of()

◆ redistribute()

◆ update()

◆ set_element()

◆ set_elements()

◆ get_element()

◆ get_element_split()

template<typename Container>
struct stapl::graph_distribution< Container >