Undirect a Graph

Question

Introduction

In this challenge, you are given a directed graph with self-loops, and your task is to convert it to an undirected graph without self-loops.

Input

Your input is a directed graph with vertex set {0, 1, ..., n-1} for some natural number n ≥ 0 (or {1, 2, ..., n} if you use 1-based indexing). The graph is given as a length-n list L where L[i] is a list of the out-neighbors of vertex i. For example, the list [[0,1],[0],[1,0,3],[]] represents the graph

.-. | v '-0<--2-->3 ^ | | | v | 1<--'

Note that the neighbor lists are not necessarily ordered, but they are guaranteed to be duplicate-free.

Output

Your output is another graph in the same format as the input, obtained from it as follows.

Delete all self-loops.
For each remaining edge u -> v, add the reversed edge v -> u if it's not already present.

As with the input, the neighbor lists of the output graph may be unordered, but they cannot contain duplicates. For the above graph, a correct output would be [[1,2],[0,2],[0,1,3],[2]], which represents the graph

0<->2<->3 ^ ^ | | v | 1<--'

Rules

You can use 0-based or 1-based indexing in the graphs. Both functions and full programs are acceptable. The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

These test cases use 0-based indexing; increment each number in the 1-based case. These neighbor lists are sorted in ascending order, but it is not required.

[] -> [] [[0]] -> [[]] [[],[0,1]] -> [[1],[0]] [[0,1],[]] -> [[1],[0]] [[0,1],[0],[1,0,3],[]] -> [[1,2],[0,2],[0,1,3],[2]] [[3],[],[5],[3],[1,3],[4]] -> [[3],[4],[5],[0,4],[1,3,5],[2,4]] [[0,1],[6],[],[3],[3],[1],[4,2]] -> [[1],[0,5,6],[6],[4],[3,6],[1],[1,2,4]] [[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]] -> [[1,6],[0,5],[4,5],[5,6],[2],[1,2,3,6],[0,3,5]] [[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]] -> [[1],[0,3,5,7],[5],[1],[5,7],[1,2,4,7],[],[1,4,5]] [[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]] -> [[2,7,8,9],[2,3,4,5,8],[0,1,4,5,7,8],[1,4,7,9],[1,2,3,8],[1,2,7,9],[7,9],[0,2,3,5,6,9],[0,1,2,4,9],[0,3,5,6,7,8]]

Jakube · Accepted Answer · 2015-05-15 10:24:01Z

Pyth, 17 16 bytes

.e-.|f}k@QTUQbkQ

Try it online: Demonstration or +"Q.e-.|f}k@QTUQbkQ&input="Test+Cases:"[][[0]][[],[0,1]][[0,1],[]][[0,1],[0],[1,0,3],[]][[3],[],[5],[3],[1,3],[4]][[0,1],[6],[],[3],[3],[1],[4,2]][[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]][[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]][[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]]&debug=0" rel="nofollow">Test Suite

Explanation

 implicit: Q = input .e Q enumerated mapping of Q (k index, b out-neighbors): f UQ filter [0, 1, ..., len(Q)-1] for elements T, which satisfy: }k@QT k in Q[T] # this are the in-neighbors .| b setwise union with b - k remove k

By the way, .e was just switched from k,Y to k,b, so to run this, use .e-.|f}k@QTUQbkQ — izzyg
– izzyg, Commented May 15, 2015 at 9:47

Martin Ender · Accepted Answer · 2015-05-13 16:23:01Z

CJam, 43 40 35 34 33 bytes

2 bytes saved by Sp3000.

This started out as a really elegant solution and then grew increasingly hideous as I tried patching up some holes I overlooked. I'm not sure yet if the original idea is still salvageable, but I'll try my best...

q~_,,\ff{&W+0=)}_z..-{_,{;(},+}%`

Test it here. Alternatively, "/0=',Ser:Q;Q~_,,\ff{&W+0=)}_z..-{ee{1=},0f=}%`oNo}/&input=[] -> [][[0]] -> [[]][[],[0,1]] -> [[1],[0]][[0,1],[]] -> [[1],[0]][[0,1],[0],[1,0,3],[]] -> [[1,2],[0,2],[0,1,3],[2]][[3],[],[5],[3],[1,3],[4]] -> [[3],[4],[5],[0,4],[1,3,5],[2,4]][[0,1],[6],[],[3],[3],[1],[4,2]] -> [[1],[0,5,6],[6],[4],[3,6],[1],[1,2,4]][[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]] -> [[1,6],[0,5],[4,5],[5,6],[2],[1,2,3,6],[0,3,5]][[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]] -> [[1],[0,3,5,7],[5],[1],[5,7],[1,2,4,7],[],[1,4,5]][[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]] -> [[2,7,8,9],[2,3,4,5,8],[0,1,4,5,7,8],[1,4,7,9],[1,2,3,8],[1,2,7,9],[7,9],[0,2,3,5,6,9],[0,1,2,4,9],[0,3,5,6,7,8]]" rel="nofollow">run the entire test harness.

I'll add an explanation once I'm sure the patient is dead.

Community · Accepted Answer · 2020-06-17 09:04:33Z

Python 2, 107 bytes

Still trying to figure out if I can golf this more, but for now, this is the best I can do.

def u(g):e=enumerate;o=[set(_)-{i}for i,_ in e(g)];[o[j].add(i)for i,_ in e(o)for j in _];print map(list,o)

I use sets to prevent duplicates; also, unlike list.remove(i), {S}-{i} doesn't throw an error if i is not in S.

Community · Accepted Answer · 2020-06-17 09:04:33Z

Ruby, 78 bytes

Finally some use for ruby's set operators ([1,2]&[2]==[2] and [3,4,5]-[4]==[3,5]).

->k{n=k.size;n.times{|i|n.times{|j|(k[j]&[i])[0]&&k[i]=(k[i]<<j).uniq-[i]}};k}

ideone, including all test cases, which it passes.

Community · Accepted Answer · 2020-06-17 09:04:33Z

CJam, 26 bytes

l~_,,:T.-_T\ff&Tf.e&.|:e_p

Not very short...

Explanation

l~ e# Read the input. _,,:T e# Get the graph size and store in T. .- e# Remove self-loops from the original input. _T\ff& e# Check if each vertex is in each list, and e# return truthy if yes, or empty list if no. Tf.e& e# Convert truthy to vertex numbers. .| e# Merge with the original graph. :e_ e# Remove empty lists. p e# Format and print.

edc65 · Accepted Answer · 2015-05-15 10:00:58Z

JavaScript(ES6), 96 110

Creating adjacency sets from adjacency list, that helps avoiding duplicates. Ad last it rebuilds the lists starting from the sets.

//Golfed U=l=> l.map((m,n)=>m.map(a=>a-n?s[n][a]=s[a][n]=1:0),s=l.map(m=>[])) &&s.map(a=>[~~k for(k in a)]) // Ungolfed undirect=(adList)=>( adSets=adList.map(_ => []), adList.forEach((curAdList,curNode)=>{ curAdList.forEach(adNode=>{ if (adNode!=curNode) { adSets[curNode][adNode]=1, adSets[adNode][curNode]=1 } }) }), adSets.map(adSet=>[~~k for(k in adSet)]) ) // Test out=s=>OUT.innerHTML+=s+'\n' test=[ [ [], [] ] ,[ [[0]], [[]] ] ,[ [[],[0,1]] , [[1],[0]] ] ,[ [[0,1],[]] , [[1],[0]] ] ,[ [[0,1],[0],[1,0,3],[]] , [[1,2],[0,2],[0,1,3],[2]] ] ,[ [[3],[],[5],[3],[1,3],[4]] , [[3],[4],[5],[0,4],[1,3,5],[2,4]] ] ,[ [[0,1],[6],[],[3],[3],[1],[4,2]] , [[1],[0,5,6],[6],[4],[3,6],[1],[1,2,4]] ] ,[ [[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]] , [[1,6],[0,5],[4,5],[5,6],[2],[1,2,3,6],[0,3,5]] ] ,[ [[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]] , [[1],[0,3,5,7],[5],[1],[5,7],[1,2,4,7],[],[1,4,5]] ] ,[ [[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]] , [[2,7,8,9],[2,3,4,5,8],[0,1,4,5,7,8],[1,4,7,9],[1,2,3,8],[1,2,7,9],[7,9],[0,2,3,5,6,9], [0,1,2,4,9],[0,3,5,6,7,8]] ] ] show=l=>'['+l.map(a=>'['+a+']').join(',')+']' test.forEach(t => ( r = U(t[0]), ck = show(r) == show(t[1]), out('Test ' + (ck ? 'OK: ':'FAIL: ') + show(t[0])+' -> ' + '\nResult: ' + show(r) + '\nCheck : ' + show(t[1]) + '\n\n') ) )

<pre id=OUT></pre>

Ypnypn · Accepted Answer · 2015-05-13 22:35:53Z

Java, 150

a->{int i=0,j,k=a.size();for(;i<k;a.get(i).remove((Object)i++))for(j=k;j-->0;)if(a.get(j).contains(i)&!a.get(i).contains(j))a.get(i).add(j);return a;}

Expanded, runnable code:

import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.function.Function public class C { static Function<List<List<Integer>>, List<List<Integer>>> f = a -> { int i = 0, j, k = a.size(); for (; i < k; a.get(i).remove((Object) i++)) { for (j = k; j-- > 0;) { if (a.get(j).contains(i) & !a.get(i).contains(j)) { a.get(i).add(j); } } } return a; }; public static void main(String[] args) { System.out.println(f.apply(new ArrayList(Arrays.asList( new ArrayList(Arrays.asList(0, 1)), new ArrayList(Arrays.asList(1)), new ArrayList(Arrays.asList(1, 0, 3)), new ArrayList(Arrays.asList())) ))); } }

dbramwell · Accepted Answer · 2015-05-14 15:34:17Z

Groovy - 87

u={g->g.eachWithIndex{n,i->g[i]=n-i;g[i].each{g[it]<<i}};g.each{it=it.sort().unique()}}

Full script to run tests:

u={g->g.eachWithIndex{n,i->g[i]=n-i;g[i].each{g[it]<<i}};g.each{it=it.sort().unique()}} assert u([]) == [] assert u([[0]]) == [[]] assert u([[],[0,1]]) == [[1],[0]] assert u([[0,1],[]]) == [[1],[0]] assert u([[0,1],[0],[1,0,3],[]]) == [[1,2],[0,2],[0,1,3],[2]] assert u([[3],[],[5],[3],[1,3],[4]]) == [[3],[4],[5],[0,4],[1,3,5],[2,4]] assert u([[0,1],[6],[],[3],[3],[1],[4,2]]) == [[1],[0,5,6],[6],[4],[3,6],[1],[1,2,4]] assert u([[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]]) == [[1,6],[0,5],[4,5],[5,6],[2],[1,2,3,6],[0,3,5]] assert u([[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]]) == [[1],[0,3,5,7],[5],[1],[5,7],[1,2,4,7],[],[1,4,5]] assert u([[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]]) == [[2,7,8,9],[2,3,4,5,8],[0,1,4,5,7,8],[1,4,7,9],[1,2,3,8],[1,2,7,9],[7,9],[0,2,3,5,6,9],[0,1,2,4,9],[0,3,5,6,7,8]]

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Mathematica, 84 66 64 bytes

Using 1-based indexing.

MapIndexed[Union[#,First/@l~Position~Tr@#2]~Complement~#2&,l=#]&

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered May 14, 2015 at 3:40

alephalpha

51.9k7 gold badges75 silver badges196 bronze badges

Add a comment |

OrangeHat · Accepted Answer · 2015-05-15 18:24:33Z

Python 3, 127 bytes

l=list;g=l(map(set,eval(input()))) for i in range(len(g)): for j in g[i]:g[j]=g[j]^g[j]&{j}|{i} print(l(map(l,g)))

Try online

Not my best attempt...

Stack Exchange Network

Undirect a Graph

Introduction

Input

Output

Rules

Test Cases

10 Answers 10

Pyth, 17 16 bytes

Explanation

CJam, 43 40 35 34 33 bytes

Python 2, 107 bytes

Ruby, 78 bytes

CJam, 26 bytes

Explanation

JavaScript(ES6), 96 110

Java, 150

Groovy - 87

Mathematica, 84 66 64 bytes

Python 3, 127 bytes

Hot Network Questions

Undirect a Graph

Introduction

Input

Output

Rules

Test Cases

10 Answers 10

Pyth, 17 16 bytes

Explanation

CJam, 43 40 35 34 33 bytes

Python 2, 107 bytes

Ruby, 78 bytes

CJam, 26 bytes

Explanation

JavaScript(ES6), 96 110

Java, 150

Groovy - 87

Mathematica, 84 66 64 bytes

Python 3, 127 bytes

Related

Hot Network Questions