# Find k-cores of an undirected graph

Here given code implementation process.

``````// 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;
}
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);
}
}
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

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;
}
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);
}
}
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.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;
}
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
{
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.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;
}
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.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;
}
\$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
{
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->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;
}
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
{
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.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

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
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.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_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_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_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

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
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.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;
}
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.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;
}
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.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;
}
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.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 :``````

## 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.