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.

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>(); 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 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; visited.add(node); 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) { 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; } }

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

**Best Open Source Business Intelligence Software Helical Insight is Here**