21
\$\begingroup\$

First attempt at a question.


Calculating Transitive Closure

According to Wikipedia, "the transitive closure \$R^*\$ of a homogeneous binary relation \$R\$ on a set \$X\$ is the smallest relation on \$X\$ that contains \$R\$ and is transitive."

Also, "a relation \$R\$ on a set \$X\$ is transitive if, for all \$x, y, z \in X\$, whenever \$x R y\$ and \$y R z\$ then \$x R z\$."

If that jargon did not make much sense, just remember the transitive law:

If \$a = b\$ and \$b = c\$, then \$a = c\$.

We can use this law for relations on sets.

Basically, transitive closure provides reachability information about a graph. If there is a path from \$a\$ to \$b\$ (\$a\$ "reaches" \$b\$), then in a transitively closed graph, \$a\$ would relate to \$b\$.

Here is another resource about transitive closure if you still do not fully understand the topic.


Challenge

Given a 2D Array (representing the graph \$R\$) where each inner array contains only positive integers and represents a vertex, determine the number of additional edges required to create the transitively closed graph \$R^*\$.


Here's an example (1-indexed):

[[2, 3], [3], [4], []]

And this would generate a graph that looks like this:

The first array is vertex 1, and it relates to vertices 2 and 3. Vertex 2 only relates to 3. Vertex 3 only relates to 4. Vertex 4 relates to nothing.

Let's take a look at the steps needed to make this graph transitively closed.

1R3 and 3R4, so 1R4       #You can reach 4 from 1, so 1 relates to 4
2R3 and 3R4, so 2R4       #Same goes for 2.

Thus, the correct answer to make this graph \$R^*\$ is 2.

This makes the graph look like this (it is transitively closed):


For completeness, here's what the transitively closed 2D array would look like (but this is not what your program should output):

[[2, 3, 4], [3, 4], [4], []]

Notes:

  1. There is an array for every vertex, but your code should be able to account for empty arrays (which means the vertex is originally not connected to any other vertex).

  2. I don't know if this is important, but you can assume the vertices listed in each inner array will be listed in increasing order.

  3. If vertex \$a\$ relates to vertex \$b\$ and vertex \$b\$ relates to vertex \$a\$, then vertex \$a\$ relates to vertex \$a\$ and vertex \$b\$ relates to vertex \$b\$ (Vertices can be related to themselves, it's called reflexive).

Picture of reflexive vertex.

  1. If the graph is already transitive, the program should output 0.

  2. You can use 1 or 0-indexing. Please just specify which.

  3. Many algorithms exist for determining transitive closure. If you'd like an added challenge, attempt this question without researching existing algorithms.


And yeah, that's pretty much it. Here are some test cases (1-indexed):

Input                                                           Output

[[], [], []]                                                    0
[[2], [1]]                                                      2
[[2], [1], []]                                                  2
[[2], [1, 3], []]                                               3
[[3], [], [2, 1], [3]]                                          5
[[2, 3, 4], [3, 4], [4], []]                                    0
[[2], [3], [4], [5], [6], [1]]                                  30

This question is tagged code-golf. Standard rules apply.

\$\endgroup\$
3
  • 4
    \$\begingroup\$ Nice first challenge btw! \$\endgroup\$
    – The Thonnu
    Commented Jul 31, 2023 at 14:25
  • \$\begingroup\$ How flexible is the input? Can we take it as an adjacency matrix (containing 0 and 1)? Or two numerical vectors indicating origin and end of edges? \$\endgroup\$
    – Luis Mendo
    Commented Jul 31, 2023 at 22:21
  • 1
    \$\begingroup\$ @LuisMendo While I want to be somewhat flexible for inputs (eg allowing Charcoal's JSON input), I do not want to allow an adjacency matrix as that is the standard approach for calculating transitive closure, and I know many algorithms using that format. So please, stick to the given input format. Thank you! \$\endgroup\$
    – SanguineL
    Commented Aug 1, 2023 at 4:37

13 Answers 13

6
\$\begingroup\$

05AB1E, 17 16 bytes

āεFè]øε˜ÙINèK}˜g

0-based indexing.

Try it online or verify all test cases or see what it does step-by-step.

Explanation:

ā           # Push a list in the range [1, (implicit) input-length]
 ε          # Map over each value:
  F         #  Loop that many times:
   è        #   Index the inner-most values of the current list into the (implicit)
            #   input-list,
            #   which will use the (implicit) input-list in the first iteration
 ]          # Close both the loop and map
  ø         # Zip/transpose; swapping rows/columns
   ε        # Map over each inner nested list:
    ˜       #  Flatten it
     Ù      #  Uniquify its values
      INè   #  Push the map-index'th list of the input
         K  #  Remove those values from the current list
   }˜       # After the map: flatten it to get all additionally created connections
     g      # Pop and push the length
            # (after which this amount is output implicitly as result)

Initially I used .Γè} instead of āεFè], and although it worked for the example test case, it didn't for any test cases that have reflexive vertices (like test case [[1],[0]] for example). Hence the use of āεFè] to loop a fixed amount of times based on the amount of input-vertices.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Love the step-by-step program! \$\endgroup\$
    – SanguineL
    Commented Jul 31, 2023 at 14:24
  • \$\begingroup\$ @SanguineL: standard form for these otherwise completely unreadable languages \$\endgroup\$
    – Joshua
    Commented Aug 3, 2023 at 17:18
  • \$\begingroup\$ @Joshua Actually, the step-by-step TIO-link OP is referring to I usually don't add. Only once in a while, when I think it's beneficial to explain some of the intermediate steps. The explanation on the other hand I always add, even if the program is just a single byte and pretty self-explanatory. :) \$\endgroup\$ Commented Aug 3, 2023 at 18:08
6
\$\begingroup\$

Itr, 11 bytes (non competing)

#µÍ®ääe*¿<S

Reads zero-indexed array from standard input, prints the solution to standard output

online interpreter

Explanation

The solution is based on the observation that an entry i,j of the k-th power of the adjacency matrix of a graph taken is nonzero iff there is a walk of length k in the graph connecting the vertices i and j. So the adjacency matrix of the transitive closure has ones in all entries that are non-zero in at least one positive power of the adjacency matrix of the original graph.

#             ; read the array from standard input
 µÍ®          ; compute adjacency matrix of graph
 µ            ; apply to all elements
  Í           ; convert array to array with ones at the indices given by the values of the array
   ®          ; convert nested array to matrix
    ää        ; duplicate matrix twice
      e       ; compute matrix exponential (sum of all powers of matrix)
       *      ; multiply with original matrix (sum of all positive powers of matrix)
        ¿     ; replace all non-zero entries with one
         <    ; point-wise comparison keeps only the entries that appear in A*e^A but not in A 
          S   ; sum up all entries (as all entries are zero or one, this give the number of nonzero entries)
              ; solution is implicitly printed

Disclaimer

This language was created after I saw the sandbox version of this challenge. While the general consensus seems to be that new languages without built-ins designed specifically for a challenge are allowed, I will still mark this solution as non-competing as this challenge heavily influenced the design process (for instance built-in matrix operations and the Í operator were introduced to simplify writing this solution)


Itr, 12 bytes (no floating point operations)

#µÍ®äL¹^S¿<S

L¹^S directly computes the sum of the first n powers

  ^  ; the matrix to the power of
L¹   ; the range from 1 to the number of rows (does not consume the array)
   S ; sum up all results (taking to the power of a vector will give a vector containing all the powers)
\$\endgroup\$
1
  • \$\begingroup\$ Great answer! Thank you for clarifying zero-indexed! \$\endgroup\$
    – SanguineL
    Commented Jul 31, 2023 at 13:27
5
\$\begingroup\$

JavaScript (ES6), 74 bytes

Uses 0-based indexing. Returns false for 0.

f=a=>a.some(b=>b.some(i=>a[i].some(v=>!b.includes(v)&&b.push(v))))&&1+f(a)

Try it online!

How?

We look for some sub-list b in the main list a and some i in b such that there's at least one value v in the sub-list a[i] that does not yet exist in b. If v is found, we add it to b and increment the final result. This process is repeated until there's nothing to update anymore.

Commented

f =                  // f is a recursive function taking ...
a =>                 // ... the main list a[]
a.some(b =>          // for each sub-list b[] in a[]:
  b.some(i =>        //   for each value i in b[]:
    a[i].some(v =>   //     for each value v in a[i]:
      !b.includes(v) //       if v is not already in b[],
      && b.push(v)   //       append v to b[] and trigger all some()'s
    )                //     end of some()
  )                  //   end of some()
)                    // end of some()
&& 1 +               // if truthy, increment the final result
f(a)                 // and do a recursive call with the updated list
\$\endgroup\$
3
\$\begingroup\$

Pyth, 12 bytes

ls-Vum{sam@G

Try it online!

Takes zero-indexed input.

Explanation

This may be the most implicitly added variables I've ever had in a Pyth golf.

ls-Vum{sam@GkddGQQ    # implicitly add kddGQQ
                      # implicitly assign Q = eval(input())
    u           Q     # find fixed point, repeatedly apply lambda G, H to the previous value, iteration number until we get a result that has occurred before, begin with Q
     m         G      #   map lambda d over G
         m   d        #     map lambda k over d
          @Gk         #       value of G at index k
        a     d       #     append d
       s              #     flatten
      {               #     deduplicate
  -V             Q    # remove any elements originally present in Q, vectorized
 s                    # flatten
l                     # output the length
\$\endgroup\$
3
\$\begingroup\$

Jelly, 13 bytes

;ịFQʋ€ÐLḟ"⁸FL

A monadic Link that accepts \$R\$ as a one-indexed adjacency list and yields the required number of edges to add to make a transitive closure, \$R*\$, containing \$R\$.

Try it online! Or see the test-suite.

How?

Repeatedly add edges that do not yet exist for all traversable pairs of edges, then count the number of new edges.

;ịFQʋ€ÐLḟ"⁸FL - Link: adjacency list, A
      ÐL      - start with X=A and loop until a fixed point applying:
     €        -   for each {node in X}:
    ʋ         -     last four links as a dyad - F(node, X)
 ị            -       {node} index into {X} (vectorises)
;             -       {node} concatenate {that}
  F           -       flatten
   Q          -       deduplicate -> updated node
          ⁸   - chain's left argument -> A
         "    - zip with:
        ḟ     -   {final node} filter discard {original node from A}
           F  - flatten
            L - length

The end, ḟ"⁸FL, seems long, is there something better than this or ;ịFQʋ€ÐLn>0SS etc.?

\$\endgroup\$
3
  • \$\begingroup\$ Great! 1-indexed! Love it :D \$\endgroup\$
    – SanguineL
    Commented Jul 31, 2023 at 16:49
  • \$\begingroup\$ Yeah, let's rid the world of its obsession with using address offsets in place of indices! Jelly uses 1-indexing by default, and also modularity in many places, so 0 is the rightmost etc. which can be useful for golf (but sometimes impedes :p). \$\endgroup\$ Commented Jul 31, 2023 at 16:56
  • \$\begingroup\$ I usually prefer 0-indexing, but I believed that using 1 instead would make the concept of transitive closure easier to understand. Also, I wasn't expecting Jelly to be 1-indexed by default since its official interpreter is in Python. \$\endgroup\$
    – SanguineL
    Commented Jul 31, 2023 at 17:09
3
\$\begingroup\$

Python 3.8, 110 bytes

f=lambda a,o=0,c=0:a!=(m:=[[*(s:={*sum([a[i]for i in n],n)},c:=c+len(s-{*n}))[0]]for n in a])and c+f(m,o or a)

A recursive function that accepts the adjacency list, a, and returns the number of required edges (with False quacking like 0).

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python3, 240 bytes:

E=enumerate
T=lambda K,g:[(v,l)for i,v in E(K)for _,l in E(K[i+1:])if l not in g[v-1]]
def e(g,n,c=[]):
 for i in g[n-1]:
  yield from T(c+[n,i],g)
  if i not in c:yield from e(g,i,c+[n])
f=lambda g:len({j for i,_ in E(g)for j in e(g,i+1)})

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 18 bytes

FθFιF⁻§θκι«⊞ιλ→»Iⅈ

Try it online! Link is to verbose version of code. 0-indexed. Explanation:

Fθ

Loop over each vertex.

Fι

Loop over the list of target indices for this vertex. Note that this list can be extended by the innermost loop in which case the additional indices will also be considered.

F⁻§θκι«

Loop over the list of target indices for the target vertex, but exclude indices already present in the list of target indices for the source vertex.

⊞ιλ

Add this index to the list of target indices for the source vertex.

Increment a counter.

»Iⅈ

Output the final count.

Bonus: Reflexive closure, 8 bytes:

IΣEθ¬№ικ

Try it online! Link is to verbose version of code.

Bonus 2: Symmetric closure, 14 bytes:

IΣEθ↨¹Eι¬№§θλκ

Try it online! Link is to verbose version of code.

\$\endgroup\$
3
  • \$\begingroup\$ Your script functions properly if the input is within an additional array (e.g. [[[1], [0]]] instead of [[1], [0]]). Is there a chance that removing the additional array from the input could save a byte or two? \$\endgroup\$
    – SanguineL
    Commented Jul 31, 2023 at 16:47
  • \$\begingroup\$ Also, Ha! I thought about doing questions for reflexive and symmetric closure, but I knew they were more simple to compute. Thanks for sharing those anyway! \$\endgroup\$
    – SanguineL
    Commented Jul 31, 2023 at 17:14
  • 1
    \$\begingroup\$ @SanguineL The additional array is actually part of Charcoal's JSON-like input format; it allows for the provision of an arbitrary number of inputs, although here obviously I only need the one. \$\endgroup\$
    – Neil
    Commented Jul 31, 2023 at 17:17
2
\$\begingroup\$

Nekomata + -n, 16 bytes

~ᵉ{$#ᵑ{ˣ@j,u}}∕~

Attempt This Online!

\$\endgroup\$
2
\$\begingroup\$

Scala, 102 bytes

Port of @CursorCoercer's Python answer in Scala.


Golfed version. Try it online!

a=>{var(m,s)=(Set[Int](),0);for(n<-a){m=n.toSet;for(_<-a;g<-m){a(g).foreach(m+=_)};m--=n;s+=m.size};s}

Ungolfed version. Try it online!

object Main extends App {
  def f(a: List[List[Int]]): Int = {
    var m = Set[Int]()
    var s = 0
    for (n <- a) {
      m = n.toSet
      for (_ <- a; g <- m) {
        a(g).foreach(m += _)
      }
      m --= n
      s += m.size
    }
    s
  }

  val tests = List(
    List(List(), List(), List()),
    List(List(2), List(1)),
    List(List(2), List(1), List()),
    List(List(2), List(1, 3), List()),
    List(List(3), List(), List(2, 1), List(3)),
    List(List(2, 3, 4), List(3, 4), List(4), List()),
    List(List(2), List(3), List(4), List(5), List(6), List(1))
  )

  tests.foreach(test => {
    val test0 = test.map(n => n.map(_ - 1))
    println(s"$test => ${f(test0)}")
  })
}

\$\endgroup\$
2
\$\begingroup\$

MATL, 18 bytes

Fi"TX@@g&(]tYezwz-

The input is a cell array of numerical vectors, 1-based. Try it online! Or verify all test cases.

Explanation

The first 11 bytes are used for computing the adjacency matrix from the specified input format. The rest of the code is essentially comparing the matrix before and after matrix exponentiation.

F       % Push false, that is, a 1x1 logical matrix containing false
i       % Push input: cell array of numerical vectors
"       % For each entry in the cell array
  T     %   Push true (*)
  X@    %   Push current iteration index, starting at 1 (**)
  @g    %   Push current numerical vector (***)
  &(    %   Write true (*) at specified row (**) and column indieces (***)
        %   in the logical matrix. This may increase the matrix size
]       % End. The stack now contains the adjacency matrix
t       % Duplicate adjacency matrix
Ye      % Compute the logical version of the adjacency matrix of the power
        % of the graph with increasing exponent until the result no longer
        % This is the same as logical(M*expm(M)), where M is the original
        % adjacency matrix and expm is matrix exponeitial, but numerical
        % precision issues are avoided
z       % Number of nonzeros
w       % Swap. Moves copy of original adjacency matrix to top
z       % Number of nonzeros
-       % Subtract. Implicit display
\$\endgroup\$
2
\$\begingroup\$

Python 3.8, 84 bytes

lambda a:sum(len((m:={*n},[m:=m|{*a[g]}for f in a for g in m])and m-{*n})for n in a)

Try it online!

Takes 0-indexed input. Essentially a port of my Pyth answer with some swapping of loop order.

\$\endgroup\$
2
\$\begingroup\$

J, 36 bytes

[:+/@,@((+/ .*+.])^:_~-])<@i.@#e.&>]

Try it online!

Uses 0 indexing.

  • <@i.@#e.&>] Convert adjacency list to adjacency matrix
  • (+/ .*+.])^:_~ Take transitive closure of matrix multiplication, but any cell that becomes 1 also remains 1 +.].
  • -] Subtract original adj matrix
  • +/@,@ Count the ones
\$\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.