# Finding all backedges in an undirected graph

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>();
}

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>();

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>();

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";

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) {
throw new NoSuchElementException("Node doesn't exist in the graph");
}
}

// Create a default empty edge set
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);
}

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?

### 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>();

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>();


You can simplify using the diamond operator <>

    Deque<Node> stack = new ArrayDeque<>();


### 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.