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>();
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
A Business Intelligence Framework
Subscribe
Login
0 Comments