Package org.graph4j.coloring

Class ExactColoringBase

java.lang.Object
org.graph4j.SimpleGraphAlgorithm
org.graph4j.coloring.ExactColoringBase
All Implemented Interfaces:
ColoringAlgorithm
Direct Known Subclasses:
BacktrackColoringBase
public abstract class ExactColoringBase extends SimpleGraphAlgorithm implements ColoringAlgorithm
Base class for exact vertex coloring algorithms.
Author:
Cristian Frăsinaru

  • Field Details

    • timeLimit

      protected long timeLimit

    • startTime

      protected long startTime

    • timeExpired

      protected boolean timeExpired

    • initialColoring

      protected Coloring initialColoring

    • components

      protected List<VertexSet> components

    • solutions

      protected Set<Coloring> solutions

    • solutionsLimit

      protected int solutionsLimit

    • outputEnabled

      protected boolean outputEnabled

  • Constructor Details

    • ExactColoringBase

      public ExactColoringBase(Graph graph)

    • ExactColoringBase

      public ExactColoringBase(Graph graph, Coloring initialColoring)
      Parameters:
      graph - the input graph.
      initialColoring - an initial coloring of the vertices.

    • ExactColoringBase

      public ExactColoringBase(Graph graph, long timeLimit)
      Parameters:
      graph - the input graph.
      timeLimit - in milliseconds.

    • ExactColoringBase

      public ExactColoringBase(Graph graph, Coloring coloring, long timeLimit)
      Parameters:
      graph - the input graph.
      coloring - an initial coloring of the vertices.
      timeLimit - in milliseconds.

  • Method Details

    • getInstance

      protected abstract ColoringAlgorithm getInstance(Graph graph, long timeLimit)

    • getMaximalClique

      public Clique getMaximalClique()
      Specified by:
      getMaximalClique in interface ColoringAlgorithm
      Returns:
      a maximal clique of the graph to be colored.

    • 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.

    • findAllColorings

      public Set<Coloring> findAllColorings(int numColors, int solutionsLimit)
      Finding all colorings is suitable for small graphs only.
      Parameters:
      numColors - the maximum number of colors to be used.
      solutionsLimit - a limit on the number of colorings to be found (use 0 in order to find all the colorings).
      Returns:
      all the vertex colorings 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.

    • solveDisconnected

      protected void solveDisconnected(int numColors)

    • solve

      protected abstract void solve(int numColors)

    • isTimeExpired

      public boolean isTimeExpired()
      Returns:
      true if time expired before determining the optimum.

    • checkTime

      protected boolean checkTime()

    • getSolutionsLimit

      public int getSolutionsLimit()
      Returns:
      the solutions limit.

    • isOutputEnabled

      public boolean isOutputEnabled()
      Returns:
      true if the output of the algorithm is enabled.

    • setOutputEnabled

      public void setOutputEnabled(boolean outputEnabled)
      Parameters:
      outputEnabled - if true, the output is enabled.