org.jgrapht.alg.scoring

## Class Coreness<V,E>

• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
VertexScoringAlgorithm<V,Integer>

public final class Coreness<V,E>
extends Object
implements VertexScoringAlgorithm<V,Integer>
Computes the coreness of each vertex in an undirected graph.

A k-core of a graph G is a maximal connected subgraph of G in which all vertices have degree at least k. Equivalently, it is one of the connected components of the subgraph of G formed by repeatedly deleting all vertices of degree less than k. A vertex u has coreness c if it belongs to a c-core but not to any (c+1)-core.

If a non-empty k-core exists, then, clearly, G has degeneracy at least k, and the degeneracy of G is the largest k for which G has a k-core.

As described in the following paper

• D. W. Matula and L. L. Beck. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM, 30(3):417--427, 1983.
it is possible to find a vertex ordering of a finite graph G that optimizes the coloring number of the ordering, in linear time, by using a bucket queue to repeatedly find and remove the vertex of smallest degree.
Author:
Dimitrios Michail
• ### Constructor Summary

Constructors
Constructor and Description
Coreness(Graph<V,E> g)
Constructor
• ### Method Summary

All Methods
Modifier and Type Method and Description
int getDegeneracy()
Compute the degeneracy of a graph.
Map<V,Integer> getScores()
Get a map with the scores of all vertices
Integer getVertexScore(V v)
Get a vertex score
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Constructor Detail

• #### Coreness

public Coreness(Graph<V,E> g)
Constructor
Parameters:
g - the input graph
• ### Method Detail

• #### getScores

public Map<V,Integer> getScores()
Get a map with the scores of all vertices
Specified by:
getScores in interface VertexScoringAlgorithm<V,Integer>
Returns:
a map with all scores
• #### getVertexScore

public Integer getVertexScore(V v)
Get a vertex score
Specified by:
getVertexScore in interface VertexScoringAlgorithm<V,Integer>
Parameters:
v - the vertex
Returns:
the score
• #### getDegeneracy

public int getDegeneracy()
Compute the degeneracy of a graph.

The degeneracy of a graph is the smallest value of k for which it is k-degenerate. In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges.

Returns:
the degeneracy of a graph