fork(6) download
copy 
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.Iterator;
  4. import java.util.List;
  5. import java.util.Map;
  6. import java.util.Set;
  7. import java.util.Stack;
  8. /**
  9.  * Directed Graph API
  10.  * @author Prateek
  11.  */
  12.  class DiGraph {
  13.  
  14. 	protected int numVertices;
  15. 	protected int numEdges;
  16.  
  17. 	//Map to maintain adjacency List
  18. 	protected Map<Integer,List<Integer>> adjList;
  19. 	// Map to maintain visit status
  20. 	protected Map<Integer, Boolean> vistedStatus;
  21.  
  22. 	/*
  23. 	 * Constructor when number of vertices are not known
  24. 	 */
  25. 	public DiGraph() {
  26. 		this.adjList = new HashMap<Integer,List<Integer>>();
  27. 		this.vistedStatus = new HashMap<Integer, Boolean>() ; 
  28. 	}
  29.  
  30. 	/*
  31. 	 * Constructor when number of vertices are known
  32. 	 */
  33. 	public DiGraph(int V) {
  34. 		this.numVertices = V;
  35. 		this.adjList = new HashMap<Integer,List<Integer>>(V);
  36. 		this.vistedStatus = new HashMap<Integer, Boolean>(V) ; 
  37. 	}
  38.  
  39. 	/**
  40. 	 * Edge in a directed graph
  41. 	 */
  42. 	protected void addEdge(int src, int dest) {
  43. 		List<Integer> list=adjList.get(src);			
  44. 		if(list==null)
  45. 			list=new ArrayList<Integer>();
  46.  
  47. 		list.add(dest);
  48. 		adjList.put(src,list);	
  49. 		vistedStatus.put(src, false);  //visit status set to false
  50. 		vistedStatus.put(dest, false);
  51. 	}
  52.  
  53. 	/**
  54. 	 * DFS run on a given vertex
  55. 	 * @param vertex
  56. 	 */
  57. 	protected void dfsUtil(int vertex){
  58. 		List <Integer> list = adjList.get(vertex) ;
  59.  
  60. 		vistedStatus.put(vertex, true) ;
  61. 		System.out.print(vertex + "\t");
  62.  
  63. 		if(list!=null){
  64. 			int size = list.size();
  65. 			for(int i = 0;i < size ; i++){
  66. 				int v=list.get(i);
  67. 				if(!vistedStatus.get(v))
  68. 					dfsUtil(v);
  69. 			}
  70. 		}
  71. 	}
  72. }
  73. //------------------------------------------------------------------------------------
  74. /**
  75.  * SCC for a direceted Graph
  76.  * @author Prateek
  77.  */
  78.  class SCC extends DiGraph{
  79.  
  80. 	//Stack to hold finishing times i.e reverse post-order of DFS
  81. 	private Stack<Integer> stack = new Stack<Integer>();
  82.  
  83. 	//Adjacency List to hold transpose Graph
  84. 	private Map<Integer,List<Integer>> reverseAdjList;
  85.  
  86. 	/**Contructor
  87. 	 * If number of vertices is not given
  88. 	 */
  89. 	public SCC() {
  90. 		this.reverseAdjList = new HashMap<Integer,List<Integer>>(numVertices) ; 
  91. 	}
  92.  
  93. 	/**
  94. 	 * Constructor: If number of vertices is given
  95. 	 */
  96. 	public SCC(int numVertices) {
  97. 		super(numVertices);
  98. 		this.reverseAdjList = new HashMap<Integer,List<Integer>>(numVertices) ; 
  99. 	}
  100.  
  101.  
  102. 	/*=========Computes SCC Starts===================*/
  103. 	/**
  104. 	 * Computes SCC, performs Kosaraju's Steps
  105. 	 */
  106. 	private void computeSCC(SCC g){
  107.  
  108. 		//Step1: Reverse Graph
  109. 		//Transpose Graph
  110. 		transpose(g);
  111.  
  112. 		Set<Map.Entry<Integer,Boolean>> set= vistedStatus.entrySet();
  113. 		Iterator<Map.Entry<Integer, Boolean>> it= set.iterator();
  114.  
  115. 		//Step 2 : Fill Stack
  116. 		 //1st DFS on Reversed Graph
  117. 		//Calcating Reverse Post order
  118. 		while(it.hasNext()){
  119. 			Map.Entry<Integer, Boolean> entry=it.next();
  120. 			int vertex= entry.getKey();
  121. 			boolean isVisited= entry.getValue();
  122. 			if(!isVisited){
  123. 				fillOrderStackDFS(vertex);
  124. 			}
  125. 		}
  126.  
  127. 		//Reset Visit Status
  128. 		resetVisitStatus();
  129.  
  130.  
  131. 		System.out.println("SCCs of Digraph: ");
  132.  
  133. 		//Step 3: Run DFS using the Stack
  134. 		//2nd DFS on Original Graph
  135. 		while(!stack.isEmpty()){
  136.  
  137. 			int poped=stack.pop();
  138. 			if(!vistedStatus.get(poped))
  139. 			{
  140. 				System.out.println("===========================");
  141. 				dfsUtil(poped);
  142. 				System.out.println();
  143. 			}
  144.  
  145. 		}
  146. 		System.out.println("===========================");
  147. 	}
  148.  
  149. 	/*=============Reversing of Graph Starts================== */
  150. 	/**
  151. 	 * Transpose given Graph, ie. reverse all the edges
  152. 	 * @param g
  153. 	 */
  154. 	private void transpose(SCC g){
  155.  
  156. 		Set<Map.Entry<Integer, Boolean>> set=vistedStatus.entrySet();	
  157. 		Iterator<Map.Entry<Integer, Boolean>> iterator=set.iterator();
  158.  
  159. 		while(iterator.hasNext())
  160. 		{
  161. 			Map.Entry<Integer,Boolean> node= iterator.next();
  162. 			int vertex=node.getKey();
  163. 			List<Integer> list=adjList.get(vertex);
  164.  
  165. 			if(list!=null)
  166. 			{
  167. 				int size=list.size();
  168. 				for(int i=0;i <size; ++i)
  169. 				{
  170. 					int adjNode=list.get(i);
  171. 					g.addReverseEdge(vertex,adjNode);
  172. 				}
  173. 			}
  174. 		}
  175. 	}
  176.  
  177. 	/**
  178. 	 * Adding reverse edge compared to original graph, 
  179. 	 * edge(dest-->src)
  180. 	 */
  181. 	private void addReverseEdge(int src, int dest) {
  182. 		List<Integer> list=reverseAdjList.get(dest);
  183.  
  184. 		if(list==null)	
  185. 			list=new ArrayList<Integer>();
  186.  
  187. 		list.add(src);
  188. 		reverseAdjList.put(dest,list);
  189. 	}
  190.  
  191. 	/*=============Reversing of Graph Ends================== */
  192.  
  193. 	/* ============= Filling The Stack Starts ===============*/
  194. 	/**
  195. 	 * Fill the stack to form reverse post-order using DFS
  196. 	 * @param vertex
  197. 	 */
  198. 	private void fillOrderStackDFS(int vertex){
  199.  
  200. 		vistedStatus.put(vertex, true);
  201. 		List<Integer> list=reverseAdjList.get(vertex);
  202.  
  203. 		if(list!=null){
  204. 			int size=list.size();
  205.  
  206. 			for(int i=0;i<size;i++){
  207. 				int adjNode= list.get(i);
  208. 				boolean isVisited = vistedStatus.get(adjNode);
  209.  
  210. 				if(!isVisited)
  211. 					fillOrderStackDFS(adjNode);
  212. 			}
  213. 		}
  214. 		stack.push(vertex); //Push the vertex when all connecting links processed
  215. 	}
  216.  
  217. 	/* ============= Filling The Stack Ends ===============*/
  218.  
  219. 	/**
  220. 	 * Reset Visit Status of all vertices
  221. 	 */
  222. 	private void resetVisitStatus(){
  223. 		for (Map.Entry<Integer, Boolean> entry : vistedStatus.entrySet()) 
  224. 		    entry.setValue(false);
  225. 	}
  226.  
  227. 	public static void main(String[] args) {
  228. 		//Test Case1: 
  229. 		/*int numVertices = 5;
  230. 		SCC g=new SCC(numVertices);
  231. 		g.addEdge(1, 0);
  232. 		g.addEdge(0, 2);
  233. 		g.addEdge(2, 1);
  234. 		g.addEdge(0, 3);
  235. 		g.addEdge(3, 4);
  236. 		g.computeSCC(g);*/
  237.  
  238. 		//Test Case2: 
  239. 		int numVertices = 11;
  240. 		SCC g=new SCC(numVertices);
  241. 		g.addEdge(1, 2);
  242. 		g.addEdge(2, 3);
  243. 		g.addEdge(3, 1);
  244. 		g.addEdge(3, 4);
  245. 		g.addEdge(3, 7);
  246. 		g.addEdge(7, 4);
  247. 		g.addEdge(4, 6);
  248. 		g.addEdge(6, 7);
  249. 		g.addEdge(4, 5);
  250. 		g.addEdge(5, 6);
  251. 		g.addEdge(4, 9);
  252. 		g.addEdge(5, 8);
  253. 		g.addEdge(8, 9);
  254. 		g.addEdge(9, 10);
  255. 		g.addEdge(10, 8);
  256. 		g.addEdge(11, 10);
  257. 		g.addEdge(11, 9);
  258. 		g.addEdge(2, 11);
  259. 		g.computeSCC(g);
  260.  
  261.  
  262. 	}
  263. }
  264.  
  265.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
SCCs of Digraph: 
===========================
8	9	10	
===========================
11	
===========================
4	6	7	5	
===========================
1	2	3	
===========================
https://ideone.com/jieqd4
language:
Java (12.0.1)
created:
11 years ago
visibility:
secret

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!