Différence entre le modèle de conception des visiteurs et la recherche en profondeur ?

Question

Une recherche en profondeur semble pouvoir remplir des fonctions similaires à celles du modèle de conception visiteur. Un visiteur vous permet de définir certaines structures de données et d'ajouter des opérations sur ces structures (sous la forme de plusieurs visiteurs) selon les besoins, sans modifier les structures elles-mêmes. Une description du patron visiteur est fournie sur wikipedia . Si nous effectuons une recherche en profondeur (ou tout autre algorithme de recherche de graphe comme la recherche en largeur) sur la structure de données, et qu'à chaque fois qu'un élément de la structure est trouvé, nous exécutons l'opération souhaitée, il semble alors que cela remplisse la même fonction que le visiteur. Par exemple, considérons un arbre. Même si certains nœuds de l'arbre ont un type différent, nous pouvons toujours vérifier les types de nœuds lors de la DFS, puis effectuer différentes opérations en fonction du type de nœud.

Answer 1

Une recherche en profondeur n'est rien d'autre qu'une recherche. Un modèle Visiteur est orthogonal à une recherche en profondeur, dans le sens où un Visiteur ne se soucie pas nécessairement de savoir si une recherche en profondeur est possible. comment l'arbre est traversé ; il sait simplement ce qu'il doit faire sur/vers/avec chaque nœud.

Answer 2

Vous pouvez avoir une mise en œuvre de Visiteur sans avoir de DFS. De même, vous pouvez faire un DFS sans utiliser le pattern Visitor. Ils sont complètement séparés.

Je suis d'accord avec l'idée qu'ils pourraient être utilisés ensemble de manière élégante.

À titre d'information, pour le modèle canonique Visitor, les objets visités doivent mettre en œuvre une sorte de mécanisme de contrôle de l'accès. AcceptVisitor interface -- la clause "sans modifier les structures elles-mêmes" dans votre question m'amène à me demander si c'est ce que vous faites.

Answer 3

Laissez-moi répondre à la question en code :

/**
 * This method makes it easier for a class to process all
 * the nodes in an item. The class should implement
 * the NodeVisitor interface. This method will cause the 
 * NodeVisitor.processNode() method to be called once for each
 * node in this item. 
 * @param visitor the class that will visit each node
 * @throws PipelineException some recoverable exception
 */
public void visitNodes(NodeVisitor visitor) throws PipelineException {
    visitNodes(visitor, root);
}

private void visitNodes(NodeVisitor visitor, Node node) throws PipelineException {
    visitor.processNode(node);
    if (node.hasChildren()) {
        int childCount = node.getChildCount();
        NodeList children = node.getChildren();
        for (int i = 0; i < childCount; i++) {
            visitNodes(visitor, children.get(i));
        }
    }
}

/**
 * Classes that implement this interface can be used with
 * Item.visitNodes(). This method provides a convenient
 * way to iterate over all the nodes in an item.
 */
public interface NodeVisitor {
        public void processNode(Node node) throws PipelineException;
}

Dans ce cas, la méthode visitNodes() met en œuvre une recherche en profondeur, mais ce n'est pas obligatoire. Elle peut implémenter n'importe quelle recherche qui touche tous les nœuds. C'est la combinaison de la méthode visitNodes() et de l'interface NodeVisitor qui constitue le "visitor pattern" (ou une manifestation particulière de celui-ci).

Il n'y a pas de "compromis" entre le modèle de conception et l'algorithme de recherche. Le modèle de conception rend simplement l'algorithme plus facile à utiliser.

Answer 4

En théorie des graphes, vous pouvez construire un graphe tel que l'arbre d'envergure minimale n'est pas un chemin issu d'une recherche en profondeur, et plus précisément un non-chemin : https://cs.stackexchange.com/questions/6749/depth-first-search-to-find-minimum-spanning-tree . Je pense que vous ne pouvez pas appliquer cela à un modèle de conception.

Answer 5

Première recherche en profondeur est un "algorithme" et le schéma de visite est un moyen d'oublier les préoccupations algorithmiques et de se concentrer sur les actions à mener.

En fait, le Motif de visite peut être un bon moyen de indice le contenu, car il offre un comportement "agnostique" (vous pouvez modifier la structure sans réécrire les visiteurs)

Mais si vous voulez effectuer un recherche je ne vous conseille pas de l'utiliser. Tout algorithme de recherche est lié à un type particulier de structure (arbre, digraphe, graphes de flux, etc).

Dans certains cas, vous pouvez obtenir un recherche en profondeur avec un schéma de visite mais ce n'est pas le but de ce modèle.

L'utilisation du modèle de visiteur ne dépend pas du type d'analyse syntaxique que vous utilisez, mais de ce pour quoi l'analyse syntaxique doit être effectuée. .