java - 如何在没有内存溢出的情况下检查图中的所有循环？

Question

相邻列表中的图形示例:

> (K01196,List(K00700, K01178, K01187, K00688))
> (K00844,List(K01835, K01810))
> (K00700,List(K00688))
> (K01178,List(K01196, K01187))
> (K00706,List(K00693, K01210, K00963, K00697, K16055))
> (K01810,List(K00844, K01835))
> (K01193,List(K00844, K01210, K01187))
> (K00693,List(K01196, K00688, K00700))
> (K16055,List(K01194, K00693))
> (K01835,List(K00844, K00688, K01810, K00963))
> (K00963,List(K00688, K16055, K00693, K01835, K00697))
> (K00697,List(K16055, K00693))
> (K01187,List(K01178, K01210, K00844))

第二个例子(容易出问题):

from,to
YIL099W,YPR184W
YIL099W,YJL216C
YIL099W,YIL172C
YIL099W,YGR292W
YIL099W,YOL157C
YIL099W,YJL221C
YIL099W,YBR299W
YIL099W,YGR287C
YLR258W,YPR184W
YLR258W,YPR160W
YLR258W,YEL011W
YGR032W,YFR015C
YGR032W,YLR258W
YGR032W,YGR282C
YGR032W,YOR190W
YGR032W,YDR261C
YGR032W,YLR300W
YGR032W,YHL012W
YGR032W,YKL035W
YGR032W,YBR126C
YGR032W,YMR261C
YGR032W,YDR074W
YGR032W,YML100W
YKL127W,YFR053C
YKL127W,YGL253W
YKL127W,YCL040W
YKL127W,YPR160W
YKL127W,YBR196C
YKL127W,YHL012W
YKL127W,YKL035W
YBR126C,YMR261C
YBR126C,YDR074W
YBR126C,YML100W
YBR126C,YFR015C
YBR126C,YLR258W
YBR299W,YIL099W
YBR299W,YIR019C
YBR299W,YGR282C
YBR299W,YOR190W
YBR299W,YDR261C
YBR299W,YLR300W
YBR299W,YFR053C
YBR299W,YGL253W
YBR299W,YCL040W
YMR105C,YFR053C
YMR105C,YGL253W
YMR105C,YCL040W
YMR105C,YPR160W
YMR105C,YBR196C
YMR105C,YHL012W
YMR105C,YKL035W
YIR019C,YPR184W
YIR019C,YJL216C
YIR019C,YIL172C
YIR019C,YGR292W
YIR019C,YOL157C
YIR019C,YJL221C
YIR019C,YBR299W
YIR019C,YGR287C
YFR053C,YKL127W
YFR053C,YMR105C
YFR053C,YMR278W
YFR053C,YBR196C
YGR287C,YIL099W
YGR287C,YIR019C
YGR287C,YGR282C
YGR287C,YOR190W
YGR287C,YDR261C
YGR287C,YLR300W
YGR287C,YFR053C
YGR287C,YGL253W
YGR287C,YCL040W
YCL040W,YKL127W
YCL040W,YMR105C
YCL040W,YMR278W
YCL040W,YBR196C
YEL011W,YPR160W
YIL162W,YFR053C
YIL162W,YGL253W
YIL162W,YCL040W
YIL162W,YGR282C
YIL162W,YOR190W
YIL162W,YDR261C
YIL162W,YLR300W
YIL162W,YJL216C
YIL162W,YIL172C
YIL162W,YGR292W
YIL162W,YOL157C
YIL162W,YJL221C
YIL162W,YBR299W
YIL162W,YGR287C
YHL012W,YPR160W
YHL012W,YMR261C
YHL012W,YDR074W
YHL012W,YML100W
YHL012W,YFR015C
YHL012W,YLR258W
YHL012W,YKL127W
YHL012W,YMR105C
YHL012W,YMR278W
YHL012W,YBR126C
YLR342W,YFR015C
YLR342W,YLR258W
YLR342W,YGR282C
YLR342W,YOR190W
YLR342W,YDR261C
YLR342W,YLR300W
YLR342W,YHL012W
YLR342W,YKL035W
YLR342W,YBR126C
YLR342W,YMR261C
YLR342W,YDR074W
YLR342W,YML100W
YGL253W,YKL127W
YGL253W,YMR105C
YGL253W,YMR278W
YGL253W,YBR196C
YGR292W,YIL099W
YGR292W,YIR019C
YGR292W,YGR282C
YGR292W,YOR190W
YGR292W,YDR261C
YGR292W,YLR300W
YGR292W,YFR053C
YGR292W,YGL253W
YGR292W,YCL040W
YJL216C,YIL099W
YJL216C,YIR019C
YJL216C,YGR282C
YJL216C,YOR190W
YJL216C,YDR261C
YJL216C,YLR300W
YJL216C,YFR053C
YJL216C,YGL253W
YJL216C,YCL040W
YPR184W,YEL011W
YPR184W,YIL099W
YPR184W,YIR019C
YPR184W,YJL216C
YPR184W,YIL172C
YPR184W,YGR292W
YPR184W,YOL157C
YPR184W,YJL221C
YPR184W,YBR299W
YPR184W,YGR287C
YPR184W,YPR160W
YOL157C,YIL099W
YOL157C,YIR019C
YOL157C,YGR282C
YOL157C,YOR190W
YOL157C,YDR261C
YOL157C,YLR300W
YOL157C,YFR053C
YOL157C,YGL253W
YOL157C,YCL040W
YDR074W,YBR001C
YDR074W,YDR001C
YDR074W,YPR026W
YDR074W,YFR015C
YDR074W,YLR258W
YJL221C,YIL099W
YJL221C,YIR019C
YJL221C,YGR282C
YJL221C,YOR190W
YJL221C,YDR261C
YJL221C,YLR300W
YJL221C,YFR053C
YJL221C,YGL253W
YJL221C,YCL040W
YMR306W,YFR015C
YMR306W,YLR258W
YMR306W,YGR282C
YMR306W,YOR190W
YMR306W,YDR261C
YMR306W,YLR300W
YMR306W,YHL012W
YMR306W,YKL035W
YMR306W,YBR126C
YMR306W,YMR261C
YMR306W,YDR074W
YMR306W,YML100W
YIL172C,YIL099W
YIL172C,YIR019C
YIL172C,YGR282C
YIL172C,YOR190W
YIL172C,YDR261C
YIL172C,YLR300W
YIL172C,YFR053C
YIL172C,YGL253W
YIL172C,YCL040W
YBR196C,YFR053C
YBR196C,YGL253W
YBR196C,YCL040W
YBR196C,YKL127W
YBR196C,YMR105C
YBR196C,YMR278W
YML100W,YBR001C
YML100W,YDR001C
YML100W,YPR026W
YML100W,YFR015C
YML100W,YLR258W
YFR015C,YPR184W
YFR015C,YPR160W
YFR015C,YEL011W
YMR278W,YFR053C
YMR278W,YGL253W
YMR278W,YCL040W
YMR278W,YPR160W
YMR278W,YBR196C
YMR278W,YHL012W
YMR278W,YKL035W
YKL035W,YPR160W
YKL035W,YMR261C
YKL035W,YDR074W
YKL035W,YML100W
YKL035W,YFR015C
YKL035W,YLR258W
YKL035W,YKL127W
YKL035W,YMR105C
YKL035W,YMR278W
YKL035W,YBR126C
YMR261C,YBR001C
YMR261C,YDR001C
YMR261C,YPR026W
YMR261C,YFR015C
YMR261C,YLR258W

相邻列表是使用默认值 List() 构建的。您可以使用以下函数加载边缘，它会返回一个相邻的列表。

 def reader_AdjacentList(edgefile: String): Map[String, List[String]] = {
    val sourcefile = Source.fromFile(edgefile)
    val pat = """([A-Z]\w+),([A-Z]\w+)""".r
    sourcefile.getLines.:\(Map[String, List[String]]().withDefaultValue(List()))((line, maps) =>
      pat.findFirstMatchIn(line) match {
        case Some(pat(from, to)) => if (maps.contains(from)) maps.updated(from, maps(from).+:(to).distinct)
        else maps.+((from, List(to)))
        case None => maps
      })
  }

下面的函数是检查给定起始节点和图形的所有循环:

def checkCycles(start: String, maps: Map[String, List[String]]): List[List[String]] = {
  def explore(node: String, visits: List[String]): List[List[String]] = {
    if (visits.contains(node)) List(visits.+:(node))
    else {
      if (maps(node).isEmpty) List()
      else {
        maps(node).flatMap(x => explore(x, visits.+:(node)))
      }
    }
  }
  explore(start, List())
}

检查所有循环路径的运行程序如下(adList 是开头相邻列表表示的图形):

val cycles = adList.toList.flatMap(pair => checkCycles(pair._1, adList))

cycles.foreach(println)

该程序适用于其他一些图形示例，例如上面给出的第一个例子，但第二个例子没有，它给出了以下错误，尽管 eclipse 中的堆大小已设置为 4G。

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

有谁知道这个程序有什么问题，以及如何改进它？

Answer 1

在我的电脑上工作完全正常，无需更改有关堆空间的任何设置。 cycles 的长度为 818。我所做的唯一更改是现在所有节点都是符号(因为我只是将您的工作人员复制到我的 IDE 中，这是让一切正常工作的最快方法)，这根本不重要。

更新 由于第二个示例不容易复制和粘贴，我正在生成我自己的更大比例的示例，这是一个随机图，每个节点都有 n 个节点和 k 个边节点(自循环和重复边被删除)。

val rand = new java.util.Random
val n = 50
val k = 4
val map = 0 until n map (i => {
  i -> ((0 until k) map (_ => rand.nextInt(n)) filter (_ != i) groupBy(identity) map (_._1) toList)
}) toMap

对于 n=50 和 k=4，有 124693 个“周期”(如您所定义)。我也尝试了n=100和k=10，似乎要计算的路径太多所以程序没有在几分钟内终止，但没有内存异常抛出。