Skip to content
Sebastian Jeckel edited this page May 24, 2014 · 2 revisions

Motivation

The Subtree engine is a hybrid approach of toposort and Sourceset.

TODO

Usage

The basic class template is SubtreeEngine<mode_tag>. The following modes are supported:

Mode tag Parallel updating Concurrent input Concurrent turns
parallel Yes No No
parallel_queue Yes Yes No

Details

Concept

The subtree engine combines sequential toposort with the initial graph marking phase of Pulsecount.

During the toposort phase, it tries to update as many lightweight nodes as possible. If it encounters a heavyweight node, it marks the subtree with the former as root. Nodes within a marked subtree are ignored in phase 1.

In phase 2, the Pulsecount algorithm is used to update the heavyweight subtrees.