Posted on by Kalkicode
Code Graph

Find k-cores of an undirected graph

The concept of k-cores in graph theory helps us identify the most tightly connected subgraphs within a larger graph. This article presents a comprehensive explanation of the k-core algorithm, along with a C code implementation that demonstrates how to find and remove k-cores from an undirected graph.

Problem Statement

Given an undirected graph, the task is to find the k-cores of the graph, which are the subgraphs where each vertex is connected to at least k other vertices within the subgraph.

Description with Example

Imagine you have a social network graph, where users are represented as vertices and friendships are depicted as edges. The k-cores of this graph could represent groups of users who are particularly close-knit, where each user has at least k friends within the group.

Idea to Solve

To find the k-cores of an undirected graph, we iteratively remove vertices with degrees less than k, along with their incident edges. This process reduces the graph's complexity while preserving the main structure. The remaining subgraph is a k-core.

Pseudocode

function find_degree(indegree, graph):
    for each vertex v in graph:
        indegree[v] = number of edges incident on v

function k_cores(graph, k):
    initialize an array indegree with zeros
    find_degree(indegree, graph)
    status = true
    while status is true:
        status = false
        for each vertex v in graph:
            if indegree[v] < k:
                remove vertex v and its incident edges
                update status to true
                decrease indegree of adjacent vertices

Algorithm Explanation

  1. Initialize the indegree array with zeros, where each index represents a vertex.
  2. Use the find_degree function to populate the indegree array with the number of edges incident on each vertex.
  3. Set status as true to track changes.
  4. While status is true: a. Iterate through each vertex in the graph. b. If the vertex's indegree is less than k, remove the vertex and its incident edges. c. Update status to true to indicate changes. d. Decrease the indegree of adjacent vertices.

Code Solution

// C Program 
// Find k-cores of an undirected graph
#include <stdio.h>
#include <stdlib.h>

// Define edge of graph node
struct AjlistNode
{
    int id; //Vertices id
    struct AjlistNode *next;
};

// Define node of graph 
struct GraphNode
{
    int data; //node key value
    struct AjlistNode *edge;
};

// Define structure of graph
struct MyGraph
{
    int size; // Number of graph nodes
    struct GraphNode *node;
};

// This are return a new graph with given number of nodes
struct MyGraph *newGraph(int size)
{
    if (size < 0)
    {
        printf("\n Invalid size of nodes %d \n", size);
        return NULL;
    }

    // Create a graph
    struct MyGraph *graph = (struct MyGraph *) malloc(sizeof(struct MyGraph));
    
    if (graph != NULL)
    {
        // Set node size
        graph->size = size;

        // Allocate memory to graph node
        graph->node = (struct GraphNode *) malloc(sizeof(struct GraphNode) *size);
        
        // Loop controlling variable
        int i = 0;

        // Set graph node level and e
        for (i = 0; i < graph->size; i++)
        {
            // Set node level (0...size-1)
            graph->node[i].data = i;
            
            // Set the node [i] have no edge
            graph->node[i].edge = NULL;
        }
    }
    else
    {
        printf("\n Graph of nodes %d is not created (memory overflow problem)\n", size);
    }
    return graph;
}

//This function are connect nodes with one edge 
void connect_edge(struct MyGraph *graph, int a, int b)
{
    if (graph->node == NULL)
    {
        printf("\n Graph have no nodes \n");
        return;
    }
    // Create Adjacency node
    struct AjlistNode *newEdge = (struct AjlistNode *) malloc(sizeof(struct AjlistNode));
    
    if (newEdge != NULL)
    {
        newEdge->next = NULL;

        newEdge->id = b;

        // Get first edge of [i] node
        struct AjlistNode *edge = graph->node[a].edge;

        if (edge == NULL)
        {
            // Whe no edge of graph node [i] then
            // Add a first edge of a [i] node
            graph->node[a].edge = newEdge;
        }
        else
        {
            //Find last location to add new edge
            while (edge->next != NULL)
            {
                edge = edge->next;
            }

            // Add edge at last position
            edge->next = newEdge;
        }
    }
    else
    {
        printf("\nMemory overflow, when connect a new edge from ( %d to %d ) nodes.\n", a, b);
    }
}
// This is handles the request of connecting Edges between given node a to b
void add_edge(struct MyGraph *graph, int a, int b)
{
    if (a < graph->size && b < graph->size)
    {
        // connect edge
        // a---->b
        connect_edge(graph, a, b);

        if (a == b)
        {
            //self loop
            return;
        }
        // connect edge
        // a <---- b
        connect_edge(graph, b, a);
    }
    else
    {
        //not valid Vertices
        printf("Invalid Node Vertices %d  %d", a, b);
    }
}
//Display Adjacency list of vertex
void print_graph(struct MyGraph *graph)
{
    if (graph->node != NULL)
    {
        struct AjlistNode *temp = NULL;

        // Loop controlling variable
        int i = 0;

        for (i = 0; i < graph->size; i++)
        {
            printf("\n Adjacency list of vertex %d  :", i);

            // Get first edge of [i] node
            temp = graph->node[i].edge;
           
            while (temp != NULL)
            {
                //temp->id is graph node vertices
                //in this case temp->id is same as 
                //node[temp->id].data
                printf("  %d", graph->node[temp->id].data);
                temp = temp->next;
            }
        }
    }
    else
    {
        printf("Empty GraphNode");
    }
}
//This is an undirected graph so indegree will be equal to outdegree
//Find indegree of each nodes of a given graph
void find_degree(int indegree[], struct MyGraph *graph)
{
    if (graph->node == NULL) 
    {
        return;
    }

    struct AjlistNode *temp = NULL;
    // Loop controlling variable
    int i = 0;
    for (i = 0; i < graph->size; ++i)
    {
        indegree[i] = 0;
    }

    //Find the  incoming edges of each node
    for (i = 0; i < graph->size; ++i)
    {
        // Get first edge of i node in given graph
        temp = graph->node[i].edge;

        while (temp != NULL)
        {
            indegree[temp->id]++;

            // visit to next edge
            temp = temp->next;
        }
    }
}

// This is removing connection of node which is less than k edges
void k_cores(struct MyGraph *graph, int k)
{
    if (k <= 0)
    {
        return;
    }
    if (graph->node != NULL)
    {


        int indegree[graph->size];

        // Loop controlling variable
        int i = 0;

        find_degree(indegree, graph);

        struct AjlistNode *edge = NULL, *auxiliary = NULL, *temp = NULL;
        
        int status = 1;
        
        while (status == 1)
        {
            status = 0;
            
            for (i = 0; i < graph->size; ++i)
            {
                if (indegree[i] > 0 && indegree[i] < k)
                {

                    edge = graph->node[i].edge;
                    graph->node[i].edge = NULL;
                    while (edge != NULL)
                    {
                        auxiliary = edge;
                        indegree[edge->id]--;
                        edge = edge->next;
                        //remove edge
                        free(auxiliary);
                        auxiliary = NULL;
                    }
                    indegree[i] = 0;
                    status = 1;
                }
            }
        }
        // Edge are connect both direction 
        // for example a---> b and b--->a 
        // remove edges which is less than k
        for (i = 0; i < graph->size; ++i)
        {
            edge = graph->node[i].edge;

            auxiliary = NULL;

            while (edge != NULL)
            {
                if (indegree[edge->id] <= 0)
                {
                    if (graph->node[i].edge == edge)
                    {
                        //delete first edge
                        graph->node[i].edge = edge->next;
                    }
                    else
                    {
                        auxiliary->next = edge->next;
                    }
                    temp = edge;
                    edge = edge->next;
                    //remove edge
                    free(temp);
                    temp = NULL;
                }
                else
                {
                    auxiliary = edge;
                    // visit to next edge
                    edge = edge->next;
                }
            }
        }
        printf("\n");
    }
    else
    {
        printf("Empty Edge\n");
    }
}
int main()
{
    struct MyGraph *graph = newGraph(10);
    //Connected two node with Edges
    add_edge(graph, 0, 1);
    add_edge(graph, 0, 4);
    add_edge(graph, 0, 7);
    add_edge(graph, 1, 2);
    add_edge(graph, 1, 4);
    add_edge(graph, 1, 6);
    add_edge(graph, 2, 3);
    add_edge(graph, 2, 4);
    add_edge(graph, 3, 4);
    add_edge(graph, 3, 5);
    add_edge(graph, 3, 6);
    add_edge(graph, 4, 5);
    add_edge(graph, 5, 6);
    add_edge(graph, 5, 7);
    add_edge(graph, 5, 8);
    add_edge(graph, 6, 9);
    add_edge(graph, 7, 8);
    add_edge(graph, 8, 9);

    print_graph(graph);
    int k = 3;

    k_cores(graph, k);

    printf("\n After remove %d Cores\n",k);
    print_graph(graph);
    return 0;
}

Output

 Adjacency list of vertex 0  :  1  4  7
 Adjacency list of vertex 1  :  0  2  4  6
 Adjacency list of vertex 2  :  1  3  4
 Adjacency list of vertex 3  :  2  4  5  6
 Adjacency list of vertex 4  :  0  1  2  3  5
 Adjacency list of vertex 5  :  3  4  6  7  8
 Adjacency list of vertex 6  :  1  3  5  9
 Adjacency list of vertex 7  :  0  5  8
 Adjacency list of vertex 8  :  5  7  9
 Adjacency list of vertex 9  :  6  8

 After remove 3 Cores

 Adjacency list of vertex 0  :
 Adjacency list of vertex 1  :  2  4  6
 Adjacency list of vertex 2  :  1  3  4
 Adjacency list of vertex 3  :  2  4  5  6
 Adjacency list of vertex 4  :  1  2  3  5
 Adjacency list of vertex 5  :  3  4  6
 Adjacency list of vertex 6  :  1  3  5
 Adjacency list of vertex 7  :
 Adjacency list of vertex 8  :
 Adjacency list of vertex 9  :
/*
  Java Program
  Find k-cores of an undirected graph
*/
// Define edge of graph node
class AjlistNode
{
	//Vertices id
	public int id;
	public AjlistNode next;
	public AjlistNode(int id)
	{
		this.id = id;
		this.next = null;
	}
}
// Define node of graph 
class GraphNode
{
	//node key value
	public int data;
	public AjlistNode edge;
	public GraphNode(int data)
	{
		this.data = data;
		this.edge = null;
	}
}
// Define structure of graph
public class MyGraph
{
	// Number of graph nodes
	public int size;
	public GraphNode[] node;
	public MyGraph(int size)
	{
		if (size < 0)
		{
			System.out.print("\n Invalid size of nodes " + size + " \n");
		}
		else
		{
			this.size = size;
			this.node = new GraphNode[this.size];
			int i = 0;
			// Set graph node level and e
			for (i = 0; i < this.size; i++)
			{
				this.node[i] = new GraphNode(i);
			}
		}
	}
	//This function are connect nodes with one edge 
	public void connectEdge(int a, int b)
	{
		if (this.size <= 0)
		{
			System.out.print("\n Graph have no nodes \n");
			return;
		}
		// Create Adjacency node
		AjlistNode newEdge = new AjlistNode(b);
		if (newEdge != null)
		{
			// Get first edge of [i] node
			AjlistNode edge = this.node[a].edge;
			if (edge == null)
			{
				// Whe no edge of graph node [i] then
				// Add a first edge of a [i] node
				this.node[a].edge = newEdge;
			}
			else
			{
				//Find last location to add new edge
				while (edge.next != null)
				{
					edge = edge.next;
				}
				// Add edge at last position
				edge.next = newEdge;
			}
		}
		else
		{
			System.out.print("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes.\n");
		}
	}
	// This is handles the request of connecting Edges between given node a to b
	public void addEdge(int a, int b)
	{
		if (this.size > 0 && a < this.size && b < this.size)
		{
			// connect edge
			// a---->b
			connectEdge(a, b);
			if (a == b)
			{
				//self loop
				return;
			}
			// connect edge
			// a <---- b
			connectEdge(b, a);
		}
		else
		{
			//not valid Vertices
			System.out.print("Invalid Node Vertices " + a + " " + b);
		}
	}
	//Display Adjacency list of vertex
	public void printGraph()
	{
		if (this.size > 0)
		{
			AjlistNode temp = null;
			// Loop controlling variable
			int i = 0;
			for (i = 0; i < this.size; i++)
			{
				System.out.print("\n Adjacency list of vertex " + i + " :");
				// Get first edge of [i] node
				temp = this.node[i].edge;
				while (temp != null)
				{
					//temp->id is graph node vertices
					//in this case temp->id is same as 
					//node[temp->id].data
					System.out.print("  " + this.node[temp.id].data);
					temp = temp.next;
				}
			}
		}
		else
		{
			System.out.print("Empty Graph Node");
		}
	}
	//This is an undirected graph so indegree will be equal to outdegree
	//Find indegree of each nodes of a given graph
	public void findDegree(int[] indegree)
	{
		if (this.size <= 0)
		{
			return;
		}
		AjlistNode temp = null;
		// Loop controlling variable
		int i = 0;
		for (i = 0; i < this.size; ++i)
		{
			indegree[i] = 0;
		}
		//Find the  incoming edges of each node
		for (i = 0; i < this.size; ++i)
		{
			// Get first edge of i node in given graph
			temp = this.node[i].edge;
			while (temp != null)
			{
				indegree[temp.id]++;
				// visit to next edge
				temp = temp.next;
			}
		}
	}
	// This is removing connection of node which is less than k edges
	public void kCores(int k)
	{
		if (k <= 0 || this.size <= 0)
		{
			System.out.print("\nGraph is empty or " + k + " core Not valid\n");
		}
		else
		{
			int[] indegree = new int[this.size];
			// Loop controlling variable
			int i = 0;
			findDegree(indegree);
			AjlistNode edge = null, auxiliary = null, temp = null;
			boolean status = true;
			while (status == true)
			{
				status = false;
				for (i = 0; i < this.size; ++i)
				{
					if (indegree[i] > 0 && indegree[i] < k)
					{
						edge = this.node[i].edge;
						this.node[i].edge = null;
						while (edge != null)
						{
							auxiliary = edge;
							indegree[edge.id]--;
							edge = edge.next;
							//remove edge
							auxiliary = null;
						}
						indegree[i] = 0;
						status = true;
					}
				}
			}
			// Edge are connect both direction 
			// for example a---> b and b--->a 
			// remove edges which is less than k
			for (i = 0; i < this.size; ++i)
			{
				edge = this.node[i].edge;
				auxiliary = null;
				while (edge != null)
				{
					if (indegree[edge.id] <= 0)
					{
						if (this.node[i].edge == edge)
						{
							//delete first edge
							this.node[i].edge = edge.next;
						}
						else
						{
							auxiliary.next = edge.next;
						}
						temp = edge;
						edge = edge.next;
						//remove edge
						temp = null;
					}
					else
					{
						auxiliary = edge;
						// visit to next edge
						edge = edge.next;
					}
				}
			}
			System.out.print("\n");
		}
	}
	public static void main(String[] args)
	{
		// 10 is number of nodes
		MyGraph graph = new MyGraph(10);
		//Connected two node with Edges
		graph.addEdge(0, 1);
		graph.addEdge(0, 4);
		graph.addEdge(0, 7);
		graph.addEdge(1, 2);
		graph.addEdge(1, 4);
		graph.addEdge(1, 6);
		graph.addEdge(2, 3);
		graph.addEdge(2, 4);
		graph.addEdge(3, 4);
		graph.addEdge(3, 5);
		graph.addEdge(3, 6);
		graph.addEdge(4, 5);
		graph.addEdge(5, 6);
		graph.addEdge(5, 7);
		graph.addEdge(5, 8);
		graph.addEdge(6, 9);
		graph.addEdge(7, 8);
		graph.addEdge(8, 9);
		graph.printGraph();
		int k = 3;
		graph.kCores(k);
		System.out.print("\n After remove " + k + " Cores\n");
		graph.printGraph();
	}
}

Output

 Adjacency list of vertex 0 :  1  4  7
 Adjacency list of vertex 1 :  0  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  0  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6  7  8
 Adjacency list of vertex 6 :  1  3  5  9
 Adjacency list of vertex 7 :  0  5  8
 Adjacency list of vertex 8 :  5  7  9
 Adjacency list of vertex 9 :  6  8

 After remove 3 Cores

 Adjacency list of vertex 0 :
 Adjacency list of vertex 1 :  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6
 Adjacency list of vertex 6 :  1  3  5
 Adjacency list of vertex 7 :
 Adjacency list of vertex 8 :
 Adjacency list of vertex 9 :
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program
  Find k-cores of an undirected graph
*/
// Define edge of graph node
class AjlistNode
{
	public:
	//  Vertices id
	int id;
	AjlistNode *next;
	AjlistNode(int id)
	{
		this->id = id;
		this->next = NULL;
	}
};
// Define node of graph
class GraphNode
{
	public:
	//  node key value
	int data;
	AjlistNode *edge;
};
//   Define structure of graph
class MyGraph
{
	public:
	//   Number of graph nodes
	int size;
	GraphNode *node;
	MyGraph(int size)
	{
		if (size < 0)
		{
			cout << "\n Invalid size of nodes " << size << " \n";
		}
		else
		{
			this->size = size;
			this->node = new GraphNode[this->size];
			int i = 0;
			//   Set graph node level and e
			i = 0;
			while (i < this->size)
			{
				this->node[i].data = i;
				this->node[i].edge = NULL;
				i++;
			}
		}
	}
	//  This function are connect nodes with one edge
	void connectEdge(int a, int b)
	{
		if (this->size <= 0)
		{
			cout << "\n Graph have no nodes \n";
			return;
		}
		//   Create Adjacency node
		AjlistNode *newEdge = new AjlistNode(b);
		if (newEdge != NULL)
		{
			//   Get first edge of [i] node
			AjlistNode *edge = this->node[a].edge;
			if (edge == NULL)
			{
				//   Whe no edge of graph node [i] then
				//   Add a first edge of a [i] node
				this->node[a].edge = newEdge;
			}
			else
			{
				//  Find last location to add new edge
				while (edge->next != NULL)
				{
					edge = edge->next;
				}
				//   Add edge at last position
				edge->next = newEdge;
			}
		}
		else
		{
			cout << "\nMemory overflow, when connect a new edge from ( " << a << " to " << b << " ) nodes.\n";
		}
	}
	//   This is handles the request of connecting Edges between given node a to b
	void addEdge(int a, int b)
	{
		if (this->size > 0 && a < this->size && b < this->size)
		{
			//   connect edge
			//   a---->b
			this->connectEdge(a, b);
			//  self loop
			if (a == b)
			{
				return;
			}
			//   connect edge
			//   a <---- b
			this->connectEdge(b, a);
		}
		else
		{
			//  not valid Vertices
			cout << "Invalid Node Vertices " << a << " " << b;
		}
	}
	//  Display Adjacency list of vertex
	void printGraph()
	{
		if (this->size > 0)
		{
			AjlistNode *temp = NULL;
			//   Loop controlling variable
			int i = 0;
			while (i < this->size)
			{
				cout << "\n Adjacency list of vertex " << i << " :";
				//   Get first edge of [i] node
				temp = this->node[i].edge;
				while (temp != NULL)
				{
					//  temp->id is graph node vertices
					//  in this case temp->id is same as
					//  node[temp->id].data
					cout << "  " << this->node[temp->id].data;
					temp = temp->next;
				}
				i++;
			}
		}
		else
		{
			cout << "Empty Graph Node";
		}
	}
	//  This is an undirected graph so indegree will be equal to outdegree
	//  Find indegree of each nodes of a given graph
	void findDegree(int indegree[])
	{
		if (this->size <= 0)
		{
			return;
		}
		AjlistNode *temp = NULL;
		//   Loop controlling variable
		int i = 0;
		while (i < this->size)
		{
			indegree[i] = 0;
			i++;
		}
		i = 0;
		//  Find the  incoming edges of each node
		while (i < this->size)
		{
			//   Get first edge of i node in given graph
			temp = this->node[i].edge;
			while (temp != NULL)
			{
				indegree[temp->id]++;
				//   visit to next edge
				temp = temp->next;
			}++i;
		}
	}
	//   This is removing connection of node which is less than k edges
	void kCores(int k)
	{
		if (k <= 0 || this->size <= 0)
		{
			cout << "\nGraph is empty or " << k << " core Not valid\n";
		}
		else
		{
			int indegree[this->size];
			//   Loop controlling variable
			int i = 0;
			this->findDegree(indegree);
			AjlistNode *edge = NULL, *auxiliary = NULL, *temp = NULL;
			bool status = true;
			while (status == true)
			{
				status = false;
				i = 0;
				while (i < this->size)
				{
					if (indegree[i] > 0 && indegree[i] < k)
					{
						edge = this->node[i].edge;
						this->node[i].edge = NULL;
						while (edge != NULL)
						{
							auxiliary = edge;
							indegree[edge->id]--;
							edge = edge->next;
							//  remove edge
							auxiliary = NULL;
						}
						indegree[i] = 0;
						status = true;
					}++i;
				}
			}
			//   Edge are connect both direction
			//   for example a---> b and b--->a
			//   remove edges which is less than k
			i = 0;
			while (i < this->size)
			{
				edge = this->node[i].edge;
				auxiliary = NULL;
				while (edge != NULL)
				{
					if (indegree[edge->id] <= 0)
					{
						if (this->node[i].edge == edge)
						{
							//  delete first edge
							this->node[i].edge = edge->next;
						}
						else
						{
							auxiliary->next = edge->next;
						}
						temp = edge;
						edge = edge->next;
						//  remove edge
						temp = NULL;
					}
					else
					{
						auxiliary = edge;
						//   visit to next edge
						edge = edge->next;
					}
				}++i;
			}
			cout << "\n";
		}
	}
};
int main()
{
	//   10 is number of nodes
	MyGraph graph = MyGraph(10);
	//  Connected two node with Edges
	graph.addEdge(0, 1);
	graph.addEdge(0, 4);
	graph.addEdge(0, 7);
	graph.addEdge(1, 2);
	graph.addEdge(1, 4);
	graph.addEdge(1, 6);
	graph.addEdge(2, 3);
	graph.addEdge(2, 4);
	graph.addEdge(3, 4);
	graph.addEdge(3, 5);
	graph.addEdge(3, 6);
	graph.addEdge(4, 5);
	graph.addEdge(5, 6);
	graph.addEdge(5, 7);
	graph.addEdge(5, 8);
	graph.addEdge(6, 9);
	graph.addEdge(7, 8);
	graph.addEdge(8, 9);
	graph.printGraph();
	int k = 3;
	graph.kCores(k);
	cout << "\n After remove " << k << " Cores\n";
	graph.printGraph();
	return 0;
}

Output

 Adjacency list of vertex 0 :  1  4  7
 Adjacency list of vertex 1 :  0  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  0  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6  7  8
 Adjacency list of vertex 6 :  1  3  5  9
 Adjacency list of vertex 7 :  0  5  8
 Adjacency list of vertex 8 :  5  7  9
 Adjacency list of vertex 9 :  6  8

 After remove 3 Cores

 Adjacency list of vertex 0 :
 Adjacency list of vertex 1 :  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6
 Adjacency list of vertex 6 :  1  3  5
 Adjacency list of vertex 7 :
 Adjacency list of vertex 8 :
 Adjacency list of vertex 9 :
// Include namespace system
using System;
/*
  C# Program
  Find k-cores of an undirected graph
*/
//  Define edge of graph node
public class AjlistNode
{
	// Vertices id
	public int id;
	public AjlistNode next;
	public AjlistNode(int id)
	{
		this.id = id;
		this.next = null;
	}
}
//  Define node of graph
public class GraphNode
{
	// node key value
	public int data;
	public AjlistNode edge;
	public GraphNode(int data)
	{
		this.data = data;
		this.edge = null;
	}
}
//  Define structure of graph
public class MyGraph
{
	//  Number of graph nodes
	public int size;
	public GraphNode[] node;
	public MyGraph(int size)
	{
		if (size < 0)
		{
			Console.Write("\n Invalid size of nodes " + size + " \n");
		}
		else
		{
			this.size = size;
			this.node = new GraphNode[this.size];
			int i = 0;
			//  Set graph node level and e
			for (i = 0; i < this.size; i++)
			{
				this.node[i] = new GraphNode(i);
			}
		}
	}
	// This function are connect nodes with one edge
	public void connectEdge(int a, int b)
	{
		if (this.size <= 0)
		{
			Console.Write("\n Graph have no nodes \n");
			return;
		}
		//  Create Adjacency node
		AjlistNode newEdge = new AjlistNode(b);
		if (newEdge != null)
		{
			//  Get first edge of [i] node
			AjlistNode edge = this.node[a].edge;
			if (edge == null)
			{
				//  Whe no edge of graph node [i] then
				//  Add a first edge of a [i] node
				this.node[a].edge = newEdge;
			}
			else
			{
				// Find last location to add new edge
				while (edge.next != null)
				{
					edge = edge.next;
				}
				//  Add edge at last position
				edge.next = newEdge;
			}
		}
		else
		{
			Console.Write("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes.\n");
		}
	}
	//  This is handles the request of connecting Edges between given node a to b
	public void addEdge(int a, int b)
	{
		if (this.size > 0 && a < this.size && b < this.size)
		{
			//  connect edge
			//  a---->b
			connectEdge(a, b);
			// self loop
			if (a == b)
			{
				return;
			}
			//  connect edge
			//  a <---- b
			connectEdge(b, a);
		}
		else
		{
			// not valid Vertices
			Console.Write("Invalid Node Vertices " + a + " " + b);
		}
	}
	// Display Adjacency list of vertex
	public void printGraph()
	{
		if (this.size > 0)
		{
			AjlistNode temp = null;
			//  Loop controlling variable
			int i = 0;
			for (i = 0; i < this.size; i++)
			{
				Console.Write("\n Adjacency list of vertex " + i + " :");
				//  Get first edge of [i] node
				temp = this.node[i].edge;
				while (temp != null)
				{
					// temp->id is graph node vertices
					// in this case temp->id is same as
					// node[temp->id].data
					Console.Write("  " + this.node[temp.id].data);
					temp = temp.next;
				}
			}
		}
		else
		{
			Console.Write("Empty Graph Node");
		}
	}
	// This is an undirected graph so indegree will be equal to outdegree
	// Find indegree of each nodes of a given graph
	public void findDegree(int[] indegree)
	{
		if (this.size <= 0)
		{
			return;
		}
		AjlistNode temp = null;
		//  Loop controlling variable
		int i = 0;
		for (i = 0; i < this.size; ++i)
		{
			indegree[i] = 0;
		}
		// Find the  incoming edges of each node
		for (i = 0; i < this.size; ++i)
		{
			//  Get first edge of i node in given graph
			temp = this.node[i].edge;
			while (temp != null)
			{
				indegree[temp.id]++;
				//  visit to next edge
				temp = temp.next;
			}
		}
	}
	//  This is removing connection of node which is less than k edges
	public void kCores(int k)
	{
		if (k <= 0 || this.size <= 0)
		{
			Console.Write("\nGraph is empty or " + k + " core Not valid\n");
		}
		else
		{
			int[] indegree = new int[this.size];
			//  Loop controlling variable
			int i = 0;
			findDegree(indegree);
			AjlistNode edge = null, auxiliary = null;
			Boolean status = true;
			while (status == true)
			{
				status = false;
				for (i = 0; i < this.size; ++i)
				{
					if (indegree[i] > 0 && indegree[i] < k)
					{
						edge = this.node[i].edge;
						this.node[i].edge = null;
						while (edge != null)
						{
							auxiliary = edge;
							indegree[edge.id]--;
							edge = edge.next;
							// remove edge
							auxiliary = null;
						}
						indegree[i] = 0;
						status = true;
					}
				}
			}
			//  Edge are connect both direction
			//  for example a---> b and b--->a
			//  remove edges which is less than k
			for (i = 0; i < this.size; ++i)
			{
				edge = this.node[i].edge;
				auxiliary = null;
				while (edge != null)
				{
					if (indegree[edge.id] <= 0)
					{
						if (this.node[i].edge == edge)
						{
							// delete first edge
							this.node[i].edge = edge.next;
						}
						else
						{
							auxiliary.next = edge.next;
						}
						
						edge = edge.next;
						
					}
					else
					{
						auxiliary = edge;
						//  visit to next edge
						edge = edge.next;
					}
				}
			}
			Console.Write("\n");
		}
	}
	public static void Main(String[] args)
	{
		//  10 is number of nodes
		MyGraph graph = new MyGraph(10);
		// Connected two node with Edges
		graph.addEdge(0, 1);
		graph.addEdge(0, 4);
		graph.addEdge(0, 7);
		graph.addEdge(1, 2);
		graph.addEdge(1, 4);
		graph.addEdge(1, 6);
		graph.addEdge(2, 3);
		graph.addEdge(2, 4);
		graph.addEdge(3, 4);
		graph.addEdge(3, 5);
		graph.addEdge(3, 6);
		graph.addEdge(4, 5);
		graph.addEdge(5, 6);
		graph.addEdge(5, 7);
		graph.addEdge(5, 8);
		graph.addEdge(6, 9);
		graph.addEdge(7, 8);
		graph.addEdge(8, 9);
		graph.printGraph();
		int k = 3;
		graph.kCores(k);
		Console.Write("\n After remove " + k + " Cores\n");
		graph.printGraph();
	}
}

Output

 Adjacency list of vertex 0 :  1  4  7
 Adjacency list of vertex 1 :  0  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  0  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6  7  8
 Adjacency list of vertex 6 :  1  3  5  9
 Adjacency list of vertex 7 :  0  5  8
 Adjacency list of vertex 8 :  5  7  9
 Adjacency list of vertex 9 :  6  8

 After remove 3 Cores

 Adjacency list of vertex 0 :
 Adjacency list of vertex 1 :  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6
 Adjacency list of vertex 6 :  1  3  5
 Adjacency list of vertex 7 :
 Adjacency list of vertex 8 :
 Adjacency list of vertex 9 :
<?php
/*
  Php Program
  Find k-cores of an undirected graph
*/
//  Define edge of graph node
class AjlistNode
{
	// Vertices id
	public $id;
	public $next;

	function __construct($id)
	{
		$this->id = $id;
		$this->next = null;
	}
}
//  Define node of graph
class GraphNode
{
	// node key value
	public $data;
	public $edge;

	function __construct($data)
	{
		$this->data = $data;
		$this->edge = null;
	}
}
//  Define structure of graph
class MyGraph
{
	//  Number of graph nodes
	public $size;
	public $node;

	function __construct($size)
	{
		if ($size < 0)
		{
			echo "\n Invalid size of nodes ". $size ." \n";
		}
		else
		{
			$this->size = $size;
			$this->node = array_fill(0, $this->size, null);
			$i = 0;
			//  Set graph node level and e
			for ($i = 0; $i < $this->size; $i++)
			{
				$this->node[$i] = new GraphNode($i);
			}
		}
	}
	// This function are connect nodes with one edge
	public	function connectEdge($a, $b)
	{
		if ($this->size <= 0)
		{
			echo "\n Graph have no nodes \n";
			return;
		}
		//  Create Adjacency node
		$newEdge = new AjlistNode($b);
		if ($newEdge != null)
		{
			//  Get first edge of [i] node
			$edge = $this->node[$a]->edge;
			if ($edge == null)
			{
				//  Whe no edge of graph node [i] then
				//  Add a first edge of a [i] node
				$this->node[$a]->edge = $newEdge;
			}
			else
			{
				// Find last location to add new edge
				while ($edge->next != null)
				{
					$edge = $edge->next;
				}
				//  Add edge at last position
				$edge->next = $newEdge;
			}
		}
		else
		{
			echo "\nMemory overflow, when connect a new edge from ( ". $a ." to ". $b ." ) nodes.\n";
		}
	}
	//  This is handles the request of connecting Edges between given node a to b
	public	function addEdge($a, $b)
	{
		if ($this->size > 0 && $a < $this->size && $b < $this->size)
		{
			//  connect edge
			//  a---->b
			$this->connectEdge($a, $b);
			// self loop
			if ($a == $b)
			{
				return;
			}
			//  connect edge
			//  a <---- b
			$this->connectEdge($b, $a);
		}
		else
		{
			// not valid Vertices
			echo "Invalid Node Vertices ". $a ." ". $b;
		}
	}
	// Display Adjacency list of vertex
	public	function printGraph()
	{
		if ($this->size > 0)
		{
			$temp = null;
			//  Loop controlling variable
			$i = 0;
			for ($i = 0; $i < $this->size; $i++)
			{
				echo "\n Adjacency list of vertex ". $i ." :";
				//  Get first edge of [i] node
				$temp = $this->node[$i]->edge;
				while ($temp != null)
				{
					// temp->id is graph node vertices
					// in this case temp->id is same as
					// node[temp->id].data
					echo "  ". $this->node[$temp->id]->data;
					$temp = $temp->next;
				}
			}
		}
		else
		{
			echo "Empty Graph Node";
		}
	}
	// This is an undirected graph so indegree will be equal to outdegree
	// Find indegree of each nodes of a given graph
	public	function findDegree( & $indegree)
	{
		if ($this->size <= 0)
		{
			return;
		}
		$temp = null;
		//  Loop controlling variable
		$i = 0;
		for ($i = 0; $i < $this->size; ++$i)
		{
			$indegree[$i] = 0;
		}
		// Find the  incoming edges of each node
		for ($i = 0; $i < $this->size; ++$i)
		{
			//  Get first edge of i node in given graph
			$temp = $this->node[$i]->edge;
			while ($temp != null)
			{
				$indegree[$temp->id]++;
				//  visit to next edge
				$temp = $temp->next;
			}
		}
	}
	//  This is removing connection of node which is less than k edges
	public	function kCores($k)
	{
		if ($k <= 0 || $this->size <= 0)
		{
			echo "\nGraph is empty or ". $k ." core Not valid\n";
		}
		else
		{
			$indegree = array_fill(0, $this->size, 0);
			//  Loop controlling variable
			$i = 0;
			$this->findDegree($indegree);
			$edge = null;
			$auxiliary = null;
			$temp = null;
			$status = true;
			while ($status == true)
			{
				$status = false;
				for ($i = 0; $i < $this->size; ++$i)
				{
					if ($indegree[$i] > 0 && $indegree[$i] < $k)
					{
						$edge = $this->node[$i]->edge;
						$this->node[$i]->edge = null;
						while ($edge != null)
						{
							$auxiliary = $edge;
							$indegree[$edge->id]--;
							$edge = $edge->next;
							// remove edge
							$auxiliary = null;
						}
						$indegree[$i] = 0;
						$status = true;
					}
				}
			}
			//  Edge are connect both direction
			//  for example a---> b and b--->a
			//  remove edges which is less than k
			for ($i = 0; $i < $this->size; ++$i)
			{
				$edge = $this->node[$i]->edge;
				$auxiliary = null;
				while ($edge != null)
				{
					if ($indegree[$edge->id] <= 0)
					{
						if ($this->node[$i]->edge == $edge)
						{
							// delete first edge
							$this->node[$i]->edge = $edge->next;
						}
						else
						{
							$auxiliary->next = $edge->next;
						}
						$temp = $edge;
						$edge = $edge->next;
						// remove edge
						$temp = null;
					}
					else
					{
						$auxiliary = $edge;
						//  visit to next edge
						$edge = $edge->next;
					}
				}
			}
			echo "\n";
		}
	}
}

function main()
{
	//  10 is number of nodes
	$graph = new MyGraph(10);
	// Connected two node with Edges
	$graph->addEdge(0, 1);
	$graph->addEdge(0, 4);
	$graph->addEdge(0, 7);
	$graph->addEdge(1, 2);
	$graph->addEdge(1, 4);
	$graph->addEdge(1, 6);
	$graph->addEdge(2, 3);
	$graph->addEdge(2, 4);
	$graph->addEdge(3, 4);
	$graph->addEdge(3, 5);
	$graph->addEdge(3, 6);
	$graph->addEdge(4, 5);
	$graph->addEdge(5, 6);
	$graph->addEdge(5, 7);
	$graph->addEdge(5, 8);
	$graph->addEdge(6, 9);
	$graph->addEdge(7, 8);
	$graph->addEdge(8, 9);
	$graph->printGraph();
	$k = 3;
	$graph->kCores($k);
	echo "\n After remove ". $k ." Cores\n";
	$graph->printGraph();
}
main();

Output

 Adjacency list of vertex 0 :  1  4  7
 Adjacency list of vertex 1 :  0  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  0  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6  7  8
 Adjacency list of vertex 6 :  1  3  5  9
 Adjacency list of vertex 7 :  0  5  8
 Adjacency list of vertex 8 :  5  7  9
 Adjacency list of vertex 9 :  6  8

 After remove 3 Cores

 Adjacency list of vertex 0 :
 Adjacency list of vertex 1 :  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6
 Adjacency list of vertex 6 :  1  3  5
 Adjacency list of vertex 7 :
 Adjacency list of vertex 8 :
 Adjacency list of vertex 9 :
/*
  Node Js Program
  Find k-cores of an undirected graph
*/
//  Define edge of graph node
class AjlistNode
{
	// Vertices id
	constructor(id)
	{
		this.id = id;
		this.next = null;
	}
}
//  Define node of graph
class GraphNode
{
	// node key value
	constructor(data)
	{
		this.data = data;
		this.edge = null;
	}
}
//  Define structure of graph
class MyGraph
{
	//  Number of graph nodes
	constructor(size)
	{
		if (size < 0)
		{
			process.stdout.write("\n Invalid size of nodes " + size + " \n");
		}
		else
		{
			this.size = size;
			this.node = Array(this.size).fill(null);
			var i = 0;
			//  Set graph node level and e
			for (i = 0; i < this.size; i++)
			{
				this.node[i] = new GraphNode(i);
			}
		}
	}
	// This function are connect nodes with one edge
	connectEdge(a, b)
	{
		if (this.size <= 0)
		{
			process.stdout.write("\n Graph have no nodes \n");
			return;
		}
		//  Create Adjacency node
		var newEdge = new AjlistNode(b);
		if (newEdge != null)
		{
			//  Get first edge of [i] node
			var edge = this.node[a].edge;
			if (edge == null)
			{
				//  Whe no edge of graph node [i] then
				//  Add a first edge of a [i] node
				this.node[a].edge = newEdge;
			}
			else
			{
				// Find last location to add new edge
				while (edge.next != null)
				{
					edge = edge.next;
				}
				//  Add edge at last position
				edge.next = newEdge;
			}
		}
		else
		{
			process.stdout.write("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes.\n");
		}
	}
	//  This is handles the request of connecting Edges between given node a to b
	addEdge(a, b)
	{
		if (this.size > 0 && a < this.size && b < this.size)
		{
			//  connect edge
			//  a---->b
			this.connectEdge(a, b);
			// self loop
			if (a == b)
			{
				return;
			}
			//  connect edge
			//  a <---- b
			this.connectEdge(b, a);
		}
		else
		{
			// not valid Vertices
			process.stdout.write("Invalid Node Vertices " + a + " " + b);
		}
	}
	// Display Adjacency list of vertex
	printGraph()
	{
		if (this.size > 0)
		{
			var temp = null;
			//  Loop controlling variable
			var i = 0;
			for (i = 0; i < this.size; i++)
			{
				process.stdout.write("\n Adjacency list of vertex " + i + " :");
				//  Get first edge of [i] node
				temp = this.node[i].edge;
				while (temp != null)
				{
					// temp->id is graph node vertices
					// in this case temp->id is same as
					// node[temp->id].data
					process.stdout.write("  " + this.node[temp.id].data);
					temp = temp.next;
				}
			}
		}
		else
		{
			process.stdout.write("Empty Graph Node");
		}
	}
	// This is an undirected graph so indegree will be equal to outdegree
	// Find indegree of each nodes of a given graph
	findDegree(indegree)
	{
		if (this.size <= 0)
		{
			return;
		}
		var temp = null;
		//  Loop controlling variable
		var i = 0;
		// Find the  incoming edges of each node
		for (i = 0; i < this.size; ++i)
		{
			//  Get first edge of i node in given graph
			temp = this.node[i].edge;
			while (temp != null)
			{
				indegree[temp.id]++;
				//  visit to next edge
				temp = temp.next;
			}
		}
	}
	//  This is removing connection of node which is less than k edges
	kCores(k)
	{
		if (k <= 0 || this.size <= 0)
		{
			process.stdout.write("\nGraph is empty or " + k + " core Not valid\n");
		}
		else
		{
			var indegree = Array(this.size).fill(0);
			//  Loop controlling variable
			var i = 0;
			this.findDegree(indegree);
			var edge = null;
			var auxiliary = null;
			var temp = null;
			var status = true;
			while (status == true)
			{
				status = false;
				for (i = 0; i < this.size; ++i)
				{
					if (indegree[i] > 0 && indegree[i] < k)
					{
						edge = this.node[i].edge;
						this.node[i].edge = null;
						while (edge != null)
						{
							auxiliary = edge;
							indegree[edge.id]--;
							edge = edge.next;
							// remove edge
							auxiliary = null;
						}
						indegree[i] = 0;
						status = true;
					}
				}
			}
			//  Edge are connect both direction
			//  for example a---> b and b--->a
			//  remove edges which is less than k
			for (i = 0; i < this.size; ++i)
			{
				edge = this.node[i].edge;
				auxiliary = null;
				while (edge != null)
				{
					if (indegree[edge.id] <= 0)
					{
						if (this.node[i].edge == edge)
						{
							// delete first edge
							this.node[i].edge = edge.next;
						}
						else
						{
							auxiliary.next = edge.next;
						}
						temp = edge;
						edge = edge.next;
						// remove edge
						temp = null;
					}
					else
					{
						auxiliary = edge;
						//  visit to next edge
						edge = edge.next;
					}
				}
			}
			process.stdout.write("\n");
		}
	}
}

function main()
{
	//  10 is number of nodes
	var graph = new MyGraph(10);
	// Connected two node with Edges
	graph.addEdge(0, 1);
	graph.addEdge(0, 4);
	graph.addEdge(0, 7);
	graph.addEdge(1, 2);
	graph.addEdge(1, 4);
	graph.addEdge(1, 6);
	graph.addEdge(2, 3);
	graph.addEdge(2, 4);
	graph.addEdge(3, 4);
	graph.addEdge(3, 5);
	graph.addEdge(3, 6);
	graph.addEdge(4, 5);
	graph.addEdge(5, 6);
	graph.addEdge(5, 7);
	graph.addEdge(5, 8);
	graph.addEdge(6, 9);
	graph.addEdge(7, 8);
	graph.addEdge(8, 9);
	graph.printGraph();
	var k = 3;
	graph.kCores(k);
	process.stdout.write("\n After remove " + k + " Cores\n");
	graph.printGraph();
}
main();

Output

 Adjacency list of vertex 0 :  1  4  7
 Adjacency list of vertex 1 :  0  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  0  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6  7  8
 Adjacency list of vertex 6 :  1  3  5  9
 Adjacency list of vertex 7 :  0  5  8
 Adjacency list of vertex 8 :  5  7  9
 Adjacency list of vertex 9 :  6  8

 After remove 3 Cores

 Adjacency list of vertex 0 :
 Adjacency list of vertex 1 :  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6
 Adjacency list of vertex 6 :  1  3  5
 Adjacency list of vertex 7 :
 Adjacency list of vertex 8 :
 Adjacency list of vertex 9 :
#   Python 3 Program
#   Find k-cores of an undirected graph

#   Define edge of graph node
class AjlistNode :

	def __init__(self, id) :
		self.id = id
		self.next = None
	
#   Define node of graph
class GraphNode :

	def __init__(self, data) :
		self.data = data
		self.edge = None
	

#   Define structure of graph
class MyGraph :

	def __init__(self, size) :
		if (size < 0) :
			print("\n Invalid size of nodes ", size ," ")
		else :
			self.size = size
			self.node = [None] * (self.size)
			i = 0
			#   Set graph node level and e
			i = 0
			while (i < self.size) :
				self.node[i] = GraphNode(i)
				i += 1
			
		
	
	#  This function are connect nodes with one edge
	def connectEdge(self, a, b) :
		if (self.size <= 0) :
			print("\n Graph have no nodes ")
			return
		
		#   Create Adjacency node
		newEdge = AjlistNode(b)
		if (newEdge != None) :
			#   Get first edge of [i] node
			edge = self.node[a].edge
			if (edge == None) :
				#   Whe no edge of graph node [i] then
				#   Add a first edge of a [i] node
				self.node[a].edge = newEdge
			else :
				#  Find last location to add new edge
				while (edge.next != None) :
					edge = edge.next
				
				#   Add edge at last position
				edge.next = newEdge
			
		else :
			print("\nMemory overflow, when connect a new edge from ( ", a ," to ", b ," ) nodes.")
		
	
	#   This is handles the request of connecting Edges between given node a to b
	def addEdge(self, a, b) :
		if (self.size > 0 and a < self.size and b < self.size) :
			#   connect edge
			#   a---->b
			self.connectEdge(a, b)
			#  self loop
			if (a == b) :
				return
			
			#   connect edge
			#   a <---- b
			self.connectEdge(b, a)
		else :
			#  not valid Vertices
			print("Invalid Node Vertices ", a ," ", b, end = "")
		
	
	#  Display Adjacency list of vertex
	def printGraph(self) :
		if (self.size > 0) :
			temp = None
			#   Loop controlling variable
			i = 0
			while (i < self.size) :
				print("\n Adjacency list of vertex ", i ," :", end = "")
				#   Get first edge of [i] node
				temp = self.node[i].edge
				while (temp != None) :
					#  temp->id is graph node vertices
					#  in this case temp->id is same as
					#  node[temp->id].data
					print("  ", self.node[temp.id].data, end = "")
					temp = temp.next
				
				i += 1
			
		else :
			print("Empty Graph Node", end = "")
		
	
	#  This is an undirected graph so indegree will be equal to outdegree
	#  Find indegree of each nodes of a given graph
	def findDegree(self, indegree) :
		if (self.size <= 0) :
			return
		
		temp = None
		#   Loop controlling variable
		i = 0
		#  Find the  incoming edges of each node
		while (i < self.size) :
			#   Get first edge of i node in given graph
			temp = self.node[i].edge
			while (temp != None) :
				indegree[temp.id] += 1
				#   visit to next edge
				temp = temp.next
			
			i += 1
		
	
	#   This is removing connection of node which is less than k edges
	def kCores(self, k) :
		if (k <= 0 or self.size <= 0) :
			print("\nGraph is empty or ", k ," core Not valid")
		else :
			indegree = [0] * (self.size)
			#   Loop controlling variable
			i = 0
			self.findDegree(indegree)
			edge = None
			auxiliary = None
			temp = None
			status = True
			while (status == True) :
				status = False
				i = 0
				while (i < self.size) :
					if (indegree[i] > 0 and indegree[i] < k) :
						edge = self.node[i].edge
						self.node[i].edge = None
						while (edge != None) :
							auxiliary = edge
							indegree[edge.id] -= 1
							edge = edge.next
							#  remove edge
							auxiliary = None
						
						indegree[i] = 0
						status = True
					
					i += 1
				
			
			#   Edge are connect both direction
			#   for example a---> b and b--->a
			#   remove edges which is less than k
			i = 0
			while (i < self.size) :
				edge = self.node[i].edge
				auxiliary = None
				while (edge != None) :
					if (indegree[edge.id] <= 0) :
						if (self.node[i].edge == edge) :
							#  delete first edge
							self.node[i].edge = edge.next
						else :
							auxiliary.next = edge.next
						
						temp = edge
						edge = edge.next
						#  remove edge
						temp = None
					else :
						auxiliary = edge
						#   visit to next edge
						edge = edge.next
					
				
				i += 1
			
			print(end = "\n")
		
	

def main() :
	#   10 is number of nodes
	graph = MyGraph(10)
	#  Connected two node with Edges
	graph.addEdge(0, 1)
	graph.addEdge(0, 4)
	graph.addEdge(0, 7)
	graph.addEdge(1, 2)
	graph.addEdge(1, 4)
	graph.addEdge(1, 6)
	graph.addEdge(2, 3)
	graph.addEdge(2, 4)
	graph.addEdge(3, 4)
	graph.addEdge(3, 5)
	graph.addEdge(3, 6)
	graph.addEdge(4, 5)
	graph.addEdge(5, 6)
	graph.addEdge(5, 7)
	graph.addEdge(5, 8)
	graph.addEdge(6, 9)
	graph.addEdge(7, 8)
	graph.addEdge(8, 9)
	graph.printGraph()
	k = 3
	graph.kCores(k)
	print("\n After remove ", k ," Cores")
	graph.printGraph()

if __name__ == "__main__": main()

Output

 Adjacency list of vertex  0  :   1   4   7
 Adjacency list of vertex  1  :   0   2   4   6
 Adjacency list of vertex  2  :   1   3   4
 Adjacency list of vertex  3  :   2   4   5   6
 Adjacency list of vertex  4  :   0   1   2   3   5
 Adjacency list of vertex  5  :   3   4   6   7   8
 Adjacency list of vertex  6  :   1   3   5   9
 Adjacency list of vertex  7  :   0   5   8
 Adjacency list of vertex  8  :   5   7   9
 Adjacency list of vertex  9  :   6   8

 After remove  3  Cores

 Adjacency list of vertex  0  :
 Adjacency list of vertex  1  :   2   4   6
 Adjacency list of vertex  2  :   1   3   4
 Adjacency list of vertex  3  :   2   4   5   6
 Adjacency list of vertex  4  :   1   2   3   5
 Adjacency list of vertex  5  :   3   4   6
 Adjacency list of vertex  6  :   1   3   5
 Adjacency list of vertex  7  :
 Adjacency list of vertex  8  :
 Adjacency list of vertex  9  :
#   Ruby Program
#   Find k-cores of an undirected graph

#   Define edge of graph node
class AjlistNode  
	# Define the accessor and reader of class AjlistNode  
	attr_reader :id, :next
	attr_accessor :id, :next
 
	#  Vertices id
	
	def initialize(id) 
		self.id = id
		self.next = nil
	end

end

#   Define node of graph
class GraphNode  
	# Define the accessor and reader of class GraphNode  
	attr_reader :data, :edge
	attr_accessor :data, :edge
 
	#  node key value
	
	def initialize(data) 
		self.data = data
		self.edge = nil
	end

end

#   Define structure of graph
class MyGraph  
	# Define the accessor and reader of class MyGraph  
	attr_reader :size, :node
	attr_accessor :size, :node
 
	#   Number of graph nodes
	
	def initialize(size) 
		if (size < 0) 
			print("\n Invalid size of nodes ", size ," \n")
		else 
			self.size = size
			self.node = Array.new(self.size) {nil}
			i = 0
			#   Set graph node level and e
			i = 0
			while (i < self.size) 
				self.node[i] = GraphNode.new(i)
				i += 1
			end

		end

	end

	#  This function are connect nodes with one edge
	def connectEdge(a, b) 
		if (self.size <= 0) 
			print("\n Graph have no nodes \n")
			return
		end

		#   Create Adjacency node
		newEdge = AjlistNode.new(b)
		if (newEdge != nil) 
			#   Get first edge of [i] node
			edge = self.node[a].edge
			if (edge == nil) 
				#   Whe no edge of graph node [i] then
				#   Add a first edge of a [i] node
				self.node[a].edge = newEdge
			else 
				#  Find last location to add new edge
				while (edge.next != nil) 
					edge = edge.next
				end

				#   Add edge at last position
				edge.next = newEdge
			end

		else 
			print("\nMemory overflow, when connect a new edge from ( ", a ," to ", b ," ) nodes.\n")
		end

	end

	#   This is handles the request of connecting Edges between given node a to b
	def addEdge(a, b) 
		if (self.size > 0 && a < self.size && b < self.size) 
			#   connect edge
			#   a---->b
			self.connectEdge(a, b)
			#  self loop
			if (a == b) 
				return
			end

			#   connect edge
			#   a <---- b
			self.connectEdge(b, a)
		else 
			#  not valid Vertices
			print("Invalid Node Vertices ", a ," ", b)
		end

	end

	#  Display Adjacency list of vertex
	def printGraph() 
		if (self.size > 0) 
			temp = nil
			#   Loop controlling variable
			i = 0
			while (i < self.size) 
				print("\n Adjacency list of vertex ", i ," :")
				#   Get first edge of [i] node
				temp = self.node[i].edge
				while (temp != nil) 
					#  temp->id is graph node vertices
					#  in this case temp->id is same as
					#  node[temp->id].data
					print("  ", self.node[temp.id].data)
					temp = temp.next
				end

				i += 1
			end

		else 
			print("Empty Graph Node")
		end

	end

	#  This is an undirected graph so indegree will be equal to outdegree
	#  Find indegree of each nodes of a given graph
	def findDegree(indegree) 
		if (self.size <= 0) 
			return
		end

		temp = nil
		#   Loop controlling variable
		i = 0
		#  Find the  incoming edges of each node
		while (i < self.size) 
			#   Get first edge of i node in given graph
			temp = self.node[i].edge
			while (temp != nil) 
				indegree[temp.id] += 1
				#   visit to next edge
				temp = temp.next
			end

			i += 1
		end

	end

	#   This is removing connection of node which is less than k edges
	def kCores(k) 
		if (k <= 0 || self.size <= 0) 
			print("\nGraph is empty or ", k ," core Not valid\n")
		else 
			indegree = Array.new(self.size) {0}
			#   Loop controlling variable
			i = 0
			self.findDegree(indegree)
			edge = nil
			auxiliary = nil
			temp = nil
			status = true
			while (status == true) 
				status = false
				i = 0
				while (i < self.size) 
					if (indegree[i] > 0 && indegree[i] < k) 
						edge = self.node[i].edge
						self.node[i].edge = nil
						while (edge != nil) 
							auxiliary = edge
							indegree[edge.id] -= 1
							edge = edge.next
							#  remove edge
							auxiliary = nil
						end

						indegree[i] = 0
						status = true
					end

					i += 1
				end

			end

			#   Edge are connect both direction
			#   for example a---> b and b--->a
			#   remove edges which is less than k
			i = 0
			while (i < self.size) 
				edge = self.node[i].edge
				auxiliary = nil
				while (edge != nil) 
					if (indegree[edge.id] <= 0) 
						if (self.node[i].edge == edge) 
							#  delete first edge
							self.node[i].edge = edge.next
						else 
							auxiliary.next = edge.next
						end

						temp = edge
						edge = edge.next
						#  remove edge
						temp = nil
					else 
						auxiliary = edge
						#   visit to next edge
						edge = edge.next
					end

				end

				i += 1
			end

			print("\n")
		end

	end

end

def main() 
	#   10 is number of nodes
	graph = MyGraph.new(10)
	#  Connected two node with Edges
	graph.addEdge(0, 1)
	graph.addEdge(0, 4)
	graph.addEdge(0, 7)
	graph.addEdge(1, 2)
	graph.addEdge(1, 4)
	graph.addEdge(1, 6)
	graph.addEdge(2, 3)
	graph.addEdge(2, 4)
	graph.addEdge(3, 4)
	graph.addEdge(3, 5)
	graph.addEdge(3, 6)
	graph.addEdge(4, 5)
	graph.addEdge(5, 6)
	graph.addEdge(5, 7)
	graph.addEdge(5, 8)
	graph.addEdge(6, 9)
	graph.addEdge(7, 8)
	graph.addEdge(8, 9)
	graph.printGraph()
	k = 3
	graph.kCores(k)
	print("\n After remove ", k ," Cores\n")
	graph.printGraph()
end

main()

Output

 Adjacency list of vertex 0 :  1  4  7
 Adjacency list of vertex 1 :  0  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  0  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6  7  8
 Adjacency list of vertex 6 :  1  3  5  9
 Adjacency list of vertex 7 :  0  5  8
 Adjacency list of vertex 8 :  5  7  9
 Adjacency list of vertex 9 :  6  8

 After remove 3 Cores

 Adjacency list of vertex 0 :
 Adjacency list of vertex 1 :  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6
 Adjacency list of vertex 6 :  1  3  5
 Adjacency list of vertex 7 :
 Adjacency list of vertex 8 :
 Adjacency list of vertex 9 :
/* 
  Scala Program
  Find k-cores of an undirected graph
*/
//   Define edge of graph node
class AjlistNode(var id: Int , var next: AjlistNode)
{
    def this(id: Int)
    {
        this(id, null);
    }
}
//   Define node of graph
class GraphNode(var data: Int , var edge: AjlistNode)
{
    def this(data: Int)
    {
        this(data, null);
    }
}
//   Define structure of graph
class MyGraph(var size: Int , var node: Array[GraphNode])
{
    def this(size: Int)
    {
        this(size, Array.fill[GraphNode](size)(null));

        if (size > 0)
        {
            var i: Int = 0;
            //  Set graph node level and e
            while (i < this.size)
            {
                this.node(i) = new GraphNode(i);
                i += 1;
            }
        }
    }
 
    //  This function are connect nodes with one edge
    def connectEdge(a: Int, b: Int): Unit = {
        if (this.size <= 0)
        {
            print("\n Graph have no nodes \n");
            return;
        }
        //   Create Adjacency node
        var newEdge: AjlistNode = new AjlistNode(b);
        if (newEdge != null)
        {
            //   Get first edge of [i] node
            var edge: AjlistNode = this.node(a).edge;
            if (edge == null)
            {
                //   Whe no edge of graph node [i] then
                //   Add a first edge of a [i] node
                this.node(a).edge = newEdge;
            }
            else
            {
                //  Find last location to add new edge
                while (edge.next != null)
                {
                    edge = edge.next;
                }
                //   Add edge at last position
                edge.next = newEdge;
            }
        }
        else
        {
            print("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes.\n");
        }
    }
    //   This is handles the request of connecting Edges between given node a to b
    def addEdge(a: Int, b: Int): Unit = {
        if (this.size > 0 && a < this.size && b < this.size)
        {
            //   connect edge
            //   a---->b
            this.connectEdge(a, b);
            //  self loop
            if (a == b)
            {
                return;
            }
            //   connect edge
            //   a <---- b
            this.connectEdge(b, a);
        }
        else
        {
            //  not valid Vertices
            print("Invalid Node Vertices " + a + " " + b);
        }
    }
    //  Display Adjacency list of vertex
    def printGraph(): Unit = {
        if (this.size > 0)
        {
            var temp: AjlistNode = null;
            //   Loop controlling variable
            var i: Int = 0;
            while (i < this.size)
            {
                print("\n Adjacency list of vertex " + i + " :");
                //   Get first edge of [i] node
                temp = this.node(i).edge;
                while (temp != null)
                {
                    //  temp->id is graph node vertices
                    //  in this case temp->id is same as
                    //  node[temp->id].data
                    print("  " + this.node(temp.id).data);
                    temp = temp.next;
                }
                i += 1;
            }
        }
        else
        {
            print("Empty Graph Node");
        }
    }
    //  This is an undirected graph so indegree will be equal to outdegree
    //  Find indegree of each nodes of a given graph
    def findDegree(indegree: Array[Int]): Unit = {
        if (this.size <= 0)
        {
            return;
        }
        var temp: AjlistNode = null;
        //   Loop controlling variable
        var i: Int = 0;
        //  Find the  incoming edges of each node
        while (i < this.size)
        {
            //   Get first edge of i node in given graph
            temp = this.node(i).edge;
            while (temp != null)
            {
                indegree(temp.id) += 1;
                //   visit to next edge
                temp = temp.next;
            }
            i += 1;
        }
    }
    //   This is removing connection of node which is less than k edges
    def kCores(k: Int): Unit = {
        if (k <= 0 || this.size <= 0)
        {
            print("\nGraph is empty or " + k + " core Not valid\n");
        }
        else
        {
            var indegree: Array[Int] = Array.fill[Int](this.size)(0);
            //   Loop controlling variable
            var i: Int = 0;
            this.findDegree(indegree);
            var edge: AjlistNode = null;
            var auxiliary: AjlistNode = null;
            var temp: AjlistNode = null;
            var status: Boolean = true;
            while (status == true)
            {
                status = false;
                i = 0;
                while (i < this.size)
                {
                    if (indegree(i) > 0 && indegree(i) < k)
                    {
                        edge = this.node(i).edge;
                        this.node(i).edge = null;
                        while (edge != null)
                        {
                            auxiliary = edge;
                            indegree(edge.id) -= 1;
                            edge = edge.next;
                            //  remove edge
                            auxiliary = null;
                        }
                        indegree(i) = 0;
                        status = true;
                    }
                    i += 1;
                }
            }
            //   Edge are connect both direction
            //   for example a---> b and b--->a
            //   remove edges which is less than k
            i = 0;
            while (i < this.size)
            {
                edge = this.node(i).edge;
                auxiliary = null;
                while (edge != null)
                {
                    if (indegree(edge.id) <= 0)
                    {
                        if (this.node(i).edge == edge)
                        {
                            //  delete first edge
                            this.node(i).edge = edge.next;
                        }
                        else
                        {
                            auxiliary.next = edge.next;
                        }
                        temp = edge;
                        edge = edge.next;
                        //  remove edge
                        temp = null;
                    }
                    else
                    {
                        auxiliary = edge;
                        //   visit to next edge
                        edge = edge.next;
                    }
                }
                i += 1;
            }
            print("\n");
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        //   10 is number of nodes
        var graph: MyGraph = new MyGraph(10);
        //  Connected two node with Edges
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(0, 7);
        graph.addEdge(1, 2);
        graph.addEdge(1, 4);
        graph.addEdge(1, 6);
        graph.addEdge(2, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 4);
        graph.addEdge(3, 5);
        graph.addEdge(3, 6);
        graph.addEdge(4, 5);
        graph.addEdge(5, 6);
        graph.addEdge(5, 7);
        graph.addEdge(5, 8);
        graph.addEdge(6, 9);
        graph.addEdge(7, 8);
        graph.addEdge(8, 9);
        graph.printGraph();
        var k: Int = 3;
        graph.kCores(k);
        print("\n After remove " + k + " Cores\n");
        graph.printGraph();
    }
}

Output

 Adjacency list of vertex 0 :  1  4  7
 Adjacency list of vertex 1 :  0  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  0  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6  7  8
 Adjacency list of vertex 6 :  1  3  5  9
 Adjacency list of vertex 7 :  0  5  8
 Adjacency list of vertex 8 :  5  7  9
 Adjacency list of vertex 9 :  6  8

 After remove 3 Cores

 Adjacency list of vertex 0 :
 Adjacency list of vertex 1 :  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6
 Adjacency list of vertex 6 :  1  3  5
 Adjacency list of vertex 7 :
 Adjacency list of vertex 8 :
 Adjacency list of vertex 9 :
/*
  Swift 4 Program
  Find k-cores of an undirected graph
*/
//   Define edge of graph node
class AjlistNode
{
	//  Vertices id
	var id: Int;
	var next: AjlistNode? ;
	init(_ id: Int)
	{
		self.id = id;
		self.next = nil;
	}
}
//   Define node of graph
class GraphNode
{
	//  node key value
	var data: Int;
	var edge: AjlistNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.edge = nil;
	}
}
//   Define structure of graph
class MyGraph
{
	//   Number of graph nodes
	var size: Int;
	var node: [GraphNode? ];
	init(_ size: Int)
	{
		if (size < 0)
		{
			print("\n Invalid size of nodes ", size ," ");
          	self.size = 0;
          	self.node = Array(repeating: nil, count: 1);
		}
		else
		{
			self.size = size;
			self.node = Array(repeating: nil, count: self.size);
			var i: Int = 0;
			//   Set graph node level and e
			i = 0;
			while (i < self.size)
			{
				self.node[i] = GraphNode(i);
				i += 1;
			}
		}
	}
	//  This function are connect nodes with one edge
	func connectEdge(_ a: Int, _ b: Int)
	{
		if (self.size <= 0)
		{
			print("\n Graph have no nodes ");
			return;
		}
		//   Create Adjacency node
		let newEdge: AjlistNode? = AjlistNode(b);
		if (newEdge != nil)
		{
			//   Get first edge of [i]node
			var edge: AjlistNode? = self.node[a]!.edge;
			if (edge == nil)
			{
				//   Whe no edge of graph node [i]then
				//   Add a first edge of a [i]node
				self.node[a]!.edge = newEdge;
			}
			else
			{
				//  Find last location to add new edge
				while (edge!.next != nil)
				{
					edge = edge!.next;
				}
				//   Add edge at last position
				edge!.next = newEdge;
			}
		}
		else
		{
			print("\nMemory overflow, when connect a new edge from ( ", a ," to ", b ," ) nodes.");
		}
	}
	//   This is handles the request of connecting Edges between given node a to b
	func addEdge(_ a: Int, _ b: Int)
	{
		if (self.size > 0 && a < self.size && b < self.size)
		{
			//   connect edge
			//   a---->b
			self.connectEdge(a, b);
			//  self loop
			if (a == b)
			{
				return;
			}
			//   connect edge
			//   a <---- b
			self.connectEdge(b, a);
		}
		else
		{
			//  not valid Vertices
			print("Invalid Node Vertices ", a ," ", b, terminator: "");
		}
	}
	//  Display Adjacency list of vertex
	func printGraph()
	{
		if (self.size > 0)
		{
			var temp: AjlistNode? = nil;
			//   Loop controlling variable
			var i: Int = 0;
			while (i < self.size)
			{
				print("\n Adjacency list of vertex ", i ," :", terminator: "");
				//   Get first edge of [i]node
				temp = self.node[i]!.edge;
				while (temp != nil)
				{
					//  temp->id is graph node vertices
					//  in this case temp->id is same as
					//  node[temp->id].data
					print("  ", self.node[temp!.id]!.data, terminator: "");
					temp = temp!.next;
				}
				i += 1;
			}
		}
		else
		{
			print("Empty Graph Node", terminator: "");
		}
	}
	//  This is an undirected graph so indegree will be equal to outdegree
	//  Find indegree of each nodes of a given graph
	func findDegree(_ indegree: inout[Int])
	{
		if (self.size <= 0)
		{
			return;
		}
		var temp: AjlistNode? = nil;
		//   Loop controlling variable
		var i: Int = 0;
		//  Find the  incoming edges of each node
		while (i < self.size)
		{
			//   Get first edge of i node in given graph
			temp = self.node[i]!.edge;
			while (temp != nil)
			{
				indegree[temp!.id] = indegree[temp!.id] + 1;
				//   visit to next edge
				temp = temp!.next;
			}
			i += 1;
		}
	}
	//   This is removing connection of node which is less than k edges
	func kCores(_ k: Int)
	{
		if (k <= 0 || self.size <= 0)
		{
			print("\nGraph is empty or ", k ," core Not valid");
		}
		else
		{
			var indegree: [Int] = Array(repeating: 0, count: self.size);
			//   Loop controlling variable
			var i: Int = 0;
			self.findDegree(&indegree);
			var edge: AjlistNode? = nil;
			var auxiliary: AjlistNode? = nil;
			var status: Bool = true;
			while (status == true)
			{
				status = false;
				i = 0;
				while (i < self.size)
				{
					if (indegree[i] > 0 && indegree[i] < k)
					{
						edge = self.node[i]!.edge;
						self.node[i]!.edge = nil;
						while (edge != nil)
						{
							auxiliary = edge;
							indegree[edge!.id] = indegree[edge!.id]-1;
							edge = edge!.next;
							//  remove edge
							auxiliary = nil;
						}
						indegree[i] = 0;
						status = true;
					}
					i += 1;
				}
			}
			//   Edge are connect both direction
			//   for example a---> b and b--->a
			//   remove edges which is less than k
			i = 0;
			while (i < self.size)
			{
				edge = self.node[i]!.edge;
				auxiliary = nil;
				while (edge != nil)
				{
					if (indegree[edge!.id] <= 0)
					{
						if (self.node[i]!.edge === edge)
						{
							//  delete first edge
							self.node[i]!.edge = edge!.next;
						}
						else
						{
							auxiliary!.next = edge!.next;
						}
					
						edge = edge!.next;
						
					}
					else
					{
						auxiliary = edge;
						//   visit to next edge
						edge = edge!.next;
					}
				}
				i += 1;
			}
			print(terminator: "\n");
		}
	}
}
func main()
{
	//   10 is number of nodes
	let graph: MyGraph = MyGraph(10);
	//  Connected two node with Edges
	graph.addEdge(0, 1);
	graph.addEdge(0, 4);
	graph.addEdge(0, 7);
	graph.addEdge(1, 2);
	graph.addEdge(1, 4);
	graph.addEdge(1, 6);
	graph.addEdge(2, 3);
	graph.addEdge(2, 4);
	graph.addEdge(3, 4);
	graph.addEdge(3, 5);
	graph.addEdge(3, 6);
	graph.addEdge(4, 5);
	graph.addEdge(5, 6);
	graph.addEdge(5, 7);
	graph.addEdge(5, 8);
	graph.addEdge(6, 9);
	graph.addEdge(7, 8);
	graph.addEdge(8, 9);
	graph.printGraph();
	let k: Int = 3;
	graph.kCores(k);
	print("\n After remove ", k ," Cores");
	graph.printGraph();
}
main();

Output

 Adjacency list of vertex  0  :   1   4   7
 Adjacency list of vertex  1  :   0   2   4   6
 Adjacency list of vertex  2  :   1   3   4
 Adjacency list of vertex  3  :   2   4   5   6
 Adjacency list of vertex  4  :   0   1   2   3   5
 Adjacency list of vertex  5  :   3   4   6   7   8
 Adjacency list of vertex  6  :   1   3   5   9
 Adjacency list of vertex  7  :   0   5   8
 Adjacency list of vertex  8  :   5   7   9
 Adjacency list of vertex  9  :   6   8

 After remove  3  Cores

 Adjacency list of vertex  0  :
 Adjacency list of vertex  1  :   2   4   6
 Adjacency list of vertex  2  :   1   3   4
 Adjacency list of vertex  3  :   2   4   5   6
 Adjacency list of vertex  4  :   1   2   3   5
 Adjacency list of vertex  5  :   3   4   6
 Adjacency list of vertex  6  :   1   3   5
 Adjacency list of vertex  7  :
 Adjacency list of vertex  8  :
 Adjacency list of vertex  9  :
/* 
  Kotlin Program
  Find k-cores of an undirected graph
*/
//   Define edge of graph node
class AjlistNode
{
    var id: Int;
    var next: AjlistNode ? ;
    constructor(id: Int)
    {
        this.id = id;
        this.next = null;
    }
}
//   Define node of graph
class GraphNode
{
    var data: Int;
    var edge: AjlistNode ? ;
    constructor(data: Int)
    {
        this.data = data;
        this.edge = null;
    }
}
//   Define structure of graph
class MyGraph
{
    var size: Int;
    var node: Array<GraphNode?>;
    constructor(size: Int)
    {
        if (size<0)
        {
            print("\n Invalid size of nodes " + size + " \n");
            this.size = 0;
            this.node = Array(1)
            {
                null
            };
        }
        else
        {
            this.size = size;
            this.node = Array(this.size)
            {
                null
            };
            var i: Int = 0;
            //   Set graph node level and e
            while (i<this.size)
            {
                this.node[i] = GraphNode(i);
                i += 1;
            }
        }
    }
    //  This function are connect nodes with one edge
    fun connectEdge(a: Int, b: Int): Unit
    {
        if (this.size <= 0)
        {
            print("\n Graph have no nodes \n");
            return;
        }
        //   Create Adjacency node
        var newEdge: AjlistNode ? = AjlistNode(b);
        if (newEdge != null)
        {
            //   Get first edge of [i] node
            var edge: AjlistNode? = this.node[a]?.edge;
            if (edge == null)
            {
                //   Whe no edge of graph node [i] then
                //   Add a first edge of a [i] node
                this.node[a]?.edge = newEdge;
            }
            else
            {
                //  Find last location to add new edge
                while (edge?.next != null)
                {
                    edge = edge.next;
                }
                //   Add edge at last position
                edge?.next = newEdge;
            }
        }
        else
        {
            print("\nMemory overflow, when connect a new edge from ( " + a + " to " + b + " ) nodes.\n");
        }
    }
    //   This is handles the request of connecting Edges between given node a to b
    fun addEdge(a: Int, b: Int): Unit
    {
        if (this.size>0 && a<this.size && b<this.size)
        {
            //   connect edge
            //   a---->b
            this.connectEdge(a, b);
            //  self loop
            if (a == b)
            {
                return;
            }
            //   connect edge
            //   a <---- b
            this.connectEdge(b, a);
        }
        else
        {
            //  not valid Vertices
            print("Invalid Node Vertices " + a + " " + b);
        }
    }
    //  Display Adjacency list of vertex
    fun printGraph(): Unit
    {
        if (this.size>0)
        {
            var temp: AjlistNode? ;
            //   Loop controlling variable
            var i: Int = 0;
            while (i < this.size)
            {
                print("\n Adjacency list of vertex " + i + " :");
                //   Get first edge of [i] node
                temp = this.node[i]?.edge;
                while (temp != null)
                {
                    //  temp->id is graph node vertices
                    //  in this case temp->id is same as
                    //  node[temp->id].data
                    print("  " + this.node[temp.id]?.data);
                    temp = temp.next;
                }
                i += 1;
            }
        }
        else
        {
            print("Empty Graph Node");
        }
    }
    //  This is an undirected graph so indegree will be equal to outdegree
    //  Find indegree of each nodes of a given graph
    fun findDegree(indegree: Array<Int>): Unit
    {
        if (this.size <= 0)
        {
            return;
        }
        var temp: AjlistNode? ;
        //   Loop controlling variable
        var i: Int = 0;
        //  Find the  incoming edges of each node
        while (i < this.size)
        {
            //   Get first edge of i node in given graph
            temp = this.node[i]?.edge;
            while (temp != null)
            {
                indegree[temp.id] += 1;
                //   visit to next edge
                temp = temp.next;
            }
            i += 1;
        }
    }
    //   This is removing connection of node which is less than k edges
    fun kCores(k: Int): Unit
    {
        if (k <= 0 || this.size <= 0)
        {
            print("\nGraph is empty or " + k + " core Not valid\n");
        }
        else
        {
            var indegree: Array<Int> = Array(this.size)
            {
                0
            };
            //   Loop controlling variable
            var i: Int ;
            this.findDegree(indegree);
            var edge: AjlistNode ? ;
            
            var auxiliary: AjlistNode ? = null;
            var status: Boolean = true;
            while (status == true)
            {
                status = false;
                i = 0;
                while (i < this.size)
                {
                    if (indegree[i] > 0 && indegree[i] < k)
                    {
                        edge = this.node[i]?.edge;
                        this.node[i]?.edge = null;
                        while (edge != null)
                        {
                           
                            indegree[edge.id] -= 1;
                            edge = edge.next;
                           
                        }
                        indegree[i] = 0;
                        status = true;
                    }
                    i += 1;
                }
            }
            //   Edge are connect both direction
            //   for example a---> b and b--->a
            //   remove edges which is less than k
            i = 0;
            while (i<this.size)
            {
                edge = this.node[i]?.edge;
             
                while (edge != null)
                {
                    if (indegree[edge.id] <= 0)
                    {
                        if (this.node[i]?.edge == edge)
                        {
                            //  delete first edge
                            this.node[i]?.edge = edge.next;
                        }
                        else
                        {
                            auxiliary?.next = edge.next;
                        }
                
                        edge = edge.next;
                       
                    }
                    else
                    {
                        auxiliary = edge;
                        //   visit to next edge
                        edge = edge.next;
                    }
                }
                auxiliary = null;
                i += 1;
            }
            print("\n");
        }
    }
}
fun main(args: Array<String>): Unit
{
    //   10 is number of nodes
    var graph: MyGraph = MyGraph(10);
    //  Connected two node with Edges
    graph.addEdge(0, 1);
    graph.addEdge(0, 4);
    graph.addEdge(0, 7);
    graph.addEdge(1, 2);
    graph.addEdge(1, 4);
    graph.addEdge(1, 6);
    graph.addEdge(2, 3);
    graph.addEdge(2, 4);
    graph.addEdge(3, 4);
    graph.addEdge(3, 5);
    graph.addEdge(3, 6);
    graph.addEdge(4, 5);
    graph.addEdge(5, 6);
    graph.addEdge(5, 7);
    graph.addEdge(5, 8);
    graph.addEdge(6, 9);
    graph.addEdge(7, 8);
    graph.addEdge(8, 9);
    graph.printGraph();
    var k: Int = 3;
    graph.kCores(k);
    print("\n After remove " + k + " Cores\n");
    graph.printGraph();
}

Output

 Adjacency list of vertex 0 :  1  4  7
 Adjacency list of vertex 1 :  0  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  0  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6  7  8
 Adjacency list of vertex 6 :  1  3  5  9
 Adjacency list of vertex 7 :  0  5  8
 Adjacency list of vertex 8 :  5  7  9
 Adjacency list of vertex 9 :  6  8

 After remove 3 Cores

 Adjacency list of vertex 0 :
 Adjacency list of vertex 1 :  2  4  6
 Adjacency list of vertex 2 :  1  3  4
 Adjacency list of vertex 3 :  2  4  5  6
 Adjacency list of vertex 4 :  1  2  3  5
 Adjacency list of vertex 5 :  3  4  6
 Adjacency list of vertex 6 :  1  3  5
 Adjacency list of vertex 7 :
 Adjacency list of vertex 8 :
 Adjacency list of vertex 9 :

Output Explanation

The output shows the adjacency list of the graph before and after the k-cores removal process. Vertices with degrees less than k are removed, and their incident edges are eliminated. This reveals the subgraph that forms the k-core of the original graph.

Time Complexity

The time complexity of the k-cores algorithm depends on the number of vertices and edges in the graph. Since each vertex and edge is examined at most once, the time complexity is O(V + E), where V is the number of vertices and E is the number of edges.

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







Saumya     453 Day ago
what is its time complexity?