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 📥

BasicSA.scala 2.84 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
package de.bbisping.coupledsim.algo.rt2010

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

/**
 * Basic similarity algorithm from [RT2010]
 * 
 * @note only considers action labels for now.
 * 
 * */

class BasicSA[S, A, L] (
    val ts: TransitionSystem[S, A, L])
  extends AlgorithmLogging[S, A, L] {
  
  def compute() = {    
    
    val labelColors = {
      val parts = for {
        (_, s) <- ts.nodesByLabel
      } yield s
      Coloring.fromPartition(parts.toSet)
    }
    
    val actionColors =
      Coloring.fromPartition(ts.actions.map(Set(_)).toSet)
    
    // partition relation pair (aka <P,Rel>)
    var partition = labelColors
    var relation = new Relation[Coloring.Color](labelColors.universe map (c => (c,c)))
    
    while ({
      // this is a modification of BasicSA to use a whole signature of splitters
      val oldPartitions = partition.partitions.withDefaultValue(Set())
      val bSplitters = for {
        (colorB, b) <- oldPartitions
        val preB = ts.pre(b)
        val preRelB = ts.pre(relation.values(colorB) flatMap oldPartitions)
        (colorC, c) <- oldPartitions
        val preRelC = (relation.values(colorC) flatMap oldPartitions)
        (a, preBA) <- preB
        if (c exists preBA) &&
           (preRelC exists (!preRelB(a)(_)))
      } yield (a, b, preBA, preRelB(a))
      
      // only use the first splitter for now (in accordance with RT2010)
      for {
        (sA, b, preBSA, sPreRelBSA) <- bSplitters.headOption
      } {
        val pPrev = partition
        val pivot = partition.freshColor() // the splitting procedure will use freshColor as the offset between old and newly added "child" partitions.
        // so c1,c2 in partition.split(...) share a parent iff c1.color = c2.color or Abs(c1.color - c2.color) = pivot.
        partition = partition.split(sPreRelBSA)
        
        val newPartitions =  partition.partitions.withDefaultValue(Set())
        val relUpdate = for {
          (colorC, c) <- newPartitions
        } yield {
          val colorParentC = if (colorC >= pivot) colorC - pivot else colorC
          val relC1 = for {
            (colorD, d) <- newPartitions.toSet
            if d subsetOf (relation.values(colorParentC) flatMap oldPartitions)
          } yield (colorD, d)
          
          if (c exists preBSA) {
            (colorC, (relC1 filter (_._2 subsetOf sPreRelBSA)) map (_._1))
          } else {
            (colorC, relC1 map (_._1))
          }
        }
        relation = (new Relation(relUpdate))
        logRelation(Relation.fromColoringPartitionRelation(partition, relation), "splitter" + bSplitters.head.toString)
      }
      
      bSplitters.nonEmpty
    }) {}
    
    Relation.fromColoringPartitionRelation(partition, relation)
  }
}