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 📥

GameDiscovery.scala 1.43 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
package de.bbisping.coupledsim.game

/**
 * this function can add a `predecessors`-function to a game that is only specified
 * in terms of some given nodes and the `successors`-function. it also adds a map for the
 * number of successors for discovered nodes `successorNum`.
 */
trait GameDiscovery {
  self: SimpleGame =>
  
  /** which nodes to start the discovery in. */
  def initialNodes: Iterable[GameNode]
  
  /** part of the game that can be reached from the initial nodes starting in the `initialNodes`. (warning: mutable!) */
  val discovered = collection.mutable.Set[GameNode]()
  
  /** number of successor states of discovered states (warning: mutable!) */
  val successorNum = collection.mutable.Map[GameNode, Int]() withDefaultValue 0
  
  override def predecessors(gn: GameNode): Iterable[GameNode] = computedPredecessors(gn)
  
  private val computedPredecessors = collection.mutable.Map[GameNode, Set[GameNode]]() withDefaultValue Set()
  
  // discover relevant game nodes and count outgoing transitions
  
  private val todo = new collection.mutable.Queue[GameNode]()
  todo ++= initialNodes
  discovered ++= initialNodes
  
  while (todo.nonEmpty) {
    val currNode = todo.dequeue()
    val succs = successors(currNode)
    successorNum(currNode) = succs.size
    for {
      gn <- succs
    } {
      computedPredecessors(gn) += currNode
      if (!(discovered contains gn)) {
        discovered += gn
        todo += gn
      }
    }
  }
}