template<typename V = Empty, typename E = Empty>
struct Grappa::Graph< V, E >
Distributed graph data structure, with customizable vertex and edge data.
This is Grappa's primary graph data structure. Graph is a symmetric data structure, so a Graph proxy object will be allocated on all cores, providing local access to common data and methods to access the entirety of the graph.
The Graph class defines two types based on the specified template parameters: Vertex and Edge. Vertex holds information about an individual vertex, such as the degree (nadj), and the associated data whose type is specified by the V template parameter. Edge holds the two global addresses to its source and destination vertices, as well as data associated with this edge, of the type specified by the E parameter.
A typical use of Graph will define a custom graph type, construct it, and then use the returned symmetric pointer to refer to the graph, possibly looking something like this:
struct VertexData { double rank; };
struct EdgeData { double weight; };
using G = Graph<VertexData,EdgeData>;
LOG(INFO) << "graph has " << g->nv << " vertices";
forall(g, [](G::Vertex& v){ });
This Graph structure is constructed from a TupleGraph (a simple list of edge tuples – source & dest) using Graph::create().
Vertices are randomly distributed among cores (using a simple global heap allocation). Edges are placed on the core of their source vertex. Therefore, iterating over outgoing edges is very efficient, but a vertex's incoming edges must be found the hard way (in practice, we just avoid doing it entirely if using this graph structure).
Parallel Iterators
A number of parallel iterators are available for Graphs, to iterate over vertices or edges using forall. Specialization is done based on which parameters are requested, sometimes resulting in different iteration schemes.
Full graph iteration:
using G = Graph<VertexData,EdgeData>;
forall(g, [](G::Vertex& v){});
forall(g, [](G::Vertex& src, G::Edge& e){ ... });
...
});
});
forall(g, [](
const G::Edge& e, G::Vertex& dst){ ... });
Iteration over adjacencies of single Vertex:
forall<async>(
adj(g,v), [&v](Edge& e){
LOG(INFO) << v.id << " -> " << e.id;
});
forall<async>(
adj(g,v), [&v](int64_t ei, Edge& e){
LOG(INFO) << "v.adj[" << ei << "] = " << e.id;
});
});
Definition at line 241 of file Graph.hpp.
