12
\$\begingroup\$

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:

enter image description here

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:

enter image description here

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.

\$\endgroup\$
3
  • \$\begingroup\$ Can we make any assumptions about the connectivity of the input? (I haven't checked all of your test cases, but do they cover multiple disconnected parts of the graph?) \$\endgroup\$ Jul 31, 2016 at 8:53
  • \$\begingroup\$ updated with what I believe is the correct language. \$\endgroup\$ Jul 31, 2016 at 9:01
  • \$\begingroup\$ I guess that's fine. You could also say that the graph is weakly connected. \$\endgroup\$ Jul 31, 2016 at 11:11

4 Answers 4

5
\$\begingroup\$

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}}}
\$\endgroup\$
4
\$\begingroup\$

Mathematica, 95 82 bytes

13 bytes saved due to @MartinEnder.

#~IsomorphicGraphQ~TransitiveReductionGraph@#&@Graph[x=0;##&@@Thread[++x->#]&/@#]&

Anonymous function. Takes a nested list as (1-based) input, and returns True or False as output. The main solution here is the 46-byte #~IsomorphicGraphQ~TransitiveReductionGraph@#&, which tests if a given graph is isomorphic to its transitive reduction. The rest converts the input to a Graph object.

\$\endgroup\$
0
3
\$\begingroup\$

CJam (41 bytes)

q~:A_,{{Af=e__&}%_}*]:.|A.&A:$:e`e_2%1-*!

Online demo, test harness

Dissection

q~:A      e# Parse input and store in A
_,{       e# Loop V times
  {       e#   Extend adjacency list representation of G^i to G^(i+1)
    Af=   e#   by extending each path by one edge
    e__&  e#   and flattening. NB :| would be shorter but breaks for empty lists
  }%
  _       e#   Duplicate, so that we build up G^2, G^3, ..., G^n
}*]       e# Gather in a single array
:.|       e# Fold pointwise union, giving the reachability from each vertex by
          e# paths of length > 1
A.&       e# Pointwise intersect with the paths of length 1
          e# We hope to get an array of empty arrays

          e# Handle the awkward special case of duplicate edges:
A:$       e# Sort each adjacency list
:e`       e# Run-length encode each adjacency list
e_2%      e# Extract only the run lengths
1-        e# Discard the 1s - so we now have an empty array unless there's a dupe

*         e# Join. We hope to be joining an array of empty arrays by an empty array
          e# giving an empty array
!         e# Check that we get a falsy value (i.e. the empty array)
\$\endgroup\$
3
\$\begingroup\$

Jelly, 20 bytes

ị³$ÐĿ€ị@Fœ&¥";œ-Q$€E

Uses 1-based indexing. Try it online!

Loose Overview

     €                for each vertex,
ị³$ÐĿ                   compute its reach.
        Fœ&¥"         intersect each vertex's lists of children and
      ị@                children's reaches.
             ;        then concatenate the list of intersections with
              œ-Q$€     all duplicate edges in the original graph.
                   E  are all elements equal? checks that all are empty lists,
                        meaning empty intersections and no duplicates.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.