Finding all the backedges in an undirected graph

Finding cycles in a graph is an interesting problem. We say that a cycle is formed if there is a way to reach the source without visiting already visited vertices.

In this article I will discuss about finding all the backedges in an undirected graph so that we can determine how many cycles are present in the graph. If there are no backedges in a graph it means that there can’t be any cycles in that graph.

Undirected Graph

For example in the above diagram, the edge between B and F forms one backedge.

```public class CycleDetection {
private final Graph<Node> graph;
private static final String GREY_COLOR = "grey";

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

public static void main(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 void detectCycles(Node source) {
final Deque<Node> stack = new ArrayDeque<Node>();
final Set<Node> visited = new LinkedHashSet<Node>();

stack.push(source);

while (!stack.isEmpty()) {
Node node = stack.pop();
node.color = GREY_COLOR;

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

//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;
}
}
```

Hope you have followed the self explanatory code…

Thanks to Janos(http://codereview.stackexchange.com/users/12390/janos) – For his insights on improving the code

–Rajasekhar
Helical IT Solutions