Options for Execute

There are a few optional parameters to sgl::execute that one should consider when developing a graph algorithm using SGL.

Active Vertex Ratio

The active vertex ratio is a rough estimate of how many vertices will be active in a given superstep during the traversal. For example, if it is expected that roughly 90% of the vertices will be active in a superstep, then the user can pass a value of 0.9.

Internally, this number is used to select different implementations of the frontier data structure used to track which vertices are active. If a high number of vertices are anticipated to be active (more than 75%), we will use a bitmap structure to efficient keep track of which vertices are in the frontier.

Superstep Occupancy

The superstep occupancy options allows the algorithm writer to describe the number of vertices for specific supersteps -- the first superstep, a middle supperstep and the last superstep. For example, in breadth-first search, the first superstep has a single vertex, a middle superstep has some vertices the last superstep has some vertices.

First superstep Intermediate superstep Last superstep Example Algorithm
single some some BFS
all some some CC
all all all PageRank

We use an enum class to denote the occupancy for a superstep.

enum class superstep_occupancy {
  none, single, some, all
};

To describe the occupancy for the algorithm, we use a tuple of std::integral_constants. For example, the breadth-first search occupancy would be specified like:

using bfs_superstep_occupancy_type
  = std::tuple<std::integral_constant<superstep_occupancy, superstep_occupancy::single>,
               std::integral_constant<superstep_occupancy, superstep_occupancy::some>,
               std::integral_constant<superstep_occupancy, superstep_occupancy::some>>;

Internally, the occupancy information is used to select appropriate implementations of our frontier data structure. For example, if an algorithm states that the occupancy is "all" for every superstep, then we do not need to have an explicit frontier.

Ordering

For some algorithms, the orderings of vertex operator and neighbor operator are sometimes important. For example, invoking a vertex operator on the same vertex twice in a row without an intermediate neighbor operator would result in an invalid state for an algorithm like label-propagation.

We ask the algorithm writer to provide a list of operator orderings that is valid:

  • vop → nop → vop
  • vop → vop

The (vop → nop → vop) ordering is called an interleaved ordering and (vop → vop) is called a successive ordering.

We are left with four cases:

  • Neither is allowed (sgl::ordering_type::neither)
    • Note: a useful algorithm would not have this restriction
  • Only (vop → vop) is allowed (sgl::ordering_type::successive)
    • Note: a useful algorithm would not have this restriction
  • Only (vop → nop → vop) is allowed (sgl::ordering_type::interleaved)
    • Note: this is the case for label-propagation
  • Both (vop → nop → vop) and (vop → vop) is allowed (sgl::ordering_type::both)
    • Note: this is the case for most graph algorithms

We provide an enum class with the four cases listed above:

enum class orderying_type {
  neither, interleaved, successive, both
};

results matching ""

    No results matching ""