fork(1) download
copy 
  1. import java.util.ArrayList;
  2. import java.util.HashMap;
  3. import java.util.List;
  4. import java.util.PriorityQueue;
  5. import java.util.Queue;
  6.  
  7. class FindTraingle {
  8.  
  9. 	public static final int BIG_NEGATIVE = -999;
  10. 	public static void main(String[] args) {
  11. 		int noOfNodes=6;
  12. 		List<Edge> grpahEdges = new ArrayList<Edge>();
  13.  
  14. 		grpahEdges.add(new Edge(0, 1,BIG_NEGATIVE));
  15. 		grpahEdges.add(new Edge(0, 3,BIG_NEGATIVE));
  16. 		//grpahEdges.add(new Edge(0, 4,BIG_NEGATIVE));
  17. 		grpahEdges.add(new Edge(1, 2,BIG_NEGATIVE));
  18. 		grpahEdges.add(new Edge(2, 3,BIG_NEGATIVE));
  19. 		grpahEdges.add(new Edge(3, 4,BIG_NEGATIVE));
  20. 		grpahEdges.add(new Edge(2, 4,BIG_NEGATIVE));
  21.  
  22. 		findTriangle(5,grpahEdges);
  23. 		for(Edge e:grpahEdges){
  24. 			e.weight=BIG_NEGATIVE;
  25. 		}
  26. 		findOneLevelTriangle(5,grpahEdges);
  27.  
  28. 	}
  29.  
  30. 	public static boolean findTriangle(int noOfNodes, List<Edge> grpahEdges){
  31. 		// e.weight ==0 not yet visited.
  32. 		int [] distance = new int[noOfNodes];
  33. 		for(int i=0;i<noOfNodes;i++){
  34. 			distance[i]=BIG_NEGATIVE;
  35. 		}
  36.  
  37. 		Queue<Integer> q = new PriorityQueue<Integer>();
  38. 		q.add(0);
  39. 		distance[0]=0;
  40. 		while(q.peek()!=null){
  41. 			int  currentNode = q.poll();
  42. 			if(findTriangleUtil(currentNode,grpahEdges,distance,q)){
  43. 				System.out.println("Big Traingle found");
  44. 				return true;
  45. 			}
  46. 		}
  47. 		return false;
  48. 	}		
  49.  
  50. 	public static boolean findTriangleUtil(int currentNode, List<Edge> grpahEdges,int [] distance,Queue q){
  51. 		Edge e ;
  52. 		do{
  53. 			e = getUnVisitedLinkForThisNode(currentNode,grpahEdges);
  54.  
  55. 			if(e!=null){
  56. 				e.weight=1; // mark it as visited
  57. 				int nextNode;
  58. 				if(e.sourcevertex == currentNode){
  59. 					nextNode = e.destinationvertex;
  60. 				}else{
  61. 					nextNode = e.sourcevertex;
  62. 				}
  63. 				if(distance[nextNode]== distance[currentNode] ){
  64. 					// Triangle is formed
  65. 					return true;
  66. 				}else{
  67. 					// update distance 
  68. 					distance[nextNode] = distance[currentNode] +1;
  69. 					q.add(nextNode);
  70. 				}				
  71. 			}
  72. 		}while(e!=null);
  73. 		return false;
  74. 	}
  75.  
  76. 	public static Edge getUnVisitedLinkForThisNode(int currentNode,List<Edge> grpahEdges){
  77. 		for(Edge e :grpahEdges){
  78. 			if((e.sourcevertex==currentNode ||  e.destinationvertex ==currentNode ) && e.weight ==BIG_NEGATIVE){
  79. 				return e;
  80. 			}
  81. 		}
  82. 		return null;
  83. 	}
  84.  
  85. 	public static ArrayList<Edge> getListOfLinks(int currentNode,List<Edge> grpahEdges){
  86. 		ArrayList<Edge> returnList = new ArrayList<Edge>();
  87. 		for(Edge e :grpahEdges){
  88. 			if((e.sourcevertex==currentNode ||  e.destinationvertex ==currentNode ) && e.weight ==BIG_NEGATIVE){
  89. 				returnList.add(e);
  90. 			}
  91. 		}
  92. 		return returnList;
  93. 	}
  94.  
  95. 	public static boolean findOneLevelTriangle(int noOfNodes, List<Edge> grpahEdges){
  96. 		// For each node find its children
  97. 		// Then for each children check if it connects to any of its siblings
  98.  
  99. 		for(int i=0;i<noOfNodes;i++){
  100. 			HashMap<Integer,Boolean> children = new HashMap<Integer,Boolean>();
  101. 			Edge e ;
  102. 			do{
  103. 				e = getUnVisitedLinkForThisNode(i,grpahEdges);
  104.  
  105. 				if(e!=null){
  106. 					e.weight=1; // mark it as visited
  107. 					int nextNode;
  108. 					if(e.sourcevertex == i){
  109. 						nextNode = e.destinationvertex;
  110. 					}else{
  111. 						nextNode = e.sourcevertex;
  112. 					}
  113. 					children.put(nextNode,Boolean.TRUE);
  114. 				}
  115. 			}while(e!=null);
  116.  
  117. 			// Queue is ready with sibling. Now get edges for each siblings
  118. 			for(int j: children.keySet()){
  119. 				for(Edge childEdge : getListOfLinks(j,grpahEdges)){
  120. 							int nextNode;
  121. 							if(childEdge.sourcevertex == j){
  122. 								nextNode = childEdge.destinationvertex;
  123. 							}else{
  124. 								nextNode = childEdge.sourcevertex;
  125. 							}
  126. 							if(children.get(nextNode) != null){
  127. 								System.out.println("Connecting to siblngs. It is a triangle");
  128. 								return true;
  129. 							}
  130. 					} 
  131. 			}
  132. 		}
  133. 		return false;
  134. 	}
  135. }
  136.  
  137.  
  138. class Edge implements Comparable<Edge>
  139. {
  140.     public int sourcevertex;
  141.     public int destinationvertex;
  142.     public int weight;
  143.  
  144.     @Override
  145.     public int compareTo(Edge edge2) {
  146.         if (this.weight < edge2.weight)
  147.             return -1;
  148.         if (this.weight > edge2.weight)
  149.             return 1;
  150.         return 0;
  151.     }
  152.  
  153.     public Edge(){
  154.  
  155.     }
  156.  
  157. 	public Edge(int sourcevertex, int destinationvertex) {
  158. 		super();
  159. 		this.sourcevertex = sourcevertex;
  160. 		this.destinationvertex = destinationvertex;
  161. 	}
  162.  
  163. 	public Edge(int sourcevertex, int destinationvertex, int weight) {
  164. 		super();
  165. 		this.sourcevertex = sourcevertex;
  166. 		this.destinationvertex = destinationvertex;
  167. 		this.weight = weight;
  168. 	}
  169.  
  170.  
  171. }
  172.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Big Traingle found
Connecting to siblngs. It is a triangle
https://ideone.com/UEKoKy
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!