wiki:GraphAPI

This page is currently being modified. The information contained in it may not be accurate.

This is a description of the graph API for the MTGL. Like the Boost Graph Library, the API consists only of global functions and types. To use another graph type with the MTGL algorithms, one only needs to define the functions and types described below.

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 compressed_sparse_row_graph.

The vertices and edges have ids of type size_type. For the two graph types included in the MTGL, the vertices and edges have contiguous ids from 0 to one less than the number of vertices or edges. Contiguous ids are not a requirement of the API, but they allow the use of array property maps. Graph types that use noncontiguous ids must use map property maps which don't perform or parallelize as well as array property maps. 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.

The ids are set during a call to init(n, m, srcs, trgs). The srcs and trgs arrays represent the source and target vertex ids of each edge. For the two graph types provided with the MTGL, the vertices will have ids from 0 - n where n is the largest vertex id given in srcs or trgs. Vertices with ids between 0 and n that aren't given as an endpoint in either srcs or trgs are assumed to exist but not have any adjacent edges. For the two graph types provided with the MTGL, the edges will have ids 0 - m-1 in the order they are given in srcs and trgs.


Types

The following types must be defined for all graphs.

Sizes
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.

Descriptors
vertex_descriptor The handle used to refer to a vertex.
edge_descriptor The handle used to refer to a edge.

Vector Iterators
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.

Thread Iterators
thread_vertex_iterator Iterator type that iterates over all the vertices in a graph.
thread_edge_iterator Iterator type that iterates over all the edges in a graph.
thread_adjacency_iterator Iterator type that iterates over the adjacent vertices of a given vertex.
thread_in_adjacency_iterator Iterator type that iterates over the in adjacent vertices of a given vertex.
thread_out_edge_iterator Iterator type that iterates over the outgoing adjacent edges of a given vertex.
thread_in_edge_iterator Iterator type that iterates over the incoming adjacent edges of a given vertex.

Categories
directed_category Indicates if the graph is undirected, directed, or bidirectional.
iterator_category Indicates if the graph supports vector iterators, thread iterators, or both.

Graphs that don't provide either vector or thread iterators should define those as void. Graphs that aren't bidirectional should define the in_* iterators as void. All other types should always be defined.


Functions

There are several categories of functions.

Graph Functions

The following functions must be defined for all graphs.

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

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

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

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

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

void
init(size_type n, size_type m, size_type* srcs, size_type* trgs, const Graph& 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& g)
Removes all the vertices and edges in the graph.

Iterator Functions

The following functions must be defined for all graphs that support vector iteration.

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

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

adjacency_iterator
adjacent_vertices(vertex_descriptor v, const Graph& 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& g)
Returns an iterator that iterates over all the outgoing edges of v.

The following functions must be defined for all graphs that support thread iteration.

thread_vertex_iterator
thread_vertices(const Graph& g)
Returns an iterator that iterates over all the vertices in g.

thread_edge_iterator
thread_edges(const Graph& g)
Returns an iterator that iterates over all the edges in g.

thread_adjacency_iterator
thread_adjacent_vertices(vertex_descriptor v, const Graph& g)
Returns an iterator that iterates over all the vertices adjacent to v via outgoing edges.

thread_out_edge_iterator
thread_out_edges(vertex_descriptor v, const Graph& g)
Returns an iterator that iterates over all the outgoing edges of v.

The following two functions also must be defined for a bidirectional graph that supports vector iteration.

in_adjacency_iterator
in_adjacent_vertices(vertex_descriptor v, const Graph& 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& g)
Returns an iterator that iterates over all the incoming edges of v.

The following two functions also must be defined for a bidirectional graph that supports thread iteration.

thread_in_adjacency_iterator
thread_in_adjacent_vertices(vertex_descriptor v, const Graph& g)
Returns an iterator that iterates over all the vertices adjacent to v via incoming edges.

thread_in_edge_iterator
thread_in_edges(vertex_descriptor v, const Graph& g)
Returns an iterator that iterates over all the incoming edges of v.

Edge Functions

The following functions must be defined for all graphs.

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

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

Vertex Functions

The following functions must be defined for all graphs.

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

In addition, the following two functions must be defined for a bidirectional graph.
size_type
in_degree(vertex_descriptor v, const Graph& g)
Returns the number of edges entering v.

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

Filtering Functions

The following functions must be defined for all graphs. They are used when implementing filtering using the filter_adapter. (See WrapperAdapters for more details.)

vertex_descriptor
null_vertex(const Graph& g)
Returns a special value for a vertex_descriptor that represents an invalid vertex.

edge_descriptor
null_edge(const Graph& g)
Returns a special value for an edge_descriptor that represents an invalid edge.

bool
is_valid(iterator_type& iter, size_type p, const Graph& g)
Returns if the vertex or edge descriptor pointed to by iter[p] is valid.


Iterators

The MTGL provides two types of iterators: vector iterators and thread iterators.

Vector Iterators

When parallelizing with inductive loops, the normal iterator approach doesn't work. For this type of parallelism, the XMT divides iterations of the loop among the threads. Iterators cannot save state as multiple threads would need that iterator to point to different things simultaneously.

We use a new iterator concept that works within the constraints of the XMT inductive loop 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 the 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. Note that these ranges do not translate to ids for the vertices and edges.

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 compressed_sparse_row_graph. The compiler also optimizes away most or all of the cost for using the iterators for compressed_sparse_row_graph.

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

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

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>::edge_descriptor edge_descriptor;
typedef graph_traits<Graph>::edge_iterator edge_iterator;

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>::vertex_descriptor vertex_descriptor;
typedef graph_traits<Graph>::adjacency_iterator adjacency_iterator;

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>::edge_descriptor edge_descriptor;
typedef graph_traits<Graph>::out_edge_iterator out_edge_iterator;

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.

Thread Iterators

This type of iterator is new with version 1.1.

When parallelizing using the for all streams pragma, the MTGL provides thread iterators. These iterators save state and function almost identically to normal iterators. Each thread gets a separate pair of the iterators. Using these iterators requires using the manual partitioning functions.

There are several benefits to thread iterators. First, they closely align with iterators used in serial C++. Second, they allow good performance with more complex graph structures. We plan for thread iterators to supplant vector iterators as the default iterator type in the MTGL. We have already rewritten some of the main algorithms in version 1.1, such as BFS, to use thread iterators instead of vector iterators. Consequently, those algorithms will not work unless you have implemented thread iterators for your adapter. You'll know if that's happening because you will get a compile error.

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

typedef graph_traits<Graph>::size_type size_type;
typedef graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef graph_traits<Graph>::thread_vertex_iterator thread_vertex_iterator;

size_type stream_id = 0;
size_type num_streams = 1;

#pragma mta for all streams stream_id of num_streams
{
  size_type start = begin_block_range(order, stream_id, num_streams);
  size_type end = end_block_range(order, stream_id, num_streams);

  thread_vertex_iterator verts = thread_vertices(start, g);
  for ( ; start != end; ++start, ++verts)
  {
    vertex_descriptor v = *verts;

    // Do something with v...
  }
}

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

typedef graph_traits<Graph>::size_type size_type;
typedef graph_traits<Graph>::edge_descriptor edge_descriptor;
typedef graph_traits<Graph>::thread_edge_iterator thread_edge_iterator;

size_type stream_id = 0;
size_type num_streams = 1;

#pragma mta for all streams stream_id of num_streams
{
  size_type start = begin_block_range(order, stream_id, num_streams);
  size_type end = end_block_range(order, stream_id, num_streams);

  thread_edge_iterator edgs = thread_edges(start, g);
  for ( ; start != end; ++start, ++edgs)
  {
    edge_descriptor e = *edgs;

    // Do something with e...
  }
}

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

typedef graph_traits<Graph>::adjacency_iterator adjacency_iterator;
typedef graph_traits<Graph>::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>::out_edge_iterator out_edge_iterator;
typedef graph_traits<Graph>::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 graph to define the internal property id for both vertices and edges. Here is an example of defining a vertex_id_map. It is the definition for compressed_sparse_row_graph.

template <typename DIRECTION>
class vertex_id_map<compressed_sparse_row_graph<DIRECTION> > :
  public put_get_helper<
             typename compressed_sparse_row_graph<DIRECTION>::size_type,
             vertex_id_map<compressed_sparse_row_graph<DIRECTION> > > {
public:
  typedef typename compressed_sparse_row_graph<DIRECTION>::vertex_descriptor
          key_type;
  typedef typename compressed_sparse_row_graph<DIRECTION>::size_type value_type;

  vertex_id_map() {}
  value_type operator[] (const key_type& k) const { return k; }
};

The class inherits from put_get_helper (defined in mtgl/mtgl_boost_property.hpp) so that it can use the predefined version of get(). This version of get() requires the map to define the [] operator and the two types key_type and value_type.

Here is an example of defining an edge_id_map. It is the definition for compressed_sparse_row_graph.

template <typename DIRECTION>
class edge_id_map<compressed_sparse_row_graph<DIRECTION> > :
  public put_get_helper<
             typename compressed_sparse_row_graph<DIRECTION>::size_type,
             edge_id_map<compressed_sparse_row_graph<DIRECTION> > > {
public:
  typedef typename compressed_sparse_row_graph<DIRECTION>::edge_descriptor
          key_type;
  typedef typename compressed_sparse_row_graph<DIRECTION>::size_type value_type;

  edge_id_map() {}
  value_type operator[] (const key_type& k) const { return k.id; }
};

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. Array property maps have better performance, but they have the requirement that the ids of the vertices and edges be contiguous and start with 0. Map property maps, which don't parallelize as well and have slower performance, can be used with any ids. The user should prefer array property maps whenever possible because of the better performance.

Array property maps can be initialized with either a C-style array or a dynamic_array. Below is an example of declaring and using an array property map initialized with a C-style array that assigns a color property to the vertices of a graph.

typedef compressed_sparse_row_graph<directedS> Graph;
typedef array_property_map<int, vertex_id_map<Graph> >
        my_property_map;

Graph g;

// g is initialized to have 8 vertices.

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

vertex_id_map<Graph> vid_map = get(_vertex_id_map, g);
my_property_map color_map(colors, vid_map);

int v2_color = get(color_map, get_vertex(2, g));  // v2_color is set to 3.

Array property maps initialized with dynamic arrays and map property maps (which utilize the xmt_hash_table) are similarly declared.

To aid in writing generic code, the MTGL also provides vertex_property_map and edge_property_map. These are classes that the API defines for each class to hide from the user the need to know if a graph type must use array or map property maps. Declaring an object of type vertex_property_map or edge_property_map declares whichever of array or map property map is appropriate. They also hide the memory allocation and deallocation for the underlying data structures. Here is an example of declaring a vertex_property_map and setting its value for the vertex with id 2. An edge_property_map would be declared similarly.

typedef compressed_sparse_row_graph<directedS> Graph;

Graph g;

// Initialize g.

vertex_property_map<Graph, int> vTypemap(g);

put(vTypemap, get_vertex(2), 3);

Writers of generic algorithms should use vertex_property_map and edge_property_map exclusively for property maps inside their algorithms. This allows the algorithm to work for both graph types that use array_property_maps and graph types that use map_property_maps.

There is a default declaration for vertex_property_map and edge_property_map that utilizes an array property map. Therefore, a graph API creator only needs to specialize this class if their graph type doesn't have contiguous ids for either vertices or edges.

Here is an example of how a graph API creator would declare a vertex_property_map that uses a map_property_map for the graph type my_graph that takes a direction template parameter. Note that this is a partial specialization, and it adds the additional template parameter DIRECTION.

template <typename T, typename DIRECTION>
class vertex_property_map<my_graph<DIRECTION>, T> :
  public map_property_map<T, vertex_id_map<my_graph<DIRECTION> > > {
public:
  typedef typename xmt_hash_table<hash_key_type, T>::size_type size_type;

  vertex_property_map(const my_graph<DIRECTION>& g) :
    ht(static_cast<size_type>(1.5 * num_vertices(g))),
    map_property_map<T, vertex_id_map<my_graph<DIRECTION> > >(
      ht, get(_vertex_id_map, g)) {}

private:
  xmt_hash_table<hash_key_type, T> ht;
};

A more complete discussion is available at PropertyMaps.


Directionality

The graphs provided in the 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 requires extra storage compared to a directed graph.

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

compressed_sparse_row_graph<bidirectionalS> sga;
adjacency_list<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 the MTGL: compressed_sparse_row_graph and adjacency_list. The compressed_sparse_row_graph 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 compressed_sparse_row_graph has been designed to be as fast and parallelizable as possible.

The adjacency_list 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 to make it efficient.