Get all unconnected inputs or outputs in a canonical order

[PanieriLorenzo]

Sorry if this is already possible, but I did not seem to find a documented way to do this.

Is there any way to iterate over all the unconnected inputs or outputs of the graph, in some predictable canonical order?

Furthermore, is the order stable across deletion of nodes or links? Say that a graph contains nodes A, B, C and I know that the inputs of A would be iterated over before the inputs of C. If I then delete B, am I guaranteed that the relative ordering of A's inputs and C's inputs are preserved?

I was developing my own implementation of port graphs before stumbling on this crate, and was thinking of abandoning my own crate to contribute to this one. I have already implemented this feature in my crate, so I would be happy to implement this feature myself.

[PanieriLorenzo]

A note on how I implemented this in my own crate: I keep an additional data structure called "free inputs", that keeps track of all ports that are not connected, providing a canonical order. Any operation that mutates the graph also has to update the list of free inputs to maintain the ordering. The main rules are that the relative order of ports must be preserved across deletions, and that the inputs of a new node added to the graph are placed after all existing inputs. This is not necessarily the best or most efficient implementation, just what made sense to me at the time.

The canonical order of free outputs in my crate is the order outputs are reached in a depth-first search starting from the first free input, then repeating the search in order from each of the inputs, skipping nodes that have been visited already by a previous DFS search on a previous input.

For context, I am using portgraphs for dataflow analysis of a programming language.

[aborgna-q]

Hi!

Is there any way to iterate over all the unconnected inputs or outputs of the graph, in some predictable canonical order?

(...) is the order stable across deletion of nodes or links?

We do not keep a list unconnected ports separate from the connected ones.
Internally, each node allocates a continuous range of PortIndices which we use to address two internal lists;

• port_link contains an efficient representation of an Option<PortIndex> that points to the neighbour when connected.
• port_meta stores the port's direction and NodeIndex

When a node or port is removed, we do not invalidate the other indices. Instead, we store a parallel linked list of "free ports indices" / "free node indices" that gets re-used when adding new nodes / ports. (We re-use the port_link entries to form a linked list of free port indices).
This is similar to petgraph's StableGraph, if you have used that before.

What this means is that

• To traverse the free ports you have to either traverse+filter all valid PortIndex.
• Or traverse all the existing nodes and for each of them, traverse/filter their ports.
  Both of these are stable under node/port deletion, but their order may change if you go through a serialization roundtrip or call compact_nodes / compact_ports manually.
  Also, new nodes/ports will re-use previously-deleted indices so they may be inserted in the middle of your order.

It may be more useful (depending on your usecase) to do an index-independant node traversal doing a topological sort of the nodes: toposort. This way you'll always get the nodes in the same order even if you have different indices. This will still have a runtime of $O(|V| + |P|)$ and will produce stable results even if you add the nodes of your graph in a different order.

If that doesn't work for you, I'd be happy to talk about adding a new implementation here (maybe as a wrapper over a Portgraph that implements all the traits?)

[PanieriLorenzo]

First off, thanks for the in-depth and thoughtful response.

The toposort solution sounds like it exhibits the most predictable behavior, however the linear time complexity could become an issue. I'll experiment with it for my use case, if I come up with some sort of wrapper with amortization over toposort, we could talk about adding it to the crate.

In case this is an XY problem, I'll include the broader context for this feature request. I am making a dataflow language, similar to a nodal language like blender's shader nodes, but textual. I have an operator that combines two graphs by connecting all outputs of the first graph pairwise with all inputs of the second graph, so to implement it, I first get the list of unconnected outputs of the first, and the unconnected inputs of the second, then I merge the two graphs and finally add all the missing links by zipping the two lists of ports.