fork download
copy 
  1. // C++ program to find K-Cores of a graph
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. // This class represents a undirected graph using adjacency
  6. // list representation
  7. class Graph
  8. {
  9. 	int V; // No. of vertices
  10.  
  11. 	// Pointer to an array containing adjacency lists
  12. 	list<int> *adj;
  13. public:
  14. 	Graph(int V); // Constructor
  15.  
  16. 	// function to add an edge to graph
  17. 	void addEdge(int u, int v);
  18.  
  19. 	// A recursive function to print DFS starting from v
  20. 	bool DFSUtil(int, vector<bool> &, vector<int> &, int k);
  21.  
  22. 	// prints k-Cores of given graph
  23. 	void printKCores(int k);
  24. };
  25.  
  26. // A recursive function to print DFS starting from v.
  27. // It returns true if degree of v after processing is less
  28. // than k else false
  29. // It also updates degree of adjacent if degree of v
  30. // is less than k. And if degree of a processed adjacent
  31. // becomes less than k, then it reduces of degree of v also,
  32. bool Graph::DFSUtil(int v, vector<bool> &visited,
  33. 					vector<int> &vDegree, int k)
  34. {
  35. 	// Mark the current node as visited and print it
  36. 	visited[v] = true;
  37.  
  38. 	cout<<v<<" degree: "<<vDegree[v]<<endl;
  39.  
  40. 	// Recur for all the vertices adjacent to this vertex
  41. 	list<int>::iterator i;
  42. 	for (i = adj[v].begin(); i != adj[v].end(); ++i)
  43. 	{
  44. 		// degree of v is less than k, then degree of adjacent
  45. 		// must be reduced
  46. 		if (vDegree[v] < k){
  47. 			vDegree[*i]--;
  48. 			cout<<*i<<" inside: "<<v<<" degree: "<<vDegree[*i]<<endl;
  49. 		}
  50.  
  51. 		// If adjacent is not processed, process it
  52. 		if (!visited[*i])
  53. 		{
  54. 			// If degree of adjacent after processing becomes
  55. 			// less than k, then reduce degree of v also.
  56. 			DFSUtil(*i, visited, vDegree, k);
  57. 		}
  58. 	}
  59.  
  60. 	// Return true if degree of v is less than k
  61. 	return (vDegree[v] < k);
  62. }
  63.  
  64. Graph::Graph(int V)
  65. {
  66. 	this->V = V;
  67. 	adj = new list<int>[V];
  68. }
  69.  
  70. void Graph::addEdge(int u, int v)
  71. {
  72. 	adj[u].push_back(v);
  73. 	adj[v].push_back(u);
  74. }
  75.  
  76. // Prints k cores of an undirected graph
  77. void Graph::printKCores(int k)
  78. {
  79. 	// INITIALIZATION
  80. 	// Mark all the vertices as not visited and not
  81. 	// processed.
  82. 	vector<bool> visited(V, false);
  83. 	vector<bool> processed(V, false);
  84.  
  85. 	int mindeg = INT_MAX;
  86. 	int startvertex;
  87.  
  88. 	// Store degrees of all vertices
  89. 	vector<int> vDegree(V);
  90. 	for (int i=0; i<V; i++)
  91. 	{
  92. 		vDegree[i] = adj[i].size();
  93.  
  94. 		if (vDegree[i] < mindeg)
  95. 		{
  96. 			mindeg = vDegree[i];
  97. 			startvertex=i;
  98. 		}
  99. 	}
  100.  
  101.  
  102. 	DFSUtil(startvertex, visited, vDegree, k);
  103.  
  104. 	// If Graph is disconnected.
  105. 	for (int i=0; i<V; i++)
  106. 		if (visited[i] == false)
  107. 			DFSUtil(i, visited, vDegree, k);
  108.  
  109. 	// PRINTING K CORES
  110. 	cout << "K-Cores : \n";
  111. 	for (int v=0; v<V; v++)
  112. 	{
  113. 		// Only considering those vertices which have degree
  114. 		// >= K after BFS
  115. 		if (vDegree[v] >= k)
  116. 		{
  117. 			cout << "\n[" << v << "]";
  118.  
  119. 			// Traverse adjacency list of v and print only
  120. 			// those adjacent which have vDegree >= k after
  121. 			// BFS.
  122. 			list<int>::iterator itr;
  123. 			for (itr = adj[v].begin(); itr != adj[v].end(); ++itr)
  124. 				if (vDegree[*itr] >= k)
  125. 					cout << " -> " << *itr;
  126. 		}
  127. 	}
  128. }
  129.  
  130. // Driver program to test methods of graph class
  131. int main()
  132. {
  133. 	// Create a graph given in the above diagram
  134. 	int k = 3;
  135. 	Graph g1(8);
  136. 	g1.addEdge(0, 3);
  137. 	g1.addEdge(0, 1);
  138. 	g1.addEdge(0, 2);
  139. 	g1.addEdge(1, 4);
  140. 	g1.addEdge(2, 3);
  141. 	g1.addEdge(2, 4);
  142. 	g1.addEdge(2, 5);
  143. 	g1.addEdge(2, 6);
  144. 	g1.addEdge(3, 6);
  145. 	g1.addEdge(4, 5);
  146. 	g1.addEdge(4, 6);
  147. 	g1.addEdge(5, 6);
  148. 	g1.printKCores(k);
  149.  
  150. 	cout << endl << endl;
  151.  
  152. 	Graph g2(13);
  153. 	g2.addEdge(0, 1);
  154. 	g2.addEdge(0, 2);
  155. 	g2.addEdge(0, 3);
  156. 	g2.addEdge(1, 4);
  157. 	g2.addEdge(1, 5);
  158. 	g2.addEdge(1, 6);
  159. 	g2.addEdge(2, 7);
  160. 	g2.addEdge(2, 8);
  161. 	g2.addEdge(2, 9);
  162. 	g2.addEdge(3, 10);
  163. 	g2.addEdge(3, 11);
  164. 	g2.addEdge(3, 12);
  165. 	g2.printKCores(k);
  166.  
  167. 	return 0;
  168. }
  169.  
Success #stdin #stdout 0s 5620KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
7 degree: 0
0 degree: 3
3 degree: 3
2 degree: 5
4 degree: 4
1 degree: 2
0 inside: 1 degree: 2
4 inside: 1 degree: 3
5 degree: 3
6 degree: 4
1 inside: 0 degree: 1
2 inside: 0 degree: 4
K-Cores : 

[2] -> 3 -> 4 -> 5 -> 6
[3] -> 2 -> 6
[4] -> 2 -> 5 -> 6
[5] -> 2 -> 4 -> 6
[6] -> 2 -> 3 -> 4 -> 5

4 degree: 1
1 inside: 4 degree: 3
1 degree: 3
0 degree: 3
2 degree: 4
7 degree: 1
2 inside: 7 degree: 3
8 degree: 1
2 inside: 8 degree: 2
9 inside: 2 degree: 0
9 degree: 0
2 inside: 9 degree: 1
3 degree: 4
10 degree: 1
3 inside: 10 degree: 3
11 degree: 1
3 inside: 11 degree: 2
12 inside: 3 degree: 0
12 degree: 0
3 inside: 12 degree: 1
5 degree: 1
1 inside: 5 degree: 2
6 inside: 1 degree: 0
6 degree: 0
1 inside: 6 degree: 1
K-Cores : 

[0]
https://ideone.com/x70AiP
language:
C++ (gcc 8.3)
created:
2 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!