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

1. Delete all self-loops.
2. 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]]


# Pyth, 17 16 bytes

.e-.|f}k@QTUQbkQ


Try it online: Demonstration or 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 Commented May 15, 2015 at 9:47
• @isaacg Will do so, once the online compiler updates. Commented May 15, 2015 at 9:51
• It has been updated. Commented May 15, 2015 at 10:08

# CJam, 43403534 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, run the entire test harness.

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

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

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


# 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

}
})
}),
)

// 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>

# 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)) {
}
}
}
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()))
)));
}
}


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


# Mathematica, 8466 64 bytes

Using 1-based indexing.

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


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