3
\$\begingroup\$

This algorithm should return a boolean value, telling if there is a path between two nodes in a given directed graph.

public enum State{
    White, Grey;
}

public class Node {
    State state = State.White;
    List<Node> neighbors = new ArrayList<Node>();
    //Assumption: Every node already knows about its direct adjacents
    public List<Node>getAdjacent(){ return neighbors;}
}

public static boolean isThereAPath(Node src, Node dst){
    //Assumption: Nodes are initialized with State.White
    if(src.state == State.White){
        src.state = State.Grey; //Means visiting this node right now
        for(Node node : src.getAdjacent()){
            if(node == dst){
                return true; //Hit - path found!
            }
            if(isThereAPath(node, dst))return true;

        }
    }
    return false; //NO path found
}

What do you think about the concept of it? What are the advantages of of an iterative solution?

\$\endgroup\$
1
\$\begingroup\$

You don't reset the src.state when you return the result.

This means that between isThereAPath calls you need to reset the state manually. Instead you should reset the state:

public static boolean isThereAPath(Node src, Node dst){
    //Assumption: Nodes are initialized with State.White
    if(src.state == State.White){
        src.state = State.Grey; //Means visiting this node right now
        for(Node node : src.getAdjacent()){
            if(node == dst){
                src.state = State.White;
                return true; //Hit - path found!
            }
            if(isThereAPath(node, dst)){
                src.state = State.White;
                return true;
            }

        }
    }
    return false; //NO path found
}
\$\endgroup\$
  • \$\begingroup\$ Okay right, If I want to use the structure again afterwards, this is a thing to do. Thanks! \$\endgroup\$ – Shady Feb 6 '15 at 8:45
-1
\$\begingroup\$

Style: avoid one-liners such as public List<Node>getAdjacent(){ return neighbors;}

\$\endgroup\$
  • \$\begingroup\$ Why? Can you explain your thought process a bit more? \$\endgroup\$ – RubberDuck Feb 9 '15 at 3:12
  • \$\begingroup\$ @RubberDuck I saw style guides (I think it was the Android style guide from Google) where they recommend not doing it because of readability. However, they allow doing one-liners like if(a==b) return a; \$\endgroup\$ – Shady Feb 16 '15 at 16:09
  • \$\begingroup\$ @Shady I'm sorry for the confusion. I was asking barq to expand on his answer. \$\endgroup\$ – RubberDuck Feb 16 '15 at 16:11
  • \$\begingroup\$ It's easier to read if you have the same style for all methods. \$\endgroup\$ – barq Feb 16 '15 at 16:18

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.