Modify DAG to improve ergonomics and robustness

[chubei]

Modify DAG to improve ergonomics and robustness

Motivation

Currently DAG is in fact a directed graph. In no way it checks if there's a cycle in the graph.

It also provides limited abstraction over the graph operations. Apart from the add_node, connect and merge method, it doesn't provide common graph operations such as topological order traversal, parent/child look up and traversal, etc.

Instead, it exposes its internal data structure to the user, pub nodes and pub edges, and expect the user to maintain its invariant when implementing common operations upon it. This is a leaky abstraction and can lead to bugs.

Ways to improve

• Use a graph library to implement cycle detection.
• Make nodes and edges private, and provide methods for needed operations.

Other ergonomics improvements

• Remove PortHandle. Instead, every node defines the number of its input/output ports and user connects using the port index.

It's extra mental burden to remember the port handle, and it doesn't provide any extra functionality over the port index.

• Panic when connect is called with invalid node/port.

If user tries to add an invalid edge, that's probably a bug instead of an error that the user wants to handle.

@snork-alt @v3g42 @mediuminvader what do you think?

[mediuminvader]

@chubei it makes sense, I have just a few questions:

1. have you already found a candidate library?
2. does it implement also the data structure or just the cycle detection logic?
3. should we check also output->input compatibility before connecting the nodes?

[chubei]

1. daggy is a good DAG library. I used it in https://github.com/chubei-oppen/async_dag.
2. It's a graph data structure + common operations.
3. From what I can see now, we are not able to check compatibility because we don't know the schemas yet when building the DAG.