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

#include <FileGraph.h>

Inheritance diagram for galois::graphs::FileGraph:

Public Types
using	GraphNode = uint64_t
	type of a node More...

using	edge_iterator = boost::counting_iterator< uint64_t >
	Edge iterators (boost iterator) More...

typedef boost::transform_iterator < Convert32, uint32_t * >	neighbor_iterator
	iterator over neighbors More...

typedef boost::transform_iterator < Convert32, uint32_t * >	node_id_iterator
	iterator over node ids More...

typedef boost::transform_iterator < Convert64, uint64_t * >	edge_id_iterator
	edge iterator More...

typedef boost::counting_iterator < uint64_t >	iterator
	uint64 boost counting iterator More...

typedef std::pair< iterator, iterator >	NodeRange
	pair specifying a node range More...

typedef std::pair < edge_iterator, edge_iterator >	EdgeRange
	pair specifying an edge range More...

typedef std::pair< NodeRange, EdgeRange >	GraphRange
	pair of a NodeRange and an EdgeRange More...

Public Member Functions
void	reset_byte_counters ()
	Reset the num bytes counters. More...

uint64_t	num_bytes_read ()
	Return all bytes read. More...

bool	containsNode (const GraphNode n) const
	Checks if a node is in the graph (already added) More...

template<typename EdgeTy >
EdgeTy &	getEdgeData (GraphNode src, GraphNode dst)
	Get edge data of an edge between 2 nodes. More...

edge_iterator	edge_begin (GraphNode N)
	Returns the index to the beginning of global node N's outgoing edges in the outgoing edges array. More...

edge_iterator	edge_end (GraphNode N)
	Returns the index to the end of global node N's outgoing edges in the outgoing edges array. More...

runtime::iterable < NoDerefIterator < edge_iterator > >	edges (GraphNode N)
	Returns the edges of node N as a range that can be iterated through by C++ foreach. More...

runtime::iterable < NoDerefIterator < edge_iterator > >	out_edges (GraphNode N)
	Returns the edges of node N as a range that can be iterated through by C++ foreach. More...

template<typename EdgeTy , typename CompTy >
void	sortEdgesByEdgeData (GraphNode N, const CompTy &comp=std::less< EdgeTy >())
	Sorts outgoing edges of a node. More...

template<typename EdgeTy , typename CompTy >
void	sortEdges (GraphNode N, const CompTy &comp)
	Sorts outgoing edges of a node. More...

template<typename EdgeTy >
EdgeTy &	getEdgeData (edge_iterator it)
	Get edge data given an edge iterator. More...

GraphNode	getEdgeDst (edge_iterator it)
	Gets the destination of some edge. More...

neighbor_iterator	neighbor_begin (GraphNode N)
	Gets an iterator to the first neighbor of node N. More...

neighbor_iterator	neighbor_end (GraphNode N)
	Gets an iterator to the end of node N's neighbors. More...

template<typename EdgeTy >
EdgeTy *	edge_data_begin () const

template<typename EdgeTy >
EdgeTy *	edge_data_end () const

iterator	begin () const
	Gets the first node of the loaded graph. More...

iterator	end () const
	Gets the end of the nodes of the loaded graph. More...

GraphRange	divideByNode (size_t nodeSize, size_t edgeSize, size_t id, size_t total)
	Given a division and a total number of divisions, return a range for that particular division to work on. More...

GraphRange	divideByEdge (size_t nodeSize, size_t edgeSize, size_t id, size_t total)
	Divides nodes only considering edges. More...

node_id_iterator	node_id_begin () const
	Returns an iterator to the beginning of the node destination array. More...

node_id_iterator	node_id_end () const
	Returns an iterator to the end of the node destination array. More...

edge_id_iterator	edge_id_begin () const
	Returns an iterator to the beginning of the array specifying the index into the destination array where a particular node's edges begin. More...

edge_id_iterator	edge_id_end () const
	Returns an iterator to the end of the array specifying the index into the destination array where a particular node's edges begin. More...

bool	hasNeighbor (GraphNode N1, GraphNode N2)
	Determines if an edge with source N1 and destination N2 existed in the currently loaded (local) graph. More...

size_t	size () const
	Returns the number of nodes in the (sub)graph. More...

size_t	sizeEdges () const
	Returns the number of edges in the (sub)graph. More...

size_t	edgeSize () const
	Returns the size of an edge. More...

	FileGraph ()
	Default file graph constructor which initializes fields to null values. More...

	FileGraph (const FileGraph &)
	Construct graph from another FileGraph. More...

FileGraph &	operator= (const FileGraph &)
	Copy constructor operator for FileGraph. More...

	FileGraph (FileGraph &&)
	Move constructor for FileGraph. More...

FileGraph &	operator= (FileGraph &&)
	Move constructor operator for FileGraph. More...

	~FileGraph ()
	Destructor. More...

void	fromFile (const std::string &filename)
	Given a file name, mmap the entire file into memory. More...

void	partFromFile (const std::string &filename, NodeRange nrange, EdgeRange erange, bool numaMap=false)
	Loads/mmaps particular portions of a graph corresponding to a node range and edge range into memory. More...

template<typename EdgeTy >
void	fromFileInterleaved (const std::string &filename, typename std::enable_if<!std::is_void< EdgeTy >::value >::type *=0)
	Reads graph connectivity information from file. More...

template<typename EdgeTy >
void	fromFileInterleaved (const std::string &filename, typename std::enable_if< std::is_void< EdgeTy >::value >::type *=0)
	Reads graph connectivity information from file. More...

template<typename T >
T *	fromGraph (FileGraph &g)
	Reads graph connectivity information from graph but not edge data. More...

void	toFile (const std::string &file)
	Write current contents of mappings to a file. More...

Protected Member Functions
void *	fromArrays (uint64_t outIdx, uint64_t numNodes, void outs, uint64_t numEdges, char *edgeData, size_t sizeofEdgeData, uint64_t nodeOffset, uint64_t edgeOffset, bool converted, int oGraphVersion=1)
	Copies graph connectivity information from arrays. More...

Detailed Description

Graph that mmaps Galois gr files for access.

Member Typedef Documentation

typedef boost::transform_iterator<Convert64, uint64_t*> galois::graphs::FileGraph::edge_id_iterator

edge iterator

using galois::graphs::FileGraph::edge_iterator = boost::counting_iterator<uint64_t>

Edge iterators (boost iterator)

typedef std::pair<edge_iterator, edge_iterator> galois::graphs::FileGraph::EdgeRange

pair specifying an edge range

using galois::graphs::FileGraph::GraphNode = uint64_t

type of a node

typedef std::pair<NodeRange, EdgeRange> galois::graphs::FileGraph::GraphRange

pair of a NodeRange and an EdgeRange

typedef boost::counting_iterator<uint64_t> galois::graphs::FileGraph::iterator

uint64 boost counting iterator

typedef boost::transform_iterator<Convert32, uint32_t*> galois::graphs::FileGraph::neighbor_iterator

iterator over neighbors

typedef boost::transform_iterator<Convert32, uint32_t*> galois::graphs::FileGraph::node_id_iterator

iterator over node ids

typedef std::pair<iterator, iterator> galois::graphs::FileGraph::NodeRange

pair specifying a node range

Constructor & Destructor Documentation

galois::graphs::FileGraph::FileGraph ( )

Default file graph constructor which initializes fields to null values.

galois::graphs::FileGraph::FileGraph ( const FileGraph & o )

Construct graph from another FileGraph.

Parameters

o	Other filegraph to initialize from.

galois::graphs::FileGraph::FileGraph ( FileGraph && other )

Move constructor for FileGraph.

galois::graphs::FileGraph::~FileGraph ( )

Destructor.

Un-mmaps mmap'd things and closes opened files.

Member Function Documentation

FileGraph::iterator galois::graphs::FileGraph::begin ( ) const

Gets the first node of the loaded graph.

Returns: An iterator to the first node of the graph. Note it is a GLOBAL id.

bool galois::graphs::FileGraph::containsNode ( const GraphNode n ) const

inline

Checks if a node is in the graph (already added)

auto galois::graphs::FileGraph::divideByEdge	(	size_t	nodeSize,
		size_t	edgeSize,
		size_t	id,
		size_t	total
	)

Divides nodes only considering edges.

IMPORTANT: Note that it may potentially not return all nodes in the graph (it will return up to the last node with edges).

Parameters

nodeSize	Weight of nodes
edgeSize	Weight of edges
id	Division id
total	Total number of divisions

Returns: A node range and an edge range specifying division "id"'s assigned nodes/edges

auto galois::graphs::FileGraph::divideByNode	(	size_t	nodeSize,
		size_t	edgeSize,
		size_t	id,
		size_t	total
	)

Given a division and a total number of divisions, return a range for that particular division to work on.

(i.e. this divides labor among divisions depending on how much weight is given to nodes/edges).

Parameters

nodeSize	Weight of nodes
edgeSize	Weight of edges
id	Division id
total	Total number of divisions

Returns: A node range and an edge range specifying division "id"'s assigned nodes/edges

FileGraph::edge_iterator galois::graphs::FileGraph::edge_begin ( GraphNode N )

Returns the index to the beginning of global node N's outgoing edges in the outgoing edges array.

Parameters

N	global node id of edge begin to get

Returns: Iterator to first edge of node N

template<typename EdgeTy >

EdgeTy* galois::graphs::FileGraph::edge_data_begin ( ) const

inline

template<typename EdgeTy >

EdgeTy* galois::graphs::FileGraph::edge_data_end ( ) const

inline

FileGraph::edge_iterator galois::graphs::FileGraph::edge_end ( GraphNode N )

Returns the index to the end of global node N's outgoing edges in the outgoing edges array.

Parameters

N	global node id of edge end to get

Returns: Iterator to end of node N's edges

FileGraph::edge_id_iterator galois::graphs::FileGraph::edge_id_begin ( ) const

Returns an iterator to the beginning of the array specifying the index into the destination array where a particular node's edges begin.

Returns: iterator to beginning of edge index array of the loaded graph

FileGraph::edge_id_iterator galois::graphs::FileGraph::edge_id_end ( ) const

Returns an iterator to the end of the array specifying the index into the destination array where a particular node's edges begin.

Returns: iterator to end of edge index array of the loaded graph

runtime::iterable<NoDerefIterator<edge_iterator> > galois::graphs::FileGraph::edges ( GraphNode N )

inline

Returns the edges of node N as a range that can be iterated through by C++ foreach.

size_t galois::graphs::FileGraph::edgeSize ( ) const

inline

Returns the size of an edge.

FileGraph::iterator galois::graphs::FileGraph::end ( ) const

Gets the end of the nodes of the loaded graph.

Returns: An iterator to the end of the nodes of the graph (of the loaded part of the graph).

void * galois::graphs::FileGraph::fromArrays	(	uint64_t *	outIdx,
		uint64_t	numNodes,
		void *	outs,
		uint64_t	numEdges,
		char *	edgeData,
		size_t	sizeofEdgeData,
		uint64_t	nodeOffset,
		uint64_t	edgeOffset,
		bool	converted,
		int	oGraphVersion = `1`
	)

protected

Copies graph connectivity information from arrays.

Returns a pointer to array to populate with edge data.

Parameters

outIdx	Out index information in an array
numNodes	number of nodes
outs	edge destination array
numEdges	number of edges
edgeData	array of edge data
sizeofEdgeData	The size of the edge data
nodeOffset	how many nodes from the beginning will this graph start from
edgeOffset	how many edges from the beginning will this edge start from
converted	whether values in arrays are in host byte ordering (false) or in FileGraph byte ordering (true)
oGraphVersion	Galois graph version to use

Returns: pointer to begining of edgeData in graph

void galois::graphs::FileGraph::fromFile ( const std::string & filename )

Given a file name, mmap the entire file into memory.

Should be a graph with some specific layout.

Parameters

filename Graph file to load

template<typename EdgeTy >

void galois::graphs::FileGraph::fromFileInterleaved	(	const std::string &	filename,
		typename std::enable_if<!std::is_void< EdgeTy >::value >::type *	= `0`
	)

inline

Reads graph connectivity information from file.

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

Edge data version.

template<typename EdgeTy >

void galois::graphs::FileGraph::fromFileInterleaved	(	const std::string &	filename,
		typename std::enable_if< std::is_void< EdgeTy >::value >::type *	= `0`
	)

inline

Reads graph connectivity information from file.

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

No edge data version.

template<typename T >

T* galois::graphs::FileGraph::fromGraph ( FileGraph & g )

inline

Reads graph connectivity information from graph but not edge data.

Returns a pointer to array to populate with edge data.

template<typename EdgeTy >

EdgeTy& galois::graphs::FileGraph::getEdgeData	(	GraphNode	src,
		GraphNode	dst
	)

inline

Get edge data of an edge between 2 nodes.

template<typename EdgeTy >

EdgeTy& galois::graphs::FileGraph::getEdgeData ( edge_iterator it )

inline

Get edge data given an edge iterator.

FileGraph::GraphNode galois::graphs::FileGraph::getEdgeDst ( edge_iterator it )

Gets the destination of some edge.

Parameters

it	local edge id of edge destination to get

Returns: a global node id representing the destination of the edge

bool galois::graphs::FileGraph::hasNeighbor	(	GraphNode	N1,
		GraphNode	N2
	)

Determines if an edge with source N1 and destination N2 existed in the currently loaded (local) graph.

Parameters

N1	global node id of neighbor 1 (source)
N2	global node id of neighbor 2 (destination)

Returns: true if edge (N1, N2) exists locally, false otherwise

neighbor_iterator galois::graphs::FileGraph::neighbor_begin ( GraphNode N )

inline

Gets an iterator to the first neighbor of node N.

Warning: only version 1 support, do not use with version 2

neighbor_iterator galois::graphs::FileGraph::neighbor_end ( GraphNode N )

inline

Gets an iterator to the end of node N's neighbors.

Warning: only version 1 support, do not use with version 2

FileGraph::node_id_iterator galois::graphs::FileGraph::node_id_begin ( ) const

Returns an iterator to the beginning of the node destination array.

Returns: iterator to beginning of the node destination array of the loaded graph (local)

FileGraph::node_id_iterator galois::graphs::FileGraph::node_id_end ( ) const

Returns an iterator to the end of the node destination array.

Returns: iterator to end of the node destination array of the loaded graph (local)

uint64_t galois::graphs::FileGraph::num_bytes_read ( )

inline

Return all bytes read.

FileGraph & galois::graphs::FileGraph::operator= ( const FileGraph & other )

Copy constructor operator for FileGraph.

FileGraph & galois::graphs::FileGraph::operator= ( FileGraph && other )

Move constructor operator for FileGraph.

runtime::iterable<NoDerefIterator<edge_iterator> > galois::graphs::FileGraph::out_edges ( GraphNode N )

inline

Returns the edges of node N as a range that can be iterated through by C++ foreach.

void galois::graphs::FileGraph::partFromFile	(	const std::string &	filename,
		NodeRange	nrange,
		EdgeRange	erange,
		bool	numaMap = `false`
	)

Loads/mmaps particular portions of a graph corresponding to a node range and edge range into memory.

Note that it makes the object work on a LOCAL scale (i.e. there are now local ids corresponding to the subgraph). Most functions will still handle global ids, though. (see below)

Parameters

filename	File to load
nrange	Node range to load
erange	Edge range to load
numaMap	if true, does interleaved numa allocation for data structures

void galois::graphs::FileGraph::reset_byte_counters ( )

inline

Reset the num bytes counters.

size_t galois::graphs::FileGraph::size ( ) const

inline

Returns the number of nodes in the (sub)graph.

size_t galois::graphs::FileGraph::sizeEdges ( ) const

inline

Returns the number of edges in the (sub)graph.

template<typename EdgeTy , typename CompTy >

void galois::graphs::FileGraph::sortEdges	(	GraphNode	N,
		const CompTy &	comp
	)

inline

Sorts outgoing edges of a node.

Comparison function is over EdgeSortValue<EdgeTy>.

template<typename EdgeTy , typename CompTy >

void galois::graphs::FileGraph::sortEdgesByEdgeData	(	GraphNode	N,
		const CompTy &	comp = `std::less<EdgeTy>()`
	)

inline

Sorts outgoing edges of a node.

Comparison function is over EdgeTy.

void galois::graphs::FileGraph::toFile ( const std::string & file )

Write current contents of mappings to a file.

Parameters

file	File to write to

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

Public Types

Public Member Functions

Protected Member Functions

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation