Walk through possible paths within a simple bidirectional graph with potentially revisitable vertex / published by https://github.com/dacr/code-examples-manager #492a2aa4-4413-44d6-9f96-5cf8687d43dc/7db01c40802f016920b492a062c1f91963f43d10

algo-graph-paths.sc

// summary : Walk through possible paths within a simple bidirectional graph with potentially revisitable vertex
// keywords : scala, algorithm, scalatest, graph, @testable
// publish : gist
// authors : David Crosson
// id : 492a2aa4-4413-44d6-9f96-5cf8687d43dc
// created-on : 2021-12-12T10:02:14+01:00
// managed-by : https://github.com/dacr/code-examples-manager
// license : Apache NON-AI License Version 2.0 (https://raw.githubusercontent.com/non-ai-licenses/non-ai-licenses/main/NON-AI-APACHE2)
// run-with : scala-cli $file

// ---------------------
//> using scala "3.4.2"
//> using dep "org.scalatest::scalatest:3.2.18"
//> using objectWrapper
// ---------------------

import org.scalatest.*
import flatspec.AnyFlatSpec
import matchers.should.Matchers

import scala.annotation.tailrec

// inspired from : https://github.com/dacr/advent-of-code-2021/blob/master/src/test/scala/day12/Puzzle.scala

// ------------------------------------------------------------------------------------------------

case class Vertex[A](id: A):
  override def toString() = id.toString

case class Edge[A](from: Vertex[A], to: Vertex[A]):
  override def toString() = s"$from-$to"

type Graph[A] = Map[Vertex[A], List[Vertex[A]]]
type Path[A] = List[Edge[A]]

def edgesToBiDirGraph[A](edges: List[Edge[A]]): Graph[A] =
  (edges ++ edges.map(edge => Edge(edge.to, edge.from)))
    .groupBy(_.from)
    .view
    .mapValues(_.map(_.to))
    .toMap

// ------------------------------------------------------------------------------------------------

// simple implementation which is using the stack, so take care ! NOT TAILREC, SEE NEXT implementation below...
def paths[A](graph: Graph[A], from: Vertex[A], to: Vertex[A], revisitable: Vertex[A] => Boolean):List[Path[A]] =
  def walk(current: Vertex[A], path: List[Edge[A]], visited: Set[Vertex[A]]): List[Path[A]] =
    if current == to then path :: Nil
    else
      val children   = graph(current).filterNot(_ == current).filterNot(visited)
      val newVisited = visited ++ Option(current).filter(revisitable)
      children.flatMap(child => walk(child, Edge(current, child) :: path, newVisited))
  walk(from, Nil, Set.empty)


case class PartialPath[A](
  current:Path[A],
  visited:Set[Vertex[A]]
)
def tailRecPaths[A](graph: Graph[A], from: Vertex[A], to: Vertex[A], revisitable: Vertex[A] => Boolean):List[Path[A]] =
  @tailrec
  def walk(partialPaths:List[PartialPath[A]], foundPaths:List[Path[A]]): List[Path[A]] =
    partialPaths match {
      case Nil => foundPaths
      case PartialPath(currentPartialPath, visited)::remainingPartialPaths =>
        currentPartialPath match {
          case Edge(currentFrom,currentTo)::path if currentTo == to =>
            walk(remainingPartialPaths, currentPartialPath::foundPaths)
          case Edge(currentFrom,currentTo)::path =>
            val children   = graph(currentTo).filterNot(_ == currentTo).filterNot(visited)
            val newVisited = visited ++ Option(currentTo).filter(revisitable)
            val newPartialPaths = children.map(child =>
              PartialPath(Edge(currentTo,child)::currentPartialPath, newVisited)
            )
            walk(newPartialPaths ++ remainingPartialPaths, foundPaths)
        }
    }
  val bootpaths = graph(from).map(to => PartialPath(Edge(from, to)::Nil, Set(from)))
  walk(bootpaths, Nil)

// ------------------------------------------------------------------------------------------------

def parseEdge(vertexSeparator: String)(input: String): Edge[String] =
  input.split("-", 2) match
    case Array(a, b) => Edge(Vertex(a), Vertex(b))

def parseEdges(input: String, vertexSeparator:String="-"): List[Edge[String]] =
  input
    .split("\n")
    .map(parseEdge(vertexSeparator))
    .toList

// ------------------------------------------------------------------------------------------------

class TestThat extends AnyFlatSpec with Matchers {
  override def suiteName: String = "TestGraphPaths"

  "recursive paths finder" should "return the right distinct paths" in {
    val edgesSpec =
      """fs-end
        |he-DX
        |fs-he
        |start-DX
        |pj-DX
        |end-zg
        |zg-sl
        |zg-pj
        |pj-he
        |RW-he
        |fs-DX
        |pj-RW
        |zg-RW
        |start-pj
        |he-WI
        |zg-he
        |pj-fs
        |start-RW""".stripMargin
    val graph = edgesToBiDirGraph(parseEdges(edgesSpec))
    val revisitable = (vertex:Vertex[String]) => vertex.id.forall(_.isLower)

    paths(graph, Vertex("start"), Vertex("end"), revisitable).distinct.size shouldBe 226
    tailRecPaths(graph, Vertex("start"), Vertex("end"), revisitable).distinct.size shouldBe 226
  }

}

org.scalatest.tools.Runner.main(Array("-oDF", "-s", classOf[TestThat].getName))