Construct a line graph / conjugate graph

Question

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

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, Commented Aug 16, 2018 at 8:04
Further to Peter Taylor's comment, can we assume that the vertex names are all 1-character long in the input? — Sundar R, Commented Aug 16, 2018 at 15:32

Sundar R · Accepted Answer · 2018-08-17 18:32:03Z

4

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

edited Aug 17, 2018 at 18:32

answered Aug 16, 2018 at 15:22

Sundar R

6,62219 silver badges33 bronze badges

\$\begingroup\$ You can use the constrained variable Ċ (couple) instead of l₂ to save one byte. \$\endgroup\$
– Fatalize
Commented Aug 17, 2018 at 7:06

Add a comment |

ngn · Accepted Answer · 2023-04-22 04:19:46Z

K (ngn/k), 45 39 33 29 30 35 and five years later: 31 bytes

(*'<:')#(3=#'?',/')#+{x@!2##x}@

Try it online!

{ }@ apply a function with implicit argument x

#x length

2# repeat twice

!2##x pairs of indices in x (the columns of a 2 by #x matrix)

x@ index into x

+ transpose

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

Doorknob · Accepted Answer · 2018-08-16 01:10:34Z

2

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.

answered Aug 16, 2018 at 1:10

Doorknob

71.7k20 gold badges143 silver badges385 bronze badges

Add a comment |

Mr. Xcoder · Accepted Answer · 2018-08-16 07:39:30Z

2

Jelly, 5 bytes

Œcf/Ƈ

Try it online!

answered Aug 16, 2018 at 7:39

Mr. Xcoder

42.5k9 gold badges81 silver badges214 bronze badges

\$\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
Commented Aug 16, 2018 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
Commented Aug 16, 2018 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
Commented Aug 16, 2018 at 11:59

Add a comment |

Neil · Accepted Answer · 2018-08-16 09:13:46Z

2

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

answered Aug 16, 2018 at 9:13

Neil

177k12 gold badges74 silver badges281 bronze badges

\$\begingroup\$ What makes Firefox 30-57 special for this answer? \$\endgroup\$
– Night2
Commented Aug 16, 2018 at 10:47
1

\$\begingroup\$ @Night2 The array comprehension syntax was only supported in those versions of Firefox. \$\endgroup\$
– Neil
Commented Aug 16, 2018 at 10:49

Add a comment |

crb233 · Accepted Answer · 2018-08-16 06:06:39Z

1

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!

answered Aug 16, 2018 at 6:06

crb233

6413 silver badges10 bronze badges

1

\$\begingroup\$ 163 bytes \$\endgroup\$
– ceilingcat
Commented Sep 3, 2022 at 17:56

Add a comment |

Sundar R · Accepted Answer · 2018-08-16 16:19:49Z

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

David G. Stork · Accepted Answer · 2018-08-16 22:56:37Z

1

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}

*)

edited Aug 16, 2018 at 22:56

answered Aug 16, 2018 at 20:35

David G. Stork

2411 silver badge11 bronze badges

Add a comment |

Chas Brown · Accepted Answer · 2018-08-17 04:25:17Z

1

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

edited Aug 17, 2018 at 4:25

answered Aug 17, 2018 at 2:33

Chas Brown

9,7571 gold badge13 silver badges39 bronze badges

Add a comment |

138 Aspen · Accepted Answer · 2023-04-22 08:08:20Z

Scala, 145 bytes

Modified from @Doorknob's Ruby answer.

Golfed version. Try it online!

def f(a:Seq[Seq[String]])=a.combinations(2).foreach{case List(x,y)=>if(x.intersect(y).nonEmpty)println(s"[${x.mkString("")},${y.mkString("")}]")}

Ungolfed version. Try it online!

object Main {
  def main(args: Array[String]): Unit = {
    val f: List[List[String]] => Unit = (a: List[List[String]]) => {
      a.combinations(2).foreach { case List(x, y) =>
        if (x.intersect(y).nonEmpty) println(s"[${x.mkString("")}, ${y.mkString("")}]")
      }
    }

    val inputList: List[List[List[String]]] = List(
      List(),
      List(List("0", "1")),
      List(List("0", "1"), List("1", "2")),
      List(List("a", "b"), List("b", "c"), List("c", "a")),
      List(List("1", "2"), List("1", "3"), List("1", "4"), List("2", "5"), List("3", "4"), List("4", "5"))
    )

    inputList.foreach { arr =>
      println(s"Input: $arr")
      println("Output:")
      f(arr)
      println()
    }
  }
}

alephalpha · Accepted Answer · 2023-08-14 09:05:50Z

1

Nekomata, 8 bytes

S:đ∩z¿ᵐj

Attempt This Online!

A port of @Sundar R's Brachylog answer

S:đ∩z¿ᵐj
S           Find a subset of the input
 :   ¿      Check that:
  đ             the subset has exactly two elements
   ∩            and the intersection of the two elements
    z           has exactly one element
      ᵐj    Join each element of the subset

Nekomata will find all solutions, which are all the edges of the edge graph.

edited Aug 14, 2023 at 9:05

answered Aug 9, 2023 at 2:20

alephalpha

50k7 gold badges68 silver badges182 bronze badges

Add a comment |

Mr. Xcoder · Accepted Answer · 2018-08-16 23:06:52Z

0

Pyth, 7 bytes

@F#.cQ2

Try it here!

If joining is necessary, 10 bytes

sMM@F#.cQ2

Try it here!

edited Aug 16, 2018 at 23:06

answered Aug 16, 2018 at 7:35

Mr. Xcoder

42.5k9 gold badges81 silver badges214 bronze badges

\$\begingroup\$ Your output does not have the required form. You need to string join the nodes. \$\endgroup\$
– DavidC
Commented Aug 16, 2018 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
Commented Aug 16, 2018 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
Commented Aug 16, 2018 at 23:12

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

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"}}*)

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 16, 2018 at 2:12

DavidC

25.4k2 gold badges52 silver badges105 bronze badges

\$\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
Commented Aug 16, 2018 at 7:29

Add a comment |

Amelia B · Accepted Answer · 2018-08-17 10:04:49Z

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("]");
        }
    }
}

Stack Exchange Network

Construct a line graph / conjugate graph

Introduction

Challenge

Input

Output

Test Cases

14 Answers 14

Brachylog, 13 bytes

K (ngn/k), 45 39 33 29 30 35 and five years later: 31 bytes

Ruby, 51 bytes

Jelly, 5 bytes

JavaScript (Firefox 30-57), 77 bytes

C (gcc), 173 bytes

MATL, 13 bytes

Mathematica 23 bytes

Python 2, 109 bytes

Scala, 145 bytes

Nekomata, 8 bytes

Pyth, 7 bytes

If joining is necessary, 10 bytes

Wolfram Language 64 53 bytes

C# 233 bytes

Example

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
math
graph-theory
or ask your own question.

Hot Network Questions

Construct a line graph / conjugate graph

Introduction

Challenge

Input

Output

Test Cases

14 Answers 14

Brachylog, 13 bytes

K (ngn/k), 45 39 33 29 30 35 and five years later: 31 bytes

Ruby, 51 bytes

Jelly, 5 bytes

JavaScript (Firefox 30-57), 77 bytes

C (gcc), 173 bytes

MATL, 13 bytes

Mathematica 23 bytes

Python 2, 109 bytes

Scala, 145 bytes

Nekomata, 8 bytes

Pyth, 7 bytes

If joining is necessary, 10 bytes

Wolfram Language 64 53 bytes

C# 233 bytes

Example

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
code-golf
math
graph-theory
or ask your own question.