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
- Initialize the
indegree
array with zeros, where each index represents a vertex. - Use the
find_degree
function to populate theindegree
array with the number of edges incident on each vertex. - Set
status
as true to track changes. - 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. Updatestatus
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.
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