Package 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,​java.lang.Integer>
    public final class Coreness<V,​E>
extends java.lang.Object
implements VertexScoringAlgorithm<V,​java.lang.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 Description
      Coreness​(Graph<V,​E> g)
      Constructor

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int getDegeneracy()
      Compute the degeneracy of a graph.
      java.util.Map<V,​java.lang.Integer> getScores()
      Get a map with the scores of all vertices
      java.lang.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 java.util.Map<V,​java.lang.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 java.lang.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