Is the DAG a transitive reduction?

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:

Is the DAG a transitive reduction?

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:

Is the DAG a transitive reduction?

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 has no disconnected components.

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 

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.

Replay

Ruby, 101 97 bytes

Simple approach that calculates the reach from each node and considers if a child node can be reached via any of the other nodes. Seemingly fails on cyclic graphs, but the definition of a DAG implies that it shouldn't be cyclic anyways.

Try it online!

->g{r=->i{i|i.map{|j|r[g[j]||[]]}.inject([],:|)}
g.all?{|e|e==e&e&&e.none?{|i|r[e-[i]].index i}}}

Category: code golf Time: 2016-07-31 Views: 2

Related post

iOS development

Android development

Python development

JAVA development

Development language

PHP development

Ruby development

search

Front-end development

Database

development tools

Open Platform

Javascript development

.NET development

cloud computing

server

Copyright (C) avrocks.com, All Rights Reserved.

processed in 0.216 (s). 12 q(s)