8
\$\begingroup\$

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

The graph G New vertices representing each edge in G Vertices are connected when their edges in G are connected The line graph L(G)

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")]
\$\endgroup\$
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – Peter Taylor Aug 16 '18 at 8:04
  • 2
    \$\begingroup\$ Further to Peter Taylor's comment, can we assume that the vertex names are all 1-character long in the input? \$\endgroup\$ – sundar Aug 16 '18 at 15:32

12 Answers 12

2
\$\begingroup\$

Ruby, 51 bytes

->a{a.combination(2){|x,y|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.

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

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

\$\endgroup\$
  • \$\begingroup\$ What makes Firefox 30-57 special for this answer? \$\endgroup\$ – Night2 Aug 16 '18 at 10:47
  • 1
    \$\begingroup\$ @Night2 The array comprehension syntax was only supported in those versions of Firefox. \$\endgroup\$ – Neil Aug 16 '18 at 10:49
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ You can use the constrained variable Ċ (couple) instead of l₂ to save one byte. \$\endgroup\$ – Fatalize Aug 17 '18 at 7:06
2
\$\begingroup\$

K (ngn/k), 45 39 33 29 30 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.

\$\endgroup\$
1
\$\begingroup\$

Jelly, 5 bytes

Œcf/Ƈ

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 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). :) \$\endgroup\$ – Kevin Cruijssen Aug 16 '18 at 11:44
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – Mr. Xcoder Aug 16 '18 at 11:49
  • \$\begingroup\$ 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! \$\endgroup\$ – Kevin Cruijssen Aug 16 '18 at 11:59
1
\$\begingroup\$

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

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;{for(n=0;*i;i+=2)for(j=i;*(j+=2);)for(m=4;m--;)strcmp(i[m/2],j[m%2])||(M(i),M(j));}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Suggest *x instead of x[0] and int** instead of char** \$\endgroup\$ – ceilingcat Aug 20 '18 at 17:31
0
\$\begingroup\$

Mathematica 23 bytes

EdgeList[LineGraph[#]]&

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

enter image description here

EdgeList@LineGraph[g]

(*

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

*)

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

Pyth, 7 bytes

@F#.cQ2

Try it here!

If joining is necessary, 10 bytes

sMM@F#.cQ2

Try it here!

\$\endgroup\$
  • \$\begingroup\$ Your output does not have the required form. You need to string join the nodes. \$\endgroup\$ – DavidC Aug 16 '18 at 23:04
  • \$\begingroup\$ @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. \$\endgroup\$ – Mr. Xcoder Aug 16 '18 at 23:07
  • \$\begingroup\$ 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! \$\endgroup\$ – DavidC Aug 16 '18 at 23:12
0
\$\begingroup\$

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"}}*)
\$\endgroup\$
  • \$\begingroup\$ 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! \$\endgroup\$ – Mr. Xcoder Aug 16 '18 at 7:29
0
\$\begingroup\$

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

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

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++){if((i[n].a+i[n].b).Contains(i[m].a)||(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("\r\n\r\n");
            }

            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++){if((i[n].a+i[n].b).Contains(i[m].a)||(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("]");
        }
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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