import collections
import math


def FractionalColorImbalance(graph, solution, alpha):
  """Evaluates the color imbalance of solution.

  Computes the fraction of nodes that are above the threshold for color
  representation.

  Args:
    graph: in nx.Graph format.
    solution: list of clusters.
    alpha: representation constraint.
  Returns:
    the fraction of nodes that are above the threshold for color.
  """
  total_violation = 0
  nodes = 0
  for cluster in solution:
    color_count = collections.defaultdict(int)
    for elem in cluster:
      color_count[graph.nodes[elem]['color']] += 1
    for count in color_count.values():
      imbalance = max(0, count - math.floor(float(len(cluster)) * alpha))
      total_violation += imbalance
    nodes += len(cluster)
  return 1.0 * total_violation / nodes