Scala Graph 循环检测算法“返回”需要吗？

Question

我在 Scala 中实现了 DAG 的小循环检测算法。 “返回”让我烦恼 - 我想要一个没有返回的版本......可能吗？

  def isCyclic() : Boolean = {
    lock.readLock().lock()
    try {
      nodes.foreach(node => node.marker = 1)
      nodes.foreach(node => {if (1 == node.marker && visit(node)) return true})
    } finally {
      lock.readLock().unlock()
    }
    false
  }

  private def visit(node: MyNode): Boolean = {
    node.marker = 3

    val nodeId = node.id
    val children = vertexMap.getChildren(nodeId).toList.map(nodeId => id2nodeMap(nodeId))
    children.foreach(child => {
      if (3 == child.marker || (1 == child.marker && visit(child))) return true
    })

    node.marker = 2

    false
  }

Answer 1

是的，通过使用“.find”而不是“foreach”+“return”：

def isCyclic() : Boolean = {
  def visit(node: MyNode): Boolean = {
      node.marker = 3

      val nodeId = node.id
      val children = vertexMap.getChildren(nodeId).toList.map(nodeId => id2nodeMap(nodeId))
      val found = children.exists(child => (3 == child.marker || (1 == child.marker && visit(child))))

      node.marker = 2

      found
  }

  lock.readLock().lock()
  try {
    nodes.foreach(node => node.marker = 1)
    nodes.exists(node => node.marker && visit(node))
  } finally {
    lock.readLock().unlock()
  }
}

Answer 2

摘要：
我提出了两个解决方案作为通用 FP 函数，它们检测有向图中的循环。根据您隐含的偏好，使用早期返回来转义递归函数已被消除。第一个 isCyclic，只要 DFS（深度优先搜索）重复节点访问就返回一个布尔值。第二个，filterToJustCycles，返回输入Map的副本，过滤到仅涉及任何/所有循环的节点，并返回一个空的Map > 当没有找到循环时。

详细信息：
对于以下内容，请考虑这样编码的有向图：

val directedGraphWithCyclesA: Map[String, Set[String]] =
  Map(
      "A" -> Set("B", "E", "J")
    , "B" -> Set("E", "F")
    , "C" -> Set("I", "G")
    , "D" -> Set("G", "L")
    , "E" -> Set("H")
    , "F" -> Set("G")
    , "G" -> Set("L")
    , "H" -> Set("J", "K")
    , "I" -> Set("K", "L")
    , "J" -> Set("B")
    , "K" -> Set("B")
  )

在下面的两个函数中，类型参数 N 指的是您想要提供的任何“Node”类型。重要的是，提供的“Node”类型既是不可变的，又具有稳定的 equals 和 hashCode 实现（所有这些都通过使用不可变的 case 类自动发生）。

---

第一个函数 isCyclic 本质上与 @the-archetypal-paul 提供的解决方案版本类似。它假设有向图已转换为 Map[N, Set[N]] ，其中 N 是图中节点的标识。

如果您需要了解如何将自定义有向图实现一般性地转换为 Map[N, Set[N]]，我在本答案的末尾概述了一个通用解决方案。

像这样调用 isCyclic 函数：

val isCyclicResult = isCyclic(directedGraphWithCyclesA)

将返回：

`true`

未提供更多信息。当检测到对节点的第一次重复访问时，DFS（深度优先搜索）将中止。

def isCyclic[N](nsByN: Map[N, Set[N]]) : Boolean = {
  def hasCycle(nAndNs: (N, Set[N]), visited: Set[N] = Set[N]()): Boolean =
    if (visited.contains(nAndNs._1))
      true
    else
      nAndNs._2.exists(
        n =>
          nsByN.get(n) match {
            case Some(ns) =>
              hasCycle((n, ns), visited + nAndNs._1)
            case None =>
              false
          }
      )
  nsByN.exists(hasCycle(_))
}

---

第二个函数 filterToJustCycles 使用集合缩减技术递归地过滤掉 Map 中未引用的根节点。如果提供的节点图中没有循环，则返回的 Map 上的 .isEmpty 将为 true。但是，如果存在任何循环，则返回参与任何循环所需的所有节点，并过滤掉所有其他非循环参与节点。

同样，如果您需要了解如何将自定义有向图实现通用地转换为 Map[N, Set[N]]，我在本答案的末尾概述了一个通用解决方案。

像这样调用 filterToJustCycles 函数：

val cycles = filterToJustCycles(directedGraphWithCyclesA)

将返回：

Map(E -> Set(H), J -> Set(B), B -> Set(E), H -> Set(J, K), K -> Set(B))

然后创建一个遍历此 Map 的过程，以生成通过其余节点的任何或所有各种循环路径，这很简单。

def filterToJustCycles[N](nsByN: Map[N, Set[N]]): Map[N, Set[N]] = {
  def recursive(nsByNRemaining: Map[N, Set[N]], referencedRootNs: Set[N] = Set[N]()): Map[N, Set[N]] = {
    val (referencedRootNsNew, nsByNRemainingNew) = {
      val referencedRootNsNewTemp =
        nsByNRemaining.values.flatten.toSet.intersect(nsByNRemaining.keySet)
      (
          referencedRootNsNewTemp
        , nsByNRemaining.collect {
            case (t, ts) if referencedRootNsNewTemp.contains(t) && referencedRootNsNewTemp.intersect(ts.toSet).nonEmpty =>
              (t, referencedRootNsNewTemp.intersect(ts.toSet))
          }
        )
    }
    if (referencedRootNsNew == referencedRootNs)
      nsByNRemainingNew
    else
      recursive(nsByNRemainingNew, referencedRootNsNew)
  }
  recursive(nsByN)
}

---

那么，一般如何将自定义有向图实现转换为 Map[N, Set[N]]？

本质上，“Go Scala 案例类！”

首先，让我们定义一个预先存在的有向图中真实节点的示例：

class CustomNode (
    val equipmentIdAndType: String //"A387.Structure" - identity is embedded in a string and must be parsed out
  , val childrenNodes: List[CustomNode] //even through Set is implied, for whatever reason this implementation used List
  , val otherImplementationNoise: Option[Any] = None
)

同样，这只是一个示例。你的可能涉及子类化、委托等。目的是访问能够获取使这项工作正常进行的两个基本内容的东西：

• 节点的身份；即区分它并使其与同一有向图中的所有其他节点唯一的东西
• 特定节点的直接子节点的身份集合 - 如果特定节点没有任何子节点，则该集合将为空

下一步，我们定义一个辅助对象，DirectedGraph，它将包含转换的基础设施：

• Node：一个适配器特征，它将包装CustomNode
• toMap：一个函数，它将接受List[CustomNode] 并将其转换为 Map[Node, Set[Node]] （其类型相当于我们的 Map[N, Set [N]]）

代码如下：

object DirectedGraph {
  trait Node[S, I] {
    def source: S
    def identity: I
    def children: Set[I]
  }

  def toMap[S, I, N <: Node[S, I]](ss: List[S], transformSToN: S => N): Map[N, Set[N]] = {
    val (ns, nByI) = {
      val iAndNs =
        ss.map(
          s => {
            val n =
              transformSToN(s)
            (n.identity, n)
          }
        )
      (iAndNs.map(_._2), iAndNs.toMap)
    }
    ns.map(n => (n, n.children.map(nByI(_)))).toMap
  }
}

现在，我们必须生成实际的适配器 CustomNodeAdapter，它将包装每个 CustomNode 实例。该适配器以非常具体的方式使用案例类；即指定两个构造函数参数列表。它确保案例类符合 Set 的要求，即 Set 成员具有正确的 equals 和 hashCode 实现。有关为什么以及如何以这种方式使用案例类的更多详细信息，请参阅此 StackOverflow 问题与解答：

object CustomNodeAdapter extends (CustomNode => CustomNodeAdapter) {
  def apply(customNode: CustomNode): CustomNodeAdapter =
    new CustomNodeAdapter(fetchIdentity(customNode))(customNode) {}

  def fetchIdentity(customNode: CustomNode): String =
    fetchIdentity(customNode.equipmentIdAndType)

  def fetchIdentity(eiat: String): String =
    eiat.takeWhile(char => char.isLetter || char.isDigit)
}
abstract case class CustomNodeAdapter(identity: String)(customNode: CustomNode) extends DirectedGraph.Node[CustomNode, String] {
  val children =
    customNode.childrenNodes.map(CustomNodeAdapter.fetchIdentity).toSet
  val source =
    customNode
}

我们现在有基础设施到位。让我们定义一个由 CustomNode 组成的“真实世界”有向图：

val customNodeDirectedGraphWithCyclesA =
  List(
      new CustomNode("A.x", List("B.a", "E.a", "J.a"))
    , new CustomNode("B.x", List("E.b", "F.b"))
    , new CustomNode("C.x", List("I.c", "G.c"))
    , new CustomNode("D.x", List("G.d", "L.d"))
    , new CustomNode("E.x", List("H.e"))
    , new CustomNode("F.x", List("G.f"))
    , new CustomNode("G.x", List("L.g"))
    , new CustomNode("H.x", List("J.h", "K.h"))
    , new CustomNode("I.x", List("K.i", "L.i"))
    , new CustomNode("J.x", List("B.j"))
    , new CustomNode("K.x", List("B.k"))
    , new CustomNode("L.x", Nil)
  )

最后，我们现在可以进行如下所示的转换：

val transformCustomNodeDirectedGraphWithCyclesA =
  DirectedGraph.toMap[CustomNode, String, CustomNodeAdapter](customNodes1, customNode => CustomNodeAdapter(customNode))

并且我们可以采用 transformCustomNodeDirectedGraphWithCyclesA，其类型为Map[CustomNodeAdapter,Set[CustomNodeAdapter]]，并提交给两个原始函数。

调用 isCyclic 函数如下：

val isCyclicResult = isCyclic(transformCustomNodeDirectedGraphWithCyclesA)

将返回：

`true`

调用 filterToJustCycles 函数如下：

val cycles = filterToJustCycles(transformCustomNodeDirectedGraphWithCyclesA)

将返回：

Map(
    CustomNodeAdapter(B) -> Set(CustomNodeAdapter(E))
  , CustomNodeAdapter(E) -> Set(CustomNodeAdapter(H))
  , CustomNodeAdapter(H) -> Set(CustomNodeAdapter(J), CustomNodeAdapter(K))
  , CustomNodeAdapter(J) -> Set(CustomNodeAdapter(B))
  , CustomNodeAdapter(K) -> Set(CustomNodeAdapter(B))
)

如果需要，此 Map 可以是转换回 Map[CustomNode, List[CustomNode]]：

cycles.map {
  case (customNodeAdapter, customNodeAdapterChildren) =>
    (customNodeAdapter.source, customNodeAdapterChildren.toList.map(_.source))
}

---

如果您有任何疑问、问题或疑虑，请告诉我，我会尽快解决。

Answer 3

我认为这个问题可以在不改变带有标记字段的节点的状态的情况下解决。以下是我认为 isCyclic 应该是什么样子的粗略代码。我当前正在存储访问的节点对象，如果节点不具有基于节点 id 的相等性，则您可以存储节点 id。

def isCyclic() : Boolean = nodes.exists(hasCycle(_, HashSet()))

def hasCycle(node:Node, visited:Seq[Node]) = visited.contains(node) || children(node).exists(hasCycle(_,  node +: visited))


def children(node:Node) = vertexMap.getChildren(node.id).toList.map(nodeId => id2nodeMap(nodeId))

Answer 4

添加答案只是为了表明 mutable-visited 也不是太不可读（尽管未经测试！）

def isCyclic() : Boolean =
{
     var visited = HashSet()

     def hasCycle(node:Node) = {
        if (visited.contains(node)) {
           true
        } else {
           visited :+= node
           children(node).exists(hasCycle(_))
        }
    }
    nodes.exists(hasCycle(_))
}

def children(node:Node) = vertexMap.getChildren(node.id).toList.map(nodeId => id2nodeMap(nodeId))

Answer 5

如果 p = 节点 => node.marker==1 &&访问（节点）并假设节点是一个列表，您可以选择以下任何一个：

• nodes.filter(p).length>0
• nodes.count(p)>0
• nodes.exists(p) （我认为最相关）

我不确定每种方法的相对复杂性，并感谢社区其他成员的评论