Find cycle/loop in the graph – Find and Union

May 17, 2018 by omt

To identify loop in the graph, We are going to use Find and Union technic. 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 algorithm below.

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 FindCycleInGraphUnionFind {

	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);

		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());
		}
	}
}

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

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 FindCycleInGraphUnionFind {

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);

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 :

A->B
H->E
D->H
C->D
E->F
B->C
Is Cycle Found:true
F->G
A->B
D->H
B->C
C->D
H->F
E->I
G->E
Is Cycle Found:false

A->B

H->E

D->H

C->D

E->F

B->C

Is Cycle Found:true

F->G

A->B

D->H

B->C

C->D

H->F

E->I

G->E

Is Cycle Found:false