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 📥

LabeledRelation.scala 3.97 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 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144
package de.bbisping.coupledsim.util

import scala.collection.immutable.Map
import scala.collection.immutable.Set
import scalaz.Scalaz._

/**
 * Represent E×L×E relations using curried Maps
 */
class LabeledRelation[E, L](val rep: Map[E, Map[L, Set[E]]]) {
 
  /*{(1,1,3), {1,1,1}} ~> {(1 |-> 1 |-> {1,3})}*/
  def this(tuples: Set[(E, L ,E)]) {
    this(tuples.groupBy(_._1).mapValues(_.groupBy(_._2).mapValues(_.map(_._3))))
  }
  
  def size = rep.values.map(_.values.map(_.size).sum).sum
  
  def apply(e1: E, l: L, e2: E) = {
    rep.getOrElse(e1, Map()).getOrElse(l, Set())(e2)
  }
  
  def apply(e1le2: (E, L, E)) = e1le2 match {
    case (e1, l, e2) =>
      rep.getOrElse(e1, Map()).getOrElse(l, Set())(e2)
  }
  
  /**
   * for e1 returns the set containing all the e2 such that R(e1, l, e2)
   */
  def values(e1: E, l: L) = {
    rep.getOrElse(e1, Map()).getOrElse(l, Set())
  }
  
  /**
   * for e2 returns the set containing all the e1 such that e1 R e2
   */
  def valuesInverse(e2: E, l: L) = {
    inverseRep.getOrElse(e2, Map()).getOrElse(l, Set())
  }
  
  def +(e1: E, l: L, e2: E) = {
    val mapE1 = rep.getOrElse(e1, Map())
    val setL = mapE1.getOrElse(l, Set())
    val newRep = rep.updated(e1, mapE1.updated(l, setL + e2))
    
    new LabeledRelation(newRep)
  }
  
  /*{(1 |-> 1 |-> {1,2})} ~> {(1,1,2), {1,1,1}} */
  lazy val tupleSet: Set[(E,L,E)] = {
    for {
      (e1, lee2) <- rep
      (l, ee2) <- lee2
      e2 <- ee2
    } yield (e1, l, e2)
  }.toSet
  
  lazy val inverseRep = {
    val invTuples = tupleSet.map { case (e1, l, e2) => (e2, l, e1) }
    invTuples.groupBy(_._1).mapValues(_.groupBy(_._2).mapValues(_.map(_._3)))
  }
  
  lazy val lhs = rep.keySet
  lazy val labels = rep.values.flatMap(_.keySet)
  lazy val rhs = rep.values.flatMap(_.values).flatten.toSet

  def merge(other: LabeledRelation[E, L]) =
    new LabeledRelation(tupleSet ++ other.tupleSet)
  
  def remove(other: LabeledRelation[E, L]) =
    new LabeledRelation(tupleSet.filterNot(other(_)))
  
  def filter(f: (E, L, E) => Boolean) =
    new LabeledRelation(tupleSet.filter { case (e1, l, e2) => f(e1, l, e2) })
  
  def toRelation = 
    new Relation(tupleSet map { case (e1, l, e2) => (e1, e2) })
  
/*  def removeKeys(toRemove: Set[E]) = {
    new Relation(tupleSet.filterNot {
      case  (l, r) => (toRemove contains l) || (toRemove contains r)
    })
  }*/
  /*
  def transitiveClosure = {
    val comp = FixedPoint[Map[E,Set[E]]](
        {rel => rel.mapValues{
          r => r ++ r.flatMap(rel.getOrElse(_, Set()))}},
        {case (a,b) => a == b})
    
    new Relation(comp(rep))
  }*/
  
  def isTransitive = rep.forall {
    case (e1,lee2) => lee2 forall {
      case (l, ee2) =>
        ee2.flatMap(values(_, l)).forall { e3 =>
          apply(e1, l, e3)
        }
    }
  }
  
  def symmetricClosure = {
    new LabeledRelation(tupleSet ++ tupleSet.map { case (e1, l, e2) => (e2, l, e1) })
  }
  
  def isSymmetric = tupleSet.forall {
    case (e1, l, e2) => tupleSet contains (e2, l, e1)
  }
  
  def isReflexiveSomewhere = tupleSet.exists{case (e1, _, e2) => e1 == e2}
  
  def toGraphString() = {
    val list = (lhs ++ rhs).toIndexedSeq
    val idFor = list.indices.map(i => (list(i), i)).toMap
    tupleSet.map { case (e1, l, e2) =>
      val label = l.toString()
      idFor(e1) + "->" + idFor(e2) + (if (label != "") "[label=\"" + label + "\"]" else "")
    }.mkString("digraph rel{\n  ", ";\n  ", "}")
  }
  
  def toCsvString() = {
    val list = (lhs ++ rhs).toIndexedSeq
    val idFor = list.indices.map(i => (list(i), i)).toMap
    tupleSet.map { case (e1, l, e2) =>
      val label = l.toString()
      idFor(e1) + "," + idFor(e2) + "," + label
    }.mkString("", "\n", "")
  }
  
  override def toString = tupleSet.mkString("{", ",", "}")
  
  override def equals(that: Any) = that match {
    case t: LabeledRelation[E, L] => rep == t.rep
    case _ => false
  }
  
  override def hashCode = rep.hashCode
}

object LabeledRelation {
  def apply[E, L](tuples: (E,L,E)*) = new LabeledRelation[E,L](tuples.toSet)
}