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

#include <LC_CSR_CSC_Graph.h>

Inheritance diagram for galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >:

Public Types
using	GraphNode = uint32_t
	Graph node typedef. More...

using	edge_iterator = boost::counting_iterator< typename EdgeIndData::value_type >
	iterator for edges More...

using	edge_data_reference = typename EdgeData::reference
	reference to edge data More...

Public Types inherited from galois::graphs::LC_CSR_Graph< NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >
template<bool _has_no_lockable>
using	_with_no_lockable = LC_CSR_Graph< NodeTy, EdgeTy, _has_no_lockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >

template<bool _use_numa_alloc>
using	_with_numa_alloc = LC_CSR_Graph< NodeTy, EdgeTy, HasNoLockable, _use_numa_alloc, HasOutOfLineLockable, FileEdgeTy >

typedef read_default_graph_tag	read_tag

typedef uint32_t	GraphNode

typedef EdgeTy	edge_data_type

typedef FileEdgeTy	file_edge_data_type

typedef NodeTy	node_data_type

typedef EdgeData::reference	edge_data_reference

typedef NodeInfoTypes::reference	node_data_reference

using	edge_iterator = boost::counting_iterator< typename EdgeIndData::value_type >

using	iterator = boost::counting_iterator< typename EdgeDst::value_type >

typedef iterator	const_iterator

typedef iterator	local_iterator

typedef iterator	const_local_iterator

Public Member Functions
	LC_CSR_CSC_Graph ()=default
	default constructor More...

	LC_CSR_CSC_Graph (LC_CSR_CSC_Graph &&rhs)=default
	default move constructor More...

LC_CSR_CSC_Graph &	operator= (LC_CSR_CSC_Graph &&)=default
	default = operator More...

void	constructIncomingEdges ()
	Call only after the LC_CSR_Graph part of this class is fully constructed. More...

edge_iterator	in_raw_begin (GraphNode N) const
	Grabs in edge beginning without lock/safety. More...

edge_iterator	in_raw_end (GraphNode N) const
	Grabs in edge end without lock/safety. More...

edge_iterator	in_edge_begin (GraphNode N, MethodFlag mflag=MethodFlag::WRITE)
	Wrapper to get the in edge end of a node; lock if necessary. More...

edge_iterator	in_edge_end (GraphNode N, MethodFlag mflag=MethodFlag::WRITE)
	Wrapper to get the in edge end of a node; lock if necessary. More...

runtime::iterable < NoDerefIterator < edge_iterator > >	in_edges (GraphNode N, MethodFlag mflag=MethodFlag::WRITE)

GraphNode	getInEdgeDst (edge_iterator ni) const
	Given an edge id for in edges, get the destination of the edge. More...

template<bool A = EdgeDataByValue, typename std::enable_if< A >::type * = nullptr>
edge_data_reference	getInEdgeData (edge_iterator ni, MethodFlag=MethodFlag::UNPROTECTED) const
	Given an edge id for in edge, get the data associated with that edge. More...

template<bool A = EdgeDataByValue, typename std::enable_if< A >::type * = nullptr>
edge_data_reference	getInEdgeData (edge_iterator ni, MethodFlag=MethodFlag::UNPROTECTED)
	Given an edge id for in edge, get the data associated with that edge. More...

template<bool A = EdgeDataByValue, typename std::enable_if<!A >::type * = nullptr>
edge_data_reference	getInEdgeData (edge_iterator ni, MethodFlag=MethodFlag::UNPROTECTED) const
	Given an edge id for in edge, get the data associated with that edge. More...

template<bool A = EdgeDataByValue, typename std::enable_if<!A >::type * = nullptr>
edge_data_reference	getInEdgeData (edge_iterator ni, MethodFlag=MethodFlag::UNPROTECTED)
	Given an edge id for in edge, get the data associated with that edge. More...

const EdgeIndData &	getInEdgePrefixSum () const

void	sortInEdgesByDst (GraphNode N, MethodFlag mflag=MethodFlag::WRITE)
	Sorts outgoing edges of a node. More...

void	sortAllInEdgesByDst (MethodFlag mflag=MethodFlag::WRITE)
	Sorts all incoming edges of all nodes in parallel. More...

void	readAndConstructBiGraphFromGRFile (const std::string &filename)
	Directly reads the GR file to construct CSR graph and then constructs reverse edges based on that. More...

Public Member Functions inherited from galois::graphs::LC_CSR_Graph< NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >
	LC_CSR_Graph (LC_CSR_Graph &&rhs)=default

	LC_CSR_Graph ()=default

LC_CSR_Graph &	operator= (LC_CSR_Graph &&)=default

void	serializeNodeData (boost::archive::binary_oarchive &ar) const
	Serializes node data using Boost. More...

void	deSerializeNodeData (boost::archive::binary_iarchive &ar)
	Deserializes a Boost archive containing node data to the local node data variable. More...

void	serializeGraph (boost::archive::binary_oarchive &ar) const
	Serializes graph using Boost. More...

void	deSerializeGraph (boost::archive::binary_iarchive &ar)
	Deserializes a Boost archive to the local graph. More...

uint64_t	operator[] (uint64_t n)
	Accesses the "prefix sum" of this graph; takes advantage of the fact that edge_end(n) is basically prefix_sum[n] (if a prefix sum existed + if prefix_sum[0] = number of edges in node 0). More...

template<typename EdgeNumFnTy , typename EdgeDstFnTy , typename EdgeDataFnTy >
	LC_CSR_Graph (uint32_t _numNodes, uint64_t _numEdges, EdgeNumFnTy edgeNum, EdgeDstFnTy _edgeDst, EdgeDataFnTy _edgeData)

node_data_reference	getData (GraphNode N, MethodFlag mflag=MethodFlag::WRITE)

edge_data_reference	getEdgeData (edge_iterator ni, MethodFlag GALOIS_UNUSED(mflag)=MethodFlag::UNPROTECTED)

GraphNode	getEdgeDst (edge_iterator ni)

size_t	size () const

size_t	sizeEdges () const

iterator	begin () const

iterator	end () const

const_local_iterator	local_begin () const

const_local_iterator	local_end () const

local_iterator	local_begin ()

local_iterator	local_end ()

edge_iterator	edge_begin (GraphNode N, MethodFlag mflag=MethodFlag::WRITE)

edge_iterator	edge_end (GraphNode N, MethodFlag mflag=MethodFlag::WRITE)

edge_iterator	findEdge (GraphNode N1, GraphNode N2)

edge_iterator	findEdgeSortedByDst (GraphNode N1, GraphNode N2)

runtime::iterable < NoDerefIterator < edge_iterator > >	edges (GraphNode N, MethodFlag mflag=MethodFlag::WRITE)

runtime::iterable < NoDerefIterator < edge_iterator > >	out_edges (GraphNode N, MethodFlag mflag=MethodFlag::WRITE)

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

template<typename CompTy >
void	sortEdges (GraphNode N, const CompTy &comp, MethodFlag mflag=MethodFlag::WRITE)
	Sorts outgoing edges of a node. More...

void	sortEdgesByDst (GraphNode N, MethodFlag mflag=MethodFlag::WRITE)
	Sorts outgoing edges of a node. More...

void	sortAllEdgesByDst (MethodFlag mflag=MethodFlag::WRITE)
	Sorts all outgoing edges of all nodes in parallel. More...

void	allocateFrom (const FileGraph &graph)

void	allocateFrom (uint32_t nNodes, uint64_t nEdges)

void	destroyAndAllocateFrom (uint32_t nNodes, uint64_t nEdges)

void	constructNodes ()

void	deallocate ()

void	constructEdge (uint64_t e, uint32_t dst, const typename EdgeData::value_type &val)

void	constructEdge (uint64_t e, uint32_t dst)

void	fixEndEdge (uint32_t n, uint64_t e)

void	transpose (const char *regionName=NULL)
	Perform an in-memory transpose of the graph, replacing the original CSR to CSC. More...

template<bool is_non_void = EdgeData::has_value>
void	edgeDataCopy (EdgeData &edgeData_new, EdgeData &edgeData, uint64_t e_new, uint64_t e, typename std::enable_if< is_non_void >::type *=0)

template<bool is_non_void = EdgeData::has_value>
void	edgeDataCopy (EdgeData &, EdgeData &, uint64_t, uint64_t, typename std::enable_if<!is_non_void >::type *=0)

template<typename E = EdgeTy, std::enable_if_t<!std::is_same< E, void >::value, int > * = nullptr>
void	constructFrom (FileGraph &graph, unsigned tid, unsigned total, const bool readUnweighted=false)

template<typename E = EdgeTy, std::enable_if_t< std::is_same< E, void >::value, int > * = nullptr>
void	constructFrom (FileGraph &graph, unsigned tid, unsigned total, const bool GALOIS_UNUSED(readUnweighted)=false)

const EdgeIndData &	getEdgePrefixSum () const
	Returns the reference to the edgeIndData LargeArray (a prefix sum of edges) More...

auto	divideByNode (size_t nodeSize, size_t edgeSize, size_t id, size_t total)

void	constructFrom (uint32_t numNodes, uint64_t numEdges, std::vector< uint64_t > &prefix_sum, std::vector< std::vector< uint32_t >> &edges_id, std::vector< std::vector< EdgeTy >> &edges_data)
	custom allocator for vector<vector<>> Adding for Louvain clustering TODO: Find better way to do this More...

void	constructFrom (uint32_t numNodes, uint64_t numEdges, std::vector< uint64_t > &prefix_sum, galois::gstl::Vector< galois::PODResizeableArray< uint32_t >> &edges_id, std::vector< std::vector< EdgeTy >> &edges_data)

template<typename U = void, typename std::enable_if<!std::is_void< EdgeTy >::value, U >::type * = nullptr>
void	readGraphFromGRFile (const std::string &filename)
	Reads the GR files directly into in-memory data-structures of LC_CSR graphs using freads. More...

template<typename U = void, typename std::enable_if< std::is_void< EdgeTy >::value, U >::type * = nullptr>
void	readGraphFromGRFile (const std::string &filename)
	Reads the GR files directly into in-memory data-structures of LC_CSR graphs using freads. More...

void	initializeLocalRanges ()
	Given a manually created graph, initialize the local ranges on this graph so that threads can iterate over a balanced number of vertices. More...

Protected Types
using	EdgeData = LargeArray< EdgeTy >
	large array for edge data More...

using	EdgeDst = LargeArray< uint32_t >
	large array for edge destinations More...

using	EdgeIndData = LargeArray< uint64_t >
	large array for edge index data More...

using	EdgeDataRep = typename std::conditional< EdgeDataByValue, EdgeData, EdgeIndData >::type
	Edge data of inedges can be a value copy of the outedges (i.e. More...

using	edge_sort_iterator = internal::EdgeSortIterator< GraphNode, typename EdgeIndData::value_type, EdgeDst, EdgeDataRep >
	redefinition of the edge sort iterator in LC_CSR_Graph More...

Protected Types inherited from galois::graphs::LC_CSR_Graph< NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >
typedef LargeArray< EdgeTy >	EdgeData

typedef LargeArray< uint32_t >	EdgeDst

typedef internal::NodeInfoBaseTypes < NodeTy,!HasNoLockable &&!HasOutOfLineLockable >	NodeInfoTypes

typedef internal::NodeInfoBase < NodeTy,!HasNoLockable &&!HasOutOfLineLockable >	NodeInfo

typedef LargeArray< uint64_t >	EdgeIndData

typedef LargeArray< NodeInfo >	NodeData

typedef internal::EdgeSortIterator < GraphNode, typename EdgeIndData::value_type, EdgeDst, EdgeData >	edge_sort_iterator

Protected Member Functions
edge_sort_iterator	in_edge_sort_begin (GraphNode N)
	beginning iterator to an edge sorter for in-edges More...

edge_sort_iterator	in_edge_sort_end (GraphNode N)
	ending iterator to an edge sorter for in-edges More...

template<bool A = EdgeDataByValue, typename std::enable_if< A >::type * = nullptr>
void	createEdgeData (const uint64_t e_new, const uint64_t e)
	Copy the data of outedge by value to inedge. More...

template<bool A = EdgeDataByValue, typename std::enable_if<!A >::type * = nullptr>
void	createEdgeData (const uint64_t e_new, const uint64_t e)
	Save a pointer to an outedge (i.e. More...

void	determineInEdgeIndices (EdgeIndData &dataBuffer)
	Determine the in-edge indices for every node by accumulating how many in-edges each node has, getting a prefix sum, and saving it to the in edge index data array. More...

void	determineInEdgeDestAndData (EdgeIndData &dataBuffer)
	Determine the destination of each in-edge and copy the data associated with an edge (or point to it). More...

Protected Member Functions inherited from galois::graphs::LC_CSR_Graph< NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >
edge_iterator	raw_begin (GraphNode N) const

edge_iterator	raw_end (GraphNode N) const

edge_sort_iterator	edge_sort_begin (GraphNode N)

edge_sort_iterator	edge_sort_end (GraphNode N)

template<bool _A1 = HasNoLockable, bool _A2 = HasOutOfLineLockable>
void	acquireNode (GraphNode N, MethodFlag mflag, typename std::enable_if<!_A1 &&!_A2 >::type *=0)

template<bool _A1 = HasOutOfLineLockable, bool _A2 = HasNoLockable>
void	acquireNode (GraphNode N, MethodFlag mflag, typename std::enable_if< _A1 &&!_A2 >::type *=0)

template<bool _A1 = HasOutOfLineLockable, bool _A2 = HasNoLockable>
void	acquireNode (GraphNode, MethodFlag, typename std::enable_if< _A2 >::type *=0)

template<bool _A1 = EdgeData::has_value, bool _A2 = LargeArray<FileEdgeTy>::has_value>
void	constructEdgeValue (FileGraph &graph, typename FileGraph::edge_iterator nn, typename std::enable_if<!_A1\|\|_A2 >::type *=0)

template<bool _A1 = EdgeData::has_value, bool _A2 = LargeArray<FileEdgeTy>::has_value>
void	constructEdgeValue (FileGraph &, typename FileGraph::edge_iterator nn, typename std::enable_if< _A1 &&!_A2 >::type *=0)

size_t	getId (GraphNode N)

GraphNode	getNode (size_t n)

Protected Attributes
EdgeIndData	inEdgeIndData
	edge index data for the reverse edges More...

EdgeDst	inEdgeDst
	edge destination data for the reverse edges More...

EdgeDataRep	inEdgeData
	The data for the reverse edges. More...

Protected Attributes inherited from galois::graphs::LC_CSR_Graph< NodeTy, EdgeTy, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >
NodeData	nodeData

EdgeIndData	edgeIndData

EdgeDst	edgeDst

EdgeData	edgeData

uint64_t	numNodes

uint64_t	numEdges

Detailed Description

template<typename NodeTy, typename EdgeTy, bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>
class galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >

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

Template Parameters

NodeTy	type of the node data
EdgeTy	type of the edge data
EdgeDataByValue	If set to true, the in-edges will have their own copy of the edge data. Otherwise, the in-edge edge data will be shared with its corresponding out-edge.
HasNoLockable	If set to true, then node accesses will cannot acquire an abstract lock. Otherwise, accessing nodes can get a lock.
UseNumaAlloc	If set to true, allocate data in a possibly more NUMA friendly way.
HasOutOfLineLockable
FileEdgeTy

Member Typedef Documentation

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::edge_data_reference = typename EdgeData::reference

reference to edge data

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::edge_iterator = boost::counting_iterator<typename EdgeIndData::value_type>

iterator for edges

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::edge_sort_iterator = internal::EdgeSortIterator<GraphNode, typename EdgeIndData::value_type, EdgeDst, EdgeDataRep>

protected

redefinition of the edge sort iterator in LC_CSR_Graph

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::EdgeData = LargeArray<EdgeTy>

protected

large array for edge data

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::EdgeDataRep = typename std::conditional<EdgeDataByValue, EdgeData, EdgeIndData>::type

protected

Edge data of inedges can be a value copy of the outedges (i.e.

in and out edges have separate edge values) or inedges can refer to the same data as its corresponding outedge; this is what this typedef is for

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::EdgeDst = LargeArray<uint32_t>

protected

large array for edge destinations

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::EdgeIndData = LargeArray<uint64_t>

protected

large array for edge index data

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::GraphNode = uint32_t

Graph node typedef.

Constructor & Destructor Documentation

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::LC_CSR_CSC_Graph ( )

default

default constructor

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::LC_CSR_CSC_Graph ( LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy > && rhs )

default

default move constructor

Member Function Documentation

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

void galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::constructIncomingEdges ( )

inline

Call only after the LC_CSR_Graph part of this class is fully constructed.

Creates the in edge data by reading from the out edge data.

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

template<bool A = EdgeDataByValue, typename std::enable_if< A >::type * = nullptr>

void galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::createEdgeData	(	const uint64_t	e_new,
		const uint64_t	e
	)

inlineprotected

Copy the data of outedge by value to inedge.

Parameters

e_new	position of out-edge to copy as an in-edge
e	position of in-edge

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

template<bool A = EdgeDataByValue, typename std::enable_if<!A >::type * = nullptr>

void galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::createEdgeData	(	const uint64_t	e_new,
		const uint64_t	e
	)

inlineprotected

Save a pointer to an outedge (i.e.

map an in-edge to an out-edge). Done to share edge data.

Parameters

e_new	position of out-edge to save
e	position of in-edge

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

void galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::determineInEdgeDestAndData ( EdgeIndData & dataBuffer )

inlineprotected

Determine the destination of each in-edge and copy the data associated with an edge (or point to it).

Parameters

dataBuffer A prefix sum of in-edges

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

void galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::determineInEdgeIndices ( EdgeIndData & dataBuffer )

inlineprotected

Determine the in-edge indices for every node by accumulating how many in-edges each node has, getting a prefix sum, and saving it to the in edge index data array.

Parameters

dataBuffer temporary buffer that is used to accumulate in-edge counts; at the end of this function, it will contain a prefix sum of in-edges

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

template<bool A = EdgeDataByValue, typename std::enable_if< A >::type * = nullptr>

edge_data_reference galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::getInEdgeData	(	edge_iterator	ni,
		MethodFlag	= `MethodFlag::UNPROTECTED`
	)		const

inline

Given an edge id for in edge, get the data associated with that edge.

Returns a constant reference.

In-edge has own copy of edge-data version.

Parameters

ni	in-edge id

Returns: data of the edge

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

template<bool A = EdgeDataByValue, typename std::enable_if< A >::type * = nullptr>

edge_data_reference galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::getInEdgeData	(	edge_iterator	ni,
		MethodFlag	= `MethodFlag::UNPROTECTED`
	)

inline

Given an edge id for in edge, get the data associated with that edge.

Returns a non-constant reference.

In-edge has own copy of edge-data version.

Parameters

ni	in-edge id

Returns: data of the edge

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

template<bool A = EdgeDataByValue, typename std::enable_if<!A >::type * = nullptr>

edge_data_reference galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::getInEdgeData	(	edge_iterator	ni,
		MethodFlag	= `MethodFlag::UNPROTECTED`
	)		const

inline

Given an edge id for in edge, get the data associated with that edge.

Returns a constant reference.

In-edge and out-edge share edge data version.

Parameters

ni	in-edge id

Returns: data of the edge

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

template<bool A = EdgeDataByValue, typename std::enable_if<!A >::type * = nullptr>

edge_data_reference galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::getInEdgeData	(	edge_iterator	ni,
		MethodFlag	= `MethodFlag::UNPROTECTED`
	)

inline

Given an edge id for in edge, get the data associated with that edge.

Returns a non-constant reference.

In-edge and out-edge share edge data version.

Parameters

ni	in-edge id

Returns: data of the edge

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

GraphNode galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::getInEdgeDst ( edge_iterator ni ) const

inline

Given an edge id for in edges, get the destination of the edge.

Parameters

ni edge id

Returns: destination for that in edge

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

const EdgeIndData& galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::getInEdgePrefixSum ( ) const

inline

Returns: the prefix sum of in-edges

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

edge_iterator galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::in_edge_begin	(	GraphNode	N,
		MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

Wrapper to get the in edge end of a node; lock if necessary.

Parameters

N	node to get edge beginning of
mflag	how safe the acquire should be

Returns: Iterator to first in edge of node N

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

edge_iterator galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::in_edge_end	(	GraphNode	N,
		MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

Wrapper to get the in edge end of a node; lock if necessary.

Parameters

N	node to get in edge end of
mflag	how safe the acquire should be

Returns: Iterator to end of in edges of node N (i.e. first in edge of N+1)

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

edge_sort_iterator galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::in_edge_sort_begin ( GraphNode N )

inlineprotected

beginning iterator to an edge sorter for in-edges

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

edge_sort_iterator galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::in_edge_sort_end ( GraphNode N )

inlineprotected

ending iterator to an edge sorter for in-edges

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

runtime::iterable<NoDerefIterator<edge_iterator> > galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::in_edges	(	GraphNode	N,
		MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

Parameters

N	node to get in edges for
mflag	how safe the acquire should be

Returns: Range to in edges of node N

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

edge_iterator galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::in_raw_begin ( GraphNode N ) const

inline

Grabs in edge beginning without lock/safety.

Parameters

N	node to get edge beginning of

Returns: Iterator to first in edge of node N

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

edge_iterator galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::in_raw_end ( GraphNode N ) const

inline

Grabs in edge end without lock/safety.

Parameters

N	node to get edge end of

Returns: Iterator to end of in edges of node N (i.e. first edge of node N+1)

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

LC_CSR_CSC_Graph& galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::operator= ( LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy > && )

default

default = operator

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

void galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::readAndConstructBiGraphFromGRFile ( const std::string & filename )

inline

Directly reads the GR file to construct CSR graph and then constructs reverse edges based on that.

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

void galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::sortAllInEdgesByDst ( MethodFlag mflag = MethodFlag::WRITE )

inline

Sorts all incoming edges of all nodes in parallel.

Comparison is over getEdgeDst(e).

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

void galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::sortInEdgesByDst	(	GraphNode	N,
		MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

Sorts outgoing edges of a node.

Comparison is over getEdgeDst(e).

Member Data Documentation

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

EdgeDataRep galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::inEdgeData

protected

The data for the reverse edges.

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

EdgeDst galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::inEdgeDst

protected

edge destination data for the reverse edges

template<typename NodeTy , typename EdgeTy , bool EdgeDataByValue = false, bool HasNoLockable = false, bool UseNumaAlloc = false, bool HasOutOfLineLockable = false, typename FileEdgeTy = EdgeTy>

EdgeIndData galois::graphs::LC_CSR_CSC_Graph< NodeTy, EdgeTy, EdgeDataByValue, HasNoLockable, UseNumaAlloc, HasOutOfLineLockable, FileEdgeTy >::inEdgeIndData

protected

edge index data for the reverse edges

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

LC_CSR_CSC_Graph.h

Public Types

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation