wiki:GraphAdapters

This is a description of the API for the graph adapters in MTGL. A graph adapter defines the following types and functions. For the following, let graph_adapter represent the type of the current graph adapter.

Note that this does not include any of the mutable parts of the API because those are not developed yet. We are starting out with only the features supported by static_graph_adapter.

The vertices and edges have ids of type size_type. The ids are set during a call to init(n, m, srcs, trgs). The vertices will have ids 0 - n-1. The srcs and trgs arrays represent the source and target vertex ids of each edge. The edges will have ids 0 - m-1 in the order they are given in trgs and srcs. Requiring ids is a break from BGL which uses solely uses vertex and edge descriptors. Users of BGL can add ids as a property map if they are required. We do this because it makes parallelism easier on the XMT.

Types

A graph adapter defines the following types.

size_type The type that represents sizes associated with the graph such as the number of edges in the graph or the degree of a vertex.
vertex_descriptor The handle used to refer to a vertex.
edge_descriptor The handle used to refer to a edge.
vertex_iterator Iterator type that iterates over all the vertices in a graph.
edge_iterator Iterator type that iterates over all the edges in a graph.
adjacency_iterator Iterator type that iterates over the adjacent vertices of a given vertex.
in_adjacency_iterator Iterator type that iterates over the in adjacent vertices of a given vertex.
out_edge_iterator Iterator type that iterates over the outgoing adjacent edges of a given vertex.
in_edge_iterator Iterator type that iterates over the incoming adjacent edges of a given vertex.
graph_type The type of the base graph for a wrapper adapter.
base_adapter_type The type of the base adapter for a wrapper adapter.


Functions

A graph adapter defines the following functions.

Constructors

graph_adapter()
Creates an empty graph adapter.

graph_adapter(const graph_adapter& g)
Initializes the graph adapter to be a copy of g. This is a deep copy.

Graph Functions

size_type
num_vertices(const graph_adapter& g)
Returns the number of vertices in g.

size_type
num_edges(const graph_adapter& g)
Returns the number of edges in g.

vertex_descriptor
get_vertex(size_type i, const graph_adapter& g)
Returns the vertex from g that has id i.

edge_descriptor
get_edge(size_type i, const graph_adapter& g)
Returns the edge from g that has id i.

bool
is_directed(const graph_adapter& g)
Returns true if a graph is directed.

bool
is_undirected(const graph_adapter& g)
Returns true if a graph is undirected.

bool
is_bidirectional(const graph_adapter& g)
Returns true if a graph is bidirectional.

void
init(size_type n, size_type m, size_type* srcs, size_type* trgs, const graph_adapter& g)
Initializes an empty graph with n vertices and m edges. The vertices will have ids 0 - n-1. The srcs and trgs arrays represent the source and target vertex ids of each edge. The edges will have ids 0 - m-1 in the order they are given in trgs and srcs.

void
clear(graph_adapter& g)
Removes all the vertices and edges in the graph.

graph_adapter&
operator=(const graph_adapter& g)
Returns a copy of g. This is a deep copy.

Iterator Functions

vertex_iterator
vertices(const graph_adapter& g)
Returns an iterator that iterates over all the vertices in g.

edge_iterator
edges(const graph_adapter& g)
Returns an iterator that iterates over all the edges in g.

adjacency_iterator
adjacent_vertices(vertex_descriptor v, const graph_adapter& g)
Returns an iterator that iterates over all the vertices adjacent to v via outgoing edges.

out_edge_iterator
out_edges(vertex_descriptor v, const graph_adapter& g)
Returns an iterator that iterates over all the outgoing edges of v.

The following two functions are only available for a bidirectional graph.
in_adjacency_iterator
in_adjacent_vertices(vertex_descriptor v, const graph_adapter& g)
Returns an iterator that iterates over all the vertices adjacent to v via incoming edges.

in_edge_iterator
in_edges(vertex_descriptor v, const graph_adapter& g)
Returns an iterator that iterates over all the incoming edges of v.

Edge Functions

vertex_descriptor
source(const edge_descriptor& e, const graph_adapter& g)
Returns the source vertex of e.

vertex_descriptor
target(const edge_descriptor& e, const graph_adapter& g)
Returns the target vertex of e.

vertex_descriptor
other(const edge_descriptor& e, const graph_adapter& g)
Returns the vertex of e that is opposite of v.

Vertex Functions

size_type
out_degree(vertex_descriptor v, const graph_adapter& g)
Returns the number of edges leaving v.

The following two functions are only available for a bidirectional graph.
size_type
in_degree(vertex_descriptor v, const graph_adapter& g)
Returns the number of edges entering v.

size_type
degree(vertex_descriptor v, const graph_adapter& g)
Returns the sum of the number of edges leaving v and the number of edges entering v.

Iterators

The normal iterator approach doesn't work on the XMT. The XMT uses loop parallelism, dividing iterations of the loop among the threads. Threads cannot share the same iterator as they would need that iterator to point to different things simultaneously. In addition, beginning and ending iterators don't have much use since the XMT can only parallelize inductive loops. The compiler doesn't know how to convert an iterator range into the number of iterations the loop will execute.

We use a new iterator concept that works within the constraints of the XMT parallel model and the compiler. Instead of using two iterators representing a range, we use a single iterator that is accessed as if it was a vector of the items being iterated over. In MTGL the range of the iterators in numerical terms is always known. For example, the vertex_iterator ranges from 0 to num_vertices(g) - 1 while an out_edge_iterator ranges from 0 to out_degree(v, g) - 1. This implementation is thread-safe as the only state information for a specific item pointed to by the iterator is passed as the parameter to operator[]. Additionally, the implementation allows the compiler to automatically parallelize loops containing iterators if the iterator is designed correctly. For example, the compiler can automatically parallelize the iterators for static graph adapter. The compiler also optimizes most or all of the cost for using the iterators for the static graph adapter.

Iterating over all the vertices in the graph would be accomplished as follows:

typedef graph_traits<graph_adapter>::vertex_iterator vertex_iterator;
typedef graph_traits<graph_adapter>::vertex_descriptor vertex_descriptor;

vertex_iterator vIter = vertices(g);
size_type n = num_vertices(g);
for (size_type i = 0; i < n; ++i)
{
  vertex_descriptor v = vIter[i];

  // Do something with v...
}

Iterating over all the edges in the graph would be accomplished as follows:

typedef graph_traits<graph_adapter>::edge_iterator edge_iterator;
typedef graph_traits<graph_adapter>::edge_descriptor edge_descriptor;

edge_iterator eIter = edges(g);
size_type m = num_edges(g);
for (size_type i = 0; i < m; ++i)
{
  edge_descriptor e = eIter[i];

  // Do something with e...
}

Iterating over the adjacent vertices of a vertex would be accomplished as follows:

typedef graph_traits<graph_adapter>::adjacency_iterator adjacency_iterator;
typedef graph_traits<graph_adapter>::vertex_descriptor vertex_descriptor;

adjacency_iterator adjIter = adjacent_vertices(v, g);
size_type out_deg = out_degree(v, g);
for (size_type i = 0; i < out_deg; ++i)
{
  vertex_descriptor v = adjIter[i];

  // Do something with v...
}

Iterating over the out edges of a vertex would be accomplished as follows:

typedef graph_traits<graph_adapter>::out_edge_iterator out_edge_iterator;
typedef graph_traits<graph_adapter>::edge_descriptor edge_descriptor;

out_edge_iterator oeIter = out_edges(v, g);
size_type out_deg = out_degree(v, g);
for (size_type i = 0; i < out_deg; ++i)
{
  edge_descriptor e = adjIter[i];

  // Do something with e...
}

Iterating over the in adjacent vertices of a vertex is similar to to iterating over the adjacent vertices. Iterating over the in edges of a vertex is similar to iterating over the out edges.

Property Maps

Property maps associate properties to vertices and edges. The library expects an adapter to define the internal property id for both vertices and edges. For user-definable properties, the library only provide external properties as opposed to BGL, which also provides internal properties. There are two types of property maps available: array and map. Below is an example of declaring and using an array property map that assigns a type property to the vertices of a graph. Map property maps are similarly declared.

typedef static_graph_adapter<directedS> Graph;
typedef array_property_map<int, vertex_id_map<Graph> >
        vertex_property_map;

// g is initialized to have 8 vertices.

int vTypes[8] = { 0, 1, 3, 1, 2, 0, 2, 3 };

vertex_id_map<Graph> g_vid_map = get(_vertex_id_map, g);
vertex_property_map vTypemap(vTypes, g_vid_map);

int v2type = vTypemap[2];  // v2type is set to 3.

A more complete discussion is available at PropertyMaps.

Directionality

The graph adapters provided in MTGL have three direction types: undirected, directed, and bidirectional. In an undirected graph, the edges have no orientation. They can be traveled in either direction. In a directed graph, the edges have an orientation. They can only be traveled in a single direction. A directed graph only has access to its outgoing edges. A bidirectional graph is a directed graph that also has access to its incoming edges. Because of this, a bidirectional graph typically requires twice the storage of a directed graph.

The direction of a graph adapter is part of its type, and it is given as a template parameter in the graph adapter declaration. The template parameter can be one of the values undirectedS, directedS, and bidirectionalS. The static_graph_adapter supports all three directions, but the graph_adapter only supports the directed and undirected directions. The graph_adapter is planned to support bidirectional graphs, but it hasn't been implemented yet. Here is an example of declaring a bidirectional static_graph_adapter and an undirected graph_adapter.

static_graph_adapter<bidirectionalS> sga;
graph_adapter<undirectedS> ga;

Right now, the graphs communicate directionality through the is_directed(), is_undirected(), and is_bidirectional() functions. These are handy for algorithms that behave differently for graphs with different directionality. It would be much cleaner if we could get the directionality to be all handled at compile time. Some work needs to be done to see if this can be done for all algorithms. If so, we could get rid of the functions.

Graph Implementations

There are two graph implementations currently offered with MTGL: static_graph_adapter and graph_adapter. The static_graph_adapter is an immutable compressed sparse row graph implementation. Immutable means that vertices and edges cannot be added on the fly. The only way to add vertices and edges is through the copy constructor, the assignment operator, and the init() function. The only way to remove vertices and edges is through the clear() function. The static_graph_adapter has been designed to be as fast and parallelizable as possible.

The graph_adapter is a mutable adjacency list graph implementation. It has functions for adding and removing vertices and edges on the fly. The mutability comes at a cost of performance, however. Additionally, not near as much work has been done yet on the graph_adapter to make it efficient.