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 📥

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

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

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

class SchematicSimilarity[S, A, L] (
    val ts: TransitionSystem[S, A, L])
  extends AlgorithmLogging[S, A, L] {
  
  def compute() = {
    val initialCandidates = for {
      s1 <- ts.nodes
      s2 <- ts.nodes
      if ts.enabled(s1) subsetOf ts.enabled(s2)
    } yield (s1, s2)
    
    var sim = new Relation[S](initialCandidates)
    logRelation(sim, "initial candidates")
    
    while ({
      val delCand = sim.rep collect {
        case (u, ww) => ww collect {
          case w if ts.post(u).exists {
            case (a, vv) => vv.exists { v =>
              val vsim = sim.values(v)
              ! ( ts.post(w, a) exists (vsim contains _) )
            }
          } => (u, w)
        }
      } flatten
      
      if (delCand.isEmpty) {
        false
      } else {
        val dcs = delCand.toSet
        sim = sim.filter((s1, s2) => !dcs.contains(s1, s2))
        logRelation(sim, "remove: " + dcs.mkString(", "))
        true
      }
    }) {}
    
    sim
  }
}