Skip to content

GraphView inputs/outputs ordering

Olivier BICHLER requested to merge graphview_io_ordering into main

This MR pretty much solves issues #54 (closed) and #52 (closed).

What is in this MR?

  • GraphView has now ordered inputs and outputs, with a default ordering mechanism;
  • GraphView inputs and outputs order can be set by the user;
  • Simplified MetaOperator to use GraphView inputs/outputs ordering;
  • Added graph/Testing.hpp for random DAG generation;
  • Updated graph visualization (GraphView::save()).
  • Updated GraphView::replace() static member function to take ordering into account;

Properties

  • Stable inputs/outputs: when adding/removing nodes, the relative ordering of the remaining inputs/outputs is not altered.
    • If a node is added to an input or output of the GraphView, its own input/output replaces the previous one at the same position (see GraphView.cpp#839 and GraphView.cpp#908);
    • If a node is added to multiple input/output of the GraphView, its own input/output replaces the previous ones at the position of the first previous input/output (see GraphView.cpp#815 and GraphView.cpp#879);
    • If the added node creates new inputs/outputs, they are added after of the existing ones.
  • The default inputs/outputs ordering is independent of the nodes construction order, but depends on the order of addition to the GraphView. If a (unordered) set of nodes is added to the GraphView, a ranking algorithm is used to determine a default addition order (see GraphView.cpp#419). Ranking, and therefore inputs/outputs ordering, is unique if the following conditions are met:
    • A "root node", or "starting node", is defined OR there is only a single node without any parent in the graph;
    • There is no independent graph, i.e. a group of nodes forming a graph without any path to the starting node.

It is therefore possible, most of the cases, to construct a GraphView from a (unordered) set of nodes (i.e. add the set of nodes to a empty, newly constructed GraphView) with a deterministic and unique node ranking and inputs/outputs ordering for a given topoplogy.

Edited by Maxence Naud

Merge request reports

Loading