1

私はスカラチョップに取り組んでおり、グラフに追加された頂点とエッジを追跡する小さなグラフ Api を実装しています。私は基本的な GraphLike Trait を持っており、この特性を拡張する無向グラフ クラス ( UnDiGraph) と有向グラフ クラス ( ) を持っています。ここにリストの一部がありますDiGraphGraphLike

trait GraphLike[T] {
    val vertices: Map[T, VertexLike[T]]
    def addEdge( a:T, b:T ): GraphLike[T]
    def addVertex( t:T ): GraphLike[T]
    def addVertex( vert: VertexLike[T] ): GraphLike[T]
    def adjacency( t:T ): Option[ List[T] ]  =
    {
      if ( vertices contains t )
        Some( vertices(t).adjList )
      else
        None
    }
    def vertNum: Integer = vertices size
    def edgeNum: Integer = 
    {
      def summer( sum: Integer, ms: Map[T, VertexLike[T] ] ): Integer =
      {
        if ( ms.isEmpty )
          sum
        else
          summer( sum + ms.head._2.adjList.size, ms.tail )
      }
      summer( 0, vertices )
    }
    def getVertex( t: T ): VertexLike[T] =
    {
      vertices( t )
    }
    def edgeExists( a:T, b:T ): Boolean =
    {
      try
      {
          if( vertices( a ).adjList contains b )
            true
          else
            false
      }catch {
        case ex: NoSuchElementException => false 
      }
    }
}

ダイレクト グラフの外観は次のとおりです。

class DiGraph[T](val vertices: Map[ T, VertexLike[ T ] ] = Map.empty ) extends GraphLike[T] {
    def makeVertex( t:T ): VertexLike[T] = new Vertex( t )

    def addEdge( a:T, b:T ): GraphLike[T] =
    {
      //Make sure vertices exist
      if( edgeExists(a, b) )
        this
      else {
        try {
          vertices(b)
          vertices(a)
        } catch {
          case ex: NoSuchElementException => println("Vertices not Found"); this
        }
        addVertex( vertices( a ) + b )
      }
    }
    def addVertex( t:T ): DiGraph[T] = 
    {
      if( vertices contains t ) this
      else
      new DiGraph[T]( vertices + ( t -> makeVertex(t) ) )
    }
    def addVertex( vert: VertexLike[T] ): DiGraph[T] =
    {
      new DiGraph[T]( vertices + ( vert.apply -> vert ) ) 
    }
}

頂点は、タイプ T から VertexLike[T] への Map に格納されます。Vertex Like は基本的に、特定の頂点の隣接リストを保持します。VertexLike は次のようになります。

trait VertexLike[T] 
{
  def addEdgeTo( dest: T ): VertexLike[T]
  def adjList: List[T]
  def +( dest: T) = addEdgeTo(dest)
  def apply: T
} 

class Vertex[T](t: T, adj: List[T] = List() ) extends VertexLike[T]
{
    def apply() = t
    def adjList = adj
    def addEdgeTo( dest: T ) = 
      if( adjList contains dest )
        this
      else
        new Vertex[T]( t, dest :: adjList )
}

（はい...クラスのapplyメソッドは役に立たず、オブジェクトでしか機能しないことに気づきました。少し後で気づきました）。

とにかく、約 80,000 個の頂点を持つサンプル グラフがあります。頂点をグラフに追加するのに時間がかかりすぎています。私は機能的に、そして不変の方法で物事をやろうとしました。グラフに頂点またはエッジを追加すると、新しいグラフが得られます (グラフ タイプのコンストラクターがあまり機能していないことを確認しようとしました)。これは、データからグラフを作成するために使用するクライアント コードです。

def GraphInstantiater: GraphLike[Int] =
{
  println( "Total number of Vertices: " + synMap.keys.size )
  def vertexAdder( ls: Iterable[Int], graph:GraphLike[Int] ): GraphLike[Int] = 
    if( ls.isEmpty) graph else vertexAdder( ls.tail, graph.addVertex( ls.head ) ) 

  val gr = vertexAdder( synMap.keys, new DiGraph[Int]( Map() ) )
  println( "Vertices added. Total: %d".format( gr.vertices.size ) )
  gr
}

新しいグラフの作成にはサイクルがかかることはわかっていますが、コンストラクターで多くのことを行っていないことを考えると、それは本当に素晴らしいことです。頂点のマップを繰り返し作成すると、問題が発生し続けます (グラフ クラスのパラメーターの 1 つです)。この方法のボトルネックについてのアイデアは大歓迎です。また、追加情報が必要な場合はお知らせください。

4

2 に答える 2

0

うわー...何が起こっているのか理解しました。GraphInstantiater メソッドでは、synMap.keys を渡す最初の呼び出しで、keys は iterable[Int] を返します。これを追跡するのは長いプロセスのように見えます。おそらく、毎回キーのセット全体を調べます。

への呼び出しを変更する

val gr = vertexAdder( synMap.keys.toList, new DiGraph[Int]( Map() ) )

すべてを高速化しました。keysMapを呼び出したときに返されるコンテナの基本的な実装を知っている人はいますか?

于 2013-05-05T14:29:50.433 に答える