Erstellen Sie ein Liniendiagramm / ein konjugiertes Diagramm

8

Einführung

Bei einem ungerichteten Graphen G können wir einen Graphen L (G) (als Liniendiagramm oder konjugierter Graph bezeichnet) konstruieren, der die Verbindungen zwischen Kanten in G darstellt. Dazu wird für jede Kante in ein neuer Scheitelpunkt in L (G) erstellt G und Verbinden dieser Eckpunkte, wenn die Kanten, die sie darstellen, einen gemeinsamen Eckpunkt haben.

Hier ist ein Beispiel aus Wikipedia, das den Aufbau eines Liniendiagramms (in grün) zeigt.

Der Graph G. Neue Eckpunkte für jede Kante in G. Scheitelpunkte werden verbunden, wenn ihre Kanten in G verbunden sind Der Liniendiagramm L (G)

Nehmen Sie als weiteres Beispiel diesen Graphen G mit den Eckpunkten A, B, C und D.

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

Wir erstellen einen neuen Scheitelpunkt für jede Kante in G. In diesem Fall wird die Kante zwischen A und C durch einen neuen Scheitelpunkt namens AC dargestellt.

   AC

 BC  CD  DE

Und verbinden Sie Scheitelpunkte, wenn die Kanten, die sie darstellen, einen gemeinsamen Scheitelpunkt haben. In diesem Fall haben die Kanten von A nach C und von B nach C den Scheitelpunkt C gemeinsam, sodass die Scheitelpunkte AC und BC verbunden sind.

   AC
  /  \
 BC--CD--DE

Dieses neue Diagramm ist das Liniendiagramm von G!

Weitere Informationen finden Sie in Wikipedia.

Herausforderung

Angesichts der Adjazenzliste für ein Diagramm G sollte Ihr Programm die Adjazenzliste für das Liniendiagramm L (G) drucken oder zurückgeben. Dies ist Code-Golf, also gewinnt die Antwort mit den wenigsten Bytes!

Eingang

Eine Liste von Zeichenfolgenpaaren, die die Kanten von G darstellen. Jedes Paar beschreibt die Eckpunkte, die durch diese Kante verbunden sind.

  • Jedes Paar (X, Y) ist garantiert eindeutig, was bedeutet, dass die Liste weder (Y, X) noch eine Sekunde (X, Y) enthält.

Zum Beispiel:

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

Ausgabe

Eine Liste von Zeichenfolgenpaaren, die die Kanten von L (G) darstellen. Jedes Paar beschreibt die Eckpunkte, die durch diese Kante verbunden sind.

  • Jedes Paar (X, Y) muss eindeutig sein, was bedeutet, dass die Liste weder (Y, X) noch eine Sekunde (X, Y) enthält.

  • Für jede Kante (X, Y) in G muss der Scheitelpunkt, den sie in L (G) erstellt, XY heißen (die Namen werden in derselben Reihenfolge miteinander verknüpft, in der sie in der Eingabe angegeben sind).

Zum Beispiel:

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

Testfälle

[] -> []

[("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
quelle
4
Ich sehe nichts in der Frage, was eine Eingabe wie [("1","23"),("23","4"),("12","3"),("3","4")], für die die Ausgabe vermutlich sein sollte, ausschließt [("123","234"),("123","34")], was nicht richtig interpretiert werden kann. Ich denke, die einzige Möglichkeit, dies zu beheben, besteht darin, zu garantieren, dass die Eingabe niemals solche Mehrdeutigkeiten enthält. Wenn diese Frage jedoch in der Sandbox veröffentlicht worden wäre, hätte ich vorgeschlagen, die Benennung von Scheitelpunkten in der Ausgabe weniger genau zu bestimmen.
Peter Taylor
2
Können wir nach Peter Taylors Kommentar annehmen, dass die Scheitelpunktnamen in der Eingabe alle 1 Zeichen lang sind?
Sundar - Reinstate Monica

Antworten:

2

Ruby, 51 Bytes

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

Probieren Sie es online aus!

Wenn sie für jede Kombination von zwei Kanten einen gemeinsamen Scheitelpunkt haben (dh wenn das erste Element ihres Schnittpunkts nicht ist nil), drucken Sie ein Array mit den beiden Kanten an STDOUT.

Türknauf
quelle
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]]

Angenommen, alle Eingaben sind einzelne Buchstaben (also jedes einzelne Zeichen außer ^und ]).

Neil
quelle
Was macht Firefox 30-57 für diese Antwort so besonders?
Night2
1
@ Night2 Die Array-Verständnis-Syntax wurde nur in diesen Versionen von Firefox unterstützt.
Neil
2

Brachylog , 13 Bytes

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

Probieren Sie es online aus!

Mit allen Testfällen

(-1 Byte ersetzt l₂mit Ċ, dank @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 - Monica wieder einsetzen
quelle
Sie können die eingeschränkte Variable Ċ(Paar) verwenden, anstatt l₂ein Byte zu speichern.
Fatalize
2

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

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

Probieren Sie es online aus!

,:' Wickeln Sie jede Kante in eine Liste mit 1 Elementen

{ }@ Wenden Sie eine Funktion mit implizitem Argument an x

x,/:\:xVerketten Sie jeden der linken xmit jedem der rechten x, erhalten Sie eine Ergebnismatrix - alle Kantenpaare

,/ Reduzieren Sie die Matrix

( )# Filter

(3=#?,/)#Filtern Sie nur die Paare, deren Verkettung ( ,/) eine Anzahl ( #) von genau 3 eindeutigen ( ?) Elementen aufweist

Dadurch werden Kanten wie ("ab";"ab")und ("ab";"cd")aus der Liste entfernt.

(*>)#Filtern Sie nur die Paare, deren sortabsteigende Permutation ( >) mit ( *) a 1 beginnt (Nicht-0 ist boolean true).

In unserem Fall könnte die sortabsteigende Permutation 0 1oder sein 1 0.

ngn
quelle
1

Gelee , 5 Bytes

Œcf/Ƈ

Probieren Sie es online aus!

Mr. Xcoder
quelle
Wie werden fund Ƈin Jelly verwendet? Wenn ich es in den Dokumenten lese, sind beide Filter. fist " Filter; entferne die Elemente aus x, die nicht in y sind. " und Ƈist " Filter (Alias ​​für Ðf). Behalte alle Elemente, die eine Bedingung erfüllen. ". Werden sie immer zusammen verwendet? Wird das Ƈzum Schließen des Filters verwendet f? Wie in, ist f...Ƈähnlich wie ʒ...}in 05AB1E? Oder hat das /(" Reduzieren oder n-weise Reduzieren ") etwas damit zu tun? Ich versuche nur, den Code zu verstehen, und ich bin verwirrt über die zwei verschiedenen Filterbefehle (und wie beide hier verwendet werden). :)
Kevin Cruijssen
2
@ KevinCruijssen Nein, fund Ƈsind zwei völlig getrennte Dinge. Sie können denken, fals Schnittpunkt (bei zwei Listen, es ihre gemeinsame Elemente zurückgibt) und Ƈist wie ʒin 05AB1E. Kurz gesagt: ŒcGibt alle möglichen Kombinationen von zwei Elementen aus der Liste zurück und Ƈbehält dann nur diejenigen bei, die den Link erfüllen (dh Jelly-Funktion) f/, wodurch der Schnittpunkt der beiden Elemente zurückgegeben wird. Aber fist eine Dyade (Zwei-Argument-Funktion) und wir müssen sie stattdessen auf eine Zwei-Elemente-Liste anwenden, also müssen wir verwenden /, reduzieren.
Herr Xcoder
Ah ok, das macht viel mehr Sinn. Ich denke, der Begriff "Filter" fin den Dokumenten hat mich, obwohl er korrekt ist, hauptsächlich mit dem tatsächlich verwendeten Filter verwechselt Ƈ. Ihre Erklärung von " zwei Listen gegeben, geben Sie ihre gemeinsamen Elemente zurück " machte alles klar. Und ich hatte tatsächlich das Gefühl /, dass damit Jellys Daten irgendwie konvertiert wurden. Eigentlich sehe ich jetzt den Abschnitt 6.6 Reduzieren im Tutorial im Jelly-Wiki, der erklärt, wie eine Dyade geplatzt und eine reduzierte Monade gepusht wird (im Grunde 2 Argumente gegen eine Liste von Paaren als Argument). Danke, jetzt alles klar!
Kevin Cruijssen
1

MATL , 13 Bytes

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

Probieren Sie es online aus!

Nicht so schlecht, wie ich es bei der Eingabe des Zellenarrays erwartet hatte. Grundsätzlich die gleiche Idee wie @ Doorknobs Ruby-Antwort .

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 - Monica wieder einsetzen
quelle
0

C (gcc) , 173 Bytes

Eingabe iund Ausgabe osind flache, nullterminierte Arrays. Ausgabenamen können bis zu 998 Zeichen lang sein, lange bevor dies unterbrochen wird.

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

Probieren Sie es online aus!

Curtis Bechtel
quelle
Schlagen Sie *xanstelle von x[0]und int**anstelle vonchar**
Deckenkatze
0

Mathematica 23 Bytes

EdgeList[LineGraph[#]]&

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

Geben Sie hier die Bildbeschreibung ein

EdgeList@LineGraph[g]

(*

{2 1, 3 2, 4 1, 4 2, 4 3}

*)

David G. Stork
quelle
0

Pyth , 7 Bytes

@F#.cQ2

Probieren Sie es hier aus!

Wenn eine Verbindung erforderlich ist, 10 Bytes

sMM@F#.cQ2

Probieren Sie es hier aus!

Mr. Xcoder
quelle
Ihre Ausgabe hat nicht das erforderliche Formular. Sie müssen die Knoten verbinden.
DavidC
@DavidC Ich verstehe nicht, warum dies erforderlich wäre, und ich kann keinen Teil der Herausforderungsspezifikation identifizieren, der dies erfordert, aber ich habe eine Version hinzugefügt, die sie verbindet.
Herr Xcoder
Die Verbindung wurde in allen Testfällen verwendet. In meinem Fall kostet das Beitreten 9 Bytes. Sie konnten dies mit nur 3 zusätzlichen Bytes tun. Beeindruckend!
DavidC
0

Wolfram Language 64 53 Bytes

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

Findet alle Eingabelisten Subsetder Länge 2, Selectdiejenigen, in denen sich die Knoten eines Paares mit den Knoten eines anderen Paares schneiden (was anzeigt, dass sich die Paare einen Knoten teilen), undStringJoin die Knoten für alle ausgewählten Paare.

Der Code ist besonders schwer zu lesen, da er 4 verschachtelte reine ( auch "anonyme") Funktionen verwendet.

Der Code verwendet Klammern "{}" als Listenbegrenzer, wie es in Wolfram Language üblich ist.

1 Byte dank Mr. Xcoder gespeichert.


Beispiel

""<>#&/@#&/@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
quelle
Ihr Strom ist tatsächlich 65 Bytes, nicht 64. Sie können jedoch 1 Byte mit Golf spielen Select[#~Subsets~{2},IntersectingQ@@#&]/.{a_,b_}:>{""<>a,""<>b}&- Probieren Sie es online aus!
Herr Xcoder
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]

Probieren Sie es online aus!

Erstellen Sie für jeden Knoten x(der durch Erstellen einer Menge aus der abgeflachten Kantenliste ermittelt wird) eine Liste der Paare p, die xMitglied sind. QFinden Sie dann für jede dieser Listen die eindeutigen, unterschiedlichen Paarungen innerhalb Q(Eindeutigkeit / Unterscheidung wird über erzwungen if s<t).

Chas Brown
quelle
0

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

Beispiel

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