Skip to content

[GraphView]: Add getOrderedNodes() method for topological order

Context

Add support for topological and deterministic ordering of a graph view nodes. Add option for topological order on the reverse graph (or post-dfs order).

Note that topological order on a cyclic graph is there defined as the order on a graph where cycles have been dropped.

For the cyclic case, in order to get a suitable walk for one pass interpretation of the graph, we add to operators the notion of back edges which are the input indexes which can be either dropped for node ordering, or ignored for interpretation over simple lattices such as in forwardDims (determination of tensor types and dimensions).

Note that one can still build a cyclic graph without specifying back edges and get a deterministic topological order. Though in this case there is no guarantee whether single pass interpretation over simple lattices may be possible.

Note that we can thus simplify forwardDims(), I may propose a further patch for this point.

Note that we can thus simplify onnx export, I may propose a further patch for this point.

Modified files

  • Operator.hpp: add support for specifying and testing back edges input indexes
  • Node.hpp: add support for testing is a parent index is a back edge
  • Memorize.cpp: this is a recurring operator, specify it's back edge index
  • GraphView.cpp: add getOrderedNodes() method
  • python bindings: add bindings

Detailed major modifications

Add back edges indexes set to operator.

TODO

nope

Merge request reports

Loading