2

隣接リストのグラフの例:

> (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))

2 番目の例 (問題が発生しやすい):

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 に設定されているにもかかわらず、次のエラーが発生する 2 番目の例では機能しません。

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

プログラムの何が問題なのか、またそれを改善する方法を知っている人はいますか?

4

1 に答える 1

0

ヒープ領域に関する設定を変更しなくても、私のコンピューターでは問題なく動作します。長さは 818 です。cycles私が行っている唯一の変更は、すべてのノードがシンボルになったことです (スタッフを IDE にコピーするだけで、これが作業を行うための最速の方法であるため)。これはまったく問題ではありません。

更新n2 番目の例は簡単にコピー アンド ペーストできないため、ノードごとにノードとエッジを 持つランダム グラフである大規模な独自の例を生成して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ました.計算するパスが多すぎるため、プログラムは数分で終了しませんが、メモリ例外はスローされません.

于 2012-12-06T21:25:58.950 に答える