2
\$\begingroup\$

I have built this Generic Graph traverser, I have this implemented with DFS, I feel it will work equally fine with BFS too.

What do you think of this implementation?

I want help in reviewing the Visitor interface. Should I have Generics in it or just use the base Object?

public abstract class GraphTraverser {
  protected final Visitor visitor;

public GraphTraverser(Visitor visitor) {
    this.visitor = visitor;
}

public abstract void traverse(Object startNode);
}

Generic DFS

public class DepthFirstSearch extends GraphTraverser {
    public DepthFirstSearch(Visitor visitor) {
        super(visitor);
    }

    public void traverse(Object startNode) {
        visitor.reset();
        traverse(startNode, 1);
    }

    private boolean traverse(Object obj, int nodeCount) {
        if (visitor.preVisit(obj, nodeCount)) {
            visitor.visit(obj, nodeCount);
            return true;
        }

        List<? extends Object> objs = visitor.getNeighbours(obj);
        visitor.visit(obj, nodeCount);
        for (Object o : objs) {
            if (traverse(o, nodeCount + 1)) {
                return true;
            }
        }
        visitor.postVisit(obj);
        return false;
    }
}

Visitor Interface

import java.util.List;

public interface Visitor {

    boolean preVisit(Object obj, int nodeVisitCount);

    void postVisit(Object obj);

    void visit(Object obj, int i);

    List<? extends Object> getNeighbours(Object obj);

    Object getResult();

    void unVisit(Object obj);

    void reset();
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.