Detect a cycle in online graph where edges are added continuously?

Question

How to detect a cycle in a directed graph where edges are added one after the other. If adding the latest edge results in cycle creation than that edge should not be added.

What can be the optimal solution for the above problem?

is is sufficient to detect that the graph has a loop (a boolean answer) or the edges that comprise the loops should also be found (like A -> B -> C ->A) ? — Mark Bramnik, Dec 28 '16 at 03:56
What do you need this for? It's likely that your specific problem is easier than this general one. — Matt Timmermans, Dec 28 '16 at 03:57
@MattTimmermans this is the complete problem statement given — Rishabh Agarwal jain, Dec 28 '16 at 04:02
dupe of http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph ? — denvercoder9, Dec 28 '16 at 04:26

Sendhilkumar Alalasundaram · Answer 1 · 2016-12-28T04:48:16.477

In Directed graph, suppose you were to add an edge from u to v :

You have to check if v and u are already connected. You can use BFS or DFS to do that.

If you have determined that there is a connection from v to u, then adding an edge from u to v will result in a cycle.

For Demo, I've taken an implementation of graph from the internet and added the logic for whether the path exists from v to u. This logic is in function doesPathExistBetween(V from, V to) in the following code.

package java8new;

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Digraph<V> {

    public static class Edge<V> {
        private V vertex;
        private int cost;

        public Edge(V v, int c) {
            vertex = v;
            cost = c;
        }

        public V getVertex() {
            return vertex;
        }

        public int getCost() {
            return cost;
        }

        @Override
        public String toString() {
            return "Edge [vertex=" + vertex + ", cost=" + cost + "]";
        }

    }

    /**
     * A Map is used to map each vertex to its list of adjacent vertices.
     */

    private Map<V, List<Edge<V>>> neighbors = new HashMap<V, List<Edge<V>>>();

    /**
     * String representation of graph.
     */
    public String toString() {
        StringBuffer s = new StringBuffer();
        for (V v : neighbors.keySet())
            s.append("\n    " + v + " -> " + neighbors.get(v));
        return s.toString();
    }

    /**
     * Add a vertex to the graph. Nothing happens if vertex is already in graph.
     */
    public void add(V vertex) {
        if (neighbors.containsKey(vertex))
            return;
        neighbors.put(vertex, new ArrayList<Edge<V>>());
    }

    /**
     * Add an edge to the graph; if either vertex does not exist, it's added.
     * This implementation allows the creation of multi-edges and self-loops.
     */
    public void add(V from, V to, int cost) {
        this.add(from);
        this.add(to);
        neighbors.get(from).add(new Edge<V>(to, cost));
    }

    public List<V> outboundNeighbors(V vertex) {
        List<V> list = new ArrayList<V>();
        for (Edge<V> e : neighbors.get(vertex))
            list.add(e.vertex);
        return list;
    }

    public void bfs(V root) {
        // Since queue is a interface
        Queue<V> queue = new LinkedList<V>();
        Map<V, Boolean> visited = new HashMap<V, Boolean>();

        if (root == null)
            return;

        visited.put(root, Boolean.TRUE);
        // Adds to end of queue
        queue.add(root);

        while (!queue.isEmpty()) {
            // removes from front of queue
            V r = queue.remove();
            System.out.println(r.toString());

            // Visit child first before grandchild
            for (V n : outboundNeighbors(r)) {
                if (!visited.containsKey(n)) {

                    queue.add(n);
                    visited.put(n, Boolean.TRUE);
                }
            }
        }
    }

    public Boolean doesPathExistBetween(V from, V to) {
        Queue<V> queue = new LinkedList<V>();
        Map<V, Boolean> visited = new HashMap<V, Boolean>();

        visited.put(from, Boolean.TRUE);

        // Adds to end of queue
        queue.add(from);

        while (!queue.isEmpty()) {
            // removes from front of queue
            V r = queue.remove();

            // Visit child first before grandchild
            for (V n : outboundNeighbors(r)) {
                if (!visited.containsKey(n)) {
                    if (n.equals(to))
                        return Boolean.TRUE;
                    queue.add(n);
                    visited.put(n, Boolean.TRUE);
                }
            }
        }
        return Boolean.FALSE;

    }

    public static void main(String[] args) throws IOException {

        Digraph<Integer> graph = new Digraph<Integer>();
        // Adding vertices
        graph.add(0);
        graph.add(1);
        graph.add(2);
        graph.add(3);
        // Adding Edges with weights
        graph.add(0, 1, 1);
        graph.add(1, 2, 2);
        graph.add(3, 0, 2);

        System.out.println("Path betwen 0 to 2 exists : " + graph.doesPathExistBetween(0, 2));
        System.out.println("Path betwen 1 to 3 exists : " + graph.doesPathExistBetween(1, 3));

        graph.bfs(0);
        graph.bfs(1);

    }
}

If connected refers to same component then suppose graph is 1->2->3,2->4, then as per your algorithm adding 4->3 will result in cycle, which is not true. — Rishabh Agarwal jain, Dec 28 '16 at 04:15
No, You'll check if there exists a path between 4 and 2. If not then you will go ahead and add 2->4. — Sendhilkumar Alalasundaram, Dec 28 '16 at 04:19
The logic to find if there is a path from 4 to 2 can use BFS or DFS — Sendhilkumar Alalasundaram, Dec 28 '16 at 04:20

score 1 · Answer 2 · answered Dec 28 '16 at 18:04

Algorithms for this problem are still a subject of research, but for many practical cases, it helps a lot to maintain the dominator tree for the graph as you add edges ( https://en.wikipedia.org/wiki/Dominator_(graph_theory) ).

Maintaining the dominator tree can be done amortized O(log(V+E)) time per add operation, or maybe a little better.

You still need to do a DFS or BFS when you add an edge, but since all vertices in a cycle go through the same immediate dominator, you only need to search vertices that will be children of the same parent, and that parent itself, in the dominator tree in order to detect that cycle.

If cycles are disallowed as you build the graph, it is likely that there will be a lot of dominators and the number of nodes you have to search for each edge insert will be small.

I'm interested in this, your approach makes sense. What would you do in the case that there is no natural entry node. Perhaps make an artificial entry node whose children are all nodes without parents in the target graph? Then if a node is dominated by the entry node, you must dfs from all these children. — Daniel, Oct 18 '20 at 06:54
Yes, you can use a dominator from *any* entry node that reaches the vertices, so your plan would work. — Matt Timmermans, Oct 18 '20 at 13:18

score 0 · Answer 3 · edited Jun 25 '18 at 09:02

The straightforward algorithm then would be like:

Traverse the graph (BFS will do the job)
When exploring the node, mark it like 'ok, I've been there'. You can use some HashSet for doing this.
If the node is already in a set then you're coming to it for the second time, so there is a loop - you can safely return 'this graph has a loop' answer.

Now given a graph in a state X (current state) doesn't have a loop, them when adding a new edge between the vertexes A --> B can create a new loop. But in this case A will be always a part of such a loop. So it makes sense to re-start a traversal from A. The chances that you'll find it faster depending on size and nature of the graph.

score 0 · Answer 4 · answered Jan 19 '21 at 05:01

If you are writing the code for Kruskal's algo to find minimum spanning tree for a Graph, that time you will encounter this use case. You have to sort all the edges based on there weight and pick on by one to form the graph . And for each edge , you have to check if it is forming any cycle or not.

public boolean isThisEdgeFormingLoop(Edge n) {
        int parent=0 ;int rank =1;
        
        int fromParent=parentRankMatrix[parent][n.getFrom()];
        int toParent=parentRankMatrix[parent][n.getTo()];
        if(fromParent==-1 && toParent==-1) {
            if(parentRankMatrix[rank][n.getTo()] > parentRankMatrix[rank][n.getFrom()]) {
                parentRankMatrix[parent][n.getFrom()]=n.getTo();
            }else if(parentRankMatrix[rank][n.getTo()] < parentRankMatrix[rank][n.getFrom()]) {
                parentRankMatrix[parent][n.getTo()]=n.getFrom();
            }else {
                parentRankMatrix[rank][n.getTo()]++;
                parentRankMatrix[parent][n.getFrom()]=n.getTo();
            }
            return false;
        }else {
            int absFromParent=getAbsoluteParent(n.getFrom());
            int absToParent=getAbsoluteParent(n.getTo());   
            if(absFromParent==absToParent) {
                return true;
            }else {
                if(parentRankMatrix[rank][absFromParent] > parentRankMatrix[rank][absToParent]) {
                    parentRankMatrix[parent][absToParent]=absFromParent;
                }else if(parentRankMatrix[rank][absFromParent] < parentRankMatrix[rank][absToParent]){
                    parentRankMatrix[parent][absFromParent]=absToParent;
                }else {
                    parentRankMatrix[rank][absToParent]++;
                    parentRankMatrix[parent][absFromParent]=absToParent;
                }
                return false;
            } 
        }
    }

Full implementation link and video explanation :

https://github.com/Sandip9021/Ds-Algo/tree/master/src/kruskal

https://www.youtube.com/watch?v=SPIyJOMI5Jc&t=209s

Detect a cycle in online graph where edges are added continuously?

4 Answers4