5
\$\begingroup\$

Calculating Graph Powers

(very similar to my other question asked here)


enter image description here

According to Wikipedia, "the \$k\$th power \$G^k\$ of an undirected graph \$G\$ is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in \$G\$ is at most \$k\$."


Challenge

Given a 2D Array (representing the graph \$G\$) where each inner array contains only non-negative integers and represents an edge, and an integer \$k\$, output the additional edges required to create the graph \$G^k\$.

Example Cases:

        Edge list                         k                   Possible answer

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

Notes:

  • Your program should account for every integer \$k > 1\$, but if \$k\$ is large, the graph will probably be complete long before the \$k\$th power is reached (citation). Thus, for a graph with diameter 6, the output should be the same for all \$k \geq\$ 6.

  • If the input graph is already complete, the program should terminate, but does not need to output anything.

  • Input can be a 2D array, or it can take multiple inputs of arrays (one for each edge). Output can be a 2D array, or it can STDOUT each edge individually.

  • Your program can have vertices 0 or 1 indexed, but please specify which.

  • Edges can be outputted in any order, and because the edges are undirected, [1,2] is the same as [2,1].

  • No, adjacency matrices (binary) are not allowed as input. Feel free to convert the edge list input format to an adjacency matrix in your code.


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

\$\endgroup\$
3
  • \$\begingroup\$ Can we take the number of vertices in the graph as an additional input? \$\endgroup\$
    – emanresu A
    Commented Jun 3 at 9:15
  • 1
    \$\begingroup\$ @Arnauld Sorry, clarified. Also, no, not all 2D arrays are adjacency matrices. \$\endgroup\$
    – SanguineL
    Commented Jun 3 at 13:05
  • \$\begingroup\$ @emanresuA If you are planning on inputting each edge individually, yes. \$\endgroup\$
    – SanguineL
    Commented Jun 3 at 13:10

5 Answers 5

2
\$\begingroup\$

JavaScript (ES10), 140 bytes

Expects (a)(n), where the edge list a is in the format used in the challenge. Prints the new edges.

a=>n=>a.flatMap(b=>a[b]=b).map(p=>(g=(k,v)=>k&&a.map(([x,y])=>x-v&&y-v||g(k-1,x^=y^v,a[P=[p,x]]||a[[x,p]]||p-x&&console.log(a[P]=P))))(n,p))

Try it online!

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

APL(Dyalog Unicode), 41 39 bytes SBCS

-2 bytes since ~x∨~y ←→ x<y

{⍸(∨\i)∧m<i∨.∧⍣⍺⍨m←∨∘⍉⍨1@⍵⊢i←∘.=⍨⍳⌈⌿∊⍵}

Try it on APLgolf!

A dfn that takes k as its left argument and the edges of a graph \$G\$ as its right argument, and outputs a list of edges that are in \$G^k\$ but not in \$G\$. It assumes the vertices come in 1 indexed.

Details

{⍸(∨\i)∧~m∨~i∨.∧⍣⍺⍨m←∨∘⍉⍨1@⍵⊢i←∘.=⍨⍳⌈⌿∊⍵}
                                    ⌈⌿∊⍵     number of nodes
                             i←∘.=⍨⍳         adjacency matrix of self loops
                   m←∨∘⍉⍨1@⍵⊢                adjacency matrix of G
            i∨.∧⍣⍺⍨                          adjacency matrix of ⍺th power of G
        ~m∨~                                   without edges in G
  (∨\i)∧                                       without edges (i j) such that i < j
 ⍸                                           list of edges in the adjacency matrix
\$\endgroup\$
1
  • \$\begingroup\$ Impressive! Love it! Thanks for the first answer! \$\endgroup\$
    – SanguineL
    Commented Jun 4 at 13:03
1
\$\begingroup\$

Charcoal, 48 bytes

F⊖ηF⁺θυFΦθ⁼¹L⁻λκ«≔⁺⁻κλ⁻λκζ≔⟦⌊ζ⌈ζ⟧ζ¿¬№⁺υθζ⊞υζ»⭆¹υ

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

F⊖η

Loop k-1 times.

F⁺θυ

Loop over all of the edges found so far. This is done because we're mutating the list of additional edges and we don't want to accidentally loop over an unseen edge.

FΦθ⁼¹L⁻λκ«

Loop over all of the original edges that share exactly one vertex with the current edge.

≔⁺⁻κλ⁻λκζ≔⟦⌊ζ⌈ζ⟧ζ

Calculate the new edge.

¿¬№⁺υθζ⊞υζ

If this edge is unseen then add it to the list of additional edges.

»⭆¹υ

Output the final list of additional edges.

\$\endgroup\$
1
\$\begingroup\$

Python 3, 101 bytes

f=lambda g,k:k and{v:k>0and f(g,1-k)[v]-g[v]-{v}or g[v].union(*map(f(g,1+k).get,g[v]))for v in g}or g

Try it online!

Takes input as a dictionary containing a set of edges for every vertex, and outputs in the same format.

\$\endgroup\$
1
\$\begingroup\$

Wolfram Language (Mathematica), 37 bytes

-2 bytes thanks to @att.

EdgeList[GraphPower@##~EdgeDelete~#]&

Try it online!

Of course there is a built-in for graph powers.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ GraphPower@## \$\endgroup\$
    – att
    Commented Jun 7 at 3:42

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.