fpmas::graph Namespace Reference

Namespaces
namespace	detail
namespace	zoltan

Classes
class	BipartiteGraphBuilder
class	ClusteredGraphBuilder
class	DefaultDistributedNodeBuilder
class	DistributedClusteredGraphBuilder
class	DistributedEdge
class	DistributedNode
class	DistributedNodeBuilder
class	DistributedUniformGraphBuilder
class	Edge
class	Graph
class	LocationManager
class	Node
class	RandomGraphBuilder
class	RandomLoadBalancing
class	RingGraphBuilder
class	ScheduledLoadBalancing
class	SmallWorldGraphBuilder
class	StaticLoadBalancing
class	TemporaryNode
class	UniformGraphBuilder
class	ZoltanLoadBalancing

Typedefs
template<typename T >
using	EdgePtrWrapper = api::utils::PtrWrapper< api::graph::DistributedEdge< T > >
template<typename T , template< typename > class SyncMode>
using	DistributedGraph = detail::DistributedGraph< T, SyncMode, graph::DistributedNode, graph::DistributedEdge, communication::TypedMpi, graph::LocationManager >
template<typename T >
using	NodePtrWrapper = api::utils::PtrWrapper< api::graph::DistributedNode< T > >

Enumerations
enum	RingType { LOOP , CYCLE }

Functions
template<typename T >
std::size_t	node_count (api::graph::DistributedGraph< T > &graph)
template<typename T >
std::size_t	edge_count (api::graph::DistributedGraph< T > &graph)
template<typename T >
std::unordered_map< DistributedId, std::vector< DistributedId > >	distant_nodes_outgoing_neighbors (fpmas::api::graph::DistributedGraph< T > &graph, fpmas::api::graph::LayerId layer)
template<typename T >
double	clustering_coefficient (fpmas::api::graph::DistributedGraph< T > &graph, fpmas::api::graph::LayerId layer)
template<typename T >
std::vector< DistributedId >	local_node_ids (fpmas::api::graph::DistributedGraph< T > &graph)
template<typename T >
std::unordered_map< DistributedId, std::unordered_map< DistributedId, float > >	shortest_path_lengths (fpmas::api::graph::DistributedGraph< T > &graph, fpmas::api::graph::LayerId layer, const std::vector< DistributedId > &source_nodes)
template<typename T >
float	characteristic_path_length (fpmas::api::graph::DistributedGraph< T > &graph, fpmas::api::graph::LayerId layer, const std::vector< DistributedId > &source_nodes)

Detailed Description

fpmas::api::graph implementations.

Typedef Documentation

EdgePtrWrapper

template<typename T >

using fpmas::graph::EdgePtrWrapper = typedef api::utils::PtrWrapper<api::graph::DistributedEdge<T> >

Alias for a DistributedEdge PtrWrapper

DistributedGraph

template<typename T , template< typename > class SyncMode>

using fpmas::graph::DistributedGraph = typedef detail::DistributedGraph< T, SyncMode, graph::DistributedNode, graph::DistributedEdge, communication::TypedMpi, graph::LocationManager>

Default api::graph::DistributedGraph implementation.

See also

detail::DistributedGraph

NodePtrWrapper

template<typename T >

using fpmas::graph::NodePtrWrapper = typedef api::utils::PtrWrapper<api::graph::DistributedNode<T> >

Alias for a DistributedNode PtrWrapper.

Enumeration Type Documentation

RingType

enum fpmas::graph::RingType

Ring graph types.

Enumerator
LOOP	A ring graph linked only in one direction, forming a directed loop.
CYCLE	A ring graph linked in both directions.

Function Documentation

node_count()

template<typename T >

std::size_t fpmas::graph::node_count

(

api::graph::DistributedGraph< T > &

graph

)

Counts the total number of nodes contained in the distributed graph.

This method is synchronous: it can't return before it as been initiated by all processes in graph.getMpiCommunicator(), since it requires collective communications.

Parameters

graph

Distributed graph instance

Returns

total node count within the graph

edge_count()

template<typename T >

std::size_t fpmas::graph::edge_count

(

api::graph::DistributedGraph< T > &

graph

)

Counts the total number of edges contained in the distributed graph.

This method is synchronous: it can't return before it as been initiated by all processes in graph.getMpiCommunicator(), since it requires collective communications.

Parameters

graph

Distributed graph instance

Returns

total edge count within the graph

distant_nodes_outgoing_neighbors()

template<typename T >

std::unordered_map< DistributedId, std::vector< DistributedId > > fpmas::graph::distant_nodes_outgoing_neighbors	(	fpmas::api::graph::DistributedGraph< T > &	graph,
		fpmas::api::graph::LayerId	layer
	)

Utility method used to retrieve the ids of outgoing neighbors of DISTANT nodes in the graph.

This can be used to build a representation of neighbors of DISTANT nodes, since such information is not supposed to be preserved by the DistributedGraph distribution process (only edges between LOCAL and DISTANT nodes are preserved).

Only edges on the specified layer are considered.

This method is synchronous: it can't return before it as been initiated by all processes in graph.getMpiCommunicator(), since it requires collective communications.

Parameters

graph	distributed graph input
layer	graph layer

Returns

a map containing an entry for each DISTANT node, in the form {node_id: {list of ids of outgoing neighbors}}

clustering_coefficient()

template<typename T >

double fpmas::graph::clustering_coefficient	(	fpmas::api::graph::DistributedGraph< T > &	graph,
		fpmas::api::graph::LayerId	layer
	)

Computes the local clustering coefficient of the specified distributed graph, as specified by Duncan J. Watts and Steven H. Strogatz to characterize small world networks. Only the edges on the specified layer are considered, so that a clustering coefficient can be computed independently for each layer.

The purpose of the measure for a single node is to evaluate how its neighbors are connected together, computing the proportion of existing edges between them. The algorithm returns the average value for all nodes in the graph.

This method is synchronous: it can't return before it as been initiated by all processes in graph.getMpiCommunicator(), since it requires collective communications.

This distributed implementation guarantees scalability, since the amount of additionnal data imported is only proportionnal to the count of DISTANT nodes in the graph.

Parameters

graph	distributed graph input
layer	layer on which the coefficient is computed

Returns

local clustering coefficient

local_node_ids()

template<typename T >

std::vector< DistributedId > fpmas::graph::local_node_ids

(

fpmas::api::graph::DistributedGraph< T > &

graph

)

Returns a vector containing the ids of LOCAL nodes within the distributed graph.

Parameters

graph

distributed graph

Returns

ids of LOCAL nodes

shortest_path_lengths()

template<typename T >

std::unordered_map< DistributedId, std::unordered_map< DistributedId, float > > fpmas::graph::shortest_path_lengths	(	fpmas::api::graph::DistributedGraph< T > &	graph,
		fpmas::api::graph::LayerId	layer,
		const std::vector< DistributedId > &	source_nodes
	)

Computes and return a distance_map such that for all local nodes in the graph and all specified source nodes the entry distance_map[node id][source id] contains the length of the shortest path from source to node on the specified layer. If no path is found, the distance is set to std::numeric_limits<float>::infinity().

This method is synchronous: it can't return before it as been initiated by all processes in graph.getMpiCommunicator(), since it requires collective communications.

Parameters

graph	distributed graph
layer	layer of edges to consider
source_nodes	ids of source node from which distances should be computed

characteristic_path_length()

template<typename T >

float fpmas::graph::characteristic_path_length	(	fpmas::api::graph::DistributedGraph< T > &	graph,
		fpmas::api::graph::LayerId	layer,
		const std::vector< DistributedId > &	source_nodes
	)

Computes the average shortest path length from sources to targets reachable on the specified layer.

When a target is not reachable, an infinite characteristic path length should mathematically be returned, but in order to get finite and meaningful values we prefer to ignore those pairs of nodes so that the characteristic path length is actually computed on the largest weakly connected component of the graph.

The source_nodes and layer parameters can be used to compute the characteristic path length only on a subgraph.

For example, in the case of a SpatialModel, the following snippet allows to compute the characteristic path length of the Cell network, ignoring SpatialAgents contained in the graph:

float L = fpmas::graph::characteristic_path_length(
   model.getModel().graph(), fpmas::api::model::CELL_SUCCESSOR,
   fpmas::model::local_agent_ids(model.cellGroup()));

Parameters

graph	distributed graph
layer	layer of edges to consider
source_nodes	ids of source node from which distances should be computed