This GitLab instance reached the end of its service life. It won't be possible to create new users or projects.

Please read the deprecation notice for more information concerning the deprecation timeline

Visit migration.git.tu-berlin.de (internal network only) to import your old projects to the new GitLab platform 📥

Coloring.scala 2.78 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
package de.bbisping.coupledsim.util

import scala.collection.mutable.HashMap

case class Coloring[E](val colors: Map[E, Coloring.Color] = Map()) {
  
  lazy val universe = colors.values.toSet
  
  lazy val partitions = 
    colors.toSet[(E, Coloring.Color)].groupBy(_._2).mapValues(_.map(_._1))
  
  def freshColor() = universe.max + 1
  
  def apply(e: E) = colors.apply(e)
  
  def partitionFor(e: E) = {
    for {
      color <- colors.get(e)
    } yield {
      for {
        (e, c) <- colors
        if c == color
      } yield e
    }.toSet
  }
  
  def map(f: (E, Coloring.Color) => Coloring.Color) = {
    Coloring(colors map { case (e, c) => (e, f(e, c)) })
  }
  
  def filter(f: E => Boolean) = {
    Coloring(colors.filterKeys(f))
  }
  
  def split(otherPart: Set[E]) = {
    val offSet = freshColor()
    
    val newColors = for {
      (e, c) <- colors
      if (otherPart contains e) 
    } yield (e, offSet + c)
    
    Coloring(colors ++ newColors)
  }
  
  def splitInsertColors[A](other: Iterable[(E, A)])  = {
    // following the sort+partition approach of [BRR2016]
    var colorOffset = freshColor()
    val newColors = new HashMap[E, Coloring.Color]()
    
    val updates = for {
      ((a, ea), i) <- other.groupBy(_._2).zipWithIndex
      (e, _) <- ea
    } {
      newColors(e) = colorOffset + i
    }
    
    Coloring(colors ++ newColors)
//    var currentColorOffset = freshColor()
//    
//    val updates = for {
//      cols <- other.groupBy(_._2).values
//    } yield {
//      val newCols = for ((e, c) <- cols) yield {
//        val newC = c + currentColorOffset
//        (e, newC)
//      }
//      currentColorOffset = newCols.map(_._2).max + 1
//      newCols.toIterable
//    }
//    
//    Coloring(colors ++ updates.flatten)
  }
  
  def representativeFor(e: E)(implicit cmp: Ordering[E]) = {
    partitionFor(e).map(_.max)
  }
  
  /** normalizes the color space to 0..n-1 for n colors, where the color order is the order of the partition representatives*/
  def normalize()(implicit cmp: Ordering[E]) = {
    
    val colorMap = partitions.toList.sortBy(_._2.max).map(_._1).zipWithIndex.toMap
    Coloring(colors.mapValues(colorMap))
  }
  
  /** normalizes the color space to 0..n-1 for n colors, where the color order is the old color order*/
  def normalizeReturnMap() = {
    
    val colorMap = partitions.toList.sortBy(_._1).map(_._1).zipWithIndex.toMap
    (Coloring(colors.mapValues(colorMap)), colorMap)
  }
  
  def toStringPretty()(implicit cmp: Ordering[E]) = {
    colors.toList.sorted.mkString("Coloring { ", ", ", "}" )
  }
  
  def toPartition() = {
    partitions
  }
}

object Coloring {
  
  type Color = Int
  
  def fromPartition[E](sets: Set[Set[E]]) = {
    val c = for {
      (s, idx) <- sets.zipWithIndex
      e <- s
    } yield (e, idx)
    Coloring(c.toMap)
  }
  
}