Scala Graph Cycle Detection算法是否需要“返回”？ [英] Scala Graph Cycle Detection Algo 'return' needed?

问题描述

我已经在Scala中为DAG实现了一个小周期检测算法。
'return'困扰着我-我想要一个没有返回的版本...可能吗？

I have implemented a small cycle detection algorithm for a DAG in Scala. The 'return' bothers me - I'd like to have a version without the return...possible?

  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
  }

推荐答案

我认为可以通过不更改节点状态来解决问题标记字段。以下是我认为isCyclic应该看起来像的大致代码。我当前正在存储要访问的节点对象，如果节点根据节点ID不相等，则可以存储节点ID。

I think the problem can be solved without changing the state of the node with the marker field. The following is a rough code of what i think the isCyclic should look like. I am currently storing the node objects which are visited instead you can store the node ids if the node doesnt have equality based on node 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))

这篇关于Scala Graph Cycle Detection算法是否需要“返回”？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！