Have an ordered inputs mechanism for graph

Today, a graph defines its inputs/outputs but with no particular order. Returned nodes are stored in a std::set. From a topological point of view, it is not always possible to define an order a priori.

However, graph manipulation will often require for the user to specify an order. For example, to map a sub-graph to another one for replacement. Or to define a meta-operator. A possible solution is to add a mechanism to specify an order for the inputs/outputs of a GraphView.

Preserve the (construction) order(?)

In fact, if we want to be possible for the user to define the order of inputs/outputs of the GraphView, I believe it would make sense to preserve that order when manipulating the graph without altering its inputs/outputs. But in this case, it may be expected by the user that trivial changes affecting inputs/outputs also preserve the order, like just adding a node at one input or output (that would just update the corresponding input or output node in the GraphView inputs/outputs list without reshuffling it).

Therefore, I think that an ordering mechanism should also preserve the defined order whenever possible. In order to do so, the only way is to have a mechanism preserving order when adding or removing nodes to the GraphView, which would imply to have in fact a default construction order!

I know this is difficult, but I may have a first implementation proposal ready soon. It may very well have important loopholes, but lets see... see !53 (merged)

Example:

%%{init: {'flowchart': { 'curve': 'monotoneY'}, 'fontFamily': 'Verdana' } }%%
flowchart TB

Fictive_1(Fictive0)
Fictive_2(Fictive6)
Fictive_3(Fictive8)
Fictive_4(Fictive9)
Fictive_5(Fictive4)
Fictive_6(Fictive3)
Fictive_7(Fictive1)
Fictive_8(Fictive7)
Fictive_9(Fictive2)
Fictive_10(Fictive5)
Fictive_1-->|0..0|Fictive_7
Fictive_1-->|0..1|Fictive_6
Fictive_1-->|1..0|Fictive_7
Fictive_1-->|1..2|Fictive_9
Fictive_2-->|0..0|Fictive_8
Fictive_3-->|0..0|Fictive_4
Fictive_3-->|1..0|Fictive_4
Fictive_5-->|0..1|Fictive_10
Fictive_5-->|0..2|Fictive_2
Fictive_6-->|0..1|Fictive_5
Fictive_6-->|0..0|Fictive_10
Fictive_6-->|0..1|Fictive_3
Fictive_7-->|0..0|Fictive_9
Fictive_7-->|0..0|Fictive_5
Fictive_8-->|0..0|Fictive_3
Fictive_9-->|0..1|Fictive_2
Fictive_9-->|1..0|Fictive_6
Fictive_10-->|0..0|Fictive_2
input0((in#0)):::inputCls-->|..0|Fictive_1
input1((in#1)):::inputCls-->|..1|Fictive_1
input2((in#2)):::inputCls-->|..2|Fictive_7
input3((in#3)):::inputCls-->|..3|Fictive_7
input4((in#4)):::inputCls-->|..1|Fictive_9
input5((in#5)):::inputCls-->|..2|Fictive_5
input6((in#6)):::inputCls-->|..2|Fictive_4
Fictive_1-->|1..|output0((out#0)):::outputCls
Fictive_4-->|0..|output1((out#1)):::outputCls
Fictive_4-->|1..|output2((out#2)):::outputCls
Fictive_3-->|1..|output3((out#3)):::outputCls
classDef inputCls fill:#afa
classDef outputCls fill:#ffa

Implementation proposal

Store a std::vector in GraphView:

std::vector<std::pair<NodePtr, IOIndex_t>> mOrderedInputs;
std::vector<std::pair<NodePtr, IOIndex_t>> mOrderedOutputs;

Example:

• Argument order = graph input order
• If an argument if a list => a GraphView input that goes to multiple nodes (@cmoineau as required for the Swift operator)

gv->setOrderedInputs({node1, 0}, {{node2, 0}, {node3, 1}});

Or, if nodes have name (failure if name is not unique):

gv->setOrderedInputs({"node1 name", "input name"}, {{node2, "input name"}, {"node3 name", 1}});

Or, if an unique ID could be defined for nodes (see issue #52 (closed))

gv->setOrderedInputs({1, 0}, {{2, 0}, {3, 1}});

Usage :

// Replace complexNode with gv, mapping input complexNode:0 to node1:0 and complexNode:1 to node2:0 AND node3:1
g->replace(complexNode, gv);

This example would work also for MetaOperator, since it stores internally a GraphView. This would eliminate the need to handle inputs ordering in the MetaOperator, as currently done.

Another example where there is no way of infering the order: the replacement of Mul+Add with FC. Mul inputs are commutative, but FC inputs are not, as its implementation may threat differently the input and the weights (as well as recipies acting on FC, like batch norm fuse). When trying to replace Mul+Add with FC, the user has to specify, at some point, which of the Mul input is the weights. This could be done by encapsulating the two operators in a GraphView, and specify an order with an argument of the recipy, that could have a default value.