3
\$\begingroup\$

I have tried to implement the DFS algorithm to find all the back-edges in a graph that lead to a cycle in the graph:

public class CycleDetection {
    private final Deque<Node> stack;
    private final Graph<Node> graph;
    private final Set<Node> visited;

    public CycleDetection(Graph<Node> graph) {
        super();
        this.graph = graph;
        this.stack = new ArrayDeque<Node>();
        this.visited = new LinkedHashSet<Node>();
    }

    public static void main1(String[] args) {
        Node one = new Node("A");
        Node two = new Node("B");
        Node three = new Node("C");
        Node four = new Node("D");
        Node five = new Node("E");
        Node six = new Node("F");

        Graph<Node> graph = new Graph<Node>();

        graph.addNode(one);
        graph.addNode(two);
        graph.addNode(three);
        graph.addNode(four);
        graph.addNode(five);
        graph.addNode(six);

        graph.addEdge(one, two);
        graph.addEdge(one, three);
        graph.addEdge(one, four);
        graph.addEdge(two, five);
        graph.addEdge(two, six);
        graph.addEdge(three, six);

        graph.addEdge(two, one);
        graph.addEdge(three, one);
        graph.addEdge(four, one);
        graph.addEdge(five, two);
        graph.addEdge(six, two);
        graph.addEdge(six, three);

        CycleDetection detection = new CycleDetection(graph);
        detection.detectCycles(six);
    }

    public static void main(String[] args) {
        Node zero = new Node("0");
        Node one = new Node("1");
        Node two = new Node("2");
        Node three = new Node("3");
        Node four = new Node("4");
        Node five = new Node("5");

        Graph<Node> graph = new Graph<Node>();

        graph.addNode(zero);
        graph.addNode(one);
        graph.addNode(two);
        graph.addNode(three);
        graph.addNode(four);
        graph.addNode(five);

        graph.addEdge(zero, one);
        graph.addEdge(zero, five);

        graph.addEdge(one, zero);
        graph.addEdge(one, two);
        graph.addEdge(one, three);

        graph.addEdge(two, one);
        graph.addEdge(two, four);

        graph.addEdge(three, one);
        graph.addEdge(three, four);
        graph.addEdge(three, five);

        graph.addEdge(four, three);
        graph.addEdge(four, two);
        graph.addEdge(four, five);

        graph.addEdge(five, three);
        graph.addEdge(five, zero);
        graph.addEdge(five, four);

        CycleDetection detection = new CycleDetection(graph);
        detection.detectCycles(five);
    }

    public void detectCycles(Node source) {
        this.stack.push(source);

        while (!this.stack.isEmpty()) {
            Node node = this.stack.pop();
            node.color = "grey";
            this.visited.add(node);

            Set<Node> neighbours = this.graph.edgesFrom(node);
            for (Node neighbour : neighbours) {
                if (!"grey".equals(neighbour.color)) {
                    if (this.stack.contains(neighbour)) {
                        System.out.println("Edge (" + node + ", " + neighbour + ") forms a backedge");
                        System.out.println("Visited " + this.visited);
                    }
                    this.stack.push(neighbour);
                }
            }
        }
    }
}

And here are the two classes, Graph and Node, used by the algorithm:

//Thanks to Keith Schwarz    
class Graph<T> {
    private final Map<T, Set<T>> graph;

    public Graph() {
        super();
        this.graph = new HashMap<T, Set<T>>();
    }

    public Set<T> getNodes() {
        return Collections.unmodifiableSet(this.graph.keySet());
    }

    public Set<T> edgesFrom(T node) {
        Set<T> adjacentNodes = this.graph.get(node);
        if (adjacentNodes == null) {
            throw new NoSuchElementException("Node doesn't exist in the graph");
        }
        return Collections.unmodifiableSet(adjacentNodes);
    }

    // Create a default empty edge set
    public boolean addNode(T node) {
        if (node == null) {
            throw new IllegalArgumentException("Node can't be null");
        }

        if (!this.graph.containsKey(node)) {
            this.graph.put(node, new HashSet<T>());
        }
        return true;
    }

    // Removes all the associated edges of this node
    public void removeNode(T node) {
        if (node == null) {
            throw new IllegalArgumentException("Node can't be null");
        }

        if (this.graph.containsKey(node)) {
            this.graph.remove(node);
        }
    }

    public void addEdge(T one, T two) {
        requireNonNullAndGraphContains(one, two);
        this.graph.get(one).add(two);
    }

    public void removeEdge(T one, T two) {
        requireNonNullAndGraphContains(one, two);
        this.graph.get(one).remove(two);
    }

    public boolean edgeExists(T one, T two) {
        requireNonNullAndGraphContains(one, two);
        return this.graph.get(one).contains(two);
    }

    private void requireNonNullAndGraphContains(T one, T two) {
        if (one == null || two == null) {
            throw new IllegalArgumentException("One or both of the arguments are null.");
        }

        if (!this.graph.containsKey(one) || !this.graph.containsKey(two)) {
            throw new IllegalArgumentException("One or both of the arguments are not part of the " + "" + "graph");
        }
    }

    public int size() {
        return this.graph.size();
    }

    @Override
    public String toString() {
        return this.graph.toString();
    }
}

class Node implements Comparable<Node> {
    private final String name;
    String color;
    private double weight = 0;// Default node weight is zero

    public Node(String name) {
        super();
        this.name = name;
        this.color = "white";
    }

    public String getName() {
        return name;
    }

    public double getWeight() {
        return weight;
    }

    public void setWeight(double weight) {
        this.weight = weight;
    }

    @Override
    public int compareTo(Node other) {
        return Double.compare(other.weight, this.weight);
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        long temp;
        temp = Double.doubleToLongBits(weight);
        result = prime * result + (int) (temp ^ (temp >>> 32));
        return result;
    }

    @Override
    public boolean equals(Object object) {
        if (this == object) {
            return true;
        }
        if (object == null) {
            return false;
        }
        if (getClass() != object.getClass()) {
            return false;
        }
        Node other = (Node) object;
        if (name == null) {
            if (other.name != null) {
                return false;
            }
        } else if (!name.equals(other.name)) {
            return false;
        }
        if (Double.doubleToLongBits(weight) != Double.doubleToLongBits(other.weight)) {
            return false;
        }
        return true;
    }

    @Override
    public String toString() {
        return name;
    }
}

How can I improve the code?

\$\endgroup\$
3
\$\begingroup\$

Don't use fields when you don't need them

stack and visited don't need to be fields in CycleDetection. They can be local variables in the detectCycles method:

class CycleDetection {
    private final Graph<Node> graph;

    public CycleDetection(Graph<Node> graph) {
        this.graph = graph;
    }

    public void detectCycles(Node source) {
        Deque<Node> stack = new ArrayDeque<Node>();
        Set<Node> visited = new LinkedHashSet<Node>();

        stack.push(source);

        // ...

Avoid magic string literals

The string literal "grey" appears twice. This is error-prone, as if you want to change later, you have to remember to make the same change everywhere. You might also mistype it. It's better to put it in private static final String variable (a constant).

Use the diamond operator <>

As of Java 7, you don't need to specify the generic type parameters when instantiating objects when the type can be inferred from the context like here:

    Deque<Node> stack = new ArrayDeque<Node>();
    Set<Node> visited = new LinkedHashSet<Node>();

You can simplify using the diamond operator <>

    Deque<Node> stack = new ArrayDeque<>();
    Set<Node> visited = new LinkedHashSet<>();

Use unit tests

Instead of the main and main1 methods, it would be better to use unit tests, for example JUnit4 is very easy to use and enabled by default in modern IDEs.

However, to use it, you will also need to rework the detectCycles method to return something instead of printing. Reading output is not a good way of testing, as it cannot be automated.

\$\endgroup\$

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.