V
- the graph vertex typeE
- the graph edge typepublic final class Coreness<V,E> extends Object implements VertexScoringAlgorithm<V,Integer>
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
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
|
public Map<V,Integer> getScores()
getScores
in interface VertexScoringAlgorithm<V,Integer>
public Integer getVertexScore(V v)
getVertexScore
in interface VertexScoringAlgorithm<V,Integer>
v
- the vertexpublic int getDegeneracy()
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.
Copyright © 2018. All rights reserved.