Recherche approfondie en profondeur, Comment détecter les dépendances diamant?

Question

Je me demandais si quelqu'un pouvait donner des indications sur la manière de vérifier les dépendances entre les diamants tout en effectuant une recherche en profondeur d'abord sur un graphique ... J'ai le graphique suivant A - > B, A - > F, B - > C, B > E, C - > D, E - > D .

J'essaie de créer une liste de conteneurs représentant le graphe spécifié. Cependant, lorsque je suis dépendant du diamant, je ne sais pas quoi faire. Par exemple, dans mon graphique, C et E sont tous deux des conteneurs enfants de B , lorsque je résous D , J'ai besoin de référencer C et E . Pourrais-je détecter une dépendance au diamant et combiner C et E dans un même conteneur?

Answer 1

Je trouve qu'il est plus facile de penser aux algorithmes de graphes utilisant des couleurs.

Tous les nœuds démarrent en blanc.

Un nœud en cours de traitement est coloré en gris.

Une fois qu'un nœud a été traité, coloriez-le en noir.

Vous colorez un nœud gris dès que vous le rencontrez.

Vous colorez un nœud en noir une fois que vous avez fini de traiter ses enfants.

Si vous rencontrez un nœud noir, vous avez une dépendance en diamant.

Answer 2

Rohan, vous pouvez utiliser la recherche de profondeur en premier pour détecter "diamant". en recherchant des bords croisés ou en avant. Si vous regardez l'implémentation en pseudo-code de depth-first-search sur la page d'accueil de boost-graph-library.

... sinon si (couleur [v] = NOIR) (u, v) est un bord en travers ou en avant ...

Answer 3

Je ne sais pas comment vous définissez les nœuds du graphique. Disons qu'une façon de représenter le nœud est comme ci-dessous -

public interface Node {
            int getValue();
            List<Node> getChildren();
        }

Le problème avec cette implémentation est que nous ne connaissons pas le parent d’un nœud. Si nous avons un moyen de savoir qui sont les paretents d’un noeud, nous pouvons déterminer la dépendance au diamant.

Par exemple, dans votre cas, nous devrions commencer par le bas de l’arbre et nous pouvons voir que D a deux parenets et qu’ils viennent de B. Je dirais donc Construisez votre graphique qui prend en charge non seulement les enfants, mais aussi les parents. Ensuite, identifiez les nœuds ayant plus d’un parent (comme D) et si ces parenets (C et E) ont le même parent (B).

Answer 4

Je ne suis pas vraiment sûr de ce que vous essayez de faire, mais au plus tard lorsque votre graphique contient des cycles, vous devez réellement détecter les nœuds que vous trouvez régulièrement lors de votre recherche. Cela se fait généralement en marquant les nœuds d'une manière ou d'une autre pendant que vous les traitez, afin que vous puissiez voir plus tard si vous les avez déjà visités auparavant. Votre efficacité dépend de votre implémentation et de l’apparence de ces nœuds.

Answer 5

Rohan, étant donné que j’enseigne parfois des algorithmes et des structures de données, je suis peut-être partial, mais je suppose que vous devez examiner un livre d’algorithmes graphiques. Cela semble suggérer de nombreuses façons différentes de faire les choses, mais vous ne savez pas vraiment ce que vous essayez réellement de faire . Oui, dans le cas où vous avez deux nœuds avec les fronts entrants et sortants vers / depuis les mêmes nœuds (ici, (B, E), (B, C) (C, D), (E, D)) it serait légitime de combiner les deux nœuds C et E en un "C, E" nœud. Il serait également légitime de diviser D en D ₁ et D ₂ en faire un arbre au lieu d’un DAG.

Autrement dit, il serait légitime de le faire en fonction du problème.

Answer 6

La théorie des graphes est un domaine très vaste et complexe des mathématiques. C'est une de ces choses où un peu de connaissance peut être une chose dangereuse :) Il peut également être difficile de trouver des explications simples pour des applications même de base de la théorie des graphes. Il est très probable que tout ce que vous rencontrez avec des graphes a été battu à mort et comporte 5 fois plus de pièges et de pièges que vous ne l'imaginiez alors que vous pouviez vous attaquer au problème.

Je suppose que vous verrez des suggestions très raisonnables ici, puis un peu plus tard, elles seront identifiées comme partiellement ou même dans l’ensemble fausses. Marchez doucement.