CODEWITHSUNDEEP
scala
user1853235
user1853235

Reputation: 313

Scala - Map join values to keys?

I have the following map with target node "E":

val map = Map("A" -> "B", "A" -> "C", "C" -> "D", "C" -> "E")

It describe a directed node graph, which looks like:

  
  A
 / \
 B  C
   / \     
  D   E

I need to enter the graph at any point and generate a route to the target node. 

Example 1: Enter at A -> Route: A->C->E
Example 2: Enter at D -> Route: D->C->E
Example 3: Enter at B -> Route: B->A->C->E

Does anyone know of a compact algo which could do this as this must have been attempted before.

Look forward to hearing from you.

Cheers,

Jez

Upvotes: 0

Views: 582

Answers (2)

Nan Jiang
Nan Jiang

Reputation: 1314

As relatively new to Scala, I take this problem as a good exercise for myself and would like to share my solution with all of you. Any comments are welcomed!

BTW, the solution given by @Eastsun is a depth-first search which "memorizes" visited nodes in each path, while mine is a breadth-first search where memorization is not required (though you can definitely add this feature to improve efficiency). For trees they yield the same answer but for general graphs they can differ.

The neighbors of each node can also be cached for optimization.

val graph = Vector(("A","B"), ("A","C"), ("C","D"), ("C","E"))
def adjacent(a: String) = {
  graph flatMap {
    case (`a`, x) => Some(x)
    case (x, `a`) => Some(x)
    case _ => None
  }
}
def go(from: String, to: String) {
  def expand(paths: Vector[Vector[String]]) {
    paths.find(_.last==to) match {
      case Some(x) => println(x); return
      case None => expand(paths flatMap { e => 
        adjacent(e.last) map (e :+ _) 
      })
    }
  }
  expand(Vector(Vector(from)))
}
// tests
go("A","E")  // Vector(A, C, E)
go("B","E")  // Vector(B, A, C, E)
go("D","E")  // Vector(D, C, E)

Version with memorization: change

adjacent(e.last) map (e :+ _)

to

adjacent(e.last) filterNot (x => paths.flatten contains x) map (e :+ _)

or put this functionality in the adjacent function.

Upvotes: 1

Eastsun
Eastsun

Reputation: 18859

So, here is it:

  val map = List("A" -> "B", "A" -> "C", "C" -> "D", "C" -> "E")

  def pathOf(tree: Iterable[(String,String)],from: String,to: String, path: List[String] = Nil): List[String] = {
    if(from == to) return to::path
    tree.filterNot{ case(a,b) => path.contains(a)||path.contains(b) }
    .collect{
      case (a,b) if a == to => b
      case (a,b) if b == to => a
    }.map{ x => pathOf(tree,from,x,to::path) }
    .find{ _.nonEmpty }
    .getOrElse(Nil)
  }

Use case:

scala>  pathOf(map,"B","E").mkString("->")
res1: String = B->A->C->E

scala>  pathOf(map,"C","E").mkString("->")
res2: String = C->E

Upvotes: 2

Related Questions