Package org.graph4j.coloring

Class Coloring

java.lang.Object
org.graph4j.coloring.Coloring
public class Coloring extends Object
A coloring of the vertices of a graph. Coloring algorithms will usually produce as solution an object of this type.
Author:
Cristian Frăsinaru
See Also:

  • Field Details

    • graph

      protected final Graph graph

    • vertexColor

      protected final int[] vertexColor

    • numColoredVertices

      protected int numColoredVertices

    • usedColors

      protected BitSet usedColors

    • colorMap

      protected Map<Integer,VertexSet> colorMap

  • Constructor Details

    • Coloring

      public Coloring(Graph graph)
      Creates an empty coloring - no vertex has a color assigned to it.
      Parameters:
      graph - the input graph.

    • Coloring

      public Coloring(Graph graph, Coloring other)
      Parameters:
      graph - the input graph.
      other - a vertex coloring.

    • Coloring

      public Coloring(Graph graph, int[] colors)
      Creates a vertex coloring using the colors in the given array: the color of the vertex with index i in the graph is colors[i].
      Parameters:
      graph - the input graph.
      colors - an array of color numbers.

    • Coloring

      public Coloring(Graph graph, List<VertexSet> colorClasses)
      Creates a vertex coloring using the specified color classes: all the vertices in the i-th set of the colorClasses list are assigned color i.
      Parameters:
      graph - the input graph.
      colorClasses - the already computed color classes.

  • Method Details

    • getGraph

      public Graph getGraph()
      Returns:
      the graph on which this coloring is defined.

    • isColorSet

      public boolean isColorSet(int v)
      Returns true if a color has been set for a vertex v.
      Parameters:
      v - a vertex number.
      Returns:
      true if a color has been set for the vertex v.

    • isColorUsed

      public boolean isColorUsed(int color)
      Returns true if the given color has been used for some vertex.
      Parameters:
      color - a color number.
      Returns:
      true if the color has been used for some vertex.

    • setColor

      public final void setColor(int v, int color)
      Assigns a color to the specified vertex.
      Parameters:
      v - a vertex number.
      color - the color to be set, or -1 to uncolor the specified vertex.

    • getColors

      public int[] getColors()
      Returns an array containing the colors of the vertices.
      Returns:
      an array containing the colors of the vertices.

    • getColor

      public int getColor(int v)
      Returns the color assigned to a vertex v, or -1 if no color has been set.
      Parameters:
      v - a vertex number;
      Returns:
      the color assigned to v, or -1 if no color has been set.

    • getColorClasses

      public Map<Integer,VertexSet> getColorClasses()
      Creates and returns the color classes. It is executed in a lazy fashion: if the color classes are already created, it only returns them. If the coloring changes, the color classes are computed again.
      Returns:
      the color classes.

    • numUsedColors

      public int numUsedColors()
      Return the number of used colors.
      Returns:
      the number of used colors.

    • numColoredVertices

      public int numColoredVertices()
      Returns the number of vertices which have been assigned a color.
      Returns:
      the number of colored vertices.

    • numColoredVertices

      public int numColoredVertices(int color)
      Parameters:
      color - a color.
      Returns:
      the number of vertices colored with color.

    • isEmpty

      public boolean isEmpty()
      Returns true if no vertex has been colored.
      Returns:
      true if no vertex has been colored.

    • isComplete

      public boolean isComplete()
      Returns true if all the vertices have been colored.
      Returns:
      true if all the vertices have been colored.

    • isProper

      public boolean isProper()
      A proper coloring is an assignment of colors to the vertices of a graph so that no two adjacent vertices have the same color.
      Returns:
      true if the coloring is proper.

    • isEquitable

      public boolean isEquitable()
      Returns:
      true if the coloring is equitable.

    • checkProper

      public void checkProper()
      If the coloring is not proper, it throws an exception.

    • checkEquitable

      public void checkEquitable()
      If the coloring is not equitable, it throws an exception.

    • getColoredVertices

      public VertexSet getColoredVertices()
      Returns:
      the set of the colored vertices.

    • getUncoloredVertices

      public VertexSet getUncoloredVertices()
      Returns:
      the set of the vertices that do not have a color.

    • getColorsUsedBy

      public Set<Integer> getColorsUsedBy(VertexSet vertexSet)
      Parameters:
      vertexSet - a set of vertices.
      Returns:
      the distinct colors used by the given vertices.

    • getColorsUsedBy

      public Set<Integer> getColorsUsedBy(int[] vertices)
      Parameters:
      vertices - an array of vertices.
      Returns:
      the distinct colors used by the given vertices.

    • maxColorNumber

      public int maxColorNumber()
      Returns:
      the maximum color number that was used.

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • hashCode

      public int hashCode()
      Overrides:
      hashCode in class Object

    • equals

      public boolean equals(Object obj)
      Overrides:
      equals in class Object