Hello Readers!!! we have come up with yet another article. Most of you must have heard about graphs that is a non-linear data structure. It's one of those data-structures from which you can expect at least one question in online assessments and interviews. This article will familiarise you with graph data structure and then move on to implementing code to find the k-cores of an undirected graph. But before we begin, let us know some terminologies related to graphs.
📈Graph Terminologies
Graph
A graph is a non-linear data structure. It has nodes or vertices which are connected through links which are called edges.
The above graph has five vertices and five edges. 1,2,3,4,5 are the vertices, and the black lines connecting these vertices are edges.
A directed graph has edges with a direction. In directed graphs, an edge can be traversed in only one way.
The above diagram shows a directed graph in which the edges have a direction. For example, the edge between vertex one and vertex two can be traversed only from 1 to 2 and not from 2 to 1.
Degree
The degree of a vertex is the number of adjacent vertices to a vertex; in simple language, it is the number of edges connecting the vertex to other vertices. Now let us move on to understand the k cores of a graph.
K-cores of a Graph
By k-cores of a graph, we mean the vertices (connected) present after removing all the vertices from the original graph having a degree less than k.
📃Problem Statement
We are given an undirected graph. We need to find the k-cores of the graph after removing the vertices with a degree less than k.
Say, we are given the following graph:
In the input, we have the number of vertices in the graph, the number of edges, all the edges of the graph, and the value of k.
The output for the given graph is the vertices that are left after removing the vertices that had a degree less than k.
The output graph for the given example is shown below:
🚶Approach/Algorithm to the solution.
We start with adding edges to the graph.
Maintain an adjacency list for each vertex.
While the vertex is being removed or the degree of the vertices are getting changed-
Get the degree for the vertex i,
Compare the degree of the vertex i, with k.
If the degree is less than k, reduce the degree of the vertex by 1 and move to the next adjacent node(vertex).
Repeat this process for all the adjacent vertices of the particular vertex.
After the degree of all the vertices has been reduced by 1 set the degree for the vertex to 0.
Check for all the vertices again if their degree is less than or equal to 0;
if it is the case remove that vertex and proceed to the next one to check the same.
Print the k-cores.
📍Implementation in C++
Below is the implementation of code in C++ for finding k-cores of a graph:
#include <iostream>
using namespace std;
class AdjListVertex
{
public:
int v;
AdjListVertex * next;
AdjListVertex(int v)
{
this -> v = v;
this -> next = NULL;
}
};
class GraphVertex
{
public:
int data;
AdjListVertex * edge;
};
// This class will construct the graph
class Graph
{
public:
//number of nodes in a graph
int size;
GraphVertex * node;
Graph(int size)
{
if (size < 0)
{
cout << "\n Invalid number of vertices " << size << " \n";
} else
{
this -> size = size;
this -> node = new GraphVertex[this -> size];
int i = 0;
while (i < this -> size)
{
this -> node[i].data = i;
this -> node[i].edge = NULL;
i++;
}
}
}
// Function to connect the edges between the vertices x and y
void connect_Edge(int x, int y)
{
if (this -> size <= 0)
{
cout << "\n Graph is empty!\n";
return;
}
// Create Adjacency list
AdjListVertex * newEdge = new AdjListVertex(y);
if (newEdge != NULL)
{
// Get the first edge of x vertex
AdjListVertex * edge = this -> node[x].edge;
// if there's no edge between x and any other vertices add the first
//edge
if (edge == NULL)
{
this -> node[x].edge = newEdge;
} else
{
// Find the last vertex which has an edge with the current
//vertex
while (edge -> next != NULL)
{
edge = edge -> next;
}
// Add edge at last position
edge -> next = newEdge;
}
} else
{
cout << "\nCannot connect edges.\n";
}
}
// It adds an edge between x and y
void add_Edge(int x, int y)
{
if (this -> size > 0 && x < this -> size && y < this -> size)
{
this -> connect_Edge(x, y);
if (x == y)
{
return;
}
this -> connect_Edge(y, x);
} else
{
cout << "Invalid number of vertices " << x << " " << y;
}
}
// Display Adjacency list of each vertex
void display_Graph()
{
if (this -> size > 0)
{
AdjListVertex * temp = NULL;
int i = 0;
while (i < this -> size)
{
cout << "\n Adjacency list of vertex " << i << "->";
// Get first edge of ith node
temp = this -> node[i].edge;
while (temp != NULL)
{
cout << " " << this -> node[temp -> v].data;
temp = temp -> next;
}
i++;
}
} else
{
cout << "Empty Graph Node";
}
}
// To find the degree of each vertex
void vertex_degree(int degree[])
{
if (this -> size <= 0)
{
return;
}
AdjListVertex * temp = NULL;
int i = 0;
while (i < this -> size)
{
degree[i] = 0;
i++;
}
i = 0;
while (i < this -> size)
{
// Get first edge of ith vertex
temp = this -> node[i].edge;
while (temp != NULL)
{
degree[temp -> v]++;
// move to the next node
temp = temp -> next;
}
++i;
}
}
// Function to find and remove vertices having degrees less than
void kCores(int k)
{
if (k <= 0 || this -> size <= 0)
{
cout << "\nGraph is empty or " << k << " core Not valid\n";
} else
{
int degree[this -> size];
// Loop controlling variable
int i = 0;
this -> vertex_degree(degree);
AdjListVertex * edge = NULL, * temp1 = NULL, * temp2 = NULL;
bool flag = true;
while (flag == true)
{
flag = false;
i = 0;
while (i < this -> size)
{
if (degree[i] > 0 && degree[i] < k)
{
edge = this -> node[i].edge;
this -> node[i].edge = NULL;
while (edge != NULL)
{
temp1 = edge;
degree[edge -> v]--;
edge = edge -> next;
// remove edge
temp1 = NULL;
}
degree[i] = 0;
flag = true;
}
++i;
}
}
// Since removing a vertex will change the degree of all its adjacent
//vertices check again for all the adjacent vertices
i = 0;
while (i < this -> size)
{
edge = this -> node[i].edge;
temp1 = NULL;
while (edge != NULL)
{
if (degree[edge -> v] <= 0)
{
if (this -> node[i].edge == edge)
{
this -> node[i].edge = edge -> next;
} else
{
temp1 -> next = edge -> next;
}
temp2 = edge;
edge = edge -> next;
// remove edge
temp2 = NULL;
} else
{
temp1 = edge;
// visit to next edge
edge = edge -> next;
}
}
++i;
}
cout << "\n";
}
}
};
int main()
{
cout << "Enter the number of vertices\n";
int n, e, k;
cin >> n;
int a, b;
Graph g1 = Graph(n);
cout << "Enter the number of edges\n";
cin >> e;
// Connected two node with Edges
cout << "Enter the edges to be added by entering the two connected vertices separated by spaces\n";
for (int i = 0; i < e; i++)
{
cin >> a >> b;
g1.add_Edge(a, b);
}
cout << "Enter the value of 'k':\n";
cin >> k;
g1.kCores(k);
cout << "\n The k cores of the graph are: \n";
g1.display_Graph();
return 0;
}
You can also try this code with Online C++ Compiler
Below is the implementation of code in Java for finding k-cores of a graph:
import java.util.*;
class AdjListVertex
{
public int v;
public AdjListVertex next;
public AdjListVertex(int v)
{
this.v = v;
this.next = null;
}
}
class GraphVertex
{
public int data;
public AdjListVertex edge;
public GraphVertex(int data)
{
this.data = data;
this.edge = null;
}
}
public class Graph
{
public int size;
public GraphVertex[] node;
public graph(int size)
{
if (size < 0)
{
System.out.println("Invalid number of vertices");
} else
{
this.size = size;
this.node = new GraphVertex[this.size];
int i = 0;
for (i = 0; i < this.size; i++)
{
this.node[i] = new GraphVertex(i);
}
}
}
public void connect_Edge(int x, int y)
{
if (this.size <= 0)
{
System.out.println("Graph is empty");
return;
}
AdjListVertex newEdge = new AdjListVertex(y);
if (newEdge != null)
{
AdjListVertex edge = this.node[x].edge;
if (edge == null)
{
this.node[x].edge = newEdge;
} else
{
while (edge.next != null)
{
edge = edge.next;
}
edge.next = newEdge;
}
} else
{
System.out.println("Cannot connect edges");
}
}
public void add_Edge(int x, int y)
{
if (this.size > 0 && x < this.size && y < this.size)
{
connect_Edge(x, y);
if (x == y)
{
return;
}
connect_Edge(y, x);
} else
{
System.out.print("Invalid Node Vertices " + x + " " + y);
}
}
public void display_Graph()
{
if (this.size > 0)
{
AdjListVertex temp = null;
int i = 0;
for (i = 0; i < this.size; i++)
{
System.out.print("\n Adjacency list of vertex " + i + " ->");
temp = this.node[i].edge;
while (temp != null)
{
System.out.print(" " + this.node[temp.v].data);
temp = temp.next;
}
}
} else
{
System.out.print("Empty Graph Node");
}
}
public void findDegree(int[] indegree)
{
if (this.size <= 0)
{
return;
}
AdjListVertex temp = null;
int i = 0;
for (i = 0; i < this.size; ++i)
{
indegree[i] = 0;
}
for (i = 0; i < this.size; ++i)
{
temp = this.node[i].edge;
while (temp != null)
{
indegree[temp.v]++;
temp = temp.next;
}
}
}
public void kCores(int k)
{
if (k <= 0 || this.size <= 0)
{
System.out.print("\nGraph is empty or core Not valid\n");
} else
{
int degree[] = new int[this.size];
int i = 0;
findDegree(degree);
AdjListVertex edge = null, temp1 = null, temp2 = null;
boolean flag = true;
while (flag == true)
{
flag = false;
for (i = 0; i < this.size; ++i)
{
if (degree[i] > 0 && degree[i] < k)
{
edge = this.node[i].edge;
this.node[i].edge = null;
while (edge != null)
{
temp1 = edge;
degree[edge.v]--;
edge = edge.next;
temp1 = null;
}
degree[i] = 0;
flag = true;
}
}
}
for (i = 0; i < this.size; ++i)
{
edge = this.node[i].edge;
temp1 = null;
while (edge != null)
{
if (degree[edge.v] <= 0)
{
if (this.node[i].edge == edge)
{
this.node[i].edge = edge.next;
} else
{
temp1.next = edge.next;
}
temp2 = edge;
edge = edge.next;
temp2 = null;
} else
{
temp1 = edge;
edge = edge.next;
}
}
}
System.out.println();
}
}
public static void main(String[] args)
{
System.out.println("Enter the number of vertices\n");
int n, e, k;
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int x, y;
Graph g1 = new Graph(n);
System.out.println("Enter the number of edges\n");
e = sc.nextInt();
System.out.println("Enter the edges to be added by entering the two connected vertices separated by spaces\n");
for (int i = 0; i < e; i++)
{
x = sc.nextInt();
y = sc.nextInt();
g1.add_Edge(x, y);
}
System.out.println("Enter the value of 'k':");
k = sc.nextInt();
g1.kCores(k);
System.out.println("The k cores of the graph are: ");
g1.display_Graph();
}
}
You can also try this code with Online Java Compiler
Time complexity for an algorithm is the amount of time it takes to process an input of some length. The time complexity for the given code is O(V+E), where 'V' represents the number of vertices present in the graph and 'E' is the number of edges present in the graph.
Since we are traversing the graph the time complexity here is O(V+E)
Space Complexity
Consecutively, for this code the space complexity will be O(V), where 'V' represents the number of vertices present in the graph Check out this problem - No of Spanning Trees in a Graph
Frequently Asked Questions
What data structures do we use to represent graphs?
We represent graphs by edges and vertices, so we can use either a list Adjacency List or a matrix Adjacency Matrix to store the input for a graph.
What are the types of degrees in a directed graph?
There are two types of degrees in a directed graph: Indegree, the number of edges coming to a vertex, and Outdegree, the number of edges leaving a vertex.
What do you mean by k-core subgraph?
A k-core subgraph is a graph in which all the vertices have at least k degrees.
Give an example where a graph is used.
To allocate a resource operating system uses Resource Allocation Graph.
117+ registered 