DependencyGraph.h

Go to the documentation of this file.

/* Copyright 2017-2020 CNRS-AIST JRL and CNRS-UM LIRMM */
 
#pragma once
 
#include <tvm/api.h>
 
#include <cstddef>
#include <cstdint>
#include <set>
#include <stack>
#include <vector>
 
namespace tvm::graph::internal
{
class TVM_DLLAPI DependencyGraph
{
public:
  size_t addNode();
  void removeNode(size_t id);
  bool addEdge(size_t from, size_t to);
  std::pair<std::vector<std::vector<size_t>>, DependencyGraph> reduce() const;
  std::vector<size_t> order() const;
  std::vector<std::vector<size_t>> groupedOrder() const;
  size_t size() const;
  const std::set<std::pair<size_t, size_t>> & edges() const;
  void clear();
 
private:
  class DisjointSet
  {
  public:
    DisjointSet() = default;
 
    DisjointSet(size_t n);
 
    void resize(size_t n);
 
    size_t root(size_t node) const;
 
    void unify(size_t node1, size_t node2);
 
    bool isRoot(size_t i) const;
 
  private:
    size_t rootCompr(size_t node);
 
    std::vector<size_t> parent_; // parent_[i] is the id of the parent of element i
    std::vector<size_t> rank_;   // rank of each element.
  };
 
  void SCCUtil(std::vector<std::vector<size_t>> & ret,
               size_t u,
               std::vector<int> & disc,
               std::vector<int> & low,
               std::stack<size_t> & st,
               std::vector<uint8_t> & stackMember,
               int & time) const;
 
  std::pair<std::vector<size_t>, DisjointSet> order_() const;
 
  void orderUtil(size_t v,
                 std::vector<size_t> & order,
                 std::vector<uint8_t> & visited,
                 std::vector<uint8_t> & stack,
                 DisjointSet & components) const;
 
  std::vector<uint8_t> roots_;                // roots_[i] is true iff the i-th node has no incoming edges
  std::vector<std::vector<size_t>> children_; // children_[i] lists all the children of node i
  std::set<std::pair<size_t, size_t>> edges_; // a list of edges (from, to)
};
} // namespace tvm::graph::internal