Module org.jgrapht.core
Package org.jgrapht.alg.scoring

Class Coreness<V,E>

java.lang.Object
org.jgrapht.alg.scoring.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 Details

    • Coreness

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

  • Method Details

    • getScores

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

    • getVertexScore

      public Integer getVertexScore(V v)
      Get a vertex score
      Specified by:
      getVertexScore in interface VertexScoringAlgorithm<V,E>
      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