CODEWITHSUNDEEP
algorithmscalapath-findingdirected-graphadjacency-list
appcodix
appcodix

Reputation: 342

Adjacency-List Paths in Scala

If I have an adjacency list, represented in Scala like this:

val l = List(
    List((1, 1), (2, 3), (4, 10)),
    List((2, 1)),
    List((3, 1), (4, 5)),
    List(4, 1)),
    List())

Every "List" contains the costs of the path from one node to another in a directed graph. So the first "List" with three entries represents the successors of the first node (counting from 0). That means Node 0 directs to Node 1 with a cost of 1, to Node 2 with a cost of 3 and to Node 4 with a cost of 10 and so on.

How would it be possible to recursively compute if there are paths with a max cost from a given node to another? I thought of something like this: 

def hasMaxCostPath: (List[List[(Int, Int)]], Int, Int, Int) => Int => Boolean = (adj, from, to, max) => len =>

So the function receives the adjacency list "adj", the start node "from", the end node "to", the max cost of the path "max" and the max length of the path "len". So I think the result should be like the following based on the above given adjacency list:

hasMaxCostPath(l, 0, 2, 2)(1) == false
hasMaxCostPath(l, 0, 2, 3)(1) == true

Furthermore how would it be possible to recursively compute a list of all costs of paths that go from one specified node to another within a given max length? Maybe like this:

def getPaths: (List[List[(Int, Int)]], List[(Int, Int)], Int, Int) => List[Int] =
(adj, vn, dest, len) =>

So this function would get the adjacency list "adj", a list of already visited nodes "vn" with (node, cost), in which we take the given node as the start node, the destination node "dest" and the max length of the path "len". And for this function the results could be like the following:

getPaths(l, List((0, 0)), 2, 1) == List(3)     // Node0 -> Node2
getPaths(l, List((0, 0)), 2, 2) == List(2, 3)  // Node0 -> Node1 -> Node2 AND Node0 -> Node2

Sorry, I'm very new to Scala

Upvotes: 2

Views: 290

Answers (1)

user152468
user152468

Reputation: 3242

Does this work for you?

package foo

object Foo {

  def main(args: Array[String]): Unit = {
    val edges = List(
      List((1, 1), (2, 3), (4, 10)),
      List((2, 1)),
      List((3, 1), (4, 5)),
      List((4, 1)),
      List())
    println(hasMaxCostPath(edges,0,1,2))
    println(hasMaxCostPath(edges,0,2,2))
  }

  def hasMaxCostPath(edges: List[List[(Int, Int)]], start: Int, end: Int, maxCost: Int): Boolean = {
    maxCost > 0 &&
    edges(start).exists(a =>
      (a._1 == end && a._2 <= maxCost) ||
      hasMaxCostPath(edges, a._1, end, maxCost - a._2)
    )
  }

}

Edit: ====

The above solution did not take into account the length parameter. Here is a solution with the length parameter: 

package foo

object Foo {

  def main(args: Array[String]): Unit = {
    val edges = List(
      List((1, 1), (2, 3), (4, 10)),
      List((2, 1)),
      List((3, 1), (4, 5)),
      List((4, 1)),
      List())
      assert(! hasMaxCostPath(edges,0,4,4,3))
      assert(hasMaxCostPath(edges,0,4,4,4))
  }

  def hasMaxCostPath(edges: List[List[(Int, Int)]], start: Int, end: Int, maxCost: Int, maxLength: Int): Boolean = {
    maxLength > 0 &&
    maxCost >= 0 &&
    edges(start).exists(a =>
      (a._1 == end && a._2 <= maxCost) ||
      hasMaxCostPath(edges, a._1, end, maxCost - a._2, maxLength - 1)
    )
  }

}

=== Edit:

And here is a solution including your second problem:

package foo

object Foo {

  def main(args: Array[String]): Unit = {
    val edges = List(
      List((1, 1), (2, 3), (4, 10)),
      List((2, 1)),
      List((3, 1), (4, 5)),
      List((4, 1)),
      List())
    assert(! hasMaxCostPath(edges,0,4,4,3))
    assert(hasMaxCostPath(edges,0,4,4,4))
    assert(getMaxCostPaths(edges,0,0,5,5) == List())
    assert(getMaxCostPaths(edges,0,1,1,1) == List(List(0,1)))
    assert(getMaxCostPaths(edges,0,2,2,2) == List(List(0,1,2)))
    assert(getMaxCostPaths(edges,0,2,5,5) == List(List(0,2), List(0,1,2)))
  }

  def hasMaxCostPath(edges: List[List[(Int, Int)]], start: Int, end: Int, maxCost: Int, maxLength: Int): Boolean = {
    maxLength > 0 &&
    maxCost >= 0 &&
    edges(start).exists(a =>
      (a._1 == end && a._2 <= maxCost) ||
      hasMaxCostPath(edges, a._1, end, maxCost - a._2, maxLength - 1)
    )
  }

  def getMaxCostPaths(
         edges: List[List[(Int, Int)]],
         from: Int, to: Int,
         maxCost: Int,
         maxLength: Int): List[List[Int]] = {
      getMaxCostPathsRec(edges, from, to, maxCost, maxLength, List(from))
  }

  def getMaxCostPathsRec(
         edges: List[List[(Int, Int)]],
         start: Int, end: Int,
         maxCost: Int,
         maxLength: Int,
         path: List[Int]) : List[List[Int]] = {
    if (maxLength <= 0 || maxCost < 0) return List()
    val direct = edges(start).filter(a => a._1 == end && a._2 <= maxCost).map(edge => path ::: List(edge._1))
    val transitive = edges(start).flatMap(a =>
      getMaxCostPathsRec(edges, a._1, end, maxCost - a._2, maxLength - 1, path ::: List(a._1))
    )
    direct ::: transitive
  }

}

Upvotes: 1

Related Questions