20
\$\begingroup\$

What?

Let's say I have this graph:

   1
    \
     \
2     3
 \   /
  \ /
   4

I can represent it in 2 ways:

  1. A list of connected vertices. [[1,3],[2,4],[3,4]]
  2. A boolean matrix which shows where edges are:
c |1 2 3 4
--|-------
1 |0 0 1 0
2 |0 0 0 1
3 |1 0 0 1
4 |0 1 1 0
----- or -----
[[0,0,1,0],[0,0,0,1],[1,0,0,1],[0,1,1,0]]

Task

  • Your code should take input in the form of 1 (as a vertex list) and output it as 2 (as an adjacency matrix)
  • The graph is not directed (aka it is an undirected graph).
  • You can also accept input which is 0-indexed. For example: [[0,2],[1,3],[2,3]]
  • This is code golf, shortest answer wins.
  • You can also output 2 different values instead of 1 and 0.

Test cases

[[1,2],[3,4]] -> [[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0]]
[[1,3],[2,4],[3,4]] -> [[0,0,1,0],[0,0,0,1],[1,0,0,1],[0,1,1,0]]
[[1,2],[2,3],[5,6]] -> [[0,1,0,0,0,0],[1,0,1,0,0,0],[0,1,0,0,0,0],[0,0,0,0,0,0],[0,0,0,0,0,1],[0,0,0,0,1,0]]
[[1,2]] -> [[0,1],[1,0]]
[[1,2],[4,5]] -> [[0,1,0,0,0],[1,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1],[0,0,0,1,0]]
[[4,5]] -> [[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1],[0,0,0,1,0]]
[[4,5],[2,1]] -> [[0,1,0,0,0],[1,0,0,0,0],[0,0,0,0,0],[0,0,0,0,1],[0,0,0,1,0]]
\$\endgroup\$
6
  • \$\begingroup\$ Related: codegolf.stackexchange.com/q/240705/55372 (part of that challenge may be calculating adjacency matrix). \$\endgroup\$
    – pajonk
    Commented Mar 21, 2022 at 11:07
  • 1
    \$\begingroup\$ Is the number of vertices required to be the largest number occurred in the input? May I output a even larger matrix with 0 padded? For example, is [[1,2]] -> [[0,1,0],[1,0,0],[0,0,0]] valid? \$\endgroup\$
    – tsh
    Commented Mar 22, 2022 at 6:26
  • \$\begingroup\$ @tsh it is not valid as it implies that more verticies are present but not connected anywhere. \$\endgroup\$
    – zoomlogo
    Commented Mar 22, 2022 at 9:10
  • 1
    \$\begingroup\$ @JonathanAllan they might be present in any order. \$\endgroup\$
    – zoomlogo
    Commented Mar 22, 2022 at 9:11
  • \$\begingroup\$ Can we assume no self loop and no duplicated input? \$\endgroup\$
    – l4m2
    Commented Mar 22, 2022 at 23:31

12 Answers 12

10
\$\begingroup\$

APL (Dyalog Extended), 6 bytes

¯⍸⊢,⌽¨

Try it online!

When given an adjacency matrix, gives the edge list (indices of 1's). Therefore the inverse ¯⍸ solves this challenge when we add the reverse edges to the input list.

I used Extended here for the short syntax for inverse functions and because the inverse of doesn't require its input to be sorted.

\$\endgroup\$
2
  • \$\begingroup\$ wow this is short. \$\endgroup\$
    – zoomlogo
    Commented Mar 21, 2022 at 10:57
  • \$\begingroup\$ From some reason I.inv isn't defined in J, so it's much longer: (<:1:`[`]}0$~>./)@,|."1 \$\endgroup\$
    – Jonah
    Commented Mar 22, 2022 at 5:42
7
\$\begingroup\$

R, 46 43 bytes

Edit: -3 bytes thanks to pajonk

function(x,m=0*diag(max(x))){m[x]=1;m|t(m)}

Try it online!

Input is 2-column matrix with each row representing 2 connected vertices; output is matrix of TRUE and FALSE to indicate pairwise connections.

We could save 2 more bytes for 41 bytes by returning a matrix of falsy (zero) and truthy (either 1 or -1) to indicate connections.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ -3 bytes by using diag. \$\endgroup\$
    – pajonk
    Commented Mar 21, 2022 at 10:59
  • \$\begingroup\$ @pajonk - Thanks! That's a neat trick to get an empty matrix! \$\endgroup\$ Commented Mar 21, 2022 at 11:02
5
\$\begingroup\$

Jelly, 4 bytes

;UŒṬ

A monadic Link that accepts a list of pairs of positive integers (the vertex list) and yields a list of lists of 1s and 0s (the adjacency matrix).

Try it online! Or see the test-suite.

How?

;UŒṬ - Link: list of pairs of positive integers, V
 U   - reverse each pair in V
;    - V concatenate that
  ŒṬ - multi-dimensional array with 1s at those coordinates and 0s elsewhere
\$\endgroup\$
4
\$\begingroup\$

BQN, 38 16 bytes

Edit: -22 bytes thanks to a change-of-approach provoked by goading clever hint from ovs.

Edit2: changed + to (logical OR) so that if there are any vertices connected to themselves, which would appear on the output matrix diagonal, they are still represented as 1 and not 2; thanks to Neil for spotting this

+⟜⍉⊢∊˜·↕2⥊1+⌈´∘∾

Try it at BQN online REPL

Uses zero-indexed input.

The BQN Range () function has the behaviour: "if its argument is list of numbers, then it returns an array of list indices" (here).
So we just use to construct an array filled with indices, check whether each index is present in the input, and then combine the result with its transpose (to fill-in the elements corresponding to the same connections the other-way-around).

∨⟜⍉⊢∊˜·↕2⥊1+⌈´∘∾    # full train:
                ∾   # flatten the input connections,
             ⌈´∘    # get the maximum,
           1+       # add 1 (since 0-based indexing),
         2⥊         # duplicate it,
       ·↕           # and construct an array of 0-based 2d-coordinates;
      ˜             # now, for each 2d-coordinate,
    ⊢∊              # check if it's in the input (1) or not (0);
∨                   # finally, logical-OR the result
 ⟜⍉                 # with the transpose of itself

\$\endgroup\$
4
  • 1
    \$\begingroup\$ Applying ↕⌈´ to the input might give you an idea for a different approach (with 0-indexing) \$\endgroup\$
    – ovs
    Commented Mar 21, 2022 at 17:46
  • \$\begingroup\$ @ovs - thanks very much for the hint. Much nicer now. \$\endgroup\$ Commented Mar 22, 2022 at 9:15
  • \$\begingroup\$ This outputs 2 for elements on the diagonal, which doesn't seem allowed to me? \$\endgroup\$
    – Neil
    Commented Mar 22, 2022 at 10:47
  • \$\begingroup\$ @Neil - Thanks! I wasn't sure that that was a possible input, but an easy fix anyway that doesn't cost any bytes. \$\endgroup\$ Commented Mar 22, 2022 at 14:10
3
\$\begingroup\$

05AB1E, 14 bytes

Z©LãδQ.«~®ôDø~

The lack of builtins to check if a list is inside another list in 05AB1E is as always pretty dang annoying.. :/

Try it online or verify all test cases.

Explanation:

Z              # Push the flattened maximum of the (implicit) input
 ©             # Store it in variable `®` (without popping)
  L            # Pop and push a list in the range [1,®]
   ã           # Cartesian product to get all pairs of this list
    δ          # Apply double-vectorized with the input-pairs:
     Q         #  Check which pairs are equal
      .«       # Then reduce this list of lists by:
        ~      #  Bitwise-OR on the bits at the same positions
         ®ô    # Split this list into parts of size `®`
           D   # Duplicate this matrix of bits
            ø  # Zip/transpose; swapping rows/columns
             ~ # Bitwise-OR the bits at the same positions again
               # (after which the result is output implicitly)
\$\endgroup\$
3
\$\begingroup\$

Python 3, 90 88 87 86 bytes

thanks to @Kevin Cruijssen for pointing out my mistake

thanks to @ophact for saving 2 bytes

thanks to @loopy walt for saving 1 byte

thanks to @Jonathan Allan for saving 1 byte

lambda a:(r:=range(max(sum(a,[]))+1)and[[[i,j]in a or[j,i]in a for j in r]for i in r]

The input is a list of lists (as in the example).

85 84 83 bytes

thanks to @loopy walt for saving 1 byte

thanks to @Jonathan Allan for saving 1 byte

lambda a:(r:=range(max(sum(a,()))+1))and[[not{(i,j),(j,i)}&a for j in r]for i in r]

The input is a set of tuples.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ You need to check both directions, so both [i,j] and [j,i] should be in a - e.g. [i,j]in a should be [i,j]in a or[j,i]in a (there might be a shorter way to do this using zip perhaps). \$\endgroup\$ Commented Mar 21, 2022 at 10:45
  • 1
    \$\begingroup\$ You can remove the spaces between or and [ and between ] and in. \$\endgroup\$
    – ophact
    Commented Mar 21, 2022 at 11:01
  • 1
    \$\begingroup\$ max(sum(a,[])) saves a byte \$\endgroup\$
    – loopy walt
    Commented Mar 21, 2022 at 11:38
3
\$\begingroup\$

Mathematica 12, 15 bytes

AdjacencyMatrix

lol.

Mathematica can accept lists of tuples as edges in a graph, so

AdjacencyMatrix@{{1, 2}, {2, 3}, {3, 4}, {4, 1}}

produces

{{0, 1, 0, 1}, 
 {1, 0, 1, 0}, 
 {0, 1, 0, 1}, 
 {1, 0, 1, 0}}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Welcome to Code Golf, and nice answer! \$\endgroup\$ Commented Mar 22, 2022 at 22:56
  • 1
    \$\begingroup\$ You don't need the @*Graph part. Most graph functions work directly on lists of TwoWayRules, e.g. AdjacencyMatrix@{1 <-> 2, 3 <-> 4}. \$\endgroup\$
    – alephalpha
    Commented Mar 23, 2022 at 3:32
  • \$\begingroup\$ Ah, I didn't realize that the other graph functions did that too. I don't think TwoWayRules are valid input, and if you use tuples instead the function needs 1-indexing. \$\endgroup\$
    – Adam
    Commented Mar 23, 2022 at 18:03
  • \$\begingroup\$ i.e. AdjacencyMatrix@{0<->2,3<->4} works but AdjacencyMatrix@{{0,2},{3,4}} doesn't, and same goes for Graph \$\endgroup\$
    – Adam
    Commented Mar 23, 2022 at 18:13
2
\$\begingroup\$

Charcoal, 24 bytes

≔⊕⌈Eθ⌈ιηEη⭆η∨№θ⟦ιλ⟧№θ⟦λι

Try it online! Link is to verbose version of code. 0-indexed. Outputs the boolean matrix as a string array of 0 and 1s for convenience. Explanation:

≔⊕⌈Eθ⌈ιηEη

Calculate the size of the array.

⭆η∨№θ⟦ιλ⟧№θ⟦λι

For each cell of the array, check whether it or its transpose exists within the input list.

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

Factor + math.matrices, 75 bytes

[ 1 swap dup mmax 1 + dup 0 <matrix> [ matrix-set-nths ] keep dup flip m+ ]

enter image description here

Explanation

  • Create a square zero-matrix large enough to accommodate the maximum value in the input.
  • Set the (zero-indexed) input coordinates in the matrix to one.
  • Add the resulting matrix to its transpose.
                         ! { { 0 1 } }
1                        ! { { 0 1 } } 1
swap                     ! 1 { { 0 1 } }
dup                      ! 1 { { 0 1 } } { { 0 1 } }
mmax                     ! 1 { { 0 1 } } 1
1                        ! 1 { { 0 1 } } 1 1
+                        ! 1 { { 0 1 } } 2
dup                      ! 1 { { 0 1 } } 2 2
0                        ! 1 { { 0 1 } } 2 2 0
<matrix>                 ! 1 { { 0 1 } } { { 0 0 } { 0 0 } }
[ matrix-set-nths ] keep ! { { 0 1 } { 0 0 } }
dup                      ! { { 0 1 } { 0 0 } } { { 0 1 } { 0 0 } }
flip                     ! { { 0 1 } { 0 0 } } { { 0 0 } { 1 0 } }
m+                       ! { { 0 1 } { 1 0 } }
\$\endgroup\$
1
\$\begingroup\$

JavaScript (Node.js), 98 bytes

x=>[...Array(eval(`1+Math.max(${x})`))].map((_,i,t)=>t.map((_,j)=>x.some(v=>v==i+[,j]|v==j+[,i])))

Try it online!

:(

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

Haskell, 66 63 bytes

f x|r<-[1..maximum$id=<<x]=[[elem[i,j]x||elem[j,i]x|j<-r]|i<-r]

Try it online! Uses True and False for the output.

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

PDL (Perl Data Language) 81 chars (the second paragraph)

use PDL;
use PDL::NiceSlice;
$_ = [[1,3],[2,4],[3,4]];

$i=pdl($_)-1;
$m=zeroes("$_",$_)for$i->max+1;
$m->indexND($i->glue(1,$i(-1:0))).=1;

print $m;

Explanation per line:

  • construct indices ndarray, turn 1-based to 0-based
  • find highest index+1; make square matrix that size; "" is to coerce to Perl scalar not ndarray as zeroes with ndarray first arg copies its dimensions
  • $i(-1:0) reverses order of indices in 0th dimension, i.e. symmetrises; glue(1,...) adds rows; indexND selects the given elements; set them to 1
\$\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.