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 📥

SignatureRefinement.scala 1.64 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
package de.bbisping.coupledsim.algo.sigref

import de.bbisping.coupledsim.ts.TransitionSystem
import de.bbisping.coupledsim.util.Relation
import de.bbisping.coupledsim.util.Coloring
import de.bbisping.coupledsim.algo.AlgorithmLogging
import de.bbisping.coupledsim.ts.WeakTransitionSystem

/**
 * Abstract signature refinement (bi)similarity algorithm
 * that keeps track of signature subsets!
 * 
 * */

abstract class SignatureRefinement[S, A, L] (
    val ts: WeakTransitionSystem[S, A, L])
  extends AlgorithmLogging[S, A, L] {
  
  val labelColors = {
    val parts = for {
      (_, ss) <- ts.nodesByLabel
    } yield ss
    Coloring.fromPartition(parts.toSet)
  }
  
  val actionColors =
    Coloring.fromPartition(ts.actions.map(Set(_)).toSet)
  
  var partition = labelColors
  
  def signature(s: S): Set[(Coloring.Color, Coloring.Color)]
  
  def computePartition() = {

    var size = 1
    println("start sigref")
    while ({
      
      val signatures = for {
        s <- ts.nodes
        sig = signature(s)
      } yield (sig, s)
      
      val blocks = signatures.groupBy(_._1).mapValues(_.map(_._2))
      
      val colorMap = blocks.keys.zipWithIndex.toMap
      
      val newColoring = for {
        (sig, ss) <- blocks
        s <- ss
      } yield (s, colorMap(sig))
      
      partition = new Coloring(newColoring)
      
      val oldSize = size
      size = colorMap.size
      //logRelation(Relation.fromColoring(partition), "refinement "+size)
      
      println(size)
      
      oldSize != size
    }) {}
    
    println("sigref complete")
    
    partition
  }
  
  def compute() = {
    Relation.fromColoring(computePartition())
  }
}