Hierarchical Paradigm

Some graph algorithms are naturally hierarchical, i.e., they are expressed via building a hierarchy of graphs. Examples of such algorithms include Boruvka’s Minimum-Spanning Tree, Graph Partitioning, etc. To allow natural expression of such algorithms, SGL provides a Hierarchical Paradigm that manages the creation of hierarchies, allowing the algorithm-developer to focus on specifying the algorithm itself.

The paradigm takes as input a match-operator, as well as vertex- and edge-reducers. The match-operator is used to indicate which vertices a given vertex wants to group with. The paradigm then creates a super-vertex representing all vertices that were mutually grouped together. Super-vertices are connected by super-edges representing cross-edges between the groupings. The property of the super-vertex and super-edges is computed by applying the vertex-reducer and edge-reducers on the child vertex and edge groups, respectively.

The process is applied iteratively until a stopping condition (done-operator) is reached, or until there is only a single super-vertex. The creation of the hierarchy executes the algorithm:

auto hierarchy = create_hierarchy(match(), vertex-reducer(), edge-reducer(),
                        done());

Optionally, we can also provide pre- and post-compute operators to operate on the graph at each level-i, as the hierarchy is being created:

auto hierarchy = create_hierarchy(match(), vertex_reducer(), edge_reducer(),
                        done(), pre_compute(), post_compute());

The resulting hierarchy can then be traversed level-by-level, using an index into the hierarchy:

auto graph_level_i = hierarchy[i];

results matching ""

    No results matching ""