Package org.graph4j.coloring

Class GreedyColoringBase

java.lang.Object
org.graph4j.SimpleGraphAlgorithm
org.graph4j.coloring.GreedyColoringBase
All Implemented Interfaces:
ColoringAlgorithm
Direct Known Subclasses:
DSaturGreedyColoring, GreedyColoring
public abstract class GreedyColoringBase extends SimpleGraphAlgorithm implements ColoringAlgorithm
Greedy coloring is a simple heuristic algorithm that assigns colors to the vertices of a graph in a greedy manner, that is, by selecting the smallest possible color that has not yet been used by any of the neighboring vertices. The greedy algorithm does not necessarily produce the optimal vertex coloring, but it can be a useful heuristic in certain cases.
Author:
Cristian Frăsinaru

  • Field Details

    • colors

      protected int[] colors

    • used

      protected BitSet used

    • numColors

      protected int numColors

  • Constructor Details

    • GreedyColoringBase

      public GreedyColoringBase(Graph graph)
      Parameters:
      graph - the input graph.

  • Method Details

    • findColoring

      public Coloring findColoring()
      Description copied from interface: ColoringAlgorithm
      In case of exact algorithms, this method should return the optimum coloring, if one can be computed within the alloted time. Otherwise, in case of heuristics or if the time limit is exceeded, it should return the best valid coloring that could be computed.
      Specified by:
      findColoring in interface ColoringAlgorithm
      Returns:
      a valid coloring of the graph.

    • findColoring

      public Coloring findColoring(int numColors)
      Specified by:
      findColoring in interface ColoringAlgorithm
      Parameters:
      numColors - maximum number of colors to be used.
      Returns:
      a coloring of the graph with the specified number of colors, or null if no coloring can be found by this algorithm.

    • markUsedColor

      protected void markUsedColor(int u, double weight)

    • init

      protected void init()

    • update

      protected void update(int v)

    • hasUncoloredVertices

      protected abstract boolean hasUncoloredVertices()

    • nextUncoloredVertex

      protected abstract int nextUncoloredVertex()