lib/tsort.h

#ifndef __TSORT_H__
#define __TSORT_H__

#include <list>
#include <set>
#include <utility>
#include <iostream>
#include "stm_export.h"

namespace control {

// Simple topological sort.  Input is a set of edges, defined as pairs of
// integers.  For scheduling purposes the pair describes the flow of 
// information <from, to>.
bool STM_EXPORT topological_sort(const std::set<std::pair<int, int> > &edges,
                                 std::list<int> &order);

// calculate_schedule gives the set of nodes that can be scheduled right now
// given the set of completed jobs.
void STM_EXPORT calculate_schedule(const std::set<std::pair<int, int> > &edges,
                                   const std::set<int> &completed,
                                   std::set<int> &can_run);

// Follow edges to find all nodes that depend on a given set of nodes.  This 
// is used for marking things as dirty.
void STM_EXPORT find_descendants(const std::set<std::pair<int, int> > &edges,
                                 const std::set<int> &root,
                                 std::set<int> &out);

}

#endif

---