What is the best way to find all final nodes ?

[setzer22]

Discussed in https://github.com/setzer22/egui_node_graph/discussions/13

^{Originally posted by rsaccon February 25, 2022} I want to find all final nodes, which is all nodes which do not have out-going connection. I haven't found any in-built way at egui_node_graph to do this.

What I found is a way to find a connection based on the InputId, by using:

egui_node_graph::graph_impls::Graph
    pub fn connection(&self, input: InputId) -> Option<OutputId>

But with that approach, to find out for one specific node, whether it has no outgoing connections, I would have to iterate over all inputs of all nodes to query if they have a connection to that specific node, which is not very efficient. Is there a better way to do this ?

If there is no good way to do this yet, I suggest we add that capability to egui_node_graph by maintaining a list of final nodes (which needs to be adapted each time a connection gets added or removed).

[gmorenz]

#30 makes this a bit easier once it's merged.

You can now lookup the nodes outputs via graph.outgoing(output_id) to check if they are connected to anything. Which is more efficient (it should be O(nodes * output_ports)), but on large graphs might still be a bit too slow if you're searching for final nodes every frame or something.

The modified events mean that it's easier to maintain an efficient external (to the library) datastructure containing a list of final nodes - since the ConnectionAdded/Removed events will now always specify the output port, from which you can get the node with the output port, and then determine if you need to modify your your final nodes set by looking at only that nodes output ports (again via graph.outgoing(output_id)). If this paragraph isn't clear I'd be happy to write some example code.

@rsaccon you might be interested in the above.