What is the best way to handle "control flow" edges

[gmorenz]

I'm trying to use this to implement something similar to unreal engine's blueprints, where as well as data carrying edges I have edges indicating control flow.

The difference here is that instead of connections being one output -> many inputs, control flow connections are many outputs -> one input.

---

I currently see two paths forward, and I'm wondering if anyone has any input or alternative suggestions.

One path would be to just "do it backwards" - add some kind of interface to the drawing code that lets me have the control flow ports be drawn on the opposite sides of the node from normal ports, and in application code just deal with the fact that control moves from input to output.

The other would be modifying the graph's internal data structures to make all ports accept many connections, and make it configurable by datatype whether a port accepts many connections or only one (i.e. whether the UI treats a drag from a connected port as a disconnection or a new connection). This would mean something like changing Graph's connections: SecondaryMap<InputId, OutputId> into incoming: SecondaryMap<InputId, SVec<OutputId>>, outgoing: SecondaryMap<OutputId, SVec<InputId>>. It would obviously come at a cost for anyone not taking advantage of the extra capability (in both performance and complexity of the system), but I think the data is likely useful to many users. For a few other examples:

• It would allow remove_node to not do a scan over the entire connections vec to find edges pointing to the node.
• It would allow one -> one edges, useful for "move" like semantics.
• It would make What is the best way to find all final nodes ? #14 possible in a single scan over nodes and their outputs (looking at the outgoing map to check if any particular port has any connections). Though I suspect that code that frequently needs that information might still be better of maintaining a dedicated datastructure.

[gmorenz]

POC of the "let all ports accept many connections" proposal here: gmorenz@394eb21

Implementing and using this made me less sure it's the right idea - because there are many cases in the code where you access a node's ports knowing it has exactly one port despite getting back a list of ports.

That said - I still haven't thought of something that I think is better.

[setzer22]

Hey! Sorry I took so long to respond 😅

I completely agree this library needs something for many-to-many edges. There are several situations in which this can become useful, and doing it backwards as your first suggestion would not cover all use cases, so I'd say we should go with your second approach.

Your suggested proposal looks great at first glance! Would you be interested in contributing this in a PR? I've been quite busy lately but things are improving, so I'd make sure to take some time to review this 😄

About your comments on complexity: It's true that the previous version was simpler, but I also can't think of a better way to represent many-to-many edges. It's unfortunate that we need to keep the bidirectional mapping in sync (two sources of truth that we need to make sure are aligned at all times), but it seems you managed to wrap that into the main API. Users should not be modifying the incoming and outgoing maps directly unless they know what they're doing. All in all, I believe this increase in complexity is justified: I've been thinking about it for a while and the many-to-many use case is going to pop up sooner or later for most node graph applications.

[gmorenz]

Thanks for the response, no worries about taking your time :)

Having used this a bit more I'm much more convinced the second approach is the right one as well.

Will submit a PR shortly.