Construct a line graph / conjugate graph

Clash Royale CLAN TAG#URR8PPP

up vote
8
down vote

favorite

Introduction

Given an undirected graph G, we can construct a graph L(G) (called the line graph or conjugate graph) that represents the connections between edges in G. This is done by creating a new vertex in L(G) for every edge in G and connecting these vertices if the edges they represent have a vertex in common.

Here's an example from Wikipedia showing the construction of a line graph (in green).

As another example, take this graph G with vertices A, B, C, and D.

 A
 |
 |
B---C---D---E

We create a new vertex for each edge in G. In this case, the edge between A and C is represented by a new vertex called AC.

 AC

 BC CD DE

And connect vertices when the edges they represent have a vertex in common. In this case, the edges from A to C and from B to C have vertex C in common, so vertices AC and BC are connected.

 AC
 / 
 BC--CD--DE

This new graph is the line graph of G!

See Wikipedia for more information.

Challenge

Given the adjacency list for a graph G, your program should print or return the adjacency list for the line graph L(G). This is code-golf, so the answer with the fewest bytes wins!

Input

A list of pairs of strings representing the the edges of G. Each pair describes the vertices that are connected by that edge.

• Each pair (X,Y) is guaranteed to be unique, meaning that that the list will not contain (Y,X) or a second (X,Y).

For example:

[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")]
[("D","E"),("C","D"),("B","C"),("A","C")]

Output

A list of pairs of strings representing the the edges of L(G). Each pair describes the vertices that are connected by that edge.

• Each pair (X,Y) must be unique, meaning that that the list will not contain (Y,X) or a second (X,Y).




• For any edge (X,Y) in G, the vertex it creates in L(G) must be named XY (the names are concatenated together in same order that they're specified in the input).

For example:

[("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]
[("DE","CD"),("CD","CB"),("CD","CA"),("BC","AB")]

Test Cases

 -> 

[("0","1")] -> 

[("0","1"),("1","2")] -> [("01","12")]

[("a","b"),("b","c"),("c","a")] -> [("ab","bc"),("bc","ca"),("ca","ab")]

[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")] -> [("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]

code-golf math graph-theory

share|improve this question

edited Aug 16 at 7:36

Mr. Xcoder

30.2k757193

asked Aug 16 at 0:49

Curtis Bechtel

29618

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  I don't see anything in the question ruling out an input like [("1","23"),("23","4"),("12","3"),("3","4")], for which the output should presumably be [("123","234"),("123","34")], which cannot be correctly interpreted. I think the only way to fix this is to edit in a guarantee that the input will never contain such ambiguities, but if this question had been posted in the sandbox then I would have suggested being less prescriptive about the naming of vertices in the output.
  – Peter Taylor
  Aug 16 at 8:04
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Further to Peter Taylor's comment, can we assume that the vertex names are all 1-character long in the input?
  – sundar
  Aug 16 at 15:32
  

  
  
  
  

add a comment | 

up vote
8
down vote

favorite

Introduction

Given an undirected graph G, we can construct a graph L(G) (called the line graph or conjugate graph) that represents the connections between edges in G. This is done by creating a new vertex in L(G) for every edge in G and connecting these vertices if the edges they represent have a vertex in common.

Here's an example from Wikipedia showing the construction of a line graph (in green).

As another example, take this graph G with vertices A, B, C, and D.

 A
 |
 |
B---C---D---E

We create a new vertex for each edge in G. In this case, the edge between A and C is represented by a new vertex called AC.

 AC

 BC CD DE

And connect vertices when the edges they represent have a vertex in common. In this case, the edges from A to C and from B to C have vertex C in common, so vertices AC and BC are connected.

 AC
 / 
 BC--CD--DE

This new graph is the line graph of G!

See Wikipedia for more information.

Challenge

Given the adjacency list for a graph G, your program should print or return the adjacency list for the line graph L(G). This is code-golf, so the answer with the fewest bytes wins!

Input

A list of pairs of strings representing the the edges of G. Each pair describes the vertices that are connected by that edge.

• Each pair (X,Y) is guaranteed to be unique, meaning that that the list will not contain (Y,X) or a second (X,Y).

For example:

[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")]
[("D","E"),("C","D"),("B","C"),("A","C")]

Output

A list of pairs of strings representing the the edges of L(G). Each pair describes the vertices that are connected by that edge.

• Each pair (X,Y) must be unique, meaning that that the list will not contain (Y,X) or a second (X,Y).




• For any edge (X,Y) in G, the vertex it creates in L(G) must be named XY (the names are concatenated together in same order that they're specified in the input).

For example:

[("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]
[("DE","CD"),("CD","CB"),("CD","CA"),("BC","AB")]

Test Cases

 -> 

[("0","1")] -> 

[("0","1"),("1","2")] -> [("01","12")]

[("a","b"),("b","c"),("c","a")] -> [("ab","bc"),("bc","ca"),("ca","ab")]

[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")] -> [("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]

code-golf math graph-theory

share|improve this question

edited Aug 16 at 7:36

Mr. Xcoder

30.2k757193

asked Aug 16 at 0:49

Curtis Bechtel

29618

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  I don't see anything in the question ruling out an input like [("1","23"),("23","4"),("12","3"),("3","4")], for which the output should presumably be [("123","234"),("123","34")], which cannot be correctly interpreted. I think the only way to fix this is to edit in a guarantee that the input will never contain such ambiguities, but if this question had been posted in the sandbox then I would have suggested being less prescriptive about the naming of vertices in the output.
  – Peter Taylor
  Aug 16 at 8:04
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Further to Peter Taylor's comment, can we assume that the vertex names are all 1-character long in the input?
  – sundar
  Aug 16 at 15:32
  

  
  
  
  

add a comment | 

up vote
8
down vote

favorite

up vote
8
down vote

favorite

Introduction

Given an undirected graph G, we can construct a graph L(G) (called the line graph or conjugate graph) that represents the connections between edges in G. This is done by creating a new vertex in L(G) for every edge in G and connecting these vertices if the edges they represent have a vertex in common.

Here's an example from Wikipedia showing the construction of a line graph (in green).

As another example, take this graph G with vertices A, B, C, and D.

 A
 |
 |
B---C---D---E

We create a new vertex for each edge in G. In this case, the edge between A and C is represented by a new vertex called AC.

 AC

 BC CD DE

And connect vertices when the edges they represent have a vertex in common. In this case, the edges from A to C and from B to C have vertex C in common, so vertices AC and BC are connected.

 AC
 / 
 BC--CD--DE

This new graph is the line graph of G!

See Wikipedia for more information.

Challenge

Given the adjacency list for a graph G, your program should print or return the adjacency list for the line graph L(G). This is code-golf, so the answer with the fewest bytes wins!

Input

A list of pairs of strings representing the the edges of G. Each pair describes the vertices that are connected by that edge.

• Each pair (X,Y) is guaranteed to be unique, meaning that that the list will not contain (Y,X) or a second (X,Y).

For example:

[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")]
[("D","E"),("C","D"),("B","C"),("A","C")]

Output

A list of pairs of strings representing the the edges of L(G). Each pair describes the vertices that are connected by that edge.

• Each pair (X,Y) must be unique, meaning that that the list will not contain (Y,X) or a second (X,Y).




• For any edge (X,Y) in G, the vertex it creates in L(G) must be named XY (the names are concatenated together in same order that they're specified in the input).

For example:

[("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]
[("DE","CD"),("CD","CB"),("CD","CA"),("BC","AB")]

Test Cases

 -> 

[("0","1")] -> 

[("0","1"),("1","2")] -> [("01","12")]

[("a","b"),("b","c"),("c","a")] -> [("ab","bc"),("bc","ca"),("ca","ab")]

[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")] -> [("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]

code-golf math graph-theory

share|improve this question

edited Aug 16 at 7:36

Mr. Xcoder

30.2k757193

asked Aug 16 at 0:49

Curtis Bechtel

29618

Introduction

Given an undirected graph G, we can construct a graph L(G) (called the line graph or conjugate graph) that represents the connections between edges in G. This is done by creating a new vertex in L(G) for every edge in G and connecting these vertices if the edges they represent have a vertex in common.

Here's an example from Wikipedia showing the construction of a line graph (in green).

As another example, take this graph G with vertices A, B, C, and D.

 A
 |
 |
B---C---D---E

We create a new vertex for each edge in G. In this case, the edge between A and C is represented by a new vertex called AC.

 AC

 BC CD DE

And connect vertices when the edges they represent have a vertex in common. In this case, the edges from A to C and from B to C have vertex C in common, so vertices AC and BC are connected.

 AC
 / 
 BC--CD--DE

This new graph is the line graph of G!

See Wikipedia for more information.

Challenge

Given the adjacency list for a graph G, your program should print or return the adjacency list for the line graph L(G). This is code-golf, so the answer with the fewest bytes wins!

Input

A list of pairs of strings representing the the edges of G. Each pair describes the vertices that are connected by that edge.

• Each pair (X,Y) is guaranteed to be unique, meaning that that the list will not contain (Y,X) or a second (X,Y).

For example:

[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")]
[("D","E"),("C","D"),("B","C"),("A","C")]

Output

A list of pairs of strings representing the the edges of L(G). Each pair describes the vertices that are connected by that edge.

• Each pair (X,Y) must be unique, meaning that that the list will not contain (Y,X) or a second (X,Y).




• For any edge (X,Y) in G, the vertex it creates in L(G) must be named XY (the names are concatenated together in same order that they're specified in the input).

For example:

[("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]
[("DE","CD"),("CD","CB"),("CD","CA"),("BC","AB")]

Test Cases

 -> 

[("0","1")] -> 

[("0","1"),("1","2")] -> [("01","12")]

[("a","b"),("b","c"),("c","a")] -> [("ab","bc"),("bc","ca"),("ca","ab")]

[("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")] -> [("12","13"),("12","14"),("12","25"),("13","14"),("13","34"),("14","34"),("14","45"),("25","45"),("34","45")]

code-golf math graph-theory

share|improve this question

edited Aug 16 at 7:36

Mr. Xcoder

30.2k757193

asked Aug 16 at 0:49

Curtis Bechtel

29618

share|improve this question

share|improve this question

edited Aug 16 at 7:36

Mr. Xcoder

30.2k757193

edited Aug 16 at 7:36

Mr. Xcoder

30.2k757193

edited Aug 16 at 7:36

Mr. Xcoder

30.2k757193

30.2k757193

asked Aug 16 at 0:49

Curtis Bechtel

29618

asked Aug 16 at 0:49

Curtis Bechtel

29618

asked Aug 16 at 0:49

Curtis Bechtel

29618

29618

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  I don't see anything in the question ruling out an input like [("1","23"),("23","4"),("12","3"),("3","4")], for which the output should presumably be [("123","234"),("123","34")], which cannot be correctly interpreted. I think the only way to fix this is to edit in a guarantee that the input will never contain such ambiguities, but if this question had been posted in the sandbox then I would have suggested being less prescriptive about the naming of vertices in the output.
  – Peter Taylor
  Aug 16 at 8:04
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Further to Peter Taylor's comment, can we assume that the vertex names are all 1-character long in the input?
  – sundar
  Aug 16 at 15:32
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  3
  

  
  
  
  
  
  

  
  I don't see anything in the question ruling out an input like [("1","23"),("23","4"),("12","3"),("3","4")], for which the output should presumably be [("123","234"),("123","34")], which cannot be correctly interpreted. I think the only way to fix this is to edit in a guarantee that the input will never contain such ambiguities, but if this question had been posted in the sandbox then I would have suggested being less prescriptive about the naming of vertices in the output.
  – Peter Taylor
  Aug 16 at 8:04
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  Further to Peter Taylor's comment, can we assume that the vertex names are all 1-character long in the input?
  – sundar
  Aug 16 at 15:32
  

  
  
  
  

3

3

I don't see anything in the question ruling out an input like [("1","23"),("23","4"),("12","3"),("3","4")], for which the output should presumably be [("123","234"),("123","34")], which cannot be correctly interpreted. I think the only way to fix this is to edit in a guarantee that the input will never contain such ambiguities, but if this question had been posted in the sandbox then I would have suggested being less prescriptive about the naming of vertices in the output.
– Peter Taylor
Aug 16 at 8:04

I don't see anything in the question ruling out an input like [("1","23"),("23","4"),("12","3"),("3","4")], for which the output should presumably be [("123","234"),("123","34")], which cannot be correctly interpreted. I think the only way to fix this is to edit in a guarantee that the input will never contain such ambiguities, but if this question had been posted in the sandbox then I would have suggested being less prescriptive about the naming of vertices in the output.
– Peter Taylor
Aug 16 at 8:04

2

2

Further to Peter Taylor's comment, can we assume that the vertex names are all 1-character long in the input?
– sundar
Aug 16 at 15:32

Further to Peter Taylor's comment, can we assume that the vertex names are all 1-character long in the input?
– sundar
Aug 16 at 15:32

add a comment | 

12 Answers
12

active

oldest

votes

up vote
2
down vote

Ruby, 51 bytes

->aa.combination(2)p [x*'',y*'']if(x&y)[0]

Try it online!

For each combination of two edges, if they have a vertex in common (i.e. if the first element of their intersection is non-nil), print an array containing the two edges to STDOUT.

share|improve this answer

answered Aug 16 at 1:10

Doorknob♦

53.1k15110339

add a comment | 

up vote
2
down vote

K (ngn/k), 45 39 33 29 bytes

(*>)#(3=#?,/)#,/x,/::x@,:'

Try it online!

,:' wrap each edge in a 1-element list

@ apply a function with implicit argument x

x,/::x concatenate each of the left x with each of the right x, get a matrix of results - all pairs of edges

,/ flatten the matrix

( )# filter

(3=#?,/)# filter only those pairs whose concatenation (,/) has a count (#) of exactly 3 unique (?) elements

This removes edges like ("ab";"ab") and ("ab";"cd") from the list.

(*>)# filter only those pairs whose sort-descending permutation (>) starts with (*) a 1 (non-0 is boolean true)

In our case, the sort-descending permutation could be 0 1 or 1 0.

share|improve this answer

edited Aug 16 at 7:39

answered Aug 16 at 1:16

ngn

6,09812256

add a comment | 

up vote
2
down vote

JavaScript (Firefox 30-57), 77 bytes

a=>[for(x of a=a.map(x=>x.join``))for(y of a)if(x<y&&x.match(`[$y]`))[x,y]]

Assumes all inputs are single letters (well, any single character other than ^ and ]).

share|improve this answer

answered Aug 16 at 9:13

Neil

74.9k744170

• 
  
  
  

  
  

  
  
  
  
  
  

  
  What makes Firefox 30-57 special for this answer?
  – Night2
  Aug 16 at 10:47
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Night2 The array comprehension syntax was only supported in those versions of Firefox.
  – Neil
  Aug 16 at 10:49
  

  
  
  
  

add a comment | 

up vote
2
down vote

Brachylog, 13 bytes

⊇Ċ.c¬≠∧ᶠcᵐ²

Try it online!

With all test cases

(-1 byte replacing l₂ with Ċ, thanks to @Fatalize.)

⊇Ċ.c¬≠∧ᶠcᵐ² Full code
 ᶠ Find all outputs of this predicate:
 ⊇Ċ. A two-element subset of the input
 c which when its subarrays are concatenated
 ­ does not have all different elements
 (i.e. some element is repeated)
 ∧ (no further constraint on output)
 cᵐ² Join vertex names in each subsubarray in that result

share|improve this answer

edited Aug 17 at 18:32

answered Aug 16 at 15:22

sundar

4,656829

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You can use the constrained variable Ċ (couple) instead of l₂ to save one byte.
  – Fatalize
  Aug 17 at 7:06
  

  
  
  
  

add a comment | 

up vote
1
down vote

Jelly, 5 bytes

Œcf/Ƈ

Try it online!

share|improve this answer

answered Aug 16 at 7:39

Mr. Xcoder

30.2k757193

• 
  
  
  

  
  

  
  
  
  
  
  

  
  How are f and Ƈ used in Jelly? If I read it in the docs, both are filters. f is "Filter; remove the elements from x that are not in y." and Ƈ is "Filter (alias for Ðf). Keep all items that satisfy a condition.". Are they always used together? Is the Ƈ used to close the filter f? As in, is f...Ƈ similar to ʒ...} in 05AB1E? Or has the / ("Reduce or n-wise reduce.") have something to do with it? Just trying to understand the code, and I'm confused by the two different filter commands (and how both are used here). :)
  – Kevin Cruijssen
  Aug 16 at 11:44
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  @KevinCruijssen No, f and Ƈ are two completely separate things. You can think of f as intersection (given two lists, it returns their common elements) and Ƈ is like ʒ in 05AB1E. In short: Ã…Â’c returns all possible combinations of two elements from the list, then Ƈ only keeps those that satisfy the link (i.e. Jelly function) f/, which returns the intersection of the two items. But f is a dyad (two-argument function) and we need to apply it on a two-element list instead, so we have to use /, reduce.
  – Mr. Xcoder
  Aug 16 at 11:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Ah ok, that makes a lot more sense. I guess the term 'filter' for f in the docs, although correct, mainly confused me with the actual filter Ƈ being used. Your explanation of "given two lists, return their common elements" made it all clear. And I indeed had the feeling the / was used to convert Jelly's data somehow. Actually, I now see the section 6.6 Reducing in the Tutorial on the Jelly wiki that explains how it pops a dyad and pushes a reduced monad (basically 2 arguments vs a list of pairs as argument). Thanks, all clear now!
  – Kevin Cruijssen
  Aug 16 at 11:59
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

MATL, 13 bytes

2XN!"@Y:X&n?@

Try it online!

Not as bad as I expected given cell array input. Basically the same idea as @Doorknob's Ruby answer.

2XN % Get all combinations of 2 elements from the input
! % Transpose
" % Iterate over the columns (combinations)
@ % Push the current combination of edges
Y: % Split it out as two separate vectors
X&n % Get the number of intersecting elements between them
?@ % If that's non-zero, push the current combination on stack
 % Implicit loop end, valid combinations collect on the stack 
 % and are implicitly output at the end

share|improve this answer

edited Aug 16 at 16:19

answered Aug 16 at 15:53

sundar

4,656829

add a comment | 

up vote
0
down vote

C (gcc), 173 bytes

Input i and output o are flat, null-terminated arrays. Output names can be up to 998 characters long before this will break.

#define M(x)o[n]=malloc(999),sprintf(o[n++],"%s%s",x[0],x[1])
f(i,o,j,n,m)char**i,**j,**o;(M(i),M(j));

Try it online!

share|improve this answer

answered Aug 16 at 6:06

Curtis Bechtel

29618

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Suggest *x instead of x[0] and int** instead of char**
  – ceilingcat
  Aug 20 at 17:31
  

  
  
  
  

add a comment | 

up vote
0
down vote

Mathematica 23 bytes

EdgeList[LineGraph[#]]&

Example: g = Graph[1 <-> 2, 2 <-> 3, 3 <-> 4, 2 <-> 4 ]

EdgeList@LineGraph[g]

(*

2 <-> 1, 3 <-> 2, 4 <-> 1, 4 <-> 2, 4 <-> 3

*)

share|improve this answer

edited Aug 16 at 22:56

answered Aug 16 at 20:35

David G. Stork

1637

add a comment | 

up vote
0
down vote

Pyth, 7 bytes

@F#.cQ2

Try it here!

If joining is necessary, 10 bytes

sMM@F#.cQ2

Try it here!

share|improve this answer

edited Aug 16 at 23:06

answered Aug 16 at 7:35

Mr. Xcoder

30.2k757193

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Your output does not have the required form. You need to string join the nodes.
  – DavidC
  Aug 16 at 23:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @DavidC I don't see why that would be needed and I cannot identify any portion of the challenge spefication that requires that, but I have added a version that joins them.
  – Mr. Xcoder
  Aug 16 at 23:07
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Joining was used in all of the test cases. In my case, joining cost 9 bytes. You were able to do it with just 3 additional bytes. Impressive!
  – DavidC
  Aug 16 at 23:12
  
  

  
  
  
  

add a comment | 

up vote
0
down vote

Wolfram Language 64 53 bytes

""<>#&/@#&/@Select[#~Subsets~2,IntersectingQ@@#&]&

Finds all the input list's Subsets of length 2, Select those in which the nodes of one pair intersect with the nodes of another pair (indicating that the pairs share a node), and StringJoin the nodes for all selected pairs.

The code is especially difficult to read because it employs 4 nested pure (aka "anonymous") functions.

The code uses braces, "", as list delimiters, as is customary in Wolfram Language.

1 byte saved thanks to Mr. Xcoder.

---

Example

""<>#&/@#&/@Select[#~Subsets~2,IntersectingQ@@#&]&["1","2","1","3","1","4","2","5","3","4","4","5"]

(*"12", "13", "12", "14", "12", "25", "13", "14", "13", "34", "14", "34", "14", "45", "25", "45", "34", "45"*)

share|improve this answer

edited Aug 16 at 23:08

answered Aug 16 at 2:12

DavidC

23.5k243100

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Your current is actually 65 bytes, not 64. However, you can golf 1 byte with Select[#~Subsets~2,IntersectingQ@@#&]/.a_,b_:>""<>a,""<>b& – Try it online!
  – Mr. Xcoder
  Aug 16 at 7:29
  
  

  
  
  
  

add a comment | 

up vote
0
down vote

Python 2, 109 bytes

lambda a:[(s,t)for Q in[[''.join(p)for p in a if x in p]for x in set(sum(a,()))]for s in Q for t in Q if s<t]

Try it online!

For each node x (discovered by making a set from the flattened list of edges), make a list of the pairs p that have x as a member; then, for each of those lists Q, find the unique, distinct pairings within Q (uniqueness/distinction is enforced via if s<t).

share|improve this answer

edited Aug 17 at 4:25

answered Aug 17 at 2:33

Chas Brown

4,1361319

add a comment | 

up vote
0
down vote

C# 233 bytes

static void c(List<(string a,string b)>i,List<(string,string)>o)for(int m=0;m<i.Count;m++)for(int n=m+1;n<i.Count;n++)(i[n].a+i[n].b).Contains(i[m].b))o.Add((i[m].a+i[m].b,i[n].a+i[n].b));

Example

using System;
using System.Collections.Generic;

namespace conjugateGraphGolf

 class Program
 
 static void Main()
 
 List<(string a, string b)> inputs = new List<(string, string)>
 
 new List<(string, string)>(),
 new List<(string, string)>() ("0", "1"),
 new List<(string, string)>() ("0", "1"),("1", "2"),
 new List<(string, string)>() ("a","b"),("b","c"),("c","a"),
 new List<(string, string)>() ("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")
 ;

 List<(string, string)> output = new List<(string, string)>();

 for(int i = 0; i < inputs.Length; i++)
 
 output.Clear();
 c(inputs[i], output);

 WriteList(inputs[i]);
 Console.Write(" -> ");
 WriteList(output);
 Console.Write("rnrn");
 

 Console.ReadKey(true);
 

 static void c(List<(string a,string b)>i,List<(string,string)>o)for(int m=0;m<i.Count;m++)for(int n=m+1;n<i.Count;n++)(i[n].a+i[n].b).Contains(i[m].b))o.Add((i[m].a+i[m].b,i[n].a+i[n].b));

 public static void WriteList(List<(string a, string b)> list)
 
 Console.Write("[");
 for(int i = 0; i < list.Count; i++)
 
 Console.Write($"("list[i].a","list[i].b")(i == list.Count - 1 ? "" : ",")");
 
 Console.Write("]");
 
 

share|improve this answer

answered Aug 17 at 10:04

Robin B

1012

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f170695%2fconstruct-a-line-graph-conjugate-graph%23new-answer', 'question_page');

);

Post as a guest

Name Email

12 Answers
12

active

oldest

votes

12 Answers
12

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
2
down vote

Ruby, 51 bytes

->aa.combination(2)p [x*'',y*'']if(x&y)[0]

Try it online!

For each combination of two edges, if they have a vertex in common (i.e. if the first element of their intersection is non-nil), print an array containing the two edges to STDOUT.

share|improve this answer

answered Aug 16 at 1:10

Doorknob♦

53.1k15110339

add a comment | 

up vote
2
down vote

Ruby, 51 bytes

->aa.combination(2)p [x*'',y*'']if(x&y)[0]

Try it online!

For each combination of two edges, if they have a vertex in common (i.e. if the first element of their intersection is non-nil), print an array containing the two edges to STDOUT.

share|improve this answer

answered Aug 16 at 1:10

Doorknob♦

53.1k15110339

add a comment | 

up vote
2
down vote

up vote
2
down vote

Ruby, 51 bytes

->aa.combination(2)p [x*'',y*'']if(x&y)[0]

Try it online!

For each combination of two edges, if they have a vertex in common (i.e. if the first element of their intersection is non-nil), print an array containing the two edges to STDOUT.

share|improve this answer

answered Aug 16 at 1:10

Doorknob♦

53.1k15110339

Ruby, 51 bytes

->aa.combination(2)p [x*'',y*'']if(x&y)[0]

Try it online!

For each combination of two edges, if they have a vertex in common (i.e. if the first element of their intersection is non-nil), print an array containing the two edges to STDOUT.

share|improve this answer

answered Aug 16 at 1:10

Doorknob♦

53.1k15110339

share|improve this answer

share|improve this answer

answered Aug 16 at 1:10

Doorknob♦

53.1k15110339

answered Aug 16 at 1:10

Doorknob♦

53.1k15110339

answered Aug 16 at 1:10

Doorknob♦

53.1k15110339

53.1k15110339

add a comment | 

add a comment | 

up vote
2
down vote

K (ngn/k), 45 39 33 29 bytes

(*>)#(3=#?,/)#,/x,/::x@,:'

Try it online!

,:' wrap each edge in a 1-element list

@ apply a function with implicit argument x

x,/::x concatenate each of the left x with each of the right x, get a matrix of results - all pairs of edges

,/ flatten the matrix

( )# filter

(3=#?,/)# filter only those pairs whose concatenation (,/) has a count (#) of exactly 3 unique (?) elements

This removes edges like ("ab";"ab") and ("ab";"cd") from the list.

(*>)# filter only those pairs whose sort-descending permutation (>) starts with (*) a 1 (non-0 is boolean true)

In our case, the sort-descending permutation could be 0 1 or 1 0.

share|improve this answer

edited Aug 16 at 7:39

answered Aug 16 at 1:16

ngn

6,09812256

add a comment | 

up vote
2
down vote

K (ngn/k), 45 39 33 29 bytes

(*>)#(3=#?,/)#,/x,/::x@,:'

Try it online!

,:' wrap each edge in a 1-element list

@ apply a function with implicit argument x

x,/::x concatenate each of the left x with each of the right x, get a matrix of results - all pairs of edges

,/ flatten the matrix

( )# filter

(3=#?,/)# filter only those pairs whose concatenation (,/) has a count (#) of exactly 3 unique (?) elements

This removes edges like ("ab";"ab") and ("ab";"cd") from the list.

(*>)# filter only those pairs whose sort-descending permutation (>) starts with (*) a 1 (non-0 is boolean true)

In our case, the sort-descending permutation could be 0 1 or 1 0.

share|improve this answer

edited Aug 16 at 7:39

answered Aug 16 at 1:16

ngn

6,09812256

add a comment | 

up vote
2
down vote

up vote
2
down vote

K (ngn/k), 45 39 33 29 bytes

(*>)#(3=#?,/)#,/x,/::x@,:'

Try it online!

,:' wrap each edge in a 1-element list

@ apply a function with implicit argument x

x,/::x concatenate each of the left x with each of the right x, get a matrix of results - all pairs of edges

,/ flatten the matrix

( )# filter

(3=#?,/)# filter only those pairs whose concatenation (,/) has a count (#) of exactly 3 unique (?) elements

This removes edges like ("ab";"ab") and ("ab";"cd") from the list.

(*>)# filter only those pairs whose sort-descending permutation (>) starts with (*) a 1 (non-0 is boolean true)

In our case, the sort-descending permutation could be 0 1 or 1 0.

share|improve this answer

edited Aug 16 at 7:39

answered Aug 16 at 1:16

ngn

6,09812256

K (ngn/k), 45 39 33 29 bytes

(*>)#(3=#?,/)#,/x,/::x@,:'

Try it online!

,:' wrap each edge in a 1-element list

@ apply a function with implicit argument x

x,/::x concatenate each of the left x with each of the right x, get a matrix of results - all pairs of edges

,/ flatten the matrix

( )# filter

(3=#?,/)# filter only those pairs whose concatenation (,/) has a count (#) of exactly 3 unique (?) elements

This removes edges like ("ab";"ab") and ("ab";"cd") from the list.

(*>)# filter only those pairs whose sort-descending permutation (>) starts with (*) a 1 (non-0 is boolean true)

In our case, the sort-descending permutation could be 0 1 or 1 0.

share|improve this answer

edited Aug 16 at 7:39

answered Aug 16 at 1:16

ngn

6,09812256

share|improve this answer

share|improve this answer

edited Aug 16 at 7:39

edited Aug 16 at 7:39

edited Aug 16 at 7:39

answered Aug 16 at 1:16

ngn

6,09812256

answered Aug 16 at 1:16

ngn

6,09812256

answered Aug 16 at 1:16

ngn

6,09812256

6,09812256

add a comment | 

add a comment | 

up vote
2
down vote

JavaScript (Firefox 30-57), 77 bytes

a=>[for(x of a=a.map(x=>x.join``))for(y of a)if(x<y&&x.match(`[$y]`))[x,y]]

Assumes all inputs are single letters (well, any single character other than ^ and ]).

share|improve this answer

answered Aug 16 at 9:13

Neil

74.9k744170

• 
  
  
  

  
  

  
  
  
  
  
  

  
  What makes Firefox 30-57 special for this answer?
  – Night2
  Aug 16 at 10:47
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Night2 The array comprehension syntax was only supported in those versions of Firefox.
  – Neil
  Aug 16 at 10:49
  

  
  
  
  

add a comment | 

up vote
2
down vote

JavaScript (Firefox 30-57), 77 bytes

a=>[for(x of a=a.map(x=>x.join``))for(y of a)if(x<y&&x.match(`[$y]`))[x,y]]

Assumes all inputs are single letters (well, any single character other than ^ and ]).

share|improve this answer

answered Aug 16 at 9:13

Neil

74.9k744170

• 
  
  
  

  
  

  
  
  
  
  
  

  
  What makes Firefox 30-57 special for this answer?
  – Night2
  Aug 16 at 10:47
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Night2 The array comprehension syntax was only supported in those versions of Firefox.
  – Neil
  Aug 16 at 10:49
  

  
  
  
  

add a comment | 

up vote
2
down vote

up vote
2
down vote

JavaScript (Firefox 30-57), 77 bytes

a=>[for(x of a=a.map(x=>x.join``))for(y of a)if(x<y&&x.match(`[$y]`))[x,y]]

Assumes all inputs are single letters (well, any single character other than ^ and ]).

share|improve this answer

answered Aug 16 at 9:13

Neil

74.9k744170

JavaScript (Firefox 30-57), 77 bytes

a=>[for(x of a=a.map(x=>x.join``))for(y of a)if(x<y&&x.match(`[$y]`))[x,y]]

Assumes all inputs are single letters (well, any single character other than ^ and ]).

share|improve this answer

answered Aug 16 at 9:13

Neil

74.9k744170

share|improve this answer

share|improve this answer

answered Aug 16 at 9:13

Neil

74.9k744170

answered Aug 16 at 9:13

Neil

74.9k744170

answered Aug 16 at 9:13

Neil

74.9k744170

74.9k744170

• 
  
  
  

  
  

  
  
  
  
  
  

  
  What makes Firefox 30-57 special for this answer?
  – Night2
  Aug 16 at 10:47
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Night2 The array comprehension syntax was only supported in those versions of Firefox.
  – Neil
  Aug 16 at 10:49
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  What makes Firefox 30-57 special for this answer?
  – Night2
  Aug 16 at 10:47
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  @Night2 The array comprehension syntax was only supported in those versions of Firefox.
  – Neil
  Aug 16 at 10:49
  

  
  
  
  

What makes Firefox 30-57 special for this answer?
– Night2
Aug 16 at 10:47

What makes Firefox 30-57 special for this answer?
– Night2
Aug 16 at 10:47

1

1

@Night2 The array comprehension syntax was only supported in those versions of Firefox.
– Neil
Aug 16 at 10:49

@Night2 The array comprehension syntax was only supported in those versions of Firefox.
– Neil
Aug 16 at 10:49

add a comment | 

up vote
2
down vote

Brachylog, 13 bytes

⊇Ċ.c¬≠∧ᶠcᵐ²

Try it online!

With all test cases

(-1 byte replacing l₂ with Ċ, thanks to @Fatalize.)

⊇Ċ.c¬≠∧ᶠcᵐ² Full code
 ᶠ Find all outputs of this predicate:
 ⊇Ċ. A two-element subset of the input
 c which when its subarrays are concatenated
 ­ does not have all different elements
 (i.e. some element is repeated)
 ∧ (no further constraint on output)
 cᵐ² Join vertex names in each subsubarray in that result

share|improve this answer

edited Aug 17 at 18:32

answered Aug 16 at 15:22

sundar

4,656829

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You can use the constrained variable Ċ (couple) instead of l₂ to save one byte.
  – Fatalize
  Aug 17 at 7:06
  

  
  
  
  

add a comment | 

up vote
2
down vote

Brachylog, 13 bytes

⊇Ċ.c¬≠∧ᶠcᵐ²

Try it online!

With all test cases

(-1 byte replacing l₂ with Ċ, thanks to @Fatalize.)

⊇Ċ.c¬≠∧ᶠcᵐ² Full code
 ᶠ Find all outputs of this predicate:
 ⊇Ċ. A two-element subset of the input
 c which when its subarrays are concatenated
 ­ does not have all different elements
 (i.e. some element is repeated)
 ∧ (no further constraint on output)
 cᵐ² Join vertex names in each subsubarray in that result

share|improve this answer

edited Aug 17 at 18:32

answered Aug 16 at 15:22

sundar

4,656829

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You can use the constrained variable Ċ (couple) instead of l₂ to save one byte.
  – Fatalize
  Aug 17 at 7:06
  

  
  
  
  

add a comment | 

up vote
2
down vote

up vote
2
down vote

Brachylog, 13 bytes

⊇Ċ.c¬≠∧ᶠcᵐ²

Try it online!

With all test cases

(-1 byte replacing l₂ with Ċ, thanks to @Fatalize.)

⊇Ċ.c¬≠∧ᶠcᵐ² Full code
 ᶠ Find all outputs of this predicate:
 ⊇Ċ. A two-element subset of the input
 c which when its subarrays are concatenated
 ­ does not have all different elements
 (i.e. some element is repeated)
 ∧ (no further constraint on output)
 cᵐ² Join vertex names in each subsubarray in that result

share|improve this answer

edited Aug 17 at 18:32

answered Aug 16 at 15:22

sundar

4,656829

Brachylog, 13 bytes

⊇Ċ.c¬≠∧ᶠcᵐ²

Try it online!

With all test cases

(-1 byte replacing l₂ with Ċ, thanks to @Fatalize.)

⊇Ċ.c¬≠∧ᶠcᵐ² Full code
 ᶠ Find all outputs of this predicate:
 ⊇Ċ. A two-element subset of the input
 c which when its subarrays are concatenated
 ­ does not have all different elements
 (i.e. some element is repeated)
 ∧ (no further constraint on output)
 cᵐ² Join vertex names in each subsubarray in that result

share|improve this answer

edited Aug 17 at 18:32

answered Aug 16 at 15:22

sundar

4,656829

share|improve this answer

share|improve this answer

edited Aug 17 at 18:32

edited Aug 17 at 18:32

edited Aug 17 at 18:32

answered Aug 16 at 15:22

sundar

4,656829

answered Aug 16 at 15:22

sundar

4,656829

answered Aug 16 at 15:22

sundar

4,656829

4,656829

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You can use the constrained variable Ċ (couple) instead of l₂ to save one byte.
  – Fatalize
  Aug 17 at 7:06
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  You can use the constrained variable Ċ (couple) instead of l₂ to save one byte.
  – Fatalize
  Aug 17 at 7:06
  

  
  
  
  

You can use the constrained variable Ċ (couple) instead of l₂ to save one byte.
– Fatalize
Aug 17 at 7:06

You can use the constrained variable Ċ (couple) instead of l₂ to save one byte.
– Fatalize
Aug 17 at 7:06

add a comment | 

up vote
1
down vote

Jelly, 5 bytes

Œcf/Ƈ

Try it online!

share|improve this answer

answered Aug 16 at 7:39

Mr. Xcoder

30.2k757193

• 
  
  
  

  
  

  
  
  
  
  
  

  
  How are f and Ƈ used in Jelly? If I read it in the docs, both are filters. f is "Filter; remove the elements from x that are not in y." and Ƈ is "Filter (alias for Ðf). Keep all items that satisfy a condition.". Are they always used together? Is the Ƈ used to close the filter f? As in, is f...Ƈ similar to ʒ...} in 05AB1E? Or has the / ("Reduce or n-wise reduce.") have something to do with it? Just trying to understand the code, and I'm confused by the two different filter commands (and how both are used here). :)
  – Kevin Cruijssen
  Aug 16 at 11:44
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  @KevinCruijssen No, f and Ƈ are two completely separate things. You can think of f as intersection (given two lists, it returns their common elements) and Ƈ is like ʒ in 05AB1E. In short: Ã…Â’c returns all possible combinations of two elements from the list, then Ƈ only keeps those that satisfy the link (i.e. Jelly function) f/, which returns the intersection of the two items. But f is a dyad (two-argument function) and we need to apply it on a two-element list instead, so we have to use /, reduce.
  – Mr. Xcoder
  Aug 16 at 11:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Ah ok, that makes a lot more sense. I guess the term 'filter' for f in the docs, although correct, mainly confused me with the actual filter Ƈ being used. Your explanation of "given two lists, return their common elements" made it all clear. And I indeed had the feeling the / was used to convert Jelly's data somehow. Actually, I now see the section 6.6 Reducing in the Tutorial on the Jelly wiki that explains how it pops a dyad and pushes a reduced monad (basically 2 arguments vs a list of pairs as argument). Thanks, all clear now!
  – Kevin Cruijssen
  Aug 16 at 11:59
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

Jelly, 5 bytes

Œcf/Ƈ

Try it online!

share|improve this answer

answered Aug 16 at 7:39

Mr. Xcoder

30.2k757193

• 
  
  
  

  
  

  
  
  
  
  
  

  
  How are f and Ƈ used in Jelly? If I read it in the docs, both are filters. f is "Filter; remove the elements from x that are not in y." and Ƈ is "Filter (alias for Ðf). Keep all items that satisfy a condition.". Are they always used together? Is the Ƈ used to close the filter f? As in, is f...Ƈ similar to ʒ...} in 05AB1E? Or has the / ("Reduce or n-wise reduce.") have something to do with it? Just trying to understand the code, and I'm confused by the two different filter commands (and how both are used here). :)
  – Kevin Cruijssen
  Aug 16 at 11:44
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  @KevinCruijssen No, f and Ƈ are two completely separate things. You can think of f as intersection (given two lists, it returns their common elements) and Ƈ is like ʒ in 05AB1E. In short: Ã…Â’c returns all possible combinations of two elements from the list, then Ƈ only keeps those that satisfy the link (i.e. Jelly function) f/, which returns the intersection of the two items. But f is a dyad (two-argument function) and we need to apply it on a two-element list instead, so we have to use /, reduce.
  – Mr. Xcoder
  Aug 16 at 11:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Ah ok, that makes a lot more sense. I guess the term 'filter' for f in the docs, although correct, mainly confused me with the actual filter Ƈ being used. Your explanation of "given two lists, return their common elements" made it all clear. And I indeed had the feeling the / was used to convert Jelly's data somehow. Actually, I now see the section 6.6 Reducing in the Tutorial on the Jelly wiki that explains how it pops a dyad and pushes a reduced monad (basically 2 arguments vs a list of pairs as argument). Thanks, all clear now!
  – Kevin Cruijssen
  Aug 16 at 11:59
  
  

  
  
  
  

add a comment | 

up vote
1
down vote

up vote
1
down vote

Jelly, 5 bytes

Œcf/Ƈ

Try it online!

share|improve this answer

answered Aug 16 at 7:39

Mr. Xcoder

30.2k757193

Jelly, 5 bytes

Œcf/Ƈ

Try it online!

share|improve this answer

answered Aug 16 at 7:39

Mr. Xcoder

30.2k757193

share|improve this answer

share|improve this answer

answered Aug 16 at 7:39

Mr. Xcoder

30.2k757193

answered Aug 16 at 7:39

Mr. Xcoder

30.2k757193

answered Aug 16 at 7:39

Mr. Xcoder

30.2k757193

30.2k757193

• 
  
  
  

  
  

  
  
  
  
  
  

  
  How are f and Ƈ used in Jelly? If I read it in the docs, both are filters. f is "Filter; remove the elements from x that are not in y." and Ƈ is "Filter (alias for Ðf). Keep all items that satisfy a condition.". Are they always used together? Is the Ƈ used to close the filter f? As in, is f...Ƈ similar to ʒ...} in 05AB1E? Or has the / ("Reduce or n-wise reduce.") have something to do with it? Just trying to understand the code, and I'm confused by the two different filter commands (and how both are used here). :)
  – Kevin Cruijssen
  Aug 16 at 11:44
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  @KevinCruijssen No, f and Ƈ are two completely separate things. You can think of f as intersection (given two lists, it returns their common elements) and Ƈ is like ʒ in 05AB1E. In short: Ã…Â’c returns all possible combinations of two elements from the list, then Ƈ only keeps those that satisfy the link (i.e. Jelly function) f/, which returns the intersection of the two items. But f is a dyad (two-argument function) and we need to apply it on a two-element list instead, so we have to use /, reduce.
  – Mr. Xcoder
  Aug 16 at 11:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Ah ok, that makes a lot more sense. I guess the term 'filter' for f in the docs, although correct, mainly confused me with the actual filter Ƈ being used. Your explanation of "given two lists, return their common elements" made it all clear. And I indeed had the feeling the / was used to convert Jelly's data somehow. Actually, I now see the section 6.6 Reducing in the Tutorial on the Jelly wiki that explains how it pops a dyad and pushes a reduced monad (basically 2 arguments vs a list of pairs as argument). Thanks, all clear now!
  – Kevin Cruijssen
  Aug 16 at 11:59
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  How are f and Ƈ used in Jelly? If I read it in the docs, both are filters. f is "Filter; remove the elements from x that are not in y." and Ƈ is "Filter (alias for Ðf). Keep all items that satisfy a condition.". Are they always used together? Is the Ƈ used to close the filter f? As in, is f...Ƈ similar to ʒ...} in 05AB1E? Or has the / ("Reduce or n-wise reduce.") have something to do with it? Just trying to understand the code, and I'm confused by the two different filter commands (and how both are used here). :)
  – Kevin Cruijssen
  Aug 16 at 11:44
  
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  @KevinCruijssen No, f and Ƈ are two completely separate things. You can think of f as intersection (given two lists, it returns their common elements) and Ƈ is like ʒ in 05AB1E. In short: Ã…Â’c returns all possible combinations of two elements from the list, then Ƈ only keeps those that satisfy the link (i.e. Jelly function) f/, which returns the intersection of the two items. But f is a dyad (two-argument function) and we need to apply it on a two-element list instead, so we have to use /, reduce.
  – Mr. Xcoder
  Aug 16 at 11:49
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Ah ok, that makes a lot more sense. I guess the term 'filter' for f in the docs, although correct, mainly confused me with the actual filter Ƈ being used. Your explanation of "given two lists, return their common elements" made it all clear. And I indeed had the feeling the / was used to convert Jelly's data somehow. Actually, I now see the section 6.6 Reducing in the Tutorial on the Jelly wiki that explains how it pops a dyad and pushes a reduced monad (basically 2 arguments vs a list of pairs as argument). Thanks, all clear now!
  – Kevin Cruijssen
  Aug 16 at 11:59
  
  

  
  
  
  

How are f and Ƈ used in Jelly? If I read it in the docs, both are filters. f is "Filter; remove the elements from x that are not in y." and Ƈ is "Filter (alias for Ðf). Keep all items that satisfy a condition.". Are they always used together? Is the Ƈ used to close the filter f? As in, is f...Ƈ similar to ʒ...} in 05AB1E? Or has the / ("Reduce or n-wise reduce.") have something to do with it? Just trying to understand the code, and I'm confused by the two different filter commands (and how both are used here). :)
– Kevin Cruijssen
Aug 16 at 11:44

How are f and Ƈ used in Jelly? If I read it in the docs, both are filters. f is "Filter; remove the elements from x that are not in y." and Ƈ is "Filter (alias for Ðf). Keep all items that satisfy a condition.". Are they always used together? Is the Ƈ used to close the filter f? As in, is f...Ƈ similar to ʒ...} in 05AB1E? Or has the / ("Reduce or n-wise reduce.") have something to do with it? Just trying to understand the code, and I'm confused by the two different filter commands (and how both are used here). :)
– Kevin Cruijssen
Aug 16 at 11:44

2

2

@KevinCruijssen No, f and Ƈ are two completely separate things. You can think of f as intersection (given two lists, it returns their common elements) and Ƈ is like ʒ in 05AB1E. In short: Ã…Â’c returns all possible combinations of two elements from the list, then Ƈ only keeps those that satisfy the link (i.e. Jelly function) f/, which returns the intersection of the two items. But f is a dyad (two-argument function) and we need to apply it on a two-element list instead, so we have to use /, reduce.
– Mr. Xcoder
Aug 16 at 11:49

@KevinCruijssen No, f and Ƈ are two completely separate things. You can think of f as intersection (given two lists, it returns their common elements) and Ƈ is like ʒ in 05AB1E. In short: Ã…Â’c returns all possible combinations of two elements from the list, then Ƈ only keeps those that satisfy the link (i.e. Jelly function) f/, which returns the intersection of the two items. But f is a dyad (two-argument function) and we need to apply it on a two-element list instead, so we have to use /, reduce.
– Mr. Xcoder
Aug 16 at 11:49

Ah ok, that makes a lot more sense. I guess the term 'filter' for f in the docs, although correct, mainly confused me with the actual filter Ƈ being used. Your explanation of "given two lists, return their common elements" made it all clear. And I indeed had the feeling the / was used to convert Jelly's data somehow. Actually, I now see the section 6.6 Reducing in the Tutorial on the Jelly wiki that explains how it pops a dyad and pushes a reduced monad (basically 2 arguments vs a list of pairs as argument). Thanks, all clear now!
– Kevin Cruijssen
Aug 16 at 11:59

Ah ok, that makes a lot more sense. I guess the term 'filter' for f in the docs, although correct, mainly confused me with the actual filter Ƈ being used. Your explanation of "given two lists, return their common elements" made it all clear. And I indeed had the feeling the / was used to convert Jelly's data somehow. Actually, I now see the section 6.6 Reducing in the Tutorial on the Jelly wiki that explains how it pops a dyad and pushes a reduced monad (basically 2 arguments vs a list of pairs as argument). Thanks, all clear now!
– Kevin Cruijssen
Aug 16 at 11:59

add a comment | 

up vote
1
down vote

MATL, 13 bytes

2XN!"@Y:X&n?@

Try it online!

Not as bad as I expected given cell array input. Basically the same idea as @Doorknob's Ruby answer.

2XN % Get all combinations of 2 elements from the input
! % Transpose
" % Iterate over the columns (combinations)
@ % Push the current combination of edges
Y: % Split it out as two separate vectors
X&n % Get the number of intersecting elements between them
?@ % If that's non-zero, push the current combination on stack
 % Implicit loop end, valid combinations collect on the stack 
 % and are implicitly output at the end

share|improve this answer

edited Aug 16 at 16:19

answered Aug 16 at 15:53

sundar

4,656829

add a comment | 

up vote
1
down vote

MATL, 13 bytes

2XN!"@Y:X&n?@

Try it online!

Not as bad as I expected given cell array input. Basically the same idea as @Doorknob's Ruby answer.

2XN % Get all combinations of 2 elements from the input
! % Transpose
" % Iterate over the columns (combinations)
@ % Push the current combination of edges
Y: % Split it out as two separate vectors
X&n % Get the number of intersecting elements between them
?@ % If that's non-zero, push the current combination on stack
 % Implicit loop end, valid combinations collect on the stack 
 % and are implicitly output at the end

share|improve this answer

edited Aug 16 at 16:19

answered Aug 16 at 15:53

sundar

4,656829

add a comment | 

up vote
1
down vote

up vote
1
down vote

MATL, 13 bytes

2XN!"@Y:X&n?@

Try it online!

Not as bad as I expected given cell array input. Basically the same idea as @Doorknob's Ruby answer.

2XN % Get all combinations of 2 elements from the input
! % Transpose
" % Iterate over the columns (combinations)
@ % Push the current combination of edges
Y: % Split it out as two separate vectors
X&n % Get the number of intersecting elements between them
?@ % If that's non-zero, push the current combination on stack
 % Implicit loop end, valid combinations collect on the stack 
 % and are implicitly output at the end

share|improve this answer

edited Aug 16 at 16:19

answered Aug 16 at 15:53

sundar

4,656829

MATL, 13 bytes

2XN!"@Y:X&n?@

Try it online!

Not as bad as I expected given cell array input. Basically the same idea as @Doorknob's Ruby answer.

2XN % Get all combinations of 2 elements from the input
! % Transpose
" % Iterate over the columns (combinations)
@ % Push the current combination of edges
Y: % Split it out as two separate vectors
X&n % Get the number of intersecting elements between them
?@ % If that's non-zero, push the current combination on stack
 % Implicit loop end, valid combinations collect on the stack 
 % and are implicitly output at the end

share|improve this answer

edited Aug 16 at 16:19

answered Aug 16 at 15:53

sundar

4,656829

share|improve this answer

share|improve this answer

edited Aug 16 at 16:19

edited Aug 16 at 16:19

edited Aug 16 at 16:19

answered Aug 16 at 15:53

sundar

4,656829

answered Aug 16 at 15:53

sundar

4,656829

answered Aug 16 at 15:53

sundar

4,656829

4,656829

add a comment | 

add a comment | 

up vote
0
down vote

C (gcc), 173 bytes

Input i and output o are flat, null-terminated arrays. Output names can be up to 998 characters long before this will break.

#define M(x)o[n]=malloc(999),sprintf(o[n++],"%s%s",x[0],x[1])
f(i,o,j,n,m)char**i,**j,**o;(M(i),M(j));

Try it online!

share|improve this answer

answered Aug 16 at 6:06

Curtis Bechtel

29618

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Suggest *x instead of x[0] and int** instead of char**
  – ceilingcat
  Aug 20 at 17:31
  

  
  
  
  

add a comment | 

up vote
0
down vote

C (gcc), 173 bytes

Input i and output o are flat, null-terminated arrays. Output names can be up to 998 characters long before this will break.

#define M(x)o[n]=malloc(999),sprintf(o[n++],"%s%s",x[0],x[1])
f(i,o,j,n,m)char**i,**j,**o;(M(i),M(j));

Try it online!

share|improve this answer

answered Aug 16 at 6:06

Curtis Bechtel

29618

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Suggest *x instead of x[0] and int** instead of char**
  – ceilingcat
  Aug 20 at 17:31
  

  
  
  
  

add a comment | 

up vote
0
down vote

up vote
0
down vote

C (gcc), 173 bytes

Input i and output o are flat, null-terminated arrays. Output names can be up to 998 characters long before this will break.

#define M(x)o[n]=malloc(999),sprintf(o[n++],"%s%s",x[0],x[1])
f(i,o,j,n,m)char**i,**j,**o;(M(i),M(j));

Try it online!

share|improve this answer

answered Aug 16 at 6:06

Curtis Bechtel

29618

C (gcc), 173 bytes

Input i and output o are flat, null-terminated arrays. Output names can be up to 998 characters long before this will break.

#define M(x)o[n]=malloc(999),sprintf(o[n++],"%s%s",x[0],x[1])
f(i,o,j,n,m)char**i,**j,**o;(M(i),M(j));

Try it online!

share|improve this answer

answered Aug 16 at 6:06

Curtis Bechtel

29618

share|improve this answer

share|improve this answer

answered Aug 16 at 6:06

Curtis Bechtel

29618

answered Aug 16 at 6:06

Curtis Bechtel

29618

answered Aug 16 at 6:06

Curtis Bechtel

29618

29618

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Suggest *x instead of x[0] and int** instead of char**
  – ceilingcat
  Aug 20 at 17:31
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Suggest *x instead of x[0] and int** instead of char**
  – ceilingcat
  Aug 20 at 17:31
  

  
  
  
  

Suggest *x instead of x[0] and int** instead of char**
– ceilingcat
Aug 20 at 17:31

Suggest *x instead of x[0] and int** instead of char**
– ceilingcat
Aug 20 at 17:31

add a comment | 

up vote
0
down vote

Mathematica 23 bytes

EdgeList[LineGraph[#]]&

Example: g = Graph[1 <-> 2, 2 <-> 3, 3 <-> 4, 2 <-> 4 ]

EdgeList@LineGraph[g]

(*

2 <-> 1, 3 <-> 2, 4 <-> 1, 4 <-> 2, 4 <-> 3

*)

share|improve this answer

edited Aug 16 at 22:56

answered Aug 16 at 20:35

David G. Stork

1637

add a comment | 

up vote
0
down vote

Mathematica 23 bytes

EdgeList[LineGraph[#]]&

Example: g = Graph[1 <-> 2, 2 <-> 3, 3 <-> 4, 2 <-> 4 ]

EdgeList@LineGraph[g]

(*

2 <-> 1, 3 <-> 2, 4 <-> 1, 4 <-> 2, 4 <-> 3

*)

share|improve this answer

edited Aug 16 at 22:56

answered Aug 16 at 20:35

David G. Stork

1637

add a comment | 

up vote
0
down vote

up vote
0
down vote

Mathematica 23 bytes

EdgeList[LineGraph[#]]&

Example: g = Graph[1 <-> 2, 2 <-> 3, 3 <-> 4, 2 <-> 4 ]

EdgeList@LineGraph[g]

(*

2 <-> 1, 3 <-> 2, 4 <-> 1, 4 <-> 2, 4 <-> 3

*)

share|improve this answer

edited Aug 16 at 22:56

answered Aug 16 at 20:35

David G. Stork

1637

Mathematica 23 bytes

EdgeList[LineGraph[#]]&

Example: g = Graph[1 <-> 2, 2 <-> 3, 3 <-> 4, 2 <-> 4 ]

EdgeList@LineGraph[g]

(*

2 <-> 1, 3 <-> 2, 4 <-> 1, 4 <-> 2, 4 <-> 3

*)

share|improve this answer

edited Aug 16 at 22:56

answered Aug 16 at 20:35

David G. Stork

1637

share|improve this answer

share|improve this answer

edited Aug 16 at 22:56

edited Aug 16 at 22:56

edited Aug 16 at 22:56

answered Aug 16 at 20:35

David G. Stork

1637

answered Aug 16 at 20:35

David G. Stork

1637

answered Aug 16 at 20:35

David G. Stork

1637

1637

add a comment | 

add a comment | 

up vote
0
down vote

Pyth, 7 bytes

@F#.cQ2

Try it here!

If joining is necessary, 10 bytes

sMM@F#.cQ2

Try it here!

share|improve this answer

edited Aug 16 at 23:06

answered Aug 16 at 7:35

Mr. Xcoder

30.2k757193

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Your output does not have the required form. You need to string join the nodes.
  – DavidC
  Aug 16 at 23:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @DavidC I don't see why that would be needed and I cannot identify any portion of the challenge spefication that requires that, but I have added a version that joins them.
  – Mr. Xcoder
  Aug 16 at 23:07
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Joining was used in all of the test cases. In my case, joining cost 9 bytes. You were able to do it with just 3 additional bytes. Impressive!
  – DavidC
  Aug 16 at 23:12
  
  

  
  
  
  

add a comment | 

up vote
0
down vote

Pyth, 7 bytes

@F#.cQ2

Try it here!

If joining is necessary, 10 bytes

sMM@F#.cQ2

Try it here!

share|improve this answer

edited Aug 16 at 23:06

answered Aug 16 at 7:35

Mr. Xcoder

30.2k757193

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Your output does not have the required form. You need to string join the nodes.
  – DavidC
  Aug 16 at 23:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @DavidC I don't see why that would be needed and I cannot identify any portion of the challenge spefication that requires that, but I have added a version that joins them.
  – Mr. Xcoder
  Aug 16 at 23:07
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Joining was used in all of the test cases. In my case, joining cost 9 bytes. You were able to do it with just 3 additional bytes. Impressive!
  – DavidC
  Aug 16 at 23:12
  
  

  
  
  
  

add a comment | 

up vote
0
down vote

up vote
0
down vote

Pyth, 7 bytes

@F#.cQ2

Try it here!

If joining is necessary, 10 bytes

sMM@F#.cQ2

Try it here!

share|improve this answer

edited Aug 16 at 23:06

answered Aug 16 at 7:35

Mr. Xcoder

30.2k757193

Pyth, 7 bytes

@F#.cQ2

Try it here!

If joining is necessary, 10 bytes

sMM@F#.cQ2

Try it here!

share|improve this answer

edited Aug 16 at 23:06

answered Aug 16 at 7:35

Mr. Xcoder

30.2k757193

share|improve this answer

share|improve this answer

edited Aug 16 at 23:06

edited Aug 16 at 23:06

edited Aug 16 at 23:06

answered Aug 16 at 7:35

Mr. Xcoder

30.2k757193

answered Aug 16 at 7:35

Mr. Xcoder

30.2k757193

answered Aug 16 at 7:35

Mr. Xcoder

30.2k757193

30.2k757193

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Your output does not have the required form. You need to string join the nodes.
  – DavidC
  Aug 16 at 23:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @DavidC I don't see why that would be needed and I cannot identify any portion of the challenge spefication that requires that, but I have added a version that joins them.
  – Mr. Xcoder
  Aug 16 at 23:07
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Joining was used in all of the test cases. In my case, joining cost 9 bytes. You were able to do it with just 3 additional bytes. Impressive!
  – DavidC
  Aug 16 at 23:12
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Your output does not have the required form. You need to string join the nodes.
  – DavidC
  Aug 16 at 23:04
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @DavidC I don't see why that would be needed and I cannot identify any portion of the challenge spefication that requires that, but I have added a version that joins them.
  – Mr. Xcoder
  Aug 16 at 23:07
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Joining was used in all of the test cases. In my case, joining cost 9 bytes. You were able to do it with just 3 additional bytes. Impressive!
  – DavidC
  Aug 16 at 23:12
  
  

  
  
  
  

Your output does not have the required form. You need to string join the nodes.
– DavidC
Aug 16 at 23:04

Your output does not have the required form. You need to string join the nodes.
– DavidC
Aug 16 at 23:04

@DavidC I don't see why that would be needed and I cannot identify any portion of the challenge spefication that requires that, but I have added a version that joins them.
– Mr. Xcoder
Aug 16 at 23:07

@DavidC I don't see why that would be needed and I cannot identify any portion of the challenge spefication that requires that, but I have added a version that joins them.
– Mr. Xcoder
Aug 16 at 23:07

Joining was used in all of the test cases. In my case, joining cost 9 bytes. You were able to do it with just 3 additional bytes. Impressive!
– DavidC
Aug 16 at 23:12

Joining was used in all of the test cases. In my case, joining cost 9 bytes. You were able to do it with just 3 additional bytes. Impressive!
– DavidC
Aug 16 at 23:12

add a comment | 

up vote
0
down vote

Wolfram Language 64 53 bytes

""<>#&/@#&/@Select[#~Subsets~2,IntersectingQ@@#&]&

Finds all the input list's Subsets of length 2, Select those in which the nodes of one pair intersect with the nodes of another pair (indicating that the pairs share a node), and StringJoin the nodes for all selected pairs.

The code is especially difficult to read because it employs 4 nested pure (aka "anonymous") functions.

The code uses braces, "", as list delimiters, as is customary in Wolfram Language.

1 byte saved thanks to Mr. Xcoder.

---

Example

""<>#&/@#&/@Select[#~Subsets~2,IntersectingQ@@#&]&["1","2","1","3","1","4","2","5","3","4","4","5"]

(*"12", "13", "12", "14", "12", "25", "13", "14", "13", "34", "14", "34", "14", "45", "25", "45", "34", "45"*)

share|improve this answer

edited Aug 16 at 23:08

answered Aug 16 at 2:12

DavidC

23.5k243100

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Your current is actually 65 bytes, not 64. However, you can golf 1 byte with Select[#~Subsets~2,IntersectingQ@@#&]/.a_,b_:>""<>a,""<>b& – Try it online!
  – Mr. Xcoder
  Aug 16 at 7:29
  
  

  
  
  
  

add a comment | 

up vote
0
down vote

Wolfram Language 64 53 bytes

""<>#&/@#&/@Select[#~Subsets~2,IntersectingQ@@#&]&

Finds all the input list's Subsets of length 2, Select those in which the nodes of one pair intersect with the nodes of another pair (indicating that the pairs share a node), and StringJoin the nodes for all selected pairs.

The code is especially difficult to read because it employs 4 nested pure (aka "anonymous") functions.

The code uses braces, "", as list delimiters, as is customary in Wolfram Language.

1 byte saved thanks to Mr. Xcoder.

---

Example

""<>#&/@#&/@Select[#~Subsets~2,IntersectingQ@@#&]&["1","2","1","3","1","4","2","5","3","4","4","5"]

(*"12", "13", "12", "14", "12", "25", "13", "14", "13", "34", "14", "34", "14", "45", "25", "45", "34", "45"*)

share|improve this answer

edited Aug 16 at 23:08

answered Aug 16 at 2:12

DavidC

23.5k243100

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Your current is actually 65 bytes, not 64. However, you can golf 1 byte with Select[#~Subsets~2,IntersectingQ@@#&]/.a_,b_:>""<>a,""<>b& – Try it online!
  – Mr. Xcoder
  Aug 16 at 7:29
  
  

  
  
  
  

add a comment | 

up vote
0
down vote

up vote
0
down vote

Wolfram Language 64 53 bytes

""<>#&/@#&/@Select[#~Subsets~2,IntersectingQ@@#&]&

Finds all the input list's Subsets of length 2, Select those in which the nodes of one pair intersect with the nodes of another pair (indicating that the pairs share a node), and StringJoin the nodes for all selected pairs.

The code is especially difficult to read because it employs 4 nested pure (aka "anonymous") functions.

The code uses braces, "", as list delimiters, as is customary in Wolfram Language.

1 byte saved thanks to Mr. Xcoder.

---

Example

""<>#&/@#&/@Select[#~Subsets~2,IntersectingQ@@#&]&["1","2","1","3","1","4","2","5","3","4","4","5"]

(*"12", "13", "12", "14", "12", "25", "13", "14", "13", "34", "14", "34", "14", "45", "25", "45", "34", "45"*)

share|improve this answer

edited Aug 16 at 23:08

answered Aug 16 at 2:12

DavidC

23.5k243100

Wolfram Language 64 53 bytes

""<>#&/@#&/@Select[#~Subsets~2,IntersectingQ@@#&]&

Finds all the input list's Subsets of length 2, Select those in which the nodes of one pair intersect with the nodes of another pair (indicating that the pairs share a node), and StringJoin the nodes for all selected pairs.

The code is especially difficult to read because it employs 4 nested pure (aka "anonymous") functions.

The code uses braces, "", as list delimiters, as is customary in Wolfram Language.

1 byte saved thanks to Mr. Xcoder.

---

Example

""<>#&/@#&/@Select[#~Subsets~2,IntersectingQ@@#&]&["1","2","1","3","1","4","2","5","3","4","4","5"]

(*"12", "13", "12", "14", "12", "25", "13", "14", "13", "34", "14", "34", "14", "45", "25", "45", "34", "45"*)

share|improve this answer

edited Aug 16 at 23:08

answered Aug 16 at 2:12

DavidC

23.5k243100

share|improve this answer

share|improve this answer

edited Aug 16 at 23:08

edited Aug 16 at 23:08

edited Aug 16 at 23:08

answered Aug 16 at 2:12

DavidC

23.5k243100

answered Aug 16 at 2:12

DavidC

23.5k243100

answered Aug 16 at 2:12

DavidC

23.5k243100

23.5k243100

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Your current is actually 65 bytes, not 64. However, you can golf 1 byte with Select[#~Subsets~2,IntersectingQ@@#&]/.a_,b_:>""<>a,""<>b& – Try it online!
  – Mr. Xcoder
  Aug 16 at 7:29
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Your current is actually 65 bytes, not 64. However, you can golf 1 byte with Select[#~Subsets~2,IntersectingQ@@#&]/.a_,b_:>""<>a,""<>b& – Try it online!
  – Mr. Xcoder
  Aug 16 at 7:29
  
  

  
  
  
  

Your current is actually 65 bytes, not 64. However, you can golf 1 byte with Select[#~Subsets~2,IntersectingQ@@#&]/.a_,b_:>""<>a,""<>b& – Try it online!
– Mr. Xcoder
Aug 16 at 7:29

Your current is actually 65 bytes, not 64. However, you can golf 1 byte with Select[#~Subsets~2,IntersectingQ@@#&]/.a_,b_:>""<>a,""<>b& – Try it online!
– Mr. Xcoder
Aug 16 at 7:29

add a comment | 

up vote
0
down vote

Python 2, 109 bytes

lambda a:[(s,t)for Q in[[''.join(p)for p in a if x in p]for x in set(sum(a,()))]for s in Q for t in Q if s<t]

Try it online!

For each node x (discovered by making a set from the flattened list of edges), make a list of the pairs p that have x as a member; then, for each of those lists Q, find the unique, distinct pairings within Q (uniqueness/distinction is enforced via if s<t).

share|improve this answer

edited Aug 17 at 4:25

answered Aug 17 at 2:33

Chas Brown

4,1361319

add a comment | 

up vote
0
down vote

Python 2, 109 bytes

lambda a:[(s,t)for Q in[[''.join(p)for p in a if x in p]for x in set(sum(a,()))]for s in Q for t in Q if s<t]

Try it online!

For each node x (discovered by making a set from the flattened list of edges), make a list of the pairs p that have x as a member; then, for each of those lists Q, find the unique, distinct pairings within Q (uniqueness/distinction is enforced via if s<t).

share|improve this answer

edited Aug 17 at 4:25

answered Aug 17 at 2:33

Chas Brown

4,1361319

add a comment | 

up vote
0
down vote

up vote
0
down vote

Python 2, 109 bytes

lambda a:[(s,t)for Q in[[''.join(p)for p in a if x in p]for x in set(sum(a,()))]for s in Q for t in Q if s<t]

Try it online!

For each node x (discovered by making a set from the flattened list of edges), make a list of the pairs p that have x as a member; then, for each of those lists Q, find the unique, distinct pairings within Q (uniqueness/distinction is enforced via if s<t).

share|improve this answer

edited Aug 17 at 4:25

answered Aug 17 at 2:33

Chas Brown

4,1361319

Python 2, 109 bytes

lambda a:[(s,t)for Q in[[''.join(p)for p in a if x in p]for x in set(sum(a,()))]for s in Q for t in Q if s<t]

Try it online!

For each node x (discovered by making a set from the flattened list of edges), make a list of the pairs p that have x as a member; then, for each of those lists Q, find the unique, distinct pairings within Q (uniqueness/distinction is enforced via if s<t).

share|improve this answer

edited Aug 17 at 4:25

answered Aug 17 at 2:33

Chas Brown

4,1361319

share|improve this answer

share|improve this answer

edited Aug 17 at 4:25

edited Aug 17 at 4:25

edited Aug 17 at 4:25

answered Aug 17 at 2:33

Chas Brown

4,1361319

answered Aug 17 at 2:33

Chas Brown

4,1361319

answered Aug 17 at 2:33

Chas Brown

4,1361319

4,1361319

add a comment | 

add a comment | 

up vote
0
down vote

C# 233 bytes

static void c(List<(string a,string b)>i,List<(string,string)>o)for(int m=0;m<i.Count;m++)for(int n=m+1;n<i.Count;n++)(i[n].a+i[n].b).Contains(i[m].b))o.Add((i[m].a+i[m].b,i[n].a+i[n].b));

Example

using System;
using System.Collections.Generic;

namespace conjugateGraphGolf

 class Program
 
 static void Main()
 
 List<(string a, string b)> inputs = new List<(string, string)>
 
 new List<(string, string)>(),
 new List<(string, string)>() ("0", "1"),
 new List<(string, string)>() ("0", "1"),("1", "2"),
 new List<(string, string)>() ("a","b"),("b","c"),("c","a"),
 new List<(string, string)>() ("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")
 ;

 List<(string, string)> output = new List<(string, string)>();

 for(int i = 0; i < inputs.Length; i++)
 
 output.Clear();
 c(inputs[i], output);

 WriteList(inputs[i]);
 Console.Write(" -> ");
 WriteList(output);
 Console.Write("rnrn");
 

 Console.ReadKey(true);
 

 static void c(List<(string a,string b)>i,List<(string,string)>o)for(int m=0;m<i.Count;m++)for(int n=m+1;n<i.Count;n++)(i[n].a+i[n].b).Contains(i[m].b))o.Add((i[m].a+i[m].b,i[n].a+i[n].b));

 public static void WriteList(List<(string a, string b)> list)
 
 Console.Write("[");
 for(int i = 0; i < list.Count; i++)
 
 Console.Write($"("list[i].a","list[i].b")(i == list.Count - 1 ? "" : ",")");
 
 Console.Write("]");
 
 

share|improve this answer

answered Aug 17 at 10:04

Robin B

1012

add a comment | 

up vote
0
down vote

C# 233 bytes

static void c(List<(string a,string b)>i,List<(string,string)>o)for(int m=0;m<i.Count;m++)for(int n=m+1;n<i.Count;n++)(i[n].a+i[n].b).Contains(i[m].b))o.Add((i[m].a+i[m].b,i[n].a+i[n].b));

Example

using System;
using System.Collections.Generic;

namespace conjugateGraphGolf

 class Program
 
 static void Main()
 
 List<(string a, string b)> inputs = new List<(string, string)>
 
 new List<(string, string)>(),
 new List<(string, string)>() ("0", "1"),
 new List<(string, string)>() ("0", "1"),("1", "2"),
 new List<(string, string)>() ("a","b"),("b","c"),("c","a"),
 new List<(string, string)>() ("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")
 ;

 List<(string, string)> output = new List<(string, string)>();

 for(int i = 0; i < inputs.Length; i++)
 
 output.Clear();
 c(inputs[i], output);

 WriteList(inputs[i]);
 Console.Write(" -> ");
 WriteList(output);
 Console.Write("rnrn");
 

 Console.ReadKey(true);
 

 static void c(List<(string a,string b)>i,List<(string,string)>o)for(int m=0;m<i.Count;m++)for(int n=m+1;n<i.Count;n++)(i[n].a+i[n].b).Contains(i[m].b))o.Add((i[m].a+i[m].b,i[n].a+i[n].b));

 public static void WriteList(List<(string a, string b)> list)
 
 Console.Write("[");
 for(int i = 0; i < list.Count; i++)
 
 Console.Write($"("list[i].a","list[i].b")(i == list.Count - 1 ? "" : ",")");
 
 Console.Write("]");
 
 

share|improve this answer

answered Aug 17 at 10:04

Robin B

1012

add a comment | 

up vote
0
down vote

up vote
0
down vote

C# 233 bytes

static void c(List<(string a,string b)>i,List<(string,string)>o)for(int m=0;m<i.Count;m++)for(int n=m+1;n<i.Count;n++)(i[n].a+i[n].b).Contains(i[m].b))o.Add((i[m].a+i[m].b,i[n].a+i[n].b));

Example

using System;
using System.Collections.Generic;

namespace conjugateGraphGolf

 class Program
 
 static void Main()
 
 List<(string a, string b)> inputs = new List<(string, string)>
 
 new List<(string, string)>(),
 new List<(string, string)>() ("0", "1"),
 new List<(string, string)>() ("0", "1"),("1", "2"),
 new List<(string, string)>() ("a","b"),("b","c"),("c","a"),
 new List<(string, string)>() ("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")
 ;

 List<(string, string)> output = new List<(string, string)>();

 for(int i = 0; i < inputs.Length; i++)
 
 output.Clear();
 c(inputs[i], output);

 WriteList(inputs[i]);
 Console.Write(" -> ");
 WriteList(output);
 Console.Write("rnrn");
 

 Console.ReadKey(true);
 

 static void c(List<(string a,string b)>i,List<(string,string)>o)for(int m=0;m<i.Count;m++)for(int n=m+1;n<i.Count;n++)(i[n].a+i[n].b).Contains(i[m].b))o.Add((i[m].a+i[m].b,i[n].a+i[n].b));

 public static void WriteList(List<(string a, string b)> list)
 
 Console.Write("[");
 for(int i = 0; i < list.Count; i++)
 
 Console.Write($"("list[i].a","list[i].b")(i == list.Count - 1 ? "" : ",")");
 
 Console.Write("]");
 
 

share|improve this answer

answered Aug 17 at 10:04

Robin B

1012

C# 233 bytes

static void c(List<(string a,string b)>i,List<(string,string)>o)for(int m=0;m<i.Count;m++)for(int n=m+1;n<i.Count;n++)(i[n].a+i[n].b).Contains(i[m].b))o.Add((i[m].a+i[m].b,i[n].a+i[n].b));

Example

using System;
using System.Collections.Generic;

namespace conjugateGraphGolf

 class Program
 
 static void Main()
 
 List<(string a, string b)> inputs = new List<(string, string)>
 
 new List<(string, string)>(),
 new List<(string, string)>() ("0", "1"),
 new List<(string, string)>() ("0", "1"),("1", "2"),
 new List<(string, string)>() ("a","b"),("b","c"),("c","a"),
 new List<(string, string)>() ("1","2"),("1","3"),("1","4"),("2","5"),("3","4"),("4","5")
 ;

 List<(string, string)> output = new List<(string, string)>();

 for(int i = 0; i < inputs.Length; i++)
 
 output.Clear();
 c(inputs[i], output);

 WriteList(inputs[i]);
 Console.Write(" -> ");
 WriteList(output);
 Console.Write("rnrn");
 

 Console.ReadKey(true);
 

 static void c(List<(string a,string b)>i,List<(string,string)>o)for(int m=0;m<i.Count;m++)for(int n=m+1;n<i.Count;n++)(i[n].a+i[n].b).Contains(i[m].b))o.Add((i[m].a+i[m].b,i[n].a+i[n].b));

 public static void WriteList(List<(string a, string b)> list)
 
 Console.Write("[");
 for(int i = 0; i < list.Count; i++)
 
 Console.Write($"("list[i].a","list[i].b")(i == list.Count - 1 ? "" : ",")");
 
 Console.Write("]");
 
 

share|improve this answer

answered Aug 17 at 10:04

Robin B

1012

share|improve this answer

share|improve this answer

answered Aug 17 at 10:04

Robin B

1012

answered Aug 17 at 10:04

Robin B

1012

answered Aug 17 at 10:04

Robin B

1012

1012

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f170695%2fconstruct-a-line-graph-conjugate-graph%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email