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

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

Leave a Reply