Graph Creation

SGL provides several types of graph containers, including directed and undirected graphs, and multi-edged or non-multiedged graphs. Graphs can further store properties on their vertices and edges, which can be custom classes. SGL also provides utilities to read and write graphs, which can read and write a variety of standard formats. SGL also allows expression of custom I/O formats by defining how vertices and edges are to be written to the file.

SGL supports three ways of mutating graphs:

• Generate the graph using generators.
• Read from / write to files.
• Manually add/delete edges and vertices.

In this section, we show how to declare a graph, as well as how to generate it, input it from file and write it to a file.

Defining the Graph

The simplest way to define a STAPL graph is as follows:

using my_vertex_prop_t = int;
using my_edge_prop_t = int;
using graph_type = stapl::multigraph<my_vertex_prop_t, my_edge_prop_t>;

graph_type g(100);

This creates a multi-graph -- an undirected graph that allows multiple edges between a pair of vertices to be added -- with the provided vertex and edge properties, stored respectively on vertices and edges. The properties in this case are both integers, but could be set to any type. The constructor of the graph tells it to create the graph with 100 vertices, indexed from 0 to 99.

SGL provides the generic graph class graph<DIRECTEDNESS, MULTIEDGEDNESS, VP, EP>. This is a generic graph, where the directedness (one of stapl::DIRECTED or stapl::UNDIRECTED) and multi-edgedness (one of stapl::MULTIEDGES or stapl::NONMULTIEDGES) can be controlled.

SGL also provides several pre-defined specializations of this generic graph container for programmer ease:

• multigraph<VP, EP>: An undirected multiedged graph.
• multidigraph<VP, EP>: A directed multiedged graph.
• digraph<VP, EP>: A directed graph which disallows multiple edges (non-multiedged)

Further, SGL provides a dynamic_graph<...>container to allow dynamically adding and deleting of vertices. Note that adding and deleting of edges is supported by both, dynamic_graph and graph containers. The graph container is static, and therefore, the number of vertices must be defined a priori, and is provided for efficiency.

We can also define a graph_view on this container like so:

stapl::graph_view<graph_type> view(g);

This creates a graph_view on the given graph, which can now be used as an input to various algorithms. Next, we look at how to read/write or generate graphs in SGL.