I have many (millions) of collider-less directed acyclic graphs (DAGs) (they're actually causal graphs, but that's unimportant for this question) I am using to model a process, and I would like to know if there is a complexity measure that is well-defined for any collider-less DAG, such that:
- More nodes in a straight chain $A\to B\to C\to D$ is more complex than a shorter chain $A\to B,$ by some reasonable factor: $2$ for this example, say.
- More forks $C\leftarrow A\to B$ is more complex than not having the forks $A\to B.$
- "Width" is about as complex as "depth". So I would expect a DAG like $C\leftarrow A\to B$ to be about as complex as $A\to B\to C.$
- A DAG having "width" and "depth" is more complex than a DAG having only "width" or only "depth": $E\leftarrow D\leftarrow A\to B\to C$ is more complex than $A\to B\to C\to D\to E$ or the graph with edges from $A$ to each of $B, C, D,$ and $E.$ This requirement, which is essential, obviously rules out a mere node count: the structure of the DAG needs to affect the complexity measure
- This measure of complexity must be relatively straight-forward to compute. I'm not interested in something research-only.
As I hinted in #4, there is no limit to the outdegree of a node; practically speaking, it's not usually going to be more than $50;$ the vast majority of the time it'll be more like $1$ or $2.$ The total node count in any of these DAGs is less than $2500.$ The indegree of any node is either $0$ or $1.$