Introducción

Dado un gráfico G no dirigido, podemos construir un gráfico L (G) (llamado gráfico lineal o gráfico conjugado) que representa las conexiones entre los bordes en G. Esto se hace creando un nuevo vértice en L (G) para cada borde en G y conectando estos vértices si los bordes que representan tienen un vértice en común.

Aquí hay un ejemplo de Wikipedia que muestra la construcción de un gráfico lineal (en verde).

Como otro ejemplo, tome este gráfico G con vértices A, B, C y D.

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

Creamos un nuevo vértice para cada borde en G. En este caso, el borde entre A y C está representado por un nuevo vértice llamado AC.

   AC

 BC  CD  DE

Y conecte los vértices cuando los bordes que representan tienen un vértice en común. En este caso, los bordes de A a C y de B a C tienen el vértice C en común, por lo que los vértices AC y BC están conectados.

   AC
  /  \
 BC--CD--DE

Este nuevo gráfico es el gráfico lineal de G!

Ver Wikipedia para más información.

Desafío

Dada la lista de adyacencia para un gráfico G, su programa debe imprimir o devolver la lista de adyacencia para el gráfico lineal L (G). Este es el código de golf, por lo que gana la respuesta con la menor cantidad de bytes.

Entrada

Una lista de pares de cadenas que representan los bordes de G. Cada par describe los vértices que están conectados por ese borde.

• Se garantiza que cada par (X, Y) es único, lo que significa que la lista no contendrá (Y, X) o un segundo (X, Y).

Por ejemplo:

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

Salida

Una lista de pares de cadenas que representan los bordes de L (G). Cada par describe los vértices que están conectados por ese borde.

• Cada par (X, Y) debe ser único, lo que significa que la lista no contendrá (Y, X) o un segundo (X, Y).

• Para cualquier borde (X, Y) en G, el vértice que crea en L (G) debe llamarse XY (los nombres se concatenan juntos en el mismo orden en que se especifican en la entrada).

Por ejemplo:

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

Casos de prueba

[] -> []

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

Ruby, 51 bytes

->a{a.combination(2){|x,y|p [x*'',y*'']if(x&y)[0]}}

Pruébalo en línea!

Para cada combinación de dos aristas, si tienen un vértice en común (es decir, si el primer elemento de su intersección no es nil), imprima una matriz que contenga las dos aristas en STDOUT.

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

Asume que todas las entradas son letras simples (bueno, cualquier carácter único que no sea ^y ]).

Brachylog , 13 bytes

{⊇Ċ.c¬≠∧}ᶠcᵐ²

Pruébalo en línea!

Con todos los casos de prueba

(-1 byte reemplazado l₂por Ċ, gracias a @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

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

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

Pruébalo en línea!

,:' envolver cada borde en una lista de 1 elemento

{ }@ aplicar una función con argumento implícito x

x,/:\:xconcatene cada una de las izquierdas xcon cada una de las derechas x, obtenga una matriz de resultados: todos los pares de aristas

,/ aplanar la matriz

( )# filtrar

(3=#?,/)#filtra solo aquellos pares cuya concatenación ( ,/) tiene un recuento ( #) de exactamente 3 ?elementos únicos ( )

Esto elimina bordes como ("ab";"ab")y ("ab";"cd")de la lista.

(*>)#filtra solo aquellos pares cuya permutación de clasificación descendente ( >) comienza con (* ) a 1 (no 0 es verdadero booleano)

En nuestro caso, la permutación descendente podría ser 0 1o 1 0.

Jalea , 5 bytes

Œcf/Ƈ

Pruébalo en línea!

MATL , 13 bytes

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

Pruébalo en línea!

No es tan malo como esperaba dada la entrada de matriz de celdas. Básicamente la misma idea que la respuesta de Ruby de @ Doorknob .

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

C (gcc) , 173 bytes

La entrada iy la salida oson matrices planas con terminación nula. Los nombres de salida pueden tener hasta 998 caracteres mucho antes de que esto se rompa.

#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));}

Pruébalo en línea!

Mathematica 23 bytes

EdgeList[LineGraph[#]]&

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

EdgeList@LineGraph[g]

(*

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

*)

Pyth , 7 bytes

@F#.cQ2

Pruébalo aquí!

Si es necesario unirse, 10 bytes

sMM@F#.cQ2

Pruébalo aquí!

Wolfram Language 64 53 bytes

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

Encuentra todas las listas de entrada Subsetde longitud 2, Selectaquellas en las que los nodos de un par se cruzan con los nodos de otro par (lo que indica que los pares comparten un nodo), yStringJoin los nodos para todos los pares seleccionados.

El código es especialmente difícil de leer porque emplea 4 anidados puros ( también conocidos como funciones "anónimas").

El código usa llaves, "{}", como delimitadores de lista, como es habitual en Wolfram Language.

1 byte guardado gracias al Sr. Xcoder.

Ejemplo

""<>#&/@#&/@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"}}*)

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]

Pruébalo en línea!

Para cada nodo x(descubierto haciendo un conjunto de la lista aplanada de bordes), haga una lista de los pares pque tienen xcomo miembro; luego, para cada una de esas listas Q, encuentre los pares únicos y distintos dentro Q(la unicidad / distinción se aplica a través de if s<t).

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));}}}}

Ejemplo

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