Construir um gráfico de linhas / gráfico conjugado

8

Introdução

Dado um gráfico não direcionado G, podemos construir um gráfico L (G) (chamado gráfico de linhas ou gráfico conjugado) que representa as conexões entre as arestas em G. Isso é feito criando um novo vértice em L (G) para cada aresta em G e conectando esses vértices se as arestas que eles representam têm um vértice em comum.

Aqui está um exemplo da Wikipedia mostrando a construção de um gráfico de linhas (em verde).

O gráfico G Novos vértices representando cada aresta em G Os vértices são conectados quando suas arestas em G são conectadas O gráfico de linhas L (G)

Como outro exemplo, considere este gráfico G com os vértices A, B, C e D.

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

Criamos um novo vértice para cada aresta em G. Nesse caso, a aresta entre A e C é representada por um novo vértice chamado AC.

   AC

 BC  CD  DE

E conecte os vértices quando as arestas que eles representam têm um vértice em comum. Nesse caso, as arestas de A a C e de B a C têm o vértice C em comum; portanto, os vértices AC e BC são conectados.

   AC
  /  \
 BC--CD--DE

Este novo gráfico é o gráfico de linhas do G!

Veja a Wikipedia para mais informações.

Desafio

Dada a lista de adjacência para um gráfico G, seu programa deve imprimir ou retornar a lista de adjacência para o gráfico de linha L (G). Isso é código-golfe, então a resposta com o menor número de bytes vence!

Entrada

Uma lista de pares de strings representando as arestas de G. Cada par descreve os vértices conectados por essa aresta.

  • Cada par (X, Y) é garantido como único, o que significa que a lista não conterá (Y, X) ou um segundo (X, Y).

Por exemplo:

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

Resultado

Uma lista de pares de cadeias representando as arestas de L (G). Cada par descreve os vértices conectados por essa borda.

  • Cada par (X, Y) deve ser único, o que significa que a lista não conterá (Y, X) ou um segundo (X, Y).

  • Para qualquer aresta (X, Y) em G, o vértice criado em L (G) deve ser nomeado XY (os nomes são concatenados juntos na mesma ordem em que foram especificados na entrada).

Por exemplo:

[("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 teste

[] -> []

[("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")]
Curtis Bechtel
fonte
4
Não vejo nada na pergunta descartando uma entrada como [("1","23"),("23","4"),("12","3"),("3","4")], para a qual a saída deva ser presumivelmente [("123","234"),("123","34")], que não possa ser corretamente interpretada. Eu acho que a única maneira de corrigir isso é editar, garantindo que a entrada nunca contenha essas ambiguidades, mas se essa pergunta tivesse sido postada na sandbox , eu sugeriria ser menos prescritivo sobre a nomeação de vértices na saída.
22418 Peter Taylor
2
Além do comentário de Peter Taylor, podemos supor que os nomes dos vértices tenham todos 1 caractere na entrada?
sundar - Restabelece Monica

Respostas:

2

Ruby, 51 bytes

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

Experimente online!

Para cada combinação de duas arestas, se elas tiverem um vértice em comum (por exemplo, se o primeiro elemento de sua interseção for não- nil), imprima uma matriz contendo as duas arestas em STDOUT.

Maçaneta da porta
fonte
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]]

Assume que todas as entradas são letras únicas (bem, qualquer caractere único que não seja ^e ]).

Neil
fonte
O que torna o Firefox 30-57 especial para esta resposta?
precisa saber é o seguinte
1
@ Night2 A sintaxe de compreensão da matriz era suportada apenas nessas versões do Firefox.
Neil
2

Braquilog , 13 bytes

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

Experimente online!

Com todos os casos de teste

(-1 byte substituindo l₂por Ċ, graças 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
sundar - Restabelecer Monica
fonte
Você pode usar a variável restrita Ċ(casal) em vez de l₂salvar um byte.
Fatalize 17/08/19
2

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

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

Experimente online!

,:' agrupar cada aresta em uma lista de 1 elemento

{ }@ aplicar uma função com argumento implícito x

x,/:\:xconcatene cada esquerda xe direita x, obtenha uma matriz de resultados - todos os pares de arestas

,/ achatar a matriz

( )# filtro

(3=#?,/)#filtre apenas os pares cuja concatenação ( ,/) tenha uma contagem ( #) de exatamente 3 ?elementos únicos ( )

Isso remove as arestas como ("ab";"ab")e ("ab";"cd")da lista.

(*>)#filtre apenas os pares cuja permutação decrescente de classificação ( >) começa com ( *) a 1 (não 0 é booleano verdadeiro)

No nosso caso, a permutação de ordenação descendente pode ser 0 1ou 1 0.

ngn
fonte
1

Gelatina , 5 bytes

Œcf/Ƈ

Experimente online!

Mr. Xcoder
fonte
Como são fe Ƈutilizados no Jelly? Se eu li nos documentos, ambos são filtros. fé " Filtro; remova os elementos de x que não estão em y " e Ƈé " Filtro (alias de Ðf). Mantenha todos os itens que atendem a uma condição. ". Eles sempre são usados ​​juntos? É Ƈusado para fechar o filtro f? Como em, é f...Ƈsemelhante ʒ...}em 05AB1E? Ou o /(" Reduzir ou reduzir em sentido n " . ) Tem algo a ver com isso? Apenas tentando entender o código, estou confuso com os dois comandos de filtro diferentes (e como os dois são usados ​​aqui). :)
Kevin Cruijssen
2
@KevinCruijssen Não, fe Ƈsão duas coisas completamente separadas. Você pode pensar fem interseção (com duas listas, ele retorna seus elementos comuns) e Ƈé como ʒem 05AB1E. Resumindo: Œcretorna todas as combinações possíveis de dois elementos da lista e depois Ƈmantém apenas aqueles que satisfazem o link (por exemplo, função Jelly) f/, que retorna a interseção dos dois itens. Mas fé uma díade (função de dois argumentos) e, em vez disso, precisamos aplicá-la em uma lista de dois elementos; portanto, temos que usar /, reduzir.
Xcoder
Ah, ok, isso faz muito mais sentido. Eu acho que o termo 'filtro' para fos documentos, embora correto, principalmente me confundiu com o filtro real Ƈsendo usado. Sua explicação sobre " dadas duas listas, retorne seus elementos comuns " deixou tudo claro. E, de fato, tive a sensação de que /foi usado para converter os dados de Jelly de alguma forma. Na verdade, agora vejo a seção 6.6 Reduzindo no Tutorial no wiki do Jelly, que explica como ele exibe uma díade e empurra uma mônada reduzida (basicamente 2 argumentos versus uma lista de pares como argumento). Obrigado, tudo claro agora!
Kevin Cruijssen
1

MATL , 13 bytes

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

Experimente online!

Não é tão ruim quanto eu esperava, dada a entrada da matriz de células. Basicamente, a mesma ideia da resposta Ruby da @ 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
sundar - Restabelecer Monica
fonte
0

C (gcc) , 173 bytes

Entrada ie saída osão matrizes simples e terminadas em nulo. Os nomes de saída podem ter até 998 caracteres antes que isso ocorra.

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

Experimente online!

Curtis Bechtel
fonte
Sugerir em *xvez de x[0]e em int**vez dechar**
tetocat
0

Mathematica 23 bytes

EdgeList[LineGraph[#]]&

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

insira a descrição da imagem aqui

EdgeList@LineGraph[g]

(*

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

*)

David G. Stork
fonte
0

Pitão , 7 bytes

@F#.cQ2

Experimente aqui!

Se a junção for necessária, 10 bytes

sMM@F#.cQ2

Experimente aqui!

Mr. Xcoder
fonte
Sua saída não possui o formulário necessário. Você precisa juntar os nós à cadeia de caracteres.
21418
@ DavidC Não vejo por que isso seria necessário e não consigo identificar nenhuma parte da especificação de desafio que exige isso, mas adicionei uma versão que os une.
Mr. Xcoder
A união foi usada em todos os casos de teste. No meu caso, ingressar custa 9 bytes. Você conseguiu fazer isso com apenas 3 bytes adicionais. Impressionante!
21418
0

Wolfram Language 64 53 bytes

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

Localiza todos os Subsets de comprimento 2 da lista de entrada , Selectaqueles em que os nós de um par se cruzam com os nós de outro par (indicando que os pares compartilham um nó) eStringJoin os nós de todos os pares selecionados.

O código é especialmente difícil de ler porque emprega 4 aninhados puros ( também conhecido como funções "anônimas").

O código usa chaves, "{}", como delimitadores de lista, como é habitual no Wolfram Language.

1 byte economizado graças ao Sr. Xcoder.


Exemplo

""<>#&/@#&/@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"}}*)
DavidC
fonte
Sua corrente atualmente é de 65 bytes, e não 64. No entanto, você pode jogar 1 byte com Select[#~Subsets~{2},IntersectingQ@@#&]/.{a_,b_}:>{""<>a,""<>b}&- Experimente on-line!
Xcoder 16/08/19
0

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]

Experimente online!

Para cada nó x(descoberto fazendo um conjunto da lista achatada de arestas), faça uma lista dos pares pque têm xcomo membro; em seguida, para cada uma dessas listas Q, encontre os pares únicos e distintos em Q(exclusividade / distinção é imposta via if s<t).

Chas Brown
fonte
0

Bytes em C # 233

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

Exemplo

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