GraphView inputs/outputs ordering
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