Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional > Class Template Reference

A Graph. More...

#include <Graph.h>

List of all members.

Classes

struct  first_eq_and_valid
struct  first_not_valid
struct  gNode
struct  is_edge
struct  is_node
struct  makeGraphNode

Public Types

typedef gNodeGraphNode
 Graph node handle.
typedef EdgeTy edge_type
 Edge data type.
typedef NodeTy node_type
 Node data type.
typedef boost::filter_iterator
< is_edge, typename
gNode::iterator
edge_iterator
 Edge iterator.
typedef gNode::EITy::reference edge_data_reference
 Reference to edge data.
typedef
boost::transform_iterator
< makeGraphNode,
boost::filter_iterator
< is_node, typename
NodeListTy::iterator > > 
iterator
 Node iterator.
typedef iterator local_iterator

Public Member Functions

GraphNode createNode (const NodeTy &nd)
 Creates a new node holding the indicated data.
void addNode (const GraphNode &n, Galois::MethodFlag mflag=ALL)
 Adds a node to the graph.
NodeTy & getData (const GraphNode &n, Galois::MethodFlag mflag=ALL) const
 Gets the node data for a node.
bool containsNode (const GraphNode &n, Galois::MethodFlag mflag=ALL) const
 Checks if a node is in the graph.
void removeNode (GraphNode n, Galois::MethodFlag mflag=ALL)
 Removes a node from the graph along with all its outgoing/incoming edges for undirected graphs or outgoing edges for directed graphs.
edge_iterator addEdge (GraphNode src, GraphNode dst, Galois::MethodFlag mflag=ALL)
 Adds an edge to graph, replacing existing value if edge already exists.
edge_iterator addMultiEdge (GraphNode src, GraphNode dst, Galois::MethodFlag mflag=ALL)
void removeEdge (GraphNode src, edge_iterator dst, Galois::MethodFlag mflag=ALL)
 Removes an edge from the graph.
edge_iterator findEdge (GraphNode src, GraphNode dst, Galois::MethodFlag mflag=ALL)
 Finds if an edge between src and dst exists.
edge_data_reference getEdgeData (edge_iterator ii, Galois::MethodFlag mflag=NONE) const
 Returns the edge data associated with the edge.
GraphNode getEdgeDst (edge_iterator ii)
 Returns the destination of an edge.
edge_iterator edge_begin (GraphNode N, Galois::MethodFlag mflag=ALL)
 Returns an iterator to the neighbors of a node.
edge_iterator edge_end (GraphNode N, Galois::MethodFlag mflag=ALL)
 Returns the end of the neighbor iterator.
iterator begin ()
 Returns an iterator to all the nodes in the graph.
iterator end ()
 Returns the end of the node iterator. Not thread-safe.
local_iterator local_begin ()
local_iterator local_end ()
unsigned int size ()
 Returns the number of nodes in the graph.
size_t sizeOfEdgeData () const
 Returns the size of edge data.
 FirstGraph ()

Private Types

typedef
GaloisRuntime::galois_insert_bag
< gNode
NodeListTy

Private Attributes

NodeListTy nodes
GraphImpl::EdgeFactory< EdgeTy > edges

Detailed Description

template<typename NodeTy, typename EdgeTy, bool Directional>
class Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >

A Graph.

An example of use:

 struct Node {
   ... // Definition of node data
 };

 typedef Galois::Graph::FastGraph<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) {
     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

Member Typedef Documentation

template<typename NodeTy , typename EdgeTy , bool Directional>
typedef gNode::EITy::reference Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::edge_data_reference

Reference to edge data.

template<typename NodeTy , typename EdgeTy , bool Directional>
typedef boost::filter_iterator<is_edge, typename gNode::iterator> Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::edge_iterator

Edge iterator.

template<typename NodeTy , typename EdgeTy , bool Directional>
typedef EdgeTy Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::edge_type

Edge data type.

template<typename NodeTy , typename EdgeTy , bool Directional>
typedef gNode* Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::GraphNode

Graph node handle.

template<typename NodeTy , typename EdgeTy , bool Directional>
typedef boost::transform_iterator<makeGraphNode, boost::filter_iterator<is_node, typename NodeListTy::iterator> > Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::iterator

Node iterator.

template<typename NodeTy , typename EdgeTy , bool Directional>
typedef iterator Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::local_iterator
template<typename NodeTy , typename EdgeTy , bool Directional>
typedef NodeTy Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::node_type

Node data type.

template<typename NodeTy , typename EdgeTy , bool Directional>
typedef GaloisRuntime::galois_insert_bag<gNode> Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::NodeListTy [private]

Constructor & Destructor Documentation

template<typename NodeTy , typename EdgeTy , bool Directional>
Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::FirstGraph (  )  [inline]

Member Function Documentation

template<typename NodeTy , typename EdgeTy , bool Directional>
edge_iterator Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::addEdge ( GraphNode  src,
GraphNode  dst,
Galois::MethodFlag  mflag = ALL 
) [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>
edge_iterator Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::addMultiEdge ( GraphNode  src,
GraphNode  dst,
Galois::MethodFlag  mflag = ALL 
) [inline]
template<typename NodeTy , typename EdgeTy , bool Directional>
void Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::addNode ( const GraphNode n,
Galois::MethodFlag  mflag = ALL 
) [inline]

Adds a node to the graph.

template<typename NodeTy , typename EdgeTy , bool Directional>
iterator Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::begin (  )  [inline]

Returns an iterator to all the nodes in the graph.

Not thread-safe.

template<typename NodeTy , typename EdgeTy , bool Directional>
bool Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::containsNode ( const GraphNode n,
Galois::MethodFlag  mflag = ALL 
) const [inline]

Checks if a node is in the graph.

template<typename NodeTy , typename EdgeTy , bool Directional>
GraphNode Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::createNode ( const NodeTy &  nd  )  [inline]

Creates a new node holding the indicated data.

Usually you should call addNode() afterwards.

template<typename NodeTy , typename EdgeTy , bool Directional>
edge_iterator Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::edge_begin ( GraphNode  N,
Galois::MethodFlag  mflag = ALL 
) [inline]

Returns an iterator to the neighbors of a node.

template<typename NodeTy , typename EdgeTy , bool Directional>
edge_iterator Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::edge_end ( GraphNode  N,
Galois::MethodFlag  mflag = ALL 
) [inline]

Returns the end of the neighbor iterator.

template<typename NodeTy , typename EdgeTy , bool Directional>
iterator Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::end (  )  [inline]

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

template<typename NodeTy , typename EdgeTy , bool Directional>
edge_iterator Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::findEdge ( GraphNode  src,
GraphNode  dst,
Galois::MethodFlag  mflag = ALL 
) [inline]

Finds if an edge between src and dst exists.

template<typename NodeTy , typename EdgeTy , bool Directional>
NodeTy& Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::getData ( const GraphNode n,
Galois::MethodFlag  mflag = ALL 
) const [inline]

Gets the node data for a node.

template<typename NodeTy , typename EdgeTy , bool Directional>
edge_data_reference Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::getEdgeData ( edge_iterator  ii,
Galois::MethodFlag  mflag = NONE 
) 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::NONE because edge_begin() dominates this call and should perform the appropriate locking.

template<typename NodeTy , typename EdgeTy , bool Directional>
GraphNode Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::getEdgeDst ( edge_iterator  ii  )  [inline]

Returns the destination of an edge.

template<typename NodeTy , typename EdgeTy , bool Directional>
local_iterator Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::local_begin (  )  [inline]
template<typename NodeTy , typename EdgeTy , bool Directional>
local_iterator Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::local_end (  )  [inline]
template<typename NodeTy , typename EdgeTy , bool Directional>
void Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::removeEdge ( GraphNode  src,
edge_iterator  dst,
Galois::MethodFlag  mflag = ALL 
) [inline]

Removes an edge from the graph.

template<typename NodeTy , typename EdgeTy , bool Directional>
void Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::removeNode ( GraphNode  n,
Galois::MethodFlag  mflag = ALL 
) [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>
unsigned int Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::size (  )  [inline]

Returns the number of nodes in the graph.

Not thread-safe.

template<typename NodeTy , typename EdgeTy , bool Directional>
size_t Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::sizeOfEdgeData (  )  const [inline]

Returns the size of edge data.


Member Data Documentation

template<typename NodeTy , typename EdgeTy , bool Directional>
GraphImpl::EdgeFactory<EdgeTy> Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::edges [private]
template<typename NodeTy , typename EdgeTy , bool Directional>
NodeListTy Galois::Graph::FirstGraph< NodeTy, EdgeTy, Directional >::nodes [private]

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

Generated on 12 Apr 2013 for Galois by  doxygen 1.6.1