scc_toposort.h

 
#ifndef BACKENDS_TOFINO_BF_P4C_COMMON_SCC_TOPOSORT_H_
#define BACKENDS_TOFINO_BF_P4C_COMMON_SCC_TOPOSORT_H_
 
#include <ostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
// SccTopoSorter is an opinionated non-boost implementation topological sort algorithm
// that supports directed graph with strongly connected components.
class SccTopoSorter {
 public:
    using Graph = std::unordered_map<int, std::unordered_set<int>>;
 
 private:
    int n_nodes_i = 0;
    Graph graph_i;
 
 public:
    int new_node();
 
    void add_dep(int a, int b);
 
    //
    //
    //
    std::unordered_map<int, int> scc_topo_sort() const;
 
 private:
    void validate_node_id(int i) const;
};
 
#endif /* BACKENDS_TOFINO_BF_P4C_COMMON_SCC_TOPOSORT_H_ */