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 📥

SchematicCoupledSimilarity.scala 1.23 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
package de.bbisping.coupledsim.algo.cs

import de.bbisping.coupledsim.util.Relation
import de.bbisping.coupledsim.ts.WeakTransitionSystem

/**
 * Simplest coupled similarity algorithm based on schematic similarity from [RT2010]
 * */

class SchematicCoupledSimilarity[S, A, L] (
    val ts: WeakTransitionSystem[S, A, L]) {
  
  def compute() = {
    val initialCandidates = for {
      s1 <- ts.nodes
      s2 <- ts.nodes
      if ts.weakEnabled(s1) subsetOf ts.weakEnabled(s2)
    } yield (s1, s2)
    
    var sim = new Relation[S](initialCandidates)
    
    while ({
      val delCand = sim.rep collect {
        case (u, ww) => ww collect {
          case w if
            // enforce simulation
            (ts.post(u).exists {
            case (a, vv) => vv.exists { v =>
              val vsim = sim.values(v)
              ! ( ts.weakPost(w, a) exists (vsim contains _) )
            }
          }) || 
            // enforce coupling
            !ts.silentReachable(w).exists { w1 => sim(w1, u) }
          => (u, w)
        }
      } flatten
      
      if (delCand.isEmpty) {
        false
      } else {
        val dcs = delCand.toSet
        sim = sim.filter((s1, s2) => !dcs.contains(s1, s2))
        true
      }
    }) {}
    
    sim
  }
}