# Convert between graph representations

## 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]]


• 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]]

• Related: codegolf.stackexchange.com/q/240705/55372 (part of that challenge may be calculating adjacency matrix). Commented Mar 21, 2022 at 11:07
• 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?
– tsh
Commented Mar 22, 2022 at 6:26
• @tsh it is not valid as it implies that more verticies are present but not connected anywhere. Commented Mar 22, 2022 at 9:10
• @JonathanAllan they might be present in any order. Commented Mar 22, 2022 at 9:11
• Can we assume no self loop and no duplicated input?
– l4m2
Commented Mar 22, 2022 at 23:31

# 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.

• wow this is short. Commented Mar 21, 2022 at 10:57
• From some reason I.inv isn't defined in J, so it's much longer: (<:1:[]}0$~>./)@,|."1 Commented Mar 22, 2022 at 5:42 # 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. • -3 bytes by using diag. Commented Mar 21, 2022 at 10:59 • @pajonk - Thanks! That's a neat trick to get an empty matrix! Commented Mar 21, 2022 at 11:02 # 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  # 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  • Applying ↕⌈´ to the input might give you an idea for a different approach (with 0-indexing) – ovs Commented Mar 21, 2022 at 17:46 • @ovs - thanks very much for the hint. Much nicer now. Commented Mar 22, 2022 at 9:15 • This outputs 2 for elements on the diagonal, which doesn't seem allowed to me? – Neil Commented Mar 22, 2022 at 10:47 • @Neil - Thanks! I wasn't sure that that was a possible input, but an easy fix anyway that doesn't cost any bytes. Commented Mar 22, 2022 at 14:10 # 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.. :/ 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)  # Python 3, 908887 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). # 8584 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. • 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). Commented Mar 21, 2022 at 10:45 • You can remove the spaces between or and [ and between ] and in. Commented Mar 21, 2022 at 11:01 • max(sum(a,[])) saves a byte Commented Mar 21, 2022 at 11:38 # 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}}  • Welcome to Code Golf, and nice answer! Commented Mar 22, 2022 at 22:56 • You don't need the @*Graph part. Most graph functions work directly on lists of TwoWayRules, e.g. AdjacencyMatrix@{1 <-> 2, 3 <-> 4}. Commented Mar 23, 2022 at 3:32 • 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. – Adam Commented Mar 23, 2022 at 18:03 • i.e. AdjacencyMatrix@{0<->2,3<->4} works but AdjacencyMatrix@{{0,2},{3,4}} doesn't, and same goes for Graph – Adam Commented Mar 23, 2022 at 18:13 # Charcoal, 24 bytes ≔⊕⌈Ｅθ⌈ιηＥη⭆η∨№θ⟦ιλ⟧№θ⟦λι  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: ≔⊕⌈Ｅθ⌈ιηＥη  Calculate the size of the array. ⭆η∨№θ⟦ιλ⟧№θ⟦λι  For each cell of the array, check whether it or its transpose exists within the input list. # Factor + math.matrices, 75 bytes [ 1 swap dup mmax 1 + dup 0 <matrix> [ matrix-set-nths ] keep dup flip m+ ]  ## 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 } }  # 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!

:(

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. # 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;

• 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