The goal of this challenge is given a finite directed acyclic graph (DAG), determine if the graph is a transitive reduction.
A brief explanation of what a DAG and transitive reductions are:
A DAG is a graph with directed edges (i.e. you can only travel in one direction on that edge) such that given any starting node on the graph, it is impossible to return to the starting node (i.e. there are no cycles).
Given any starting node, if it is possible to travel to another ending node in the graph via any arbitrary positive number of edges, then that ending node is defined as reachable from the starting node. In a general DAG, there might be multiple paths which can be taken from a starting node to a target ending node. For example, take this diamond graph:
To get to node D from A, you could take the path A->B->D or A->C->D. Thus, D is reachable from A. However, there is no path which can be taken to get to node B starting from node C. Thus, node B is not reachable from node C.
Define the reachability of the graph as the list of reachable nodes for every starting node in the graph. So for the same example diamond graph, the reachability is:
A: [B, C, D]
B: [D]
C: [D]
D: []
Another graph which has the same reachability as the above graph is shown below:
However, this second graph has more edges than the original graph. The transitive reduction of a graph is a graph with the least number of edges and same reachability of the original graph. So the first graph is the transitive reduction of the second one.
For a finite DAG, the transitive reduction is guaranteed to exist and is unique.
Input
The input is a "list of lists", where the external list has the length of the number of vertices, and each internal list is the length of the number of edges leaving the associated node, and contains the indices of destination nodes. For example, one way to describe the first graph above would be (assuming zero based indexing):
[[1, 2], [3], [3], []]
You may begin indexing of the first node at any arbitrary integer value (e.g. 0 or 1 based indexing).
The input may come from any input source desired (stdio, function parameter, etc.). You are free to choose the exact input format as long as no additional information is given. For example, if you want to take input from stdio, you could have each line be a list of edges for the associated node. Ex.:
1 2
3
3
'' (blank line)
The indices in each adjacency list is not necessarily sorted, and there could be multiple edges connecting two nodes (ex.: [[1,1],[]]). You may assume the input graph is weakly connected, and contains no cycles (i.e. it is a DAG).
Output
The output is truthy if the given input DAG is a transitive reduction, and a falsy value otherwise. This may be to any sink desired (stdio, return value, output parameter, etc.)
Examples
All examples use 0-based indexing.
[[1,2],[3],[3],[]]
true
[[1,2,3],[3],[3],[]]
false
[[1,1],[]]
false
[[1,2,3,4],[5,6,7],[5,8,9],[6,8,10],[7,9,10],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
true
[[5,6,7],[2,3,0,4],[5,8,9],[6,8,10],[7,9,10],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
true
[[5,6,7],[2,3,0,4,14,5,7],[5,8,9],[6,8,10],[7,9,10],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
false
[[5,6,7],[2,3,0,4],[5,8,9],[6,8,10],[7,9,10,14],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
false
[[1,3],[2],[3],[]]
false
Scoring
This is code golf; smallest code in bytes wins. Your code should complete in a reasonable amount of time (10 minutes max on whatever hardware you have). Standard loopholes apply. You may use any built-ins desired.
