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