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 📥

SA.scala 3.54 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 115 116 117
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

/**
 *SA similarity algorithm from [RT2010]
 * 
 * this experimental re-implementation presumably is not yet correct. don't use it!
 * 
 * @note only considers action labels for now.
 * 
 * */

class SA[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)))
    
    val initRel = relation
    val initPart = partition
    logRelation(Relation.fromColoringPartitionRelation(initPart, initRel), "intial")
    
    var remove = {
      for {
        b <- partition.universe
        a <- ts.actions
        val preRelBA = ts.pre(relation.values(b) flatMap partition.partitions.withDefaultValue(Set()), a)
      } yield ((b, a), ts.nodes -- preRelBA)
    }.toMap
    
    while ({
      
      val pickedBA = remove.find (_._2.nonEmpty)
      
      for {
        ((colorB, a), removeBA) <- pickedBA
      } {
        remove = remove updated ((colorB, a), Set())
        
        val oldPartitions = partition.partitions.withDefaultValue(Set())
        
        val preBA = ts.pre(oldPartitions(colorB),a)
        
        val pivot = partition.freshColor()
        
        partition = partition.split(removeBA)
        
        val newPartitions =  partition.partitions.withDefaultValue(Set())
        
        val removeUpdate = for {
          (colorC, c) <- newPartitions
          val colorParentC = if (colorC >= pivot) colorC - pivot else colorC
          action <- ts.actions
        } yield ((colorC, action), remove(colorParentC, action))
        remove = removeUpdate
        
        val relUpdate1 = for {
          (colorC, c) <- newPartitions
          val colorParentC = if (colorC >= pivot) colorC - pivot else colorC
        } yield (colorC, {
          for {
            (colorD, d) <- newPartitions.toSet
            if d subsetOf (relation.values(colorParentC) flatMap oldPartitions)
          } yield (colorD)
        })
        relation = new Relation(relUpdate1)
        
        val removeList = (newPartitions filter {case (colorD, d) => d subsetOf removeBA}).toSet
        
        for {
          (colorC, c) <- newPartitions
          if c exists preBA
          (colorD, d) <- removeList
          val relC =  for {
            c <- relation.values(colorC)
          } yield (c,newPartitions(c))
          if relC contains (colorD, d)
        } {
          relation = relation - (colorC, colorD)
          for {
            (action, ss) <- ts.pre(d)
            s <- ss
            if !(ts.pre(relation.values(colorC) flatMap newPartitions, action) contains s)
          } {
            val k = (colorC, action)
            remove = remove updated (k, remove.getOrElse(k, Set()) + s)
          }
        }
      }
      val logRel = relation
      val logPart = partition
      logRelation(Relation.fromColoringPartitionRelation(logPart, logRel), "splitter" + pickedBA.toString)
      
      pickedBA.nonEmpty
    }) {}
    
    Relation.fromColoringPartitionRelation(partition, relation)
  }
}