1

我正在研究我的 scala 印章并实现了一个小图形 Api 来跟踪添加到图形中的顶点和边。我有基本的 GraphLike 特征，并且有一个无向图类 ( UnDiGraph) 和一个DiGraph扩展该GraphLike特征的有向图类 ( )。这是一些清单

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 
      }
    }
}

这是 Directe Graph 的样子。

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 基本上保存了特定 Vertex 的邻接列表。这是 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
}

我知道构建新图表需要循环，但考虑到我在构造函数中做的不多，这真的很棒吗？会反复创建顶点图不断导致问题（它是图形类的参数之一）。任何关于这种方法的瓶颈是什么的想法都将不胜感激。另外，如果您需要任何其他信息，请告诉我。

4

2 回答 2

1

synMap.keys作为对您回答的补充：您确实每次调用时都会无意中遍历整个ls.tail。

会发生什么：

  • Map.key返回 的值Map.keySet，这是一个自定义的不可变Set。
  • 这Set会覆盖一些东西，但会保留tail它们drop的默认实现。它的tail实现（来自TraversableLike）只是调用drop.
  • 这就是一切都崩溃的地方：它得到了dropfrom的实现IterableLike，而这只能做你可以用Iterable: 迭代做的事情。因此创建了一个新的构建器，删除了迭代器的头部，然后将迭代器添加到构建器中，它遍历了所有的键，并返回了一个新的集合（尾部）。

您可能可以通过使用迭代器完全避免转换为列表，例如：

def vertexAdder( ls: Iterator[Int], graph:GraphLike[Int] ): GraphLike[Int] = {
  if(!ls.hasNext) 
    graph 
  else
    val h = ls.next
    vertexAdder( ls, graph.addVertex(h) ) 
}

接着：

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

附带说明一下，Set没有提供自己的tail. 它可能只取它自己的迭代器的头部并返回它自己减去那个元素。

于 2013-05-05T16:45:23.293 回答
0

哦，哇……我知道发生了什么。在 GraphInstantier 方法中，第一次调用传递 synMap.keys，keys 返回一个 iterable[Int]。看起来这是一个漫长的过程，很可能每次都要经过整套密钥。

将呼叫更改为

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

让一切变得更快。有谁知道调用keysMap 时返回的容器的底层实现是什么？

于 2013-05-05T14:29:50.433 回答