Das Ziel dieser Herausforderung ist ein endlich gerichteter azyklischer Graph (DAG), der bestimmt, ob der Graph eine transitive Reduktion ist .

Eine kurze Erklärung, was eine DAG und transitive Reduktionen sind:

Eine DAG ist ein Diagramm mit gerichteten Kanten (dh Sie können an dieser Kante nur in eine Richtung fahren), sodass es bei einem beliebigen Startknoten im Diagramm unmöglich ist, zum Startknoten zurückzukehren (dh es gibt keine Zyklen).

Wenn es bei einem beliebigen Startknoten möglich ist, über eine beliebige positive Anzahl von Kanten zu einem anderen Endknoten im Diagramm zu gelangen, wird dieser Endknoten als vom Startknoten aus erreichbar definiert. In einer allgemeinen DAG kann es mehrere Pfade geben, die von einem Startknoten zu einem Zielendknoten genommen werden können. Nehmen Sie zum Beispiel dieses Diamantdiagramm:

Um zu Knoten Daus A, könnte nehmen Sie den Weg A->B->Doder A->C->D. Somit Dist erreichbar von A. Es gibt jedoch keinen Pfad, der verwendet werden kann, um Bvom Knoten zum Knoten zu gelangen C. Somit ist der Knoten Bvom Knoten nicht erreichbar C.

Definieren Sie die Erreichbarkeit des Diagramms als Liste der erreichbaren Knoten für jeden Startknoten im Diagramm. Für das gleiche Beispiel eines Diamantgraphen ist die Erreichbarkeit also:

A: [B, C, D]
B: [D]
C: [D]
D: []

Ein weiteres Diagramm mit der gleichen Erreichbarkeit wie das obige Diagramm ist unten dargestellt:

Dieses zweite Diagramm hat jedoch mehr Kanten als das ursprüngliche Diagramm. Die transitive Reduzierung eines Diagramms ist ein Diagramm mit der geringsten Anzahl von Kanten und der gleichen Erreichbarkeit des ursprünglichen Diagramms. Der erste Graph ist also die transitive Reduktion des zweiten.

Für eine endliche DAG ist die transitive Reduktion garantiert und einzigartig.

Eingang

Die Eingabe ist eine "Liste von Listen", wobei die externe Liste die Länge der Anzahl der Scheitelpunkte hat und jede interne Liste die Länge der Anzahl der Kanten ist, die den zugeordneten Knoten verlassen, und die Indizes der Zielknoten enthält. Eine Möglichkeit zur Beschreibung des ersten Diagramms oben wäre beispielsweise (unter der Annahme einer auf Null basierenden Indizierung):

[[1, 2], [3], [3], []]

Sie können mit der Indizierung des ersten Knotens bei einem beliebigen ganzzahligen Wert beginnen (z. B. 0- oder 1-basierte Indizierung).

Die Eingabe kann von jeder gewünschten Eingangsquelle stammen (Standard, Funktionsparameter usw.). Sie können das genaue Eingabeformat frei wählen, solange keine zusätzlichen Informationen angegeben werden. Wenn Sie beispielsweise Eingaben von stdio übernehmen möchten, kann jede Zeile eine Liste von Kanten für den zugeordneten Knoten sein. Ex.:

1 2
3
3
'' (blank line)

Die Indizes in jeder Adjazenzliste sind nicht unbedingt sortiert, und es können mehrere Kanten vorhanden sein, die zwei Knoten verbinden (z. B. :) [[1,1],[]]. Sie können davon ausgehen, dass der Eingabediagramm schwach verbunden ist und keine Zyklen enthält (dh es handelt sich um eine DAG).

Ausgabe

Die Ausgabe ist wahr, wenn die gegebene Eingangs-DAG eine transitive Reduktion ist, und ansonsten ein falscher Wert. Dies kann für jede gewünschte Senke gelten (stdio, Rückgabewert, Ausgabeparameter usw.)

Beispiele

Alle Beispiele verwenden eine 0-basierte Indizierung.

[[1,2],[3],[3],[]]
true

[[1,2,3],[3],[3],[]]
false

[[1,1],[]]
false

[[1,2,3,4],[5,6,7],[5,8,9],[6,8,10],[7,9,10],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
true

[[5,6,7],[2,3,0,4],[5,8,9],[6,8,10],[7,9,10],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
true

[[5,6,7],[2,3,0,4,14,5,7],[5,8,9],[6,8,10],[7,9,10],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
false

[[5,6,7],[2,3,0,4],[5,8,9],[6,8,10],[7,9,10,14],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
false

[[1,3],[2],[3],[]]
false

Wertung

Das ist Code Golf; kleinster Code in Bytes gewinnt. Ihr Code sollte in angemessener Zeit abgeschlossen sein (maximal 10 Minuten auf jeder Hardware, die Sie haben). Es gelten Standardlücken. Sie können alle gewünschten integrierten Funktionen verwenden.

Ruby, 101 97 Bytes

Einfacher Ansatz, der die Reichweite von jedem Knoten berechnet und berücksichtigt, ob ein untergeordneter Knoten über einen der anderen Knoten erreicht werden kann. Scheint in zyklischen Graphen scheinbar zu versagen, aber die Definition einer DAG impliziert, dass sie sowieso nicht zyklisch sein sollte.

Probieren Sie es online aus!

->g{r=->i{i|i.map{|j|r[g[j]||[]]}.inject([],:|)}
g.all?{|e|e==e&e&&e.none?{|i|r[e-[i]].index i}}}

Mathematica, 95 82 Bytes

^{13 Bytes aufgrund von @MartinEnder gespeichert .}

#~IsomorphicGraphQ~TransitiveReductionGraph@#&@Graph[x=0;##&@@Thread[++x->#]&/@#]&

Anonyme Funktion. Nimmt eine verschachtelte Liste als (1-basierte) Eingabe und gibt sie zurück Trueoder Falseals Ausgabe. Die Hauptlösung ist hier das 46-Byte #~IsomorphicGraphQ~TransitiveReductionGraph@#&, das prüft, ob ein gegebener Graph zu seiner transitiven Reduktion isomorph ist. Der Rest konvertiert die Eingabe in ein GraphObjekt.

CJam (41 Bytes)

q~:A_,{{Af=e__&}%_}*]:.|A.&A:$:e`e_2%1-*!

Online-Demo , Testgeschirr

Präparation

q~:A      e# Parse input and store in A
_,{       e# Loop V times
  {       e#   Extend adjacency list representation of G^i to G^(i+1)
    Af=   e#   by extending each path by one edge
    e__&  e#   and flattening. NB :| would be shorter but breaks for empty lists
  }%
  _       e#   Duplicate, so that we build up G^2, G^3, ..., G^n
}*]       e# Gather in a single array
:.|       e# Fold pointwise union, giving the reachability from each vertex by
          e# paths of length > 1
A.&       e# Pointwise intersect with the paths of length 1
          e# We hope to get an array of empty arrays

          e# Handle the awkward special case of duplicate edges:
A:$       e# Sort each adjacency list
:e`       e# Run-length encode each adjacency list
e_2%      e# Extract only the run lengths
1-        e# Discard the 1s - so we now have an empty array unless there's a dupe

*         e# Join. We hope to be joining an array of empty arrays by an empty array
          e# giving an empty array
!         e# Check that we get a falsy value (i.e. the empty array)

Gelee, 20 Bytes

ị³$ÐĿ€ị@Fœ&¥";œ-Q$€E

Verwendet 1-basierte Indizierung. Probieren Sie es online aus!

Lose Übersicht

     €                for each vertex,
ị³$ÐĿ                   compute its reach.
        Fœ&¥"         intersect each vertex's lists of children and
      ị@                children's reaches.
             ;        then concatenate the list of intersections with
              œ-Q$€     all duplicate edges in the original graph.
                   E  are all elements equal? checks that all are empty lists,
                        meaning empty intersections and no duplicates.