Le but de ce défi est donné un graphique acyclique dirigé fini (DAG), déterminer si le graphique est une réduction transitive .

Une brève explication de ce qu'est un DAG et des réductions transitives:

Un DAG est un graphique avec des bords dirigés (c'est-à-dire que vous ne pouvez vous déplacer que dans une seule direction sur ce bord) de telle sorte que, étant donné un nœud de départ sur le graphique, il est impossible de revenir au nœud de départ (c'est-à-dire qu'il n'y a pas de cycles).

Étant donné n'importe quel nœud de départ, s'il est possible de se rendre à un autre nœud de fin dans le graphique via un nombre positif quelconque d'arêtes, alors ce nœud de fin est défini comme accessible à partir du nœud de départ. Dans un DAG général, il peut y avoir plusieurs chemins qui peuvent être empruntés d'un nœud de départ à un nœud d'arrivée cible. Par exemple, prenez ce graphique en losange:

Pour accéder au nœud Ddepuis A, vous pouvez prendre le chemin A->B->Dou A->C->D. Ainsi, Dest accessible à partir de A. Cependant, aucun chemin ne peut être emprunté pour se rendre au nœud à Bpartir du nœud C. Ainsi, le nœud Bn'est pas accessible à partir du nœud C.

Définissez l' accessibilité du graphique comme la liste des nœuds accessibles pour chaque nœud de départ dans le graphique. Donc, pour le même exemple de graphe en diamant, l'accessibilité est:

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

Un autre graphique qui a la même accessibilité que le graphique ci-dessus est illustré ci-dessous:

Cependant, ce deuxième graphique a plus d'arêtes que le graphique d'origine. La réduction transitive d'un graphe est un graphe avec le moins de bords et la même accessibilité du graphe d'origine. Le premier graphique est donc la réduction transitive du second.

Pour un DAG fini, la réduction transitive est garantie d'exister et est unique.

Contribution

L'entrée est une "liste de listes", où la liste externe a la longueur du nombre de sommets, et chaque liste interne est la longueur du nombre d'arêtes quittant le nœud associé, et contient les indices des nœuds de destination. Par exemple, une façon de décrire le premier graphique ci-dessus serait (en supposant une indexation basée sur zéro):

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

Vous pouvez commencer l'indexation du premier nœud à n'importe quelle valeur entière arbitraire (par exemple une indexation basée sur 0 ou 1).

L'entrée peut provenir de n'importe quelle source d'entrée souhaitée (stdio, paramètre de fonction, etc.). Vous êtes libre de choisir le format d'entrée exact tant qu'aucune information supplémentaire n'est fournie. Par exemple, si vous souhaitez prendre une entrée de stdio, vous pouvez avoir chaque ligne comme une liste d'arêtes pour le nœud associé. Ex.:

1 2
3
3
'' (blank line)

Les indices de chaque liste d'adjacence ne sont pas nécessairement triés, et il pourrait y avoir plusieurs fronts reliant deux nœuds (ex. [[1,1],[]]). Vous pouvez supposer que le graphique d'entrée est faiblement connecté et ne contient aucun cycle (c'est-à-dire qu'il s'agit d'un DAG).

Production

La sortie est vraie si l'entrée DAG donnée est une réduction transitive et une valeur fausse sinon. Il peut s'agir de n'importe quel récepteur souhaité (stdio, valeur de retour, paramètre de sortie, etc.)

Exemples

Tous les exemples utilisent une indexation basée sur 0.

[[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

Notation

C'est le golf de code; le plus petit code en octets gagne. Votre code devrait se terminer dans un délai raisonnable (10 minutes maximum sur tout le matériel dont vous disposez). Des échappatoires standard s'appliquent. Vous pouvez utiliser toutes les fonctions intégrées souhaitées.

Rubis, 101 97 octets

Approche simple qui calcule la portée de chaque nœud et considère si un nœud enfant peut être atteint via l'un des autres nœuds. Échoue apparemment sur les graphiques cycliques, mais la définition d'un DAG implique qu'il ne devrait de toute façon pas être cyclique.

Essayez-le en ligne!

->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 octets

^{13 octets enregistrés grâce à @MartinEnder .}

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

Fonction anonyme. Prend une liste imbriquée comme entrée (basée sur 1) et retourne Trueou Falsecomme sortie. La principale solution ici est le 46 octets #~IsomorphicGraphQ~TransitiveReductionGraph@#&, qui teste si un graphe donné est isomorphe à sa réduction transitive. Le reste convertit l'entrée en un Graphobjet.

CJam (41 octets)

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

Démo en ligne , test harnais

Dissection

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)

Gelée, 20 octets

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

Utilise l'indexation basée sur 1. Essayez-le en ligne!

Présentation lâche

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