wiki:CreatingAGraphAdapter

This page is under construction. It will describe how to create a graph adapter.


This is a description of the API for the graph adapters in MTGL. To define a graph adapter for a new graph type, the following types, functions, and objects must be defined. For the following, let graph_adapter represent the type of the current graph adapter.

Note that this discussion does not yet include any of the mutable concepts. We are starting out with only the features supported by static_graph.

The vertices and edges are expected to 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 things 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.

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.

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.


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.

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.

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

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

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.
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.
out_edge_iterator
out_edges(vertex_descriptor v, const graph_adapter& g)
Returns an iterator that iterates over all the outgoing adjacent edges of v.
in_edge_iterator
in_edges(vertex_descriptor v, const graph_adapter& g)
Returns an iterator that iterates over all the incoming adjacent 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_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, vertex_descriptor v)
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.

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.

size_type
out_degree(vertex_descriptor v, const graph_adapter& g)
Returns the number of edges leaving v.
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.


Objects

The user needs to define the vertex_id_map and edge_id_map objects. These objects tell the API how to access the vertex and edge ids. The user should use the following template and needs to fill in the bodies of the operator[]() functions.

class vertex_id_map :
  public put_get_helper<int, vertex_id_map<graph_adapter> > {
public:
  typedef typename graph_traits<graph_adapter>::vertex_descriptor key_type;
  typedef typename graph_traits<graph_adapter>::size_type value_type;
  vertex_id_map() {}

  value_type operator[] (const key_type& k) const { /* Function body. */ }
  value_type operator[] (const key_type* k) const { /* Function body. */ }
};

class edge_id_map :
  public put_get_helper<int, edge_id_map<graph_adapter> > {
public:
  typedef typename graph_traits<graph_adapter>::edge_descriptor key_type;
  typedef typename graph_traits<graph_adapter>::size_type value_type;
  edge_id_map() {}

  value_type operator[] (const key_type& k) const { /* Function body. */ }
  value_type operator[] (const key_type* k) const { /* Function body. */ }
};

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 away any cost for using the iterators for the static graph adapter.

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

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.

Directionality

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.

Wrapper Adapters

There are two types of graph adapters: normal adapters and wrapper adapters. A normal adapter wraps directly around a graph object. An example of this is static_graph_adapter. A wrapper adapter wraps around another adapter to provide a different view of a graph. We currently provide three types of wrapper adapters: duplicate_adapter, subgraph_adapter, and transpose_adapter.