@Override
    public void addEdge(Edge<V, E> edge) {
      if (edge.s == this) {
        DagGraph.DagNode<V, E> t = (DagGraph.DagNode<V, E>) edge.t;
        ensureDagIdxAtLeast(t.dagIdx + 1);
        if (t.dagIdx > dagIdx) {
          throw new IllegalArgumentException("adding this edge would violate dag properties");
        }
      }
      super.addEdge(edge);
    }
A directed graph extended with support to check dag property.
ql/src/java/org/apache/hadoop/hive/ql/optimizer/graph/DagGraph.java