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

#include <MorphGraph.h>

Inheritance diagram for galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >:

Classes
struct	AuxNode
	Wrapper around a graph node that provides a lock for it as well as in-neighbor tracking. More...

struct	with_directional
	Struct used to define directionality of the graph. More...

struct	with_edge_data
	Struct used to define the type of edge data in the graph. More...

struct	with_file_edge_data
	Struct used to define the type of file edge data in the graph. More...

struct	with_no_lockable
	Struct used to define the HasNoLockable template parameter as a type in the struct. More...

struct	with_node_data
	Struct used to define the type of node data in the graph. More...

struct	with_sorted_neighbors
	Struct used to define if neighbors are sorted or not in the graph. More...

Public Types
using	read_tag = read_with_aux_first_graph_tag
	Tag that defines to graph reader how to read a graph into this class. More...

using	GraphNode = gNode *
	Graph node handle. More...

using	edge_data_type = EdgeTy
	Edge data type. More...

using	file_edge_data_type = FileEdgeTy
	Edge data type of file we are loading this graph from. More...

using	node_data_type = NodeTy
	Node data type. More...

using	edge_iterator = typename boost::filter_iterator< is_out_edge, typename gNodeTypes::iterator >
	(Out or Undirected) Edge iterator More...

using	in_edge_iterator = typename boost::filter_iterator< is_in_edge, typename gNodeTypes::iterator >
	In Edge iterator. More...

using	edge_data_reference = typename gNodeTypes::EdgeInfo::reference
	Reference to edge data. More...

using	node_data_reference = typename gNodeTypes::reference
	Reference to node data. More...

using	iterator = boost::transform_iterator< makeGraphNode, boost::filter_iterator< is_node, typename NodeListTy::iterator >>
	Node iterator. More...

using	AuxNodePadded = typename galois::substrate::CacheLineStorage< AuxNode >
	Padded version of AuxNode. More...

using	ReadGraphAuxData = typename std::conditional< DirectedNotInOut, LargeArray< GraphNode >, LargeArray< AuxNodePadded >>::type
	Large array that contains auxiliary data for each node (AuxNodes) More...

using	local_iterator = iterator
	local iterator over nodes More...

Public Member Functions
template<typename... Args>
GraphNode	createNode (Args &&...args)
	Creates a new node holding the indicated data. More...

void	addNode (const GraphNode &n, galois::MethodFlag mflag=MethodFlag::WRITE)
	Adds a node to the graph. More...

node_data_reference	getData (const GraphNode &n, galois::MethodFlag mflag=MethodFlag::WRITE) const
	Gets the node data for a node. More...

bool	containsNode (const GraphNode &n, galois::MethodFlag mflag=MethodFlag::WRITE) const
	Checks if a node is in the graph. More...

void	removeNode (GraphNode n, galois::MethodFlag mflag=MethodFlag::WRITE)
	Removes a node from the graph along with all its outgoing/incoming edges for undirected graphs or outgoing edges for directed graphs. More...

void	resizeEdges (GraphNode src, size_t size, galois::MethodFlag mflag=MethodFlag::WRITE)
	Resize the edges of the node. More...

edge_iterator	addEdge (GraphNode src, GraphNode dst, galois::MethodFlag mflag=MethodFlag::WRITE)
	Adds an edge to graph, replacing existing value if edge already exists. More...

template<typename... Args>
edge_iterator	addMultiEdge (GraphNode src, GraphNode dst, galois::MethodFlag mflag, Args &&...args)
	Adds and initializes an edge to graph but does not check for duplicate edges. More...

void	removeEdge (GraphNode src, edge_iterator dst, galois::MethodFlag mflag=MethodFlag::WRITE)
	Removes an edge from the graph. More...

edge_iterator	findEdge (GraphNode src, GraphNode dst, galois::MethodFlag mflag=MethodFlag::WRITE)
	Finds if an edge between src and dst exists. More...

edge_iterator	findEdgeSortedByDst (GraphNode src, GraphNode dst, galois::MethodFlag mflag=MethodFlag::WRITE)
	Find/return edge between src/dst if it exists; assumes that edges are sorted by destination. More...

template<bool _Undirected = !Directional>
edge_iterator	findInEdge (GraphNode src, GraphNode dst, galois::MethodFlag mflag=MethodFlag::WRITE, typename std::enable_if< _Undirected >::type *=0)
	Find a particular in-edge: note this function activates for the undirected graph case, so it just calls the regular out-edge finding function. More...

template<bool _DirectedInOut = (Directional && InOut)>
in_edge_iterator	findInEdge (GraphNode src, GraphNode dst, galois::MethodFlag mflag=MethodFlag::WRITE, typename std::enable_if< _DirectedInOut >::type *=0)
	Find if an incoming edge between src and dst exists for directed in-out graphs. More...

edge_data_reference	getEdgeData (edge_iterator ii, galois::MethodFlag mflag=MethodFlag::UNPROTECTED) const
	Returns the edge data associated with the edge. More...

edge_data_reference	getEdgeData (in_edge_iterator ii, galois::MethodFlag mflag=MethodFlag::UNPROTECTED) const
	Get edge data for an in-edge. More...

GraphNode	getEdgeDst (edge_iterator ii)
	Returns the destination of an edge. More...

GraphNode	getEdgeDst (in_edge_iterator ii)
	Returns the destination of an in-edge. More...

void	sortEdgesByDst (GraphNode N, galois::MethodFlag mflag=MethodFlag::WRITE)
	Sorts edge of a node by destination. More...

void	sortAllEdgesByDst (MethodFlag mflag=MethodFlag::WRITE)
	Sort all edges by destination. More...

edge_iterator	edge_begin (GraphNode N, galois::MethodFlag mflag=MethodFlag::WRITE)
	Returns an iterator to the neighbors of a node. More...

template<bool _Undirected = !Directional>
in_edge_iterator	in_edge_begin (GraphNode N, galois::MethodFlag mflag=MethodFlag::WRITE, typename std::enable_if<!_Undirected >::type *=0)
	Returns an iterator to the in-neighbors of a node. More...

template<bool _Undirected = !Directional>
edge_iterator	in_edge_begin (GraphNode N, galois::MethodFlag mflag=MethodFlag::WRITE, typename std::enable_if< _Undirected >::type *=0)
	Returns an iterator to the in-neighbors of a node; undirected case in which it's the same as a regular neighbor. More...

edge_iterator	edge_end (GraphNode N, galois::MethodFlag GALOIS_UNUSED(mflag)=MethodFlag::WRITE)
	Returns the end of the neighbor edge iterator. More...

template<bool _Undirected = !Directional>
in_edge_iterator	in_edge_end (GraphNode N, galois::MethodFlag GALOIS_UNUSED(mflag)=MethodFlag::WRITE, typename std::enable_if<!_Undirected >::type *=0)
	Returns the end of an in-neighbor edge iterator. More...

template<bool _Undirected = !Directional>
edge_iterator	in_edge_end (GraphNode N, galois::MethodFlag mflag=MethodFlag::WRITE, typename std::enable_if< _Undirected >::type *=0)
	Returns the end of an in-neighbor edge iterator, undirected case. More...

runtime::iterable < NoDerefIterator < edge_iterator > >	edges (GraphNode N, galois::MethodFlag mflag=MethodFlag::WRITE)
	Return a range of edges that can be iterated over by C++ for-each. More...

template<bool _Undirected = !Directional>
runtime::iterable < NoDerefIterator < in_edge_iterator > >	in_edges (GraphNode N, galois::MethodFlag mflag=MethodFlag::WRITE, typename std::enable_if<!_Undirected >::type *=0)
	Return a range of in-edges that can be iterated over by C++ for-each. More...

template<bool _Undirected = !Directional>
runtime::iterable < NoDerefIterator < edge_iterator > >	in_edges (GraphNode N, galois::MethodFlag mflag=MethodFlag::WRITE, typename std::enable_if< _Undirected >::type *=0)
	Return a range of in-edges that can be iterated over by C++ for-each Undirected case, equivalent to out-edge iteration. More...

internal::EdgesIterator < MorphGraph >	out_edges (GraphNode N, MethodFlag mflag=MethodFlag::WRITE)
	An object with begin() and end() methods to iterate over the outgoing edges of N. More...

iterator	begin ()
	Returns an iterator to all the nodes in the graph. More...

iterator	end ()
	Returns the end of the node iterator. Not thread-safe. More...

local_iterator	local_begin ()
	Return the beginning of local range of nodes. More...

local_iterator	local_end ()
	Return the end of local range of nodes. More...

unsigned int	size ()
	Returns the number of nodes in the graph. More...

size_t	sizeOfEdgeData () const
	Returns the size of edge data. More...

void	allocateFrom (FileGraph &graph, ReadGraphAuxData &aux)
	Allocate memory for nodes given a file graph with a particular number of nodes. More...

template<bool V = DirectedNotInOut>
std::enable_if_t<!V >	constructNodesFrom (FileGraph &graph, unsigned tid, unsigned total, ReadGraphAuxData &aux)
	Constructs the MorphGraph nodes given a FileGraph to construct it from. More...

template<bool V = DirectedNotInOut>
std::enable_if_t< V >	constructNodesFrom (FileGraph &graph, unsigned tid, unsigned total, ReadGraphAuxData &aux)
	Constructs the MorphGraph nodes given a FileGraph to construct it from. More...

template<bool V = DirectedNotInOut>
std::enable_if_t<!V >	constructOutEdgesFrom (FileGraph &graph, unsigned tid, unsigned total, ReadGraphAuxData &aux)
	Constructs the MorphGraph edges given a FileGraph to construct it from and already created nodes. More...

template<bool V = DirectedNotInOut>
std::enable_if_t< V >	constructOutEdgesFrom (FileGraph &graph, unsigned tid, unsigned total, const ReadGraphAuxData &aux)
	Constructs the MorphGraph edges given a FileGraph to construct it from and already created nodes. More...

template<bool V = DirectedNotInOut>
std::enable_if_t<!V >	constructInEdgesFrom (FileGraph &graph, unsigned tid, unsigned total, ReadGraphAuxData &aux)
	Constructs the MorphGraph in-edges given a FileGraph to construct it from and already created nodes. More...

template<bool V = DirectedNotInOut>
std::enable_if_t< V >	constructInEdgesFrom (FileGraph &, unsigned, unsigned, ReadGraphAuxData &)
	If a directed graph and no in-edges exist (i.e. More...

Static Public Attributes
static constexpr const bool	DirectedNotInOut = (Directional && !InOut)
	True if a node is both directional and not storing both in and out edges. More...

Detailed Description

template<typename NodeTy, typename EdgeTy, bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>
class galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >

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

An example of use:

struct Node {
  ... // Definition of node data
};
typedef galois::graphs::MorphGraph<Node,int,true> Graph;
// Create graph
Graph g;
Node n1, n2;
Graph::GraphNode a, b;
a = g.createNode(n1);
g.addNode(a);
b = g.createNode(n2);
g.addNode(b);
g.getEdgeData(g.addEdge(a, b)) = 5;
// Traverse graph
for (Graph::iterator ii = g.begin(), ei = g.end(); ii != ei; ++ii) {
  Graph::GraphNode src = *ii;
  for (Graph::edge_iterator jj = g.edge_begin(src), ej = g.edge_end(src);
       jj != ej;
       ++jj) {
    Graph::GraphNode dst = graph.getEdgeDst(jj);
    int edgeData = g.getEdgeData(jj);
    assert(edgeData == 5);
  }
}

And in C++11:

// Traverse graph
for (Graph::GraphNode src : g) {
  for (Graph::edge_iterator edge : g.out_edges(src)) {
    Graph::GraphNode dst = g.getEdgeDst(edge);
    int edgeData = g.getEdgeData(edge);
    assert(edgeData == 5);
  }
}

Template Parameters

NodeTy	Type of node data
EdgeTy	Type of edge data
Directional	true if graph is directed
InOut	true if directed graph tracks in-edges
HasNoLockable	if true, use no abstract locks in the graph
SortedNeighbors	Keep neighbors sorted (for faster findEdge)
FileEdgeTy	type of edges on file to be read from

Examples:: lonestar/tutorial_examples/TorusConstruction.cpp.

Member Typedef Documentation

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::AuxNodePadded = typename galois::substrate::CacheLineStorage<AuxNode>

Padded version of AuxNode.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::edge_data_reference = typename gNodeTypes::EdgeInfo::reference

Reference to edge data.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::edge_data_type = EdgeTy

Edge data type.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::edge_iterator = typename boost::filter_iterator<is_out_edge, typename gNodeTypes::iterator>

(Out or Undirected) Edge iterator

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::file_edge_data_type = FileEdgeTy

Edge data type of file we are loading this graph from.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::GraphNode = gNode*

Graph node handle.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::in_edge_iterator = typename boost::filter_iterator<is_in_edge, typename gNodeTypes::iterator>

In Edge iterator.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::iterator = boost::transform_iterator< makeGraphNode, boost::filter_iterator<is_node, typename NodeListTy::iterator>>

Node iterator.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::local_iterator = iterator

local iterator over nodes

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::node_data_reference = typename gNodeTypes::reference

Reference to node data.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::node_data_type = NodeTy

Node data type.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::read_tag = read_with_aux_first_graph_tag

Tag that defines to graph reader how to read a graph into this class.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

using galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::ReadGraphAuxData = typename std::conditional<DirectedNotInOut, LargeArray<GraphNode>, LargeArray<AuxNodePadded>>::type

Large array that contains auxiliary data for each node (AuxNodes)

Member Function Documentation

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

edge_iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::addEdge	(	GraphNode	src,
		GraphNode	dst,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

Adds an edge to graph, replacing existing value if edge already exists.

Ignore the edge data, let the caller use the returned iterator to set the value if desired. This frees us from dealing with the void edge data problem in this API

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<typename... Args>

edge_iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::addMultiEdge	(	GraphNode	src,
		GraphNode	dst,
		galois::MethodFlag	mflag,
		Args &&...	args
	)

inline

Adds and initializes an edge to graph but does not check for duplicate edges.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

void galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::addNode	(	const GraphNode &	n,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

Adds a node to the graph.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

void galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::allocateFrom	(	FileGraph &	graph,
		ReadGraphAuxData &	aux
	)

inline

Allocate memory for nodes given a file graph with a particular number of nodes.

Parameters

graph	FileGraph with a number of nodes to allocate
aux	Data structure in which to allocate space for nodes.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::begin ( )

inline

Returns an iterator to all the nodes in the graph.

Not thread-safe.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<bool V = DirectedNotInOut>

std::enable_if_t<!V> galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::constructInEdgesFrom	(	FileGraph &	graph,
		unsigned	tid,
		unsigned	total,
		ReadGraphAuxData &	aux
	)

inline

Constructs the MorphGraph in-edges given a FileGraph to construct it from and already created nodes.

Meant to be called by multiple threads. DirectedNotInOut = false version

Parameters

[in]	graph	FileGraph to construct a morph graph from
[in]	tid	Thread id of thread calling this function
[in]	total	Total number of threads in current execution
[in]	aux	Contains created nodes to create edges for

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<bool V = DirectedNotInOut>

std::enable_if_t<V> galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::constructInEdgesFrom	(	FileGraph &	,
		unsigned	,
		unsigned	,
		ReadGraphAuxData &
	)

inline

If a directed graph and no in-edges exist (i.e.

DirectedNotInOut = true), then construct in edges should do nothing.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<bool V = DirectedNotInOut>

std::enable_if_t<!V> galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::constructNodesFrom	(	FileGraph &	graph,
		unsigned	tid,
		unsigned	total,
		ReadGraphAuxData &	aux
	)

inline

Constructs the MorphGraph nodes given a FileGraph to construct it from.

Meant to be called by multiple threads. Version for DirectedNotInOut = false.

Parameters

[in]	graph	FileGraph to construct a morph graph from
[in]	tid	Thread id of thread calling this function
[in]	total	Total number of threads in current execution
[in,out]	aux	Allocated memory to store newly created nodes

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<bool V = DirectedNotInOut>

std::enable_if_t<V> galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::constructNodesFrom	(	FileGraph &	graph,
		unsigned	tid,
		unsigned	total,
		ReadGraphAuxData &	aux
	)

inline

Constructs the MorphGraph nodes given a FileGraph to construct it from.

Meant to be called by multiple threads. Version for DirectedNotInOut = true.

Parameters

[in]	graph	FileGraph to construct a morph graph from
[in]	tid	Thread id of thread calling this function
[in]	total	Total number of threads in current execution
[in,out]	aux	Allocated memory to store newly created nodes

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<bool V = DirectedNotInOut>

std::enable_if_t<!V> galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::constructOutEdgesFrom	(	FileGraph &	graph,
		unsigned	tid,
		unsigned	total,
		ReadGraphAuxData &	aux
	)

inline

Constructs the MorphGraph edges given a FileGraph to construct it from and already created nodes.

Meant to be called by multiple threads. DirectedNotInOut = false version

Parameters

[in]	graph	FileGraph to construct a morph graph from
[in]	tid	Thread id of thread calling this function
[in]	total	Total number of threads in current execution
[in]	aux	Contains created nodes to create edges for

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<bool V = DirectedNotInOut>

std::enable_if_t<V> galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::constructOutEdgesFrom	(	FileGraph &	graph,
		unsigned	tid,
		unsigned	total,
		const ReadGraphAuxData &	aux
	)

inline

Constructs the MorphGraph edges given a FileGraph to construct it from and already created nodes.

Meant to be called by multiple threads. DirectedNotInOut = true version

Parameters

[in]	graph	FileGraph to construct a morph graph from
[in]	tid	Thread id of thread calling this function
[in]	total	Total number of threads in current execution
[in]	aux	Contains created nodes to create edges for

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

bool galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::containsNode	(	const GraphNode &	n,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`
	)		const

inline

Checks if a node is in the graph.

Returns: true if a node has is in the graph

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<typename... Args>

GraphNode galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::createNode ( Args &&... args )

inline

Creates a new node holding the indicated data.

Usually you should call addNode() afterwards.

Parameters

[in] args constructor arguments for node data

Returns: newly created graph node

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

edge_iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::edge_begin	(	GraphNode	N,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

Returns an iterator to the neighbors of a node.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

edge_iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::edge_end	(	GraphNode	N,
		galois::MethodFlag	GALOIS_UNUSEDmflag = `MethodFlag::WRITE`
	)

inline

Returns the end of the neighbor edge iterator.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

runtime::iterable<NoDerefIterator<edge_iterator> > galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::edges	(	GraphNode	N,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

Return a range of edges that can be iterated over by C++ for-each.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::end ( )

inline

Returns the end of the node iterator. Not thread-safe.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

edge_iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::findEdge	(	GraphNode	src,
		GraphNode	dst,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

Finds if an edge between src and dst exists.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

edge_iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::findEdgeSortedByDst	(	GraphNode	src,
		GraphNode	dst,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

Find/return edge between src/dst if it exists; assumes that edges are sorted by destination.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<bool _Undirected = !Directional>

edge_iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::findInEdge	(	GraphNode	src,
		GraphNode	dst,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`,
		typename std::enable_if< _Undirected >::type *	= `0`
	)

inline

Find a particular in-edge: note this function activates for the undirected graph case, so it just calls the regular out-edge finding function.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<bool _DirectedInOut = (Directional && InOut)>

in_edge_iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::findInEdge	(	GraphNode	src,
		GraphNode	dst,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`,
		typename std::enable_if< _DirectedInOut >::type *	= `0`
	)

inline

Find if an incoming edge between src and dst exists for directed in-out graphs.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

node_data_reference galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::getData	(	const GraphNode &	n,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`
	)		const

inline

Gets the node data for a node.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

edge_data_reference galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::getEdgeData	(	edge_iterator	ii,
		galois::MethodFlag	mflag = `MethodFlag::UNPROTECTED`
	)		const

inline

Returns the edge data associated with the edge.

It is an error to get the edge data for a non-existent edge. It is an error to get edge data for inactive edges. By default, the mflag is galois::MethodFlag::UNPROTECTED because edge_begin() dominates this call and should perform the appropriate locking.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

edge_data_reference galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::getEdgeData	(	in_edge_iterator	ii,
		galois::MethodFlag	mflag = `MethodFlag::UNPROTECTED`
	)		const

inline

Get edge data for an in-edge.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

GraphNode galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::getEdgeDst ( edge_iterator ii )

inline

Returns the destination of an edge.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

GraphNode galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::getEdgeDst ( in_edge_iterator ii )

inline

Returns the destination of an in-edge.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<bool _Undirected = !Directional>

in_edge_iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::in_edge_begin	(	GraphNode	N,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`,
		typename std::enable_if<!_Undirected >::type *	= `0`
	)

inline

Returns an iterator to the in-neighbors of a node.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<bool _Undirected = !Directional>

edge_iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::in_edge_begin	(	GraphNode	N,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`,
		typename std::enable_if< _Undirected >::type *	= `0`
	)

inline

Returns an iterator to the in-neighbors of a node; undirected case in which it's the same as a regular neighbor.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<bool _Undirected = !Directional>

in_edge_iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::in_edge_end	(	GraphNode	N,
		galois::MethodFlag	GALOIS_UNUSEDmflag = `MethodFlag::WRITE`,
		typename std::enable_if<!_Undirected >::type *	= `0`
	)

inline

Returns the end of an in-neighbor edge iterator.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<bool _Undirected = !Directional>

edge_iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::in_edge_end	(	GraphNode	N,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`,
		typename std::enable_if< _Undirected >::type *	= `0`
	)

inline

Returns the end of an in-neighbor edge iterator, undirected case.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<bool _Undirected = !Directional>

runtime::iterable<NoDerefIterator<in_edge_iterator> > galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::in_edges	(	GraphNode	N,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`,
		typename std::enable_if<!_Undirected >::type *	= `0`
	)

inline

Return a range of in-edges that can be iterated over by C++ for-each.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

template<bool _Undirected = !Directional>

runtime::iterable<NoDerefIterator<edge_iterator> > galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::in_edges	(	GraphNode	N,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`,
		typename std::enable_if< _Undirected >::type *	= `0`
	)

inline

Return a range of in-edges that can be iterated over by C++ for-each Undirected case, equivalent to out-edge iteration.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

local_iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::local_begin ( )

inline

Return the beginning of local range of nodes.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

local_iterator galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::local_end ( )

inline

Return the end of local range of nodes.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

internal::EdgesIterator<MorphGraph> galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::out_edges	(	GraphNode	N,
		MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

An object with begin() and end() methods to iterate over the outgoing edges of N.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

void galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::removeEdge	(	GraphNode	src,
		edge_iterator	dst,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

Removes an edge from the graph.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

void galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::removeNode	(	GraphNode	n,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

Removes a node from the graph along with all its outgoing/incoming edges for undirected graphs or outgoing edges for directed graphs.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

void galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::resizeEdges	(	GraphNode	src,
		size_t	size,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

Resize the edges of the node.

For best performance, should be done serially.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

unsigned int galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::size ( )

inline

Returns the number of nodes in the graph.

Not thread-safe.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

size_t galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::sizeOfEdgeData ( ) const

inline

Returns the size of edge data.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

void galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::sortAllEdgesByDst ( MethodFlag mflag = MethodFlag::WRITE )

inline

Sort all edges by destination.

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

void galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::sortEdgesByDst	(	GraphNode	N,
		galois::MethodFlag	mflag = `MethodFlag::WRITE`
	)

inline

Sorts edge of a node by destination.

Member Data Documentation

template<typename NodeTy , typename EdgeTy , bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>

constexpr const bool galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >::DirectedNotInOut = (Directional && !InOut)

static

True if a node is both directional and not storing both in and out edges.

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

MorphGraph.h

Classes

Public Types

Public Member Functions

Static Public Attributes

Detailed Description

template<typename NodeTy, typename EdgeTy, bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy> class galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >

Member Typedef Documentation

Member Function Documentation

Member Data Documentation

template<typename NodeTy, typename EdgeTy, bool Directional, bool InOut = false, bool HasNoLockable = false, bool SortedNeighbors = false, typename FileEdgeTy = EdgeTy>
class galois::graphs::MorphGraph< NodeTy, EdgeTy, Directional, InOut, HasNoLockable, SortedNeighbors, FileEdgeTy >