Buat grafik garis / grafik konjugat

8

pengantar

Diberikan graf G tidak berarah, kita dapat membuat grafik L (G) (disebut grafik garis atau grafik konjugat) yang mewakili koneksi antara tepi dalam G. Ini dilakukan dengan membuat simpul baru di L (G) untuk setiap tepi di G dan menghubungkan simpul-simpul ini jika ujung-ujungnya mewakili memiliki simpul yang sama.

Berikut adalah contoh dari Wikipedia yang menunjukkan pembuatan grafik garis (berwarna hijau).

Grafik G Simpul baru yang mewakili setiap tepi di G Verteks terhubung ketika ujungnya di G terhubung Grafik garis L (G)

Sebagai contoh lain, ambil grafik G ini dengan simpul A, B, C, dan D.

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

Kami membuat simpul baru untuk setiap tepi di G. Dalam hal ini, tepi antara A dan C diwakili oleh simpul baru yang disebut AC.

   AC

 BC  CD  DE

Dan hubungkan simpul ketika tepi yang mereka wakili memiliki titik yang sama. Dalam hal ini, ujung-ujungnya dari A ke C dan dari B ke C memiliki titik sudut C yang sama, sehingga simpul AC dan BC terhubung.

   AC
  /  \
 BC--CD--DE

Grafik baru ini adalah grafik garis G!

Lihat Wikipedia untuk informasi lebih lanjut.

Tantangan

Dengan diberikan daftar adjacency untuk grafik G, program Anda harus mencetak atau mengembalikan daftar adjacency untuk grafik garis L (G). Ini kode-golf, jadi jawabannya dengan byte paling sedikit menang!

Memasukkan

Daftar pasangan string yang mewakili tepi G. Setiap pasangan menggambarkan simpul yang terhubung dengan tepi itu.

  • Setiap pasangan (X, Y) dijamin unik, artinya daftar tidak akan berisi (Y, X) atau yang kedua (X, Y).

Sebagai contoh:

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

Keluaran

Daftar pasangan string yang mewakili tepi L (G). Setiap pasangan menggambarkan simpul yang terhubung dengan tepi itu.

  • Setiap pasangan (X, Y) harus unik, artinya daftar tidak akan berisi (Y, X) atau yang kedua (X, Y).

  • Untuk setiap tepi (X, Y) dalam G, simpul yang dibuatnya dalam L (G) harus dinamai XY (nama-nama tersebut digabungkan bersama-sama dalam urutan yang sama seperti yang ditentukan dalam input).

Sebagai contoh:

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

Uji Kasus

[] -> []

[("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
sumber
4
Saya tidak melihat apa pun dalam pertanyaan yang mengesampingkan input seperti [("1","23"),("23","4"),("12","3"),("3","4")], yang hasilnya mungkin seharusnya [("123","234"),("123","34")], yang tidak dapat ditafsirkan dengan benar. Saya pikir satu-satunya cara untuk memperbaikinya adalah dengan mengedit dalam jaminan bahwa input tidak akan pernah mengandung ambiguitas seperti itu, tetapi jika pertanyaan ini telah diposting di kotak pasir maka saya akan menyarankan menjadi kurang preskriptif tentang penamaan simpul dalam output.
Peter Taylor
2
Lebih jauh dari komentar Peter Taylor, dapatkah kita berasumsi bahwa nama-nama simpul semua panjangnya 1 karakter dalam input?
sundar - Reinstate Monica

Jawaban:

2

Ruby, 51 byte

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

Cobalah online!

Untuk setiap kombinasi dari dua tepi, jika mereka memiliki titik yang sama (yaitu jika elemen pertama dari persimpangan mereka adalah non- nil), cetak array yang berisi dua tepi ke STDOUT.

Gagang pintu
sumber
2

JavaScript (Firefox 30-57), 77 byte

a=>[for(x of a=a.map(x=>x.join``))for(y of a)if(x<y&&x.match(`[${y}]`))[x,y]]

Asumsikan semua input adalah huruf tunggal (well, setiap karakter selain ^dan ]).

Neil
sumber
Apa yang membuat Firefox 30-57 istimewa untuk jawaban ini?
Night2
1
@ Night2 Sintaks pemahaman array hanya didukung di versi Firefox tersebut.
Neil
2

Brachylog , 13 byte

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

Cobalah online!

Dengan semua kasus uji

(-1 byte diganti l₂dengan Ċ, terima kasih kepada @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 - Pasang kembali Monica
sumber
Anda dapat menggunakan variabel terbatas Ċ(pasangan) alih-alih l₂menyimpan satu byte.
Fatalkan
2

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

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

Cobalah online!

,:' bungkus setiap sisi dalam daftar 1-elemen

{ }@ menerapkan fungsi dengan argumen implisit x

x,/:\:x menyatukan masing-masing kiri x dengan masing-masing kanan x, dapatkan matriks hasil - semua pasang tepi

,/ ratakan matriks

( )# Saring

(3=#?,/)#memfilter hanya pasangan yang rangkaian ( ,/) memiliki jumlah ( #) tepat 3 ?elemen unik ( )

Ini menghilangkan tepi seperti ("ab";"ab")dan ("ab";"cd")dari daftar.

(*>)#filter hanya pasangan yang permutasinya menurun ( >) dimulai dengan ( *) a 1 (bukan-0 adalah boolean true)

Dalam kasus kami, permutasi sort-descending bisa 0 1atau 1 0.

ngn
sumber
1

Jelly , 5 byte

Œcf/Ƈ

Cobalah online!

Tuan Xcoder
sumber
Bagaimana fdan Ƈdigunakan dalam Jelly? Jika saya membacanya di dokumen, keduanya adalah filter. fadalah " Filter; hapus elemen-elemen dari x yang tidak ada di dalam y. " dan Ƈadalah " Filter (alias untuk Ðf). Simpan semua item yang memenuhi syarat. ". Apakah mereka selalu digunakan bersama? Apakah Ƈdigunakan untuk menutup filter f? Seperti di, f...Ƈmirip dengan ʒ...}di 05AB1E? Atau apakah /(" Mengurangi atau mengurangi n-bijaksana. ") Ada hubungannya dengan itu? Hanya mencoba memahami kode, dan saya bingung dengan dua perintah filter yang berbeda (dan bagaimana keduanya digunakan di sini). :)
Kevin Cruijssen
2
@KevinCruijssen Tidak, fdan Ƈdua hal yang sepenuhnya terpisah. Anda dapat menganggapnya fsebagai persimpangan (diberi dua daftar, itu mengembalikan elemen umum mereka) dan Ƈseperti ʒdi 05AB1E. Singkatnya: Œcmengembalikan semua kombinasi yang mungkin dari dua elemen dari daftar, kemudian Ƈhanya membuat mereka yang memenuhi tautan (yaitu fungsi Jelly) f/, yang mengembalikan persimpangan dua item. Tetapi fadalah angka dua (fungsi dua argumen) dan kita perlu menerapkannya pada daftar dua elemen, jadi kita harus menggunakan /, mengurangi.
Tn. Xcoder
Ah ok, itu jauh lebih masuk akal. Saya kira istilah 'filter' fdalam dokumen, meskipun benar, terutama membingungkan saya dengan filter yang sebenarnya Ƈdigunakan. Penjelasan Anda tentang " diberikan dua daftar, kembalikan unsur-unsur umum mereka " membuat semuanya jelas. Dan saya memang merasa bahwa /itu digunakan untuk mengkonversi data Jelly entah bagaimana. Sebenarnya, saya sekarang melihat bagian 6.6 Mengurangi dalam Tutorial pada wiki Jelly yang menjelaskan bagaimana itu muncul angka dua dan mendorong pengurangan monad (pada dasarnya 2 argumen vs daftar pasangan sebagai argumen). Terima kasih, semuanya jelas sekarang!
Kevin Cruijssen
1

MATL , 13 byte

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

Cobalah online!

Tidak seburuk yang saya harapkan diberi input array sel. Ide dasarnya sama dengan jawaban Ruby @ 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 - Pasang kembali Monica
sumber
0

C (gcc) , 173 byte

Input idan output oadalah array datar, null-dihentikan. Nama keluaran bisa hingga 998 karakter jauh sebelum ini akan rusak.

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

Cobalah online!

Curtis Bechtel
sumber
Sarankan *xalih-alih x[0]dan int**bukannyachar**
ceilingcat
0

Mathematica 23 byte

EdgeList[LineGraph[#]]&

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

masukkan deskripsi gambar di sini

EdgeList@LineGraph[g]

(*

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

*)

David G. Stork
sumber
0

Pyth , 7 byte

@F#.cQ2

Coba di sini!

Jika perlu bergabung, 10 byte

sMM@F#.cQ2

Coba di sini!

Tuan Xcoder
sumber
Output Anda tidak memiliki formulir yang diperlukan. Anda perlu merangkai dengan simpul.
DavidC
@ DavidvidC Saya tidak melihat mengapa itu diperlukan dan saya tidak dapat mengidentifikasi bagian dari spefikasi tantangan yang mengharuskan itu, tetapi saya telah menambahkan versi yang bergabung dengan mereka.
Tn. Xcoder
Bergabung digunakan dalam semua kasus uji. Dalam kasus saya, biaya bergabung dengan 9 byte. Anda dapat melakukannya hanya dengan 3 byte tambahan. Impresif!
DavidC
0

Bahasa Wolfram 64 53 byte

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

Menemukan semua daftar masukan dengan Subsetpanjang 2, Selectyaitu titik-titik di mana pasangan berpasangan bersilangan dengan pasangan berpasangan lainnya (yang menunjukkan bahwa pasangan berbagi sebuah simpul), danStringJoin simpul untuk semua pasangan yang dipilih.

Kode ini sangat sulit dibaca karena mempekerjakan 4 fungsi bersarang murni ( alias "anonim").

Kode ini menggunakan kurung kurawal, "{}", sebagai pembatas daftar, seperti biasa dalam Bahasa Wolfram.

1 byte disimpan berkat Tn. Xcoder.


Contoh

""<>#&/@#&/@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
sumber
Saat ini Anda sebenarnya 65 byte, bukan 64. Namun, Anda dapat bermain golf 1 byte dengan Select[#~Subsets~{2},IntersectingQ@@#&]/.{a_,b_}:>{""<>a,""<>b}&- Cobalah online!
Tn. Xcoder
0

Python 2 , 109 byte

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]

Cobalah online!

Untuk setiap node x (ditemukan dengan membuat satu set dari daftar tepi rata), buat daftar pasangan pyang memiliki xsebagai anggota; kemudian, untuk masing-masing daftar itu Q, temukan pasangan unik dan berbeda di dalam Q(keunikan / perbedaan diberlakukan melalui if s<t).

Chas Brown
sumber
0

C # 233 byte

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

Contoh

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
sumber