11
\$\begingroup\$

Background

A little while ago, someone posted an interesting puzzle on Math.SE:

What is the smallest digraph (directed graph) G where the following eight graphs are all distinct:

  • G, the original graph
  • Reflexive closure of G
  • Symmetric closure of G
  • Transitive closure of G
  • Reflexive symmetric closure of G
  • Symmetric transitive closure of G
  • Reflexive transitive closure of G
  • Reflexive symmetric transitive closure of G

A quick refresher on the terminology:

  • A reflexive graph satisfies: for every vertex X of G, the edge (X,X) is present in G.
  • A symmetric graph satisfies: for every pair of vertices X and Y of G, if the edge (X,Y) is present in G, the edge (Y,X) is also present.
  • A transitive graph satisfies: for every triple of vertices X, Y, and Z of G, if the edges (X,Y) and (Y,Z) are present in G, the edge (X,Z) is also present.
  • A reflexive/symmetric/transitive closure of G is the smallest superset of G that satisfies the given property. Note that, for example, symmetric transitive closure is not equal to symmetric closure of transitive closure in general.

For example, the following (from the original Math.SE post) shows an example graph that satisfies the original question:

Challenge

Given a digraph G, determine if it satisfies the above puzzle (G and its seven closures are all distinct).

The input digraph G can be represented in any reasonable way: adjacency matrix, adjacency list, flat lists of vertices and edges, etc. Since the answer is always false when isolated vertices are not allowed, the representation must include some representation of the list of vertices.

For output, you can choose to

  1. output truthy/falsy using your language's convention (swapping is allowed), or
  2. use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

The shortest code in bytes wins.

Test cases

Truthy

# the example in the image
vertices: [1, 2, 3, 4, 5, 6]
edges: [[1, 2], [2, 3], [3, 4], [4, 2], [4, 5]]
adjacency matrix:
[[0, 1, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0],
 [0, 0, 0, 1, 0, 0],
 [0, 1, 0, 0, 1, 0],
 [0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0]]

# the smallest answer in Math.SE
vertices: [1, 2, 3, 4]
edges: [[1, 2], [2, 3]]
adjacency matrix:
[[0, 1, 0, 0],
 [0, 0, 1, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 0]]

Falsy

# the incorrect answer in Math.SE
vertices: [1, 2, 3]
edges: [[1, 2], [2, 3]]
adjacency matrix:
[[0, 1, 0],
 [0, 0, 1],
 [0, 0, 0]]

# a modification of 4-vertex correct answer, ST=RST
vertices: [1, 2, 3, 4]
edges: [[1, 2], [2, 3], [4, 4]]
adjacency matrix:
[[0, 1, 0, 0],
 [0, 0, 1, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 1]]
\$\endgroup\$
3
  • \$\begingroup\$ Do you have an example of symmetric transitive closure is not equal to symmetric closure of transitive closure? \$\endgroup\$
    – Neil
    Jan 22 at 11:05
  • \$\begingroup\$ @Neil a -> b <- c's symmetric closure of its transitive closure (which is still the original) is a <-> b <-> c, while the symmetric transitive closure is its complete graph with e.g. a <-> c. \$\endgroup\$
    – xash
    Jan 22 at 11:32
  • \$\begingroup\$ @xash Thanks that's a great clarification. \$\endgroup\$
    – Neil
    Jan 22 at 11:36
8
\$\begingroup\$

J, 71 58 bytes

Takes in the adjacency matrix.

*/@~:@(,([+./@,#)"#/~^:_"2)@(,s@r,(s=:+.|:),:r=:[+.=@i.@#)

Try it online!

How it works

First the original, s, r and r->s variants are computed, then all their transitive closures. Albeit the operations are not commutative, I believe calculating the transitive closure last will work here (r->t is equal to r->t->r as r just adds the diagonal, which was already set. s->t is equal to s->t->s as every transition was already symmetric. s->r is equal to r->s as every reflexion is symmetric.) Though this might be wrong, and if it is, I'm happy to slap some ^:_ on there. :-)

  • r=:+.=@i.@#: original matrix OR the diagonal =@i.@#.
  • s=:+.|:: original matrix OR its transposition |:.
  • ,s@r,s,:r: original matrix and all its variants in a list.
  • ([+./@,#)"#/~^:_"2: until the result does not change ^:_: for every node: take the neighboring rows #, append them to the current row [ , and OR them together +./.
  • */@~:: ~: returns whether each element of the list is unique, then AND */ those booleans.
\$\endgroup\$
5
\$\begingroup\$

Jelly, 31 29 27 26 25 24 bytes

,|Z$æ*ⱮLS,Ʋ€Ẏæ*0|,Ʋ€Ẏ¬QƑ

Try it online! (comes with a test harness that runs all test inputs)

Takes the adjacency matrix and returns 1 or 0.

I'm very rusty in code golf (especially in Jelly) and this solution tries to stay very safe regarding the specification, so there is very likely room for improvement. (Edit 7 bytes later: yes, there was. For example, just found out about Ƒ when re-reading the docs.)

Explanation

  1. The main link gets the adjacency matrix.
  2. Z transposes the matrix and | bitwise-ORs it with the original. This gives the symmetric closure. , makes the pair [orig, SC].
  3. does the following for each of the two matrices:
    1. L finds the edge length N of the matrix. æ*Ɱ raises the matrix to each power 1…N to find routes of length 1 to N. S sums the resulting matrices together to find all routes. This gives the transitive closure, but the matrix can have values greater than one. , makes the pair [TC, orig].
  4. flattens the outermost array, giving [TC, orig, STC, SC].
  5. does the following for each of the four matrices:
    1. æ*0 gets the zeroth matrix power, i.e. the identity matrix. | bitwise-ORs it with the previous matrix, giving the reflexive closure. , makes the pair [RC, orig].
  6. flattens the outermost array, giving [RTC, TC, RC, orig, RSTC, STC, RSC, SC].
  7. ¬ logical-NOTs all values in the matrices to turn 0 into 1 and anything else into 0. This makes all nonzero values equal.
  8. Q removes duplicates from that list and Ƒ sees if it stayed the same.

Correctness

The order of operations here is important. The transitive closure must be performed after the symmetric closure, but the reflexive closure can be performed at any point. I'll try to give a (very hand-wavy) proof of my algorithm's correctness.

For any path A1→…→An in SC(G), An→…→A1 will also exist, and thus TC(SC(G)) will be symmetric. SC(G) must be a subset of STC(G) (all "new edges" of SC(G) must also be in STC(G)) and TC(SC(G)) is the minimal transitive superset of SC(G). Thus TC(SC(G)) = STC(G).

RC(STC(G)) is always symmetric and transitive, since the edges added by RC will never break transitivity or symmetricity. STC(G) must be a subset of RSTC(G) (all "new edges" of STC(G) must also be in RSTC(G)) and RC(STC(G)) is the minimal reflexive superset of STC(G), so RC(STC(G)) = RSTC(G).1

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You can golf "symmetricity" to "symmetry". \$\endgroup\$
    – Neil
    Jan 26 at 19:54
4
\$\begingroup\$

Charcoal, 66 bytes

⊞υθ⊞υEθEι∨맧θμκF⮌υ⊞υEιEκ∨μ⁼νλFEυEιλ«FθUMιEλ∨ν⊙λ∧π§§ιρξ⊞υι»⬤υ⁼¹№υι

Try it online! Link is to verbose version of code. Takes input as an adjacency matrix. Explanation: Port of @xash's answer.

⊞υθ

Push the input to the predefined empty list.

⊞υEθEι∨맧θμκ

Logical Or the input with its transpose and push it to the list.

F⮌υ⊞υEιEκ∨μ⁼νλ

For each matrix in the (reversed) list, logical Or it with the identity matrix and push the result to the list. (The list is reversed because otherwise the For command will attempt to iterate over the new results.)

FEυEιλ«

For each shallow cloned matrix in the list...

Fθ

... for as many times as the size of the matrix...

UMιEλ∨ν⊙λ∧π§§ιρξ

... logical Or the matrix with its square, and...

⊞υι

... push the final result to the list.

»⬤υ⁼¹№υι

Check that all of the matrices are unique.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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