Base DistGraph class that all distributed graphs extend from. More...

#include <DistributedGraph.h>

Inheritance diagram for galois::graphs::DistGraph< NodeTy, EdgeTy >:

Classes
struct	IdLess
	used to sort edges in the sort edges function More...

Public Types
using	GraphNode = typename GraphTy::GraphNode
	Type representing a node in this graph. More...

using	EdgeType = EdgeTy
	Expose EdgeTy to other classes. More...

using	iterator = typename GraphTy::iterator
	iterator type over nodes More...

using	const_iterator = typename GraphTy::const_iterator
	constant iterator type over nodes More...

using	edge_iterator = typename GraphTy::edge_iterator
	iterator type over edges More...

Public Member Functions
	DistGraph (unsigned host, unsigned numHosts)
	Constructor for DistGraph. More...

std::vector< std::pair < uint32_t, uint32_t > >	getMirrorRanges () const
	Return a vector of pairs denoting mirror node ranges. More...

std::vector< std::vector < size_t > > &	getMirrorNodes ()

virtual unsigned	getHostID (uint64_t) const =0
	Determines which host has the master for a particular node. More...

virtual bool	isOwned (uint64_t) const =0
	Determine if a node has a master on this host. More...

virtual bool	isLocal (uint64_t) const =0
	Determine if a node has a proxy on this host. More...

virtual bool	is_vertex_cut () const =0
	Returns true if current partition is a vertex cut. More...

virtual std::pair< unsigned, unsigned >	cartesianGrid () const
	Returns Cartesian split (if it exists, else returns pair of 0s. More...

bool	isTransposed ()

uint64_t	getGID (const uint32_t nodeID) const
	Converts a local node id into a global node id. More...

uint32_t	getLID (const uint64_t nodeID) const
	Converts a global node id into a local node id. More...

NodeTy &	getData (GraphNode N, galois::MethodFlag mflag=galois::MethodFlag::UNPROTECTED)
	Get data of a node. More...

GraphTy::edge_data_reference	getEdgeData (edge_iterator ni, galois::MethodFlag mflag=galois::MethodFlag::UNPROTECTED)
	Get the edge data for a particular edge in the graph. More...

GraphNode	getEdgeDst (edge_iterator ni)
	Gets edge destination of edge ni. More...

edge_iterator	edge_begin (GraphNode N)
	Gets the first edge of some node. More...

edge_iterator	edge_end (GraphNode N)
	Gets the end edge boundary of some node. More...

galois::runtime::iterable < galois::NoDerefIterator < edge_iterator > >	edges (GraphNode N)
	Returns an iterable object over the edges of a particular node in the graph. More...

size_t	size () const
	Gets number of nodes on this (local) graph. More...

size_t	sizeEdges () const
	Gets number of edges on this (local) graph. More...

size_t	numMasters () const
	Gets number of nodes on this (local) graph. More...

size_t	getNumNodesWithEdges () const
	Gets number of nodes with edges (may include nodes without edges) on this (local) graph. More...

size_t	globalSize () const
	Gets number of nodes on the global unpartitioned graph. More...

size_t	globalSizeEdges () const
	Gets number of edges on the global unpartitioned graph. More...

const NodeRangeType &	allNodesRange () const
	Returns a range object that encapsulates all nodes of the graph. More...

const NodeRangeType &	masterNodesRange () const
	Returns a range object that encapsulates only master nodes in this graph. More...

const NodeRangeType &	allNodesWithEdgesRange () const
	Returns a range object that encapsulates master nodes and nodes with edges in this graph. More...

void	save_local_graph_to_file (std::string)
	Write the local LC_CSR graph to the file on a disk. More...

void	read_local_graph_from_file (std::string)
	Read the local LC_CSR graph from the file on a disk. More...

void	deallocate ()
	Deallocates underlying LC CSR Graph. More...

void	sortEdgesByDestination ()
	Sort the underlying LC_CSR_Graph by ID (destinations) It sorts edges of the nodes by destination. More...

Protected Member Functions
void	increment_evilPhase ()
	Increments evilPhase, a phase counter used by communication. More...

unsigned	evilPhasePlus1 ()
	Returns evilPhase + 1, handling loop around as necessary. More...

uint64_t	computeMasters (MASTERS_DISTRIBUTION masters_distribution, galois::graphs::OfflineGraph &g, const std::vector< unsigned > &scalefactor, uint32_t nodeWeight=0, uint32_t edgeWeight=0, unsigned DecomposeFactor=1)
	Wrapper call that will call into more specific compute masters functions that compute masters based on nodes, edges, or both. More...

void	readersFromFile (galois::graphs::OfflineGraph &g, std::string filename)
	reader assignment from a file corresponds to master assignment if using an edge cut More...

uint32_t	G2L (uint64_t gid) const

uint64_t	L2G (uint32_t lid) const

void	determineThreadRanges ()
	Uses a pre-computed prefix sum to determine division of nodes among threads. More...

void	determineThreadRangesMaster ()
	Determines the thread ranges for master nodes only and saves them to the object. More...

void	determineThreadRangesWithEdges ()
	Determines the thread ranges for nodes with edges only and saves them to the object. More...

void	initializeSpecificRanges ()
	Initializes the 3 range objects that a user can access to iterate over the graph in different ways. More...

void	edgesEqualMasters ()
	Specific range editor: makes the range for edges equivalent to the range for masters. More...

Protected Attributes
GraphTy	graph
	The internal graph used by DistGraph to represent the graph. More...

bool	transposed
	Marks if the graph is transposed or not. More...

uint64_t	numGlobalNodes
	Total nodes in the global unpartitioned graph. More...

uint64_t	numGlobalEdges
	Total edges in the global unpartitioned graph. More...

uint32_t	numNodes
	Num nodes in this graph in total. More...

uint64_t	numEdges
	Num edges in this graph in total. More...

const unsigned	id
	ID of the machine. More...

const uint32_t	numHosts
	Total number of machines. More...

uint32_t	numOwned
	Number of nodes owned (masters) by this host. More...

uint32_t	beginMaster
	Local id of the beginning of master nodes. More...

uint32_t	numNodesWithEdges
	Number of nodes (masters + mirrors) that have outgoing edges. More...

std::vector< std::pair < uint64_t, uint64_t > >	gid2host
	Information that converts host to range of nodes that host reads. More...

std::vector< std::vector < size_t > >	mirrorNodes
	Mirror nodes from different hosts. For reduce. More...

std::vector< uint64_t >	localToGlobalVector
	GID = localToGlobalVector[LID]. More...

std::unordered_map< uint64_t, uint32_t >	globalToLocalMap
	LID = globalToLocalMap[GID]. More...

Detailed Description

template<typename NodeTy, typename EdgeTy>
class galois::graphs::DistGraph< NodeTy, EdgeTy >

Base DistGraph class that all distributed graphs extend from.

Template Parameters

NodeTy	type of node data for the graph
EdgeTy	type of edge data for the graph

Member Typedef Documentation

template<typename NodeTy , typename EdgeTy >

using galois::graphs::DistGraph< NodeTy, EdgeTy >::const_iterator = typename GraphTy::const_iterator

constant iterator type over nodes

template<typename NodeTy , typename EdgeTy >

using galois::graphs::DistGraph< NodeTy, EdgeTy >::edge_iterator = typename GraphTy::edge_iterator

iterator type over edges

template<typename NodeTy , typename EdgeTy >

using galois::graphs::DistGraph< NodeTy, EdgeTy >::EdgeType = EdgeTy

Expose EdgeTy to other classes.

template<typename NodeTy , typename EdgeTy >

using galois::graphs::DistGraph< NodeTy, EdgeTy >::GraphNode = typename GraphTy::GraphNode

Type representing a node in this graph.

template<typename NodeTy , typename EdgeTy >

using galois::graphs::DistGraph< NodeTy, EdgeTy >::iterator = typename GraphTy::iterator

iterator type over nodes

Constructor & Destructor Documentation

template<typename NodeTy , typename EdgeTy >

galois::graphs::DistGraph< NodeTy, EdgeTy >::DistGraph	(	unsigned	host,
		unsigned	numHosts
	)

inline

Constructor for DistGraph.

Initializes metadata fields.

Parameters

host	host number that this graph resides on
numHosts	total number of hosts in the currently executing program

Member Function Documentation

template<typename NodeTy , typename EdgeTy >

const NodeRangeType& galois::graphs::DistGraph< NodeTy, EdgeTy >::allNodesRange ( ) const

inline

Returns a range object that encapsulates all nodes of the graph.

Returns: A range object that contains all the nodes in this graph

template<typename NodeTy , typename EdgeTy >

const NodeRangeType& galois::graphs::DistGraph< NodeTy, EdgeTy >::allNodesWithEdgesRange ( ) const

inline

Returns a range object that encapsulates master nodes and nodes with edges in this graph.

Returns: A range object that contains the master nodes and the nodes with outgoing edges in this graph

template<typename NodeTy , typename EdgeTy >

virtual std::pair<unsigned, unsigned> galois::graphs::DistGraph< NodeTy, EdgeTy >::cartesianGrid ( ) const

inlinevirtual

Returns Cartesian split (if it exists, else returns pair of 0s.

Reimplemented in galois::graphs::NewDistGraphGeneric< NodeTy, EdgeTy, Partitioner >.

template<typename NodeTy , typename EdgeTy >

uint64_t galois::graphs::DistGraph< NodeTy, EdgeTy >::computeMasters	(	MASTERS_DISTRIBUTION	masters_distribution,
		galois::graphs::OfflineGraph &	g,
		const std::vector< unsigned > &	scalefactor,
		uint32_t	nodeWeight = `0`,
		uint32_t	edgeWeight = `0`,
		unsigned	DecomposeFactor = `1`
	)

inlineprotected

Wrapper call that will call into more specific compute masters functions that compute masters based on nodes, edges, or both.

Parameters

masters_distribution	method of masters distribution to use
g	The offline graph which has loaded the graph you want to get the masters for
scalefactor	A vector that specifies if a particular host should have more or less than other hosts
nodeWeight	weight to give nodes when computing balance
edgeWeight	weight to give edges when computing balance
DecomposeFactor	Specifies how decomposed the blocking of nodes should be. For example, a factor of 2 will make 2 blocks out of 1 block had the decompose factor been set to 1.

template<typename NodeTy , typename EdgeTy >

void galois::graphs::DistGraph< NodeTy, EdgeTy >::deallocate ( )

inline

Deallocates underlying LC CSR Graph.

template<typename NodeTy , typename EdgeTy >

void galois::graphs::DistGraph< NodeTy, EdgeTy >::determineThreadRanges ( )

inlineprotected

Uses a pre-computed prefix sum to determine division of nodes among threads.

The call uses binary search to determine the ranges.

template<typename NodeTy , typename EdgeTy >

void galois::graphs::DistGraph< NodeTy, EdgeTy >::determineThreadRangesMaster ( )

inlineprotected

Determines the thread ranges for master nodes only and saves them to the object.

Only call after graph is constructed + only call once

template<typename NodeTy , typename EdgeTy >

void galois::graphs::DistGraph< NodeTy, EdgeTy >::determineThreadRangesWithEdges ( )

inlineprotected

Determines the thread ranges for nodes with edges only and saves them to the object.

Only call after graph is constructed + only call once

template<typename NodeTy , typename EdgeTy >

edge_iterator galois::graphs::DistGraph< NodeTy, EdgeTy >::edge_begin ( GraphNode N )

inline

Gets the first edge of some node.

Parameters

N	node to get the edge of

Returns: iterator to first edge of N

template<typename NodeTy , typename EdgeTy >

edge_iterator galois::graphs::DistGraph< NodeTy, EdgeTy >::edge_end ( GraphNode N )

inline

Gets the end edge boundary of some node.

Parameters

N	node to get the edge of

Returns: iterator to the end of the edges of node N, i.e. the first edge of the next node (or an "end" iterator if there is no next node)

template<typename NodeTy , typename EdgeTy >

galois::runtime::iterable<galois::NoDerefIterator<edge_iterator> > galois::graphs::DistGraph< NodeTy, EdgeTy >::edges ( GraphNode N )

inline

Returns an iterable object over the edges of a particular node in the graph.

Parameters

N	node to get edges iterator over

template<typename NodeTy , typename EdgeTy >

void galois::graphs::DistGraph< NodeTy, EdgeTy >::edgesEqualMasters ( )

inlineprotected

Specific range editor: makes the range for edges equivalent to the range for masters.

template<typename NodeTy , typename EdgeTy >

unsigned galois::graphs::DistGraph< NodeTy, EdgeTy >::evilPhasePlus1 ( )

inlineprotected

Returns evilPhase + 1, handling loop around as necessary.

template<typename NodeTy , typename EdgeTy >

uint32_t galois::graphs::DistGraph< NodeTy, EdgeTy >::G2L ( uint64_t gid ) const

inlineprotected

template<typename NodeTy , typename EdgeTy >

NodeTy& galois::graphs::DistGraph< NodeTy, EdgeTy >::getData	(	GraphNode	N,
		galois::MethodFlag	mflag = `galois::MethodFlag::UNPROTECTED`
	)

inline

Get data of a node.

Parameters

N	node to get the data of
mflag	access flag for node data

Returns: A node data object

template<typename NodeTy , typename EdgeTy >

GraphTy::edge_data_reference galois::graphs::DistGraph< NodeTy, EdgeTy >::getEdgeData	(	edge_iterator	ni,
		galois::MethodFlag	mflag = `galois::MethodFlag::UNPROTECTED`
	)

inline

Get the edge data for a particular edge in the graph.

Parameters

ni	edge to get the data of
mflag	access flag for edge data

Returns: The edge data for the requested edge

template<typename NodeTy , typename EdgeTy >

GraphNode galois::graphs::DistGraph< NodeTy, EdgeTy >::getEdgeDst ( edge_iterator ni )

inline

Gets edge destination of edge ni.

Parameters

ni	edge id to get destination of

Returns: Local ID of destination of edge ni

template<typename NodeTy , typename EdgeTy >

uint64_t galois::graphs::DistGraph< NodeTy, EdgeTy >::getGID ( const uint32_t nodeID ) const

inline

Converts a local node id into a global node id.

Parameters

nodeID local node id

Returns: global node id corresponding to the local one

template<typename NodeTy , typename EdgeTy >

virtual unsigned galois::graphs::DistGraph< NodeTy, EdgeTy >::getHostID ( uint64_t ) const

pure virtual

Determines which host has the master for a particular node.

Returns: Host id of node in question

Implemented in galois::graphs::MiningGraph< NodeTy, EdgeTy, Partitioner >, and galois::graphs::NewDistGraphGeneric< NodeTy, EdgeTy, Partitioner >.

template<typename NodeTy , typename EdgeTy >

uint32_t galois::graphs::DistGraph< NodeTy, EdgeTy >::getLID ( const uint64_t nodeID ) const

inline

Converts a global node id into a local node id.

Parameters

nodeID global node id

Returns: local node id corresponding to the global one

template<typename NodeTy , typename EdgeTy >

std::vector<std::vector<size_t> >& galois::graphs::DistGraph< NodeTy, EdgeTy >::getMirrorNodes ( )

inline

template<typename NodeTy , typename EdgeTy >

std::vector<std::pair<uint32_t, uint32_t> > galois::graphs::DistGraph< NodeTy, EdgeTy >::getMirrorRanges ( ) const

inline

Return a vector of pairs denoting mirror node ranges.

Assumes all mirror nodes occur after the masters: this invariant should be held by CuSP.

template<typename NodeTy , typename EdgeTy >

size_t galois::graphs::DistGraph< NodeTy, EdgeTy >::getNumNodesWithEdges ( ) const

inline

Gets number of nodes with edges (may include nodes without edges) on this (local) graph.

Returns: number of nodes with edges (may include nodes without edges as it measures a contiguous range)

template<typename NodeTy , typename EdgeTy >

size_t galois::graphs::DistGraph< NodeTy, EdgeTy >::globalSize ( ) const

inline

Gets number of nodes on the global unpartitioned graph.

Returns: number of nodes present in the global unpartitioned graph

template<typename NodeTy , typename EdgeTy >

size_t galois::graphs::DistGraph< NodeTy, EdgeTy >::globalSizeEdges ( ) const

inline

Gets number of edges on the global unpartitioned graph.

Returns: number of edges present in the global unpartitioned graph

template<typename NodeTy , typename EdgeTy >

void galois::graphs::DistGraph< NodeTy, EdgeTy >::increment_evilPhase ( )

inlineprotected

Increments evilPhase, a phase counter used by communication.

template<typename NodeTy , typename EdgeTy >

void galois::graphs::DistGraph< NodeTy, EdgeTy >::initializeSpecificRanges ( )

inlineprotected

Initializes the 3 range objects that a user can access to iterate over the graph in different ways.

template<typename NodeTy , typename EdgeTy >

virtual bool galois::graphs::DistGraph< NodeTy, EdgeTy >::is_vertex_cut ( ) const

pure virtual

Returns true if current partition is a vertex cut.

Returns: true if partition being stored in this graph is a vertex cut

Implemented in galois::graphs::NewDistGraphGeneric< NodeTy, EdgeTy, Partitioner >.

template<typename NodeTy , typename EdgeTy >

virtual bool galois::graphs::DistGraph< NodeTy, EdgeTy >::isLocal ( uint64_t ) const

pure virtual

Determine if a node has a proxy on this host.

Returns: True if passed in global id has a proxy on this host

Implemented in galois::graphs::MiningGraph< NodeTy, EdgeTy, Partitioner >, and galois::graphs::NewDistGraphGeneric< NodeTy, EdgeTy, Partitioner >.

template<typename NodeTy , typename EdgeTy >

virtual bool galois::graphs::DistGraph< NodeTy, EdgeTy >::isOwned ( uint64_t ) const

pure virtual

Determine if a node has a master on this host.

Returns: True if passed in global id has a master on this host

Implemented in galois::graphs::MiningGraph< NodeTy, EdgeTy, Partitioner >, and galois::graphs::NewDistGraphGeneric< NodeTy, EdgeTy, Partitioner >.

template<typename NodeTy , typename EdgeTy >

bool galois::graphs::DistGraph< NodeTy, EdgeTy >::isTransposed ( )

inline

template<typename NodeTy , typename EdgeTy >

uint64_t galois::graphs::DistGraph< NodeTy, EdgeTy >::L2G ( uint32_t lid ) const

inlineprotected

template<typename NodeTy , typename EdgeTy >

const NodeRangeType& galois::graphs::DistGraph< NodeTy, EdgeTy >::masterNodesRange ( ) const

inline

Returns a range object that encapsulates only master nodes in this graph.

Returns: A range object that contains the master nodes in this graph

template<typename NodeTy , typename EdgeTy >

size_t galois::graphs::DistGraph< NodeTy, EdgeTy >::numMasters ( ) const

inline

Gets number of nodes on this (local) graph.

Returns: number of nodes present in this (local) graph

template<typename NodeTy , typename EdgeTy >

void galois::graphs::DistGraph< NodeTy, EdgeTy >::read_local_graph_from_file ( std::string )

inline

Read the local LC_CSR graph from the file on a disk.

template<typename NodeTy , typename EdgeTy >

void galois::graphs::DistGraph< NodeTy, EdgeTy >::readersFromFile	(	galois::graphs::OfflineGraph &	g,
		std::string	filename
	)

inlineprotected

reader assignment from a file corresponds to master assignment if using an edge cut

template<typename NodeTy , typename EdgeTy >

void galois::graphs::DistGraph< NodeTy, EdgeTy >::save_local_graph_to_file ( std::string )

inline

Write the local LC_CSR graph to the file on a disk.

template<typename NodeTy , typename EdgeTy >

size_t galois::graphs::DistGraph< NodeTy, EdgeTy >::size ( ) const

inline

Gets number of nodes on this (local) graph.

Returns: number of nodes present in this (local) graph

template<typename NodeTy , typename EdgeTy >

size_t galois::graphs::DistGraph< NodeTy, EdgeTy >::sizeEdges ( ) const

inline

Gets number of edges on this (local) graph.

Returns: number of edges present in this (local) graph

template<typename NodeTy , typename EdgeTy >

void galois::graphs::DistGraph< NodeTy, EdgeTy >::sortEdgesByDestination ( )

inline

Sort the underlying LC_CSR_Graph by ID (destinations) It sorts edges of the nodes by destination.

Member Data Documentation

template<typename NodeTy , typename EdgeTy >

uint32_t galois::graphs::DistGraph< NodeTy, EdgeTy >::beginMaster

protected

Local id of the beginning of master nodes.

beginMaster + numOwned = local id of the end of master nodes

template<typename NodeTy , typename EdgeTy >

std::vector<std::pair<uint64_t, uint64_t> > galois::graphs::DistGraph< NodeTy, EdgeTy >::gid2host

protected

Information that converts host to range of nodes that host reads.

template<typename NodeTy , typename EdgeTy >

std::unordered_map<uint64_t, uint32_t> galois::graphs::DistGraph< NodeTy, EdgeTy >::globalToLocalMap

protected

LID = globalToLocalMap[GID].

template<typename NodeTy , typename EdgeTy >

GraphTy galois::graphs::DistGraph< NodeTy, EdgeTy >::graph

protected

The internal graph used by DistGraph to represent the graph.

template<typename NodeTy , typename EdgeTy >

const unsigned galois::graphs::DistGraph< NodeTy, EdgeTy >::id

protected

ID of the machine.

template<typename NodeTy , typename EdgeTy >

std::vector<uint64_t> galois::graphs::DistGraph< NodeTy, EdgeTy >::localToGlobalVector

protected

GID = localToGlobalVector[LID].

template<typename NodeTy , typename EdgeTy >

std::vector<std::vector<size_t> > galois::graphs::DistGraph< NodeTy, EdgeTy >::mirrorNodes

protected

Mirror nodes from different hosts. For reduce.

template<typename NodeTy , typename EdgeTy >

uint64_t galois::graphs::DistGraph< NodeTy, EdgeTy >::numEdges

protected

Num edges in this graph in total.

template<typename NodeTy , typename EdgeTy >

uint64_t galois::graphs::DistGraph< NodeTy, EdgeTy >::numGlobalEdges

protected

Total edges in the global unpartitioned graph.

template<typename NodeTy , typename EdgeTy >

uint64_t galois::graphs::DistGraph< NodeTy, EdgeTy >::numGlobalNodes

protected

Total nodes in the global unpartitioned graph.

template<typename NodeTy , typename EdgeTy >

const uint32_t galois::graphs::DistGraph< NodeTy, EdgeTy >::numHosts

protected

Total number of machines.

template<typename NodeTy , typename EdgeTy >

uint32_t galois::graphs::DistGraph< NodeTy, EdgeTy >::numNodes

protected

Num nodes in this graph in total.

template<typename NodeTy , typename EdgeTy >

uint32_t galois::graphs::DistGraph< NodeTy, EdgeTy >::numNodesWithEdges

protected

Number of nodes (masters + mirrors) that have outgoing edges.

template<typename NodeTy , typename EdgeTy >

uint32_t galois::graphs::DistGraph< NodeTy, EdgeTy >::numOwned

protected

Number of nodes owned (masters) by this host.

size() - numOwned = mirrors on this host

template<typename NodeTy , typename EdgeTy >

bool galois::graphs::DistGraph< NodeTy, EdgeTy >::transposed

protected

Marks if the graph is transposed or not.

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

DistributedGraph.h

Classes

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

template<typename NodeTy, typename EdgeTy> class galois::graphs::DistGraph< NodeTy, EdgeTy >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<typename NodeTy, typename EdgeTy>
class galois::graphs::DistGraph< NodeTy, EdgeTy >