Package org.graph4j.ordering

Class SmallestDegreeLastOrdering

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.ordering.SmallestDegreeLastOrdering

public class SmallestDegreeLastOrdering
extends GraphAlgorithm

Computes the vertex ordering from the end to the beginning. At each step, the node of minimum degree in the current graph is selected and then it is removed from the graph. So, the first vertex to be selected is the one with the smallest degree in the graph, and it is stored at the end of the ordering. Suppose that the vertices V'={vi+1,..., vn} have been already selected, the next vertex to be chosen is v_i in V-V' such that the degree of v_i in the subgraph induced by the remaining vertices V-V' is minimal.

Author:

Cristian Frăsinaru

See Also:

• VertexOrderings

Field Summary

Fields inherited from class org.graph4j.GraphAlgorithm

directed, graph

Constructor Summary

Constructors

Constructor	Description
SmallestDegreeLastOrdering(Graph graph)

Method Summary

Modifier and Type	Method	Description
int[]	compute()	Computes the smallest-degree-last vertex ordering.

Methods inherited from class org.graph4j.GraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

SmallestDegreeLastOrdering

public SmallestDegreeLastOrdering(Graph graph)

Method Details

compute

public int[] compute()

Computes the smallest-degree-last vertex ordering.

Returns:

the vertex ordering.