Parallel data graph structures in Galois. More...

Classes
class	PartitioningScaffold
	Default fields and functions all CuSP partitioners use; this is a class to inherit from. More...

class	ReadMasterAssignment
	Policies that use the read assignment of nodes as the masters. More...

class	CustomMasterAssignment
	Policies that use a custom assignment of masters (from the user). More...

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

class	MiningGraph

class	NewDistGraphGeneric

class	BufferedGraph
	Class that loads a portion of a Galois graph from disk directly into memory buffers for access. More...

struct	read_default_graph_tag

struct	read_with_aux_graph_tag

struct	read_lc_inout_graph_tag

struct	read_with_aux_first_graph_tag

class	EdgeSortValue
	Proxy object for internal EdgeSortReference. More...

class	FileGraph
	Graph that mmaps Galois gr files for access. More...

class	FileGraphWriter
	Simplifies writing graphs. More...

class	LC_Adaptor_Graph

class	LC_CSR_CSC_Graph
	An bidirectional LC_CSR_Graph that allows the construction of in-edges from its outedges. More...

class	LC_CSR_Graph
	Local computation graph (i.e., graph structure does not change). More...

class	LC_CSR_Hypergraph
	Local computation graph (i.e., graph structure does not change). More...

class	LC_InlineEdge_Graph
	Local computation graph (i.e., graph structure does not change). More...

class	LC_InOut_Graph
	Modify a LC_Graph to have in and out edges. More...

class	LC_Linear_Graph
	Local computation graph (i.e., graph structure does not change). More...

class	LC_Morph_Graph
	Local computation graph that allows addition of nodes (but not removals) if the maximum degree of a node is known at the time it is added. More...

class	Morph_SepInOut_Graph
	A Graph. More...

class	MorphGraph
	A graph that can have new nodes and edges added to it. More...

class	MorphHyperGraph
	A graph that can have new nodes and edges added to it. More...

class	BindSegmentGraph
	Binds the segment parameter of an out-of-core graph so that it can be used in place of a non out-of-core graph. More...

class	OCFileGraph
	Like FileGraph but allows partial loading of the graph. More...

struct	read_oc_immutable_edge_graph_tag

class	OCImmutableEdgeGraph

class	OfflineGraph

class	OfflineGraphWriter

struct	ReadGraphConstructFrom

struct	ReadGraphConstructNodesFrom

struct	ReadGraphConstructEdgesFrom

struct	ReadGraphConstructOutEdgesFrom

struct	ReadGraphConstructInEdgesFrom

class	SpatialTree2d
	Stores sets of objects at specific spatial coordinates in a quad tree. More...

struct	is_segmented

class	GluonEdgeSubstrate
	Gluon communication substrate that handles communication given a user graph. More...

class	GluonSubstrate
	Gluon communication substrate that handles communication given a user graph. More...

Enumerations
enum	MASTERS_DISTRIBUTION { BALANCED_MASTERS, BALANCED_EDGES_OF_MASTERS, BALANCED_MASTERS_AND_EDGES }
	Enums specifying how masters are to be distributed among hosts. More...

Functions
template<typename EdgeTy >
void	makeSymmetric (FileGraph &in_graph, FileGraph &out)
	Adds reverse edges to a graph. More...

template<typename EdgeTy , typename PTy >
void	permute (FileGraph &in_graph, const PTy &p, FileGraph &out)
	Permutes a graph. More...

template<typename PrefixSumType , typename NodeType = uint64_t>
auto	divideNodesBinarySearch (NodeType numNodes, uint64_t numEdges, size_t nodeWeight, size_t edgeWeight, size_t id, size_t total, PrefixSumType &edgePrefixSum, std::vector< unsigned > scaleFactor=std::vector< unsigned >(), uint64_t edgeOffset=0, uint64_t nodeOffset=0)
	Returns 2 ranges (one for nodes, one for edges) for a particular division. More...

template<typename GraphTy >
std::vector< uint32_t >	determineUnitRangesFromGraph (GraphTy &graph, uint32_t unitsToSplit, uint32_t nodeAlpha=0)
	Determines node division ranges for all nodes in a graph and returns it in an offset vector. More...

template<typename GraphTy >
std::vector< uint32_t >	determineUnitRangesFromGraph (GraphTy &graph, uint32_t unitsToSplit, uint32_t beginNode, uint32_t endNode, uint32_t nodeAlpha=0)
	Determines node division ranges for a given range of nodes and returns it as an offset vector. More...

template<typename VectorTy >
std::vector< uint32_t >	determineUnitRangesFromPrefixSum (uint32_t unitsToSplit, VectorTy &edgePrefixSum, uint32_t nodeAlpha=0)
	Uses the divideByNode function (which is binary search based) to divide nodes among units using a provided prefix sum. More...

template<typename VectorTy >
std::vector< uint32_t >	determineUnitRangesFromPrefixSum (uint32_t unitsToSplit, VectorTy &edgePrefixSum, uint32_t beginNode, uint32_t endNode, uint32_t nodeAlpha=0)
	Uses the divideByNode function (which is binary search based) to divide nodes among units using a provided prefix sum. More...

template<typename GraphTy , typename... Args>
void	readGraphDispatch (GraphTy &graph, read_oc_immutable_edge_graph_tag, Args &&...args)

template<typename GraphTy , typename... Args>
void	readGraph (GraphTy &graph, Args &&...args)
	Allocates and constructs a graph from a file. More...

template<typename GraphTy >
void	readGraphDispatch (GraphTy &graph, read_default_graph_tag tag, const std::string &filename, const bool readUnweighted=false)

template<typename GraphTy >
void	readGraphDispatch (GraphTy &graph, read_default_graph_tag, FileGraph &f, const bool readUnweighted=false)

template<typename GraphTy >
void	readGraphDispatch (GraphTy &graph, read_with_aux_graph_tag tag, const std::string &filename)

template<typename GraphTy >
void	readGraphDispatch (GraphTy &graph, read_with_aux_graph_tag, FileGraph &f)

template<typename GraphTy >
void	readGraphDispatch (GraphTy &graph, read_with_aux_first_graph_tag, FileGraph &f)

template<typename GraphTy >
void	readGraphDispatch (GraphTy &graph, read_with_aux_first_graph_tag tag, const std::string &filename)

template<typename GraphTy >
void	readGraphDispatch (GraphTy &graph, read_lc_inout_graph_tag, const std::string &f1, const std::string &f2)

template<typename GraphTy >
void	readGraphDispatch (GraphTy &graph, read_lc_inout_graph_tag, FileGraph &f1, FileGraph &f2)

template<typename GraphTy >
void	readGraphDispatch (GraphTy &graph, read_lc_inout_graph_tag, FileGraph &f1)

template<typename GraphTy >
void	readGraphDispatch (GraphTy &graph, read_lc_inout_graph_tag, const std::string &f1)

Detailed Description

Parallel data graph structures in Galois.

Parallel graph data structures.

Enumeration Type Documentation

enum galois::graphs::MASTERS_DISTRIBUTION

Enums specifying how masters are to be distributed among hosts.

Enumerator
BALANCED_MASTERS	balance nodes
BALANCED_EDGES_OF_MASTERS	balance edges
BALANCED_MASTERS_AND_EDGES	balance nodes and edges

Function Documentation

template<typename GraphTy >

std::vector<uint32_t> galois::graphs::determineUnitRangesFromGraph	(	GraphTy &	graph,
		uint32_t	unitsToSplit,
		uint32_t	nodeAlpha = `0`
	)

Determines node division ranges for all nodes in a graph and returns it in an offset vector.

(node ranges = assigned nodes that a particular unit of execution should work on)

Checks for corner cases, then calls the main loop function.

ONLY CALL AFTER GRAPH IS CONSTRUCTED as it uses functions that assume the graph is already constructed.

Template Parameters

GraphTy type of the graph object

Parameters

graph	The graph object to get prefix sum information from
unitsToSplit	number of units to split nodes among
nodeAlpha	The higher the number, the more weight nodes have in determining division of nodes (edges have weight 1).

Returns: vector that indirectly specifies which units get which nodes

template<typename GraphTy >

std::vector<uint32_t> galois::graphs::determineUnitRangesFromGraph	(	GraphTy &	graph,
		uint32_t	unitsToSplit,
		uint32_t	beginNode,
		uint32_t	endNode,
		uint32_t	nodeAlpha = `0`
	)

Determines node division ranges for a given range of nodes and returns it as an offset vector.

(node ranges = assigned nodes that a particular unit of execution should work on)

Checks for corner cases, then calls the main loop function.

ONLY CALL AFTER GRAPH IS CONSTRUCTED as it uses functions that assume the graph is already constructed.

Template Parameters

GraphTy type of the graph object

Parameters

graph	The graph object to get prefix sum information from
unitsToSplit	number of units to split nodes among
beginNode	Beginning of range
endNode	End of range, non-inclusive
nodeAlpha	The higher the number, the more weight nodes have in determining division of nodes (edges have weight 1).

Returns: vector that indirectly specifies which units get which nodes

template<typename VectorTy >

std::vector<uint32_t> galois::graphs::determineUnitRangesFromPrefixSum	(	uint32_t	unitsToSplit,
		VectorTy &	edgePrefixSum,
		uint32_t	nodeAlpha = `0`
	)

Uses the divideByNode function (which is binary search based) to divide nodes among units using a provided prefix sum.

Template Parameters

VectorTy type of the prefix sum object

Parameters

unitsToSplit	number of units to split nodes among
edgePrefixSum	A prefix sum of edges
nodeAlpha	amount of weight to give to nodes when dividing work among threads

Returns: vector that indirectly specifies how nodes are split amongs units of execution

template<typename VectorTy >

std::vector<uint32_t> galois::graphs::determineUnitRangesFromPrefixSum	(	uint32_t	unitsToSplit,
		VectorTy &	edgePrefixSum,
		uint32_t	beginNode,
		uint32_t	endNode,
		uint32_t	nodeAlpha = `0`
	)

Uses the divideByNode function (which is binary search based) to divide nodes among units using a provided prefix sum.

Provide a node range so that the prefix sum is only calculated using that range.

Template Parameters

VectorTy type of the prefix sum object

Parameters

unitsToSplit	number of units to split nodes among
edgePrefixSum	A prefix sum of edges
beginNode	Beginning of range
endNode	End of range, non-inclusive
nodeAlpha	amount of weight to give to nodes when dividing work among threads

Returns: vector that indirectly specifies how nodes are split amongs units of execution

template<typename PrefixSumType , typename NodeType = uint64_t>

auto galois::graphs::divideNodesBinarySearch	(	NodeType	numNodes,
		uint64_t	numEdges,
		size_t	nodeWeight,
		size_t	edgeWeight,
		size_t	id,
		size_t	total,
		PrefixSumType &	edgePrefixSum,
		std::vector< unsigned >	scaleFactor = `std::vector<unsigned>()`,
		uint64_t	edgeOffset = `0`,
		uint64_t	nodeOffset = `0`
	)

Returns 2 ranges (one for nodes, one for edges) for a particular division.

The ranges specify the nodes/edges that a division is responsible for. The function attempts to split them evenly among units given some kind of weighting for both nodes and edges.

Assumes the parameters passed in apply to a local portion of whatever is being divided (i.e. concept of a "global" object is abstracted away in some sense)

Template Parameters

PrefixSumType	type of the object that holds the edge prefix sum
NodeType	size of the type representing the node

Parameters

numNodes	Total number of nodes included in prefix sum
numEdges	Total number of edges included in prefix sum
nodeWeight	weight to give to a node in division
edgeWeight	weight to give to an edge in division
id	Division number you want the range for
total	Total number of divisions to divide nodes among
edgePrefixSum	Prefix sum of the edges in the graph
scaleFactor	Vector specifying if certain divisions should get more than other divisions
edgeOffset	number of edges to subtract from numbers in edgePrefixSum
nodeOffset	number of nodes to skip over when looking in the prefix sum: useful if the prefix sum is over the entire graph while you just want to divide the nodes for a particular region (jump to the region with the nodeOffset)

Returns: A node pair and an edge pair specifying the assigned nodes/edges to division "id"; returns LOCAL ids, not global ids (i.e. if node offset was used, it is up to the caller to add the offset to the numbers)

template<typename EdgeTy >

void galois::graphs::makeSymmetric	(	FileGraph &	in_graph,
		FileGraph &	out
	)

Adds reverse edges to a graph.

Reverse edges have edge data copied from the original edge. The new graph is placed in the out parameter. The previous out is destroyed.

template<typename EdgeTy , typename PTy >

void galois::graphs::permute	(	FileGraph &	in_graph,
		const PTy &	p,
		FileGraph &	out
	)

Permutes a graph.

Permutation array, P, conforms to: P[i] = j where i is a node index from the original graph and j is a node index in the permuted graph. New, permuted graph is placed in the out parameter. The previous out is destroyed.

Parameters

in_graph	original graph
p	permutation array
out	permuted graph

template<typename GraphTy , typename... Args>

void galois::graphs::readGraph	(	GraphTy &	graph,
		Args &&...	args
	)

Allocates and constructs a graph from a file.

Tries to balance memory evenly across system. Cannot be called during parallel execution.

Examples:: lonestar/tutorial_examples/CountLevels.cpp, lonestar/tutorial_examples/GraphTraversalPullOperator.cpp, lonestar/tutorial_examples/GraphTraversalPushOperator.cpp, lonestar/tutorial_examples/GraphTraversalSerial.cpp, and lonestar/tutorial_examples/SSSPPushSimple.cpp.

template<typename GraphTy >

void galois::graphs::readGraphDispatch	(	GraphTy &	graph,
		read_default_graph_tag	tag,
		const std::string &	filename,
		const bool	readUnweighted = `false`
	)

If user specifies that the input graph is unweighted, the file graph also should be aware of this. Note that the application still could use the edge data array.

template<typename GraphTy >

void galois::graphs::readGraphDispatch	(	GraphTy &	graph,
		read_default_graph_tag	,
		FileGraph &	f,
		const bool	readUnweighted = `false`
	)

template<typename GraphTy >

void galois::graphs::readGraphDispatch	(	GraphTy &	graph,
		read_with_aux_graph_tag	tag,
		const std::string &	filename
	)

template<typename GraphTy >

void galois::graphs::readGraphDispatch	(	GraphTy &	graph,
		read_with_aux_graph_tag	,
		FileGraph &	f
	)

template<typename GraphTy >

void galois::graphs::readGraphDispatch	(	GraphTy &	graph,
		read_with_aux_first_graph_tag	,
		FileGraph &	f
	)

template<typename GraphTy >

void galois::graphs::readGraphDispatch	(	GraphTy &	graph,
		read_with_aux_first_graph_tag	tag,
		const std::string &	filename
	)

template<typename GraphTy >

void galois::graphs::readGraphDispatch	(	GraphTy &	graph,
		read_lc_inout_graph_tag	,
		const std::string &	f1,
		const std::string &	f2
	)

template<typename GraphTy >

void galois::graphs::readGraphDispatch	(	GraphTy &	graph,
		read_lc_inout_graph_tag	,
		FileGraph &	f1,
		FileGraph &	f2
	)

template<typename GraphTy >

void galois::graphs::readGraphDispatch	(	GraphTy &	graph,
		read_lc_inout_graph_tag	,
		FileGraph &	f1
	)

template<typename GraphTy >

void galois::graphs::readGraphDispatch	(	GraphTy &	graph,
		read_lc_inout_graph_tag	,
		const std::string &	f1
	)

template<typename GraphTy , typename... Args>

void galois::graphs::readGraphDispatch	(	GraphTy &	graph,
		read_oc_immutable_edge_graph_tag	,
		Args &&...	args
	)

Classes

Enumerations

Functions

Detailed Description

Enumeration Type Documentation

Function Documentation