Add a unique nodes ordering in a graph

This is a proposal to add a well-specified and unique nodes ordering method in a graph (inputs ordering for a given node is already present).

One of the objective is to define a consistant and unique node inputs ordering for any sub-graph. This would allow for example to canonically handle the connections ordering for matching sub-graphs. General topological sorting algorithms garantees uniqueness only for a DAG forming a Hamiltonian path (i.e. no parallel branch). However, in our case, I thing this could be extended to any Aidge graph because 1) inputs (and outputs) are ordered, meaning parallel branches can be ordered and 2) cycles in the graph should only exist through a specific statefull operator making cycle easily breakable from the point of view of topological sorting.

Advantages:

• Do not rely on user's construction order;
• Is consistant also for generated graphs;
• Possibility to automatically generate meaningful and even predictable unique names for the nodes.

Implementation proposal

Each node stores an ID that can be set within a set of nodes (or a GraphView) by the ordering method (Q: store the ID internally in each node or in a separate structure?). Then, a getSortedInputs() method allows to get the GraphView inputs by correct order. This method may be implemented with std::sort() on a pair of node ID and input ID with a custom compare function.

We could use the Longest-Path algorithm or the Coffman–Graham algorithm for the ordering method. Nodes at identical level would then be ordered by highest child level and, if not enough, childs input ranking (for example), in order to garantee uniqueness.

⚠ How to handle graph with multiple output nodes? => no way to define a proper order without additionnal information. The ordering method should therefore take only one final (output) node as argument.

Examples of automatic connections mapping deduction

In these examples, the inputs are ordered and mapping between topologies can be made by connecting inputs of identical rank.

PaddedConv meta-op

flowchart LR
    I{"I [1]"} -->|1| Pad("Pad [2]")
    Pad --> Conv("Conv [5]")
    W{"W [3]"} -->|2| Conv
    B{"B [4]"} -->|3| Conv

↔

flowchart LR
    I{"I [1]"} -->|1| PaddedConv("PaddedConv [4]")
    W{"W [2]"} -->|2| PaddedConv
    B{"B [3]"} -->|3| PaddedConv

FC equivalence

⚠ This is typically a wrong example, where unique node ordering would not solve the graph inputs ordering problem! See issue #54 (closed).

flowchart LR
    I{"I [1]"} -->|1| Mul("Mul [3]")
    W{"W [2]"} -->|2| Mul
    Mul --> Add("Add [5]")
    B{"B [4]"} -->|3| Add

↔

flowchart LR
    I -->|"[1].1 = 1"| Mul("Mul [1]")
    W -->|"[1].2 = 2"| Mul
    B -->|"[2].1 = 3"| Add("Add [2]")
    Mul -->|"[2].2 = 4"| Add

↔ (for the FC operator, the role of I and W should be symmetrical!)

flowchart LR
    W -->|"[1].1 = 1"| Mul("Mul [1]")
    I -->|"[1].2 = 2"| Mul
    B -->|"[2].2 = 3"| Add("Add [2]")
    Mul -->|"[2].1 = 4"| Add

↔

flowchart LR
    I -->|"[1].1 = 1"| FC("FC [1]")
    W -->|"[1].2 = 2"| FC
    B -->|"[1].3 = 3"| FC