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).
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")]
fonte
[("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.Respostas:
Ruby, 51 bytes
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.fonte
JavaScript (Firefox 30-57), 77 bytes
Assume que todas as entradas são letras únicas (bem, qualquer caractere único que não seja
^
e]
).fonte
Braquilog , 13 bytes
Experimente online!
Com todos os casos de teste
(-1 byte substituindo
l₂
porĊ
, graças a @Fatalize.)fonte
Ċ
(casal) em vez del₂
salvar um byte.K (ngn / k) ,
4539332930 bytesExperimente online!
,:'
agrupar cada aresta em uma lista de 1 elemento{
}@
aplicar uma função com argumento implícitox
x,/:\:x
concatene cada esquerdax
e direitax
, 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 1
ou1 0
.fonte
Gelatina , 5 bytes
Experimente online!
fonte
f
eƇ
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 filtrof
? 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). :)f
eƇ
são duas coisas completamente separadas. Você pode pensarf
em interseção (com duas listas, ele retorna seus elementos comuns) eƇ
é comoʒ
em 05AB1E. Resumindo:Œc
retorna 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. Masf
é 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.f
os 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!MATL , 13 bytes
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 .
fonte
C (gcc) , 173 bytes
Entrada
i
e saídao
são matrizes simples e terminadas em nulo. Os nomes de saída podem ter até 998 caracteres antes que isso ocorra.Experimente online!
fonte
*x
vez dex[0]
e emint**
vez dechar**
Mathematica 23 bytes
Exemplo:
g = Graph[{1 <-> 2, 2 <-> 3, 3 <-> 4, 2 <-> 4 }]
(*
{2 <-> 1, 3 <-> 2, 4 <-> 1, 4 <-> 2, 4 <-> 3}
*)
fonte
Pitão , 7 bytes
Experimente aqui!
Se a junção for necessária, 10 bytes
Experimente aqui!
fonte
Wolfram Language
6453 bytesLocaliza todos os
Subset
s de comprimento 2 da lista de entrada ,Select
aqueles 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
fonte
Select[#~Subsets~{2},IntersectingQ@@#&]/.{a_,b_}:>{""<>a,""<>b}&
- Experimente on-line!Python 2 , 109 bytes
Experimente online!
Para cada nó
x
(descoberto fazendo um conjunto da lista achatada de arestas), faça uma lista dos paresp
que têmx
como membro; em seguida, para cada uma dessas listasQ
, encontre os pares únicos e distintos emQ
(exclusividade / distinção é imposta viaif s<t
).fonte
Bytes em C # 233
Exemplo
fonte