Find cycle/loop in the graph – Find and Union with Path Compression
To identify loop in the graph, We are going to use Find and Union technic with Path Compression. We are going to create subject of each vertex and we will represent one element of that subset as a parent, So next time we will take two vertex will check the parent of each, if both has same parent then loop found.
See Utility for graph to get Graph and Node class
Lets see below two graphs,
Find same algorithm without using path compression
Find algorithm below.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 |
package com.omt.learn.geekforgeek.greedy; import java.util.HashMap; import java.util.Map; import com.omt.learn.algo.util.graph.Graph; import com.omt.learn.algo.util.graph.Node; import com.omt.learn.algo.util.graph.State; public class FindCycleInGraphUnionFindPathComp { public static void main(String[] args) { System.out.println("Is Cycle Found:" + isCycleInGraph(generateLoopGraph())); System.out.println("Is Cycle Found:" + isCycleInGraph(generateNonLoopGraph())); } public static boolean isCycleInGraph(Graph graph) { Map<Node, Node> subSet = new HashMap<Node, Node>(); for (Node n : graph.getVertices()) { if (n.getAdjacent() != null && !n.getAdjacent().isEmpty()) { n.setState(State.VISITED); for (Node to : n.getAdjacent()) { if (to.isVisited()) { continue; } Node n1 = find(subSet, n); Node n2 = find(subSet, to); if (n1 == n2) { prettyPrintMap(subSet); return true; } else { union(subSet, n, to); } } } } prettyPrintMap(subSet); return false; } public static Node find(Map<Node, Node> subSet, Node n) { if (subSet.get(n) == null) { return n; } return find(subSet, subSet.get(n)); } public static void union(Map<Node, Node> subSet, Node from, Node to) { Node n1 = find(subSet, from); Node n2 = find(subSet, to); //Below code is for PATH COMPRESSION if (n1.getNodeId() < n2.getNodeId()) { subSet.put(n2, n1); } else if (n1.getNodeId() > n2.getNodeId()) { subSet.put(n1, n2); } else { n1.setNodeId(n1.getNodeId() + 1); subSet.put(n1, n2); } } public static Graph generateLoopGraph() { Graph graph = new Graph(); Node a = new Node("A"); // 0 Node b = new Node("B"); // 1 Node c = new Node("C"); // 2 Node d = new Node("D"); // 3 Node e = new Node("E"); // 4 Node f = new Node("F"); // 5 Node g = new Node("G"); // 6 Node h = new Node("H"); // 7 Node i = new Node("I"); // 8 a.addAdjacent(b); a.addAdjacent(c); b.addAdjacent(d); b.addAdjacent(a); d.addAdjacent(b); d.addAdjacent(e); d.addAdjacent(f); e.addAdjacent(d); e.addAdjacent(f); e.addAdjacent(g); f.addAdjacent(e); f.addAdjacent(d); f.addAdjacent(g); g.addAdjacent(e); g.addAdjacent(f); c.addAdjacent(a); c.addAdjacent(h); h.addAdjacent(c); graph.addVertex(a); graph.addVertex(b); graph.addVertex(c); graph.addVertex(d); graph.addVertex(e); graph.addVertex(f); graph.addVertex(g); graph.addVertex(h); graph.addVertex(i); return graph; } public static Graph generateNonLoopGraph() { Graph graph = new Graph(); Node a = new Node("A"); // 0 Node b = new Node("B"); // 1 Node c = new Node("C"); // 2 Node d = new Node("D"); // 3 Node e = new Node("E"); // 4 Node f = new Node("F"); // 5 Node g = new Node("G"); // 6 Node h = new Node("H"); // 7 Node i = new Node("I"); // 8 a.addAdjacent(b); a.addAdjacent(c); b.addAdjacent(d); b.addAdjacent(a); d.addAdjacent(b); d.addAdjacent(f); e.addAdjacent(i); e.addAdjacent(g); f.addAdjacent(d); f.addAdjacent(g); g.addAdjacent(e); g.addAdjacent(f); c.addAdjacent(a); c.addAdjacent(h); h.addAdjacent(c); i.addAdjacent(e); graph.addVertex(a); graph.addVertex(b); graph.addVertex(c); graph.addVertex(h); graph.addVertex(d); graph.addVertex(f); graph.addVertex(g); graph.addVertex(e); graph.addVertex(i); return graph; } public static void prettyPrintMap(Map<Node, Node> subSet) { for (Node key : subSet.keySet()) { System.out.println(key.getVertex() + "->" + subSet.get(key).getVertex()); } } } |
Output of above algorithm
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
F->A H->A D->A C->A E->A B->A Is Cycle Found:true F->A I->A D->A B->A C->A H->A E->A G->A Is Cycle Found:false |
