CODEWITHSUNDEEP
javadesign-patternsvisitor-pattern
LyB8899
LyB8899

Reputation: 323

Applying the visitor pattern for detecting cycles in a graph

i need to detect if in a directed graph there is a cycle , something likes the topological sort , but i wanna use the visitor pattern.. Do you have some ideas ? I can use the arraylist of nodes , and edges or other structures (not array) .

Upvotes: 0

Views: 1001

Answers (1)

Edwin Buck
Edwin Buck

Reputation: 70929

The visitor pattern really can't achieve such a thing in its purest form.

Remember that a visitor pattern typically has the "visitor" travelling the web of objects, but the web of objects "directing" the visitor. Since the visitor is effectively path-unaware, it prevents certain kinds of breakage.

from the wikipedia example of the Visitor pattern (in Java)

class Car implements CarElement {
    CarElement[] elements;
 
    public Car() {
        //create new Array of elements
        this.elements = new CarElement[] { new Wheel("front left"), 
            new Wheel("front right"), new Wheel("back left") , 
            new Wheel("back right"), new Body(), new Engine() };
    }
 
    public void accept(CarElementVisitor visitor) {     
        for(CarElement elem : elements) {
            elem.accept(visitor);
        }
        visitor.visit(this);    
    }
}

note the Car accept method. It ensures that all the sub-elements of the car are covered, encapsulating navigation, yet exposing the ability to apply external functions against the entire data structure.

Since your code requires knowledge of how the data structure is wired together, the visitor pattern is poorly suited to the task. If a visitor encounters a circular data structure, the future visitors will get stuck in the same loop, not visiting some of the data, breaking the contract between the Visitor and the VisitAcceptors.

Now you might be able to somewhat achieve the goal, provided you had "possibly circular" links in the visiting path not followed. You'd still have to ensure all nodes of the graph were followed in the visiting path, just by other branches of the visiting path. Then your visitor would basically become a large collection of nodes that could be hit by the non-travelled back links, but by the time you implemented such an odd solution, you'd wonder why you bothered with the visitor part.

Upvotes: 2

Related Questions