IBMPPL Graph Library

System G Graph Middleware provides a graph programming framework similar to the Boost Graph Library (BGL) or the Standard Template Adaptive Parallel Library (STAPL). Our framework employs a generic C++ design using templates to allow users to customize a particular graph data structure. The core graph data structure models a single property graph. In this model the graph stores one property for each vertex and one property for each edge.

System G Native Store Graph Interface

We employ an adjacency list and the consequence of this is that we don’t store the edges as a contiguous set but each vertex stores its outgoing edges. Thus traversing the whole structure of a graph is often a composition of two nested loops: a first one over each vertex, and a nested one over each edge of a vertex.

Native Store whole graph traversal

we show a simple example on how users can specify a work function which is the body of the task, and how it can schedule a number of tasks that is a multiple of the number of cores on the machine. The particular code can be used for example to populate the graph with vertices and edges. If the graph already has data, then the number of the tasks created can vary from the number of cores to the number of vertices in the graph depending on the granularity of the computation per vertex.

Expressing parallelism in System G Native Store

A common graph used for graph analytics is the multi- property graph where each vertex and edge can have an arbitrary number of properties. This functionality is provided by our graph framework by instantiating the base graph class with a multiproperty class for both vertices and edges. A multiproperty class is essentially a map data structure allowing dynamic insertion and deletion of an arbitrary number of key, value pairs.

Native Store class hierarchy. The base graph class is in memory only. The inDiskGraph derives from it and adds storage capability. The multiproperty graph can derive from either base graph or inDiskGraph as requested by user.
Multiproperty graph