Tutorial

This section will introduce the basic concepts to use the STAPL Graph Library.

We are going to implement a simple program that will read a graph from disk, compute the betweenness centrality metric for each vertex, and print out the vertex that has highest centrality value.

Includes

First, we will include the appropriate files for the graph container, helpers for graph I/O and the algorithms we want to run.

#include <stapl/containers/graph/graph.hpp>
#include <stapl/containers/graph/algorithms/graph_io.hpp>
#include <stapl/containers/graph/algorithms/properties.hpp>
#include <stapl/containers/graph/algorithms/betweenness_centrality.hpp>
#include <stapl/algorithms/algorithm.hpp>

We are going to use the betweenness centrality algorithm, so we need to include it. Note that we also include the general algorithm.hpp because want to use the STL-style algorithm max_element.

Main

Every STAPL program begins with the stapl_main function, which is the entry point for the program. It receives the command-line arguments in argc and argv like a traditional C++ main. At the end of the function, we'll return 0 for success, or an error code if something went wrong.

stapl::exit_code stapl_main(int argc, char* argv[])
{
  // ...
  return 0;
}

Graph I/O

Next, we will read in a graph from the disk:

auto graph = stapl::load_edge_list<stapl::properties::bc_property>(argv[1]);

The function load_edge_list will read a graph from the disk that is formatted using the traditional edge list format, which is something like:

num_verts num_edges
0 1
2 3
...

After it reads the graph, it will populate a container and return a graph_view to it. Note that we are using the bc_property for the vertices, which will allow us to store information on the vertex to run the betweenness computation and retrieve the result.

Algorithms

For the main computation, we will run a parallel graph algorithm and a parallel STL algorithm:

stapl::betweenness_centrality(graph);

auto v = stapl::max_element(graph, [](auto x, auto y) {
  return x.property().BC() < y.property().BC();
});

After invoking betweenness_centrality on the graph, all vertices will have their centrality values stored in their properties. That is, for each vertex v, v.property().BC() will contain the centrality value for v.

We can then use max_element to find the largest vertex with respect to this value. We use a custom comparison lambda to specify how we are to compare vertices. In the end, we have a reference to the vertex with highest centrality value as v.

Output

Finally, we want to print out the vertex we found. We use the stapl::do_once construct to ensure that only a single location prints, as we do not want overlapping output.

stapl::do_once([&]() {
  std::cout << v << " is the most important vertex!" << std::endl;
});

Running

Using a C++14 compiler with MPI, we can compile and run the code as follows:

$ make most_central
$ mpirun -np 16 ./most_central my_graph.el
189 is the most important vertex!

Full Code

The full code is below.

#include <stapl/containers/graph/graph.hpp>
#include <stapl/containers/graph/algorithms/graph_io.hpp>
#include <stapl/containers/graph/algorithms/properties.hpp>
#include <stapl/containers/graph/algorithms/betweenness_centrality.hpp>
#include <stapl/algorithms/algorithm.hpp>

stapl::exit_code stapl_main(int argc, char* argv[])
{
  auto graph = stapl::load_edge_list<stapl::properties::bc_property>(argv[1]);

  stapl::betweenness_centrality(graph);

  auto v = stapl::max_element(graph, [](auto x, auto y) {
    return x.property().BC() < y.property().BC();
  });

  stapl::do_once([&]() {
    std::cout << v << " is the most important vertex!" << std::endl;
  });

  return 0;
}

results matching ""

    No results matching ""