17
\$\begingroup\$

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]]
\$\endgroup\$

10 Answers 10

5
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ By the way, .e was just switched from k,Y to k,b, so to run this, use .e-.|f}k@QTUQbkQ \$\endgroup\$
    – isaacg
    May 15, 2015 at 9:47
  • \$\begingroup\$ @isaacg Will do so, once the online compiler updates. \$\endgroup\$
    – Jakube
    May 15, 2015 at 9:51
  • \$\begingroup\$ It has been updated. \$\endgroup\$
    – isaacg
    May 15, 2015 at 10:08
5
\$\begingroup\$

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

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

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

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.
\$\endgroup\$
1
\$\begingroup\$

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>

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

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()))
        )));
    }
}
\$\endgroup\$
0
\$\begingroup\$

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]]
\$\endgroup\$
0
\$\begingroup\$

Mathematica, 84 66 64 bytes

Using 1-based indexing.

MapIndexed[Union[#,First/@l~Position~Tr@#2]~Complement~#2&,l=#]&
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.