fork download
copy 
  1.  
  2.  
  3. /**
  4.  * Rishi Verma
  5.  * rktios@gmail.com
  6.  * 21-March-2015
  7.  * Common graph implementations in Java
  8.  */
  9. import java.util.HashMap;
  10. import java.util.LinkedList;
  11. import java.util.Queue;
  12. import java.util.Set;
  13. import java.util.Stack;
  14.  
  15. class GraphNode {
  16. 	private HashMap<Integer, LinkedList<Integer>> adjList = null;
  17. 	private HashMap<Integer, Boolean> visited = null;
  18. 	public Stack<Integer> topologicalSortStack = new Stack<Integer>();
  19.  
  20. 	enum BIPARTITECOLOR {
  21. 		NOTVISITED, RED, BLUE
  22. 	}
  23.  
  24. 	private HashMap<Integer, BIPARTITECOLOR> bipartiteColor = null;
  25.  
  26. 	public void initializeBipartiteColor() {
  27.  
  28. 		bipartiteColor = new HashMap<Integer, BIPARTITECOLOR>();
  29.  
  30. 		for (int node : adjList.keySet()) {
  31. 			bipartiteColor.put(node, BIPARTITECOLOR.NOTVISITED);
  32. 		}
  33. 	}
  34.  
  35. 	public GraphNode(int node[]) {
  36. 		System.out.println("GraphNode.GraphNode()");
  37.  
  38. 		adjList = new HashMap<Integer, LinkedList<Integer>>();
  39.  
  40. 		for (int i : node) {
  41. 			adjList.put(i, new LinkedList<Integer>());
  42. 		}
  43.  
  44. 	}
  45.  
  46. 	void checkBipartite(int source) {
  47. 		initializeBipartiteColor();
  48. 		Queue<Integer> q = new LinkedList<Integer>();
  49. 		q.add(source);
  50. 		bipartiteColor.put(source, BIPARTITECOLOR.RED);
  51. 		System.out.println(doCheckBipartite(q));
  52.  
  53. 	}
  54.  
  55. 	boolean doCheckBipartite(Queue<Integer> q) {
  56.  
  57. 		if (false == q.isEmpty()) {
  58.  
  59. 			int currentNode = q.remove();
  60. 			BIPARTITECOLOR color = bipartiteColor.get(currentNode);
  61. 			LinkedList<Integer> neighbours = findNeighbour(currentNode);
  62.  
  63. 			for (Integer neighbour : neighbours) {
  64. 				if (bipartiteColor.get(neighbour) == BIPARTITECOLOR.NOTVISITED) {
  65. 					q.add(neighbour);
  66. 					if (color == BIPARTITECOLOR.RED) {
  67. 						bipartiteColor.put(neighbour, BIPARTITECOLOR.BLUE);
  68. 					} else {
  69. 						bipartiteColor.put(neighbour, BIPARTITECOLOR.RED);
  70. 					}
  71. 				} else {
  72. 					if (color == bipartiteColor.get(neighbour)) {
  73. 						return false;
  74. 					}
  75. 				}
  76. 			}
  77. 			return doCheckBipartite(q);
  78.  
  79. 		}
  80. 		return true;
  81. 	}
  82.  
  83. 	public void addEdge(int source, int destination) {
  84.  
  85. 		adjList.get(source).add(destination);
  86.  
  87. 	}
  88.  
  89. 	public LinkedList<Integer> findNeighbour(int node) {
  90. 		// System.out.println("GraphNode.findNeighbour() source: " + node);
  91.  
  92. 		LinkedList<Integer> neighbours = adjList.get(node);
  93.  
  94. 		for (Integer i : neighbours) {
  95. 			// System.out.println(i);
  96. 		}
  97.  
  98. 		return neighbours;
  99. 	}
  100.  
  101. 	public void initializeVisitedMap() {
  102. 		System.out.println("GraphNode.dfs()");
  103. 		// Creating Visited hashmap
  104. 		visited = new HashMap<Integer, Boolean>();
  105. 		Set<Integer> key = adjList.keySet();
  106. 		for (int i : key) {
  107. 			visited.put(i, false);
  108. 		}
  109.  
  110. 		// doDfs(source);
  111.  
  112. 	}
  113.  
  114. 	public void dfs(int source) {
  115.  
  116. 		if (true == visited.get(source)) {
  117. 			return;
  118. 		}
  119. 		visited.put(source, true);
  120. 		System.err.println("GraphNode.doDfs() " + source);
  121.  
  122. 		LinkedList<Integer> neighbours = findNeighbour(source);
  123. 		for (int neighbour : neighbours) {
  124. 			dfs(neighbour);
  125.  
  126. 		}
  127. 	}
  128.  
  129. 	public void bfs(int source) {
  130.  
  131. 		Queue<Integer> bfsq = new LinkedList<Integer>();
  132. 		bfsq.add(source);
  133. 		visited.put(source, true);
  134. 		doBfs(bfsq);
  135. 	}
  136.  
  137. 	private void doBfs(Queue<Integer> q) {
  138. 		if (q.isEmpty() == false) {
  139. 			Integer currentNode = q.remove();
  140.  
  141. 			System.err.println("GraphNode.bfs() " + currentNode);
  142.  
  143. 			LinkedList<Integer> neighbours = findNeighbour(currentNode);
  144. 			for (Integer i : neighbours) {
  145. 				if (false == visited.get(i)) {
  146. 					visited.put(i, true);
  147. 					q.add(i);
  148. 				}
  149.  
  150. 			}
  151. 			doBfs(q);
  152. 		}
  153. 	}
  154.  
  155. 	private void topologicalSortOnEachNode(int source) {
  156. 		if (true == visited.get(source)) {
  157. 			return;
  158. 		}
  159. 		visited.put(source, true);
  160. 		LinkedList<Integer> neighbours = adjList.get(source);
  161. 		for (Integer i : neighbours) {
  162. 			topologicalSortOnEachNode(i);
  163. 		}
  164. 		topologicalSortStack.push(source);
  165.  
  166. 	}
  167.  
  168. 	public void topologicalSort() {
  169.  
  170. 		Set<Integer> nodes = adjList.keySet();
  171. 		for (Integer node : nodes) {
  172. 			System.out.println("GraphNode.topologicalSort() " + node);
  173. 			topologicalSortOnEachNode(node);
  174. 		}
  175.  
  176. 	}
  177.  
  178. 	public void printTopologicalSortStack() {
  179. 		System.out.println("GraphNode.printTopologicalSortStack()");
  180.  
  181. 		/*
  182. 		 * for (Integer i : topologicalSortStack) { System.out.println(i); }
  183. 		 */
  184.  
  185. 		while (topologicalSortStack.isEmpty() == false) {
  186. 			System.out.println(topologicalSortStack.pop());
  187. 		}
  188. 	}
  189.  
  190. 	/**
  191. 	 *
  192. 	 * 
  193. 	 * @param source
  194. 	 * @param parent
  195. 	 */
  196. 	public boolean isCyclic(int source, int parent) {
  197.  
  198. 		if (true == visited.get(source)) {
  199. 			return true;
  200. 		}
  201. 		visited.put(source, true);
  202.  
  203. 		LinkedList<Integer> neighbours = findNeighbour(source);
  204. 		for (int neighbour : neighbours) {
  205. 			if (parent != neighbour && true == visited.get(neighbour)) {
  206. 				System.out.println("isCyclic() TRUE Source" + source
  207. 						+ " Parent " + parent + "Neighbour" + neighbour);
  208. 				return true;
  209. 			}
  210.  
  211. 			return isCyclic(neighbour, source);
  212.  
  213. 		}
  214. 		return false;
  215. 	}
  216.  
  217. }
  218.  
  219. class Graph {
  220.  
  221. 	public static void main(String[] args) {
  222. 		System.out.println("Graph.main()");
  223. 		// GraphNode graphNode = createGraphExampleForDfs();
  224.  
  225. 		GraphNode graphNode = createGraphExampleForCycle();
  226. 		// GraphNode graphNode = createGraphExampleForTopologicalSort();
  227. 		// GraphNode graphNode = createGraphExampleForBiPartite();
  228. 		// graphNode.findNeighbour(1);
  229. 		graphNode.initializeVisitedMap();
  230. 		// graphNode.topologicalSort();
  231. 		// graphNode.printTopologicalSortStack();
  232. 		// graphNode.dfs(2);
  233. 		System.out.println("IS cyclic " + graphNode.isCyclic(3, 3));
  234. 		// graphNode.bfs(4);
  235. 		// graphNode.checkBipartite(4);
  236. 	}
  237.  
  238. 	private static GraphNode createGraphExampleForBiPartite() {
  239.  
  240. 		int node[] = { 0, 1, 2, 3, 4 };
  241. 		GraphNode graphNode = new GraphNode(node);
  242.  
  243. 		graphNode.addEdge(0, 1);
  244. 		graphNode.addEdge(0, 4);
  245.  
  246. 		graphNode.addEdge(1, 0);
  247. 		graphNode.addEdge(1, 2);
  248.  
  249. 		graphNode.addEdge(2, 1);
  250. 		graphNode.addEdge(2, 3);
  251.  
  252. 		graphNode.addEdge(3, 2);
  253. 		graphNode.addEdge(3, 4);
  254.  
  255. 		graphNode.addEdge(4, 0);
  256. 		graphNode.addEdge(4, 3);
  257.  
  258. 		return graphNode;
  259. 	}
  260.  
  261. 	private static GraphNode createGraphExampleForTopologicalSort() {
  262. 		int nodeList[] = { 0, 1, 2, 3, 4, 5 };
  263. 		// Ref graph
  264. 		// http://c...content-available-to-author-only...g.com/images/topologicalsort.png
  265. 		GraphNode graphNode = new GraphNode(nodeList);
  266.  
  267. 		graphNode.addEdge(2, 3);
  268.  
  269. 		graphNode.addEdge(3, 1);
  270.  
  271. 		graphNode.addEdge(4, 0);
  272. 		graphNode.addEdge(4, 1);
  273.  
  274. 		graphNode.addEdge(5, 0);
  275. 		graphNode.addEdge(5, 2);
  276.  
  277. 		return graphNode;
  278. 	}
  279.  
  280. 	private static GraphNode createGraphExampleForDfs() {
  281. 		int nodeList[] = { 0, 1, 2, 3, 4 };
  282. 		// Ref graph
  283. 		/*
  284. 		 * http://d...content-available-to-author-only...t.net/wp-content/uploads/
  285. 		 * graph_representation12.png
  286. 		 */
  287. 		GraphNode graphNode = new GraphNode(nodeList);
  288. 		graphNode.addEdge(0, 1);
  289. 		graphNode.addEdge(0, 4);
  290.  
  291. 		graphNode.addEdge(1, 0);
  292. 		graphNode.addEdge(1, 2);
  293. 		graphNode.addEdge(1, 3);
  294. 		graphNode.addEdge(1, 4);
  295.  
  296. 		graphNode.addEdge(2, 1);
  297. 		graphNode.addEdge(2, 3);
  298.  
  299. 		graphNode.addEdge(3, 1);
  300. 		graphNode.addEdge(3, 2);
  301. 		graphNode.addEdge(3, 4);
  302.  
  303. 		graphNode.addEdge(4, 0);
  304. 		graphNode.addEdge(4, 1);
  305. 		graphNode.addEdge(4, 3);
  306.  
  307. 		return graphNode;
  308. 	}
  309.  
  310. 	// For testing cycleGraph
  311. 	private static GraphNode createGraphExampleForCycle() {
  312. 		int nodeList[] = { 0, 1, 2, 3, 4, 5 };
  313. 		// Ref graph
  314. 		/*
  315. 		 * http://d...content-available-to-author-only...t.net/wp-content/uploads/cycleGraph-300
  316. 		 * x156.png
  317. 		 */GraphNode graphNode = new GraphNode(nodeList);
  318. 		graphNode.addEdge(0, 1);
  319. 		graphNode.addEdge(0, 3);
  320. 		graphNode.addEdge(0, 5);
  321.  
  322. 		graphNode.addEdge(1, 0);
  323. 		graphNode.addEdge(1, 2);
  324.  
  325. 		graphNode.addEdge(2, 1);
  326. 		graphNode.addEdge(2, 5);
  327.  
  328. 		graphNode.addEdge(3, 0);
  329. 		graphNode.addEdge(3, 4);
  330.  
  331. 		graphNode.addEdge(4, 3);
  332.  
  333. 		graphNode.addEdge(5, 0);
  334. 		graphNode.addEdge(5, 2);
  335.  
  336. 		return graphNode;
  337. 	}
  338. }
  339.  
Success #stdin #stdout 0.1s 320256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Graph.main()
GraphNode.GraphNode()
GraphNode.dfs()
IS cyclic true
https://ideone.com/TA4ldc
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!