3

在无向图 G = (V, E) 中，一个团 C 是顶点 C ⊆ V 的子集，因此每两个不同的顶点都是相邻的。这等价于由 C 引出的 G 的子图完备的条件。在某些情况下，术语 clique 也可以直接指代子图。

所以，我将 GraphX 与 Apache-Spark 一起使用。我阅读了它的文档指南，它们提供了一种在图中找出连接组件的方法，但不是派系/强连接组件。我怎样才能使用 Scala 做到这一点？谢谢！

编辑：正如评论中所建议的，我在 R 中编写的用于执行相同任务的一段代码如下：（将此代码与 Spark 一起使用的问题是最近发布的 SparkR，通过它我可以将 R 与 Spark 一起使用支持库（例如，igraph）。因此，我开始使用 GraphX 和 Scala），现在我需要算法。

library(igraph)
files <- paste0("NP",1:10,".txt") // Files which represent graphs
func.clique <- function(file)
{
    w <- read.table(file)
    g <- graph.edgelist(cbind(as.character(w$V1),as.character(w$V2)))
    plot(g)
    cli <- cliques(g)
    return (cli)
}
cliquevalues <- sapply(files,func.clique)
4

1 回答 1

2

我们最近使用了 jgrapht，与上面@marios 在评论中提到的相同。关于如何使用它的示例代码，这里 Vertex 是自定义 Vertex 类，并且 cliques 为您提供图中所有 cliques 的列表：

import org.jgrapht._
import org.jgrapht.graph._
import org.jgrapht.alg._
import scala.collection.JavaConverters._
import Util._
import Constants._
import Implicits._

class CliqueGraph(vertices:List[Vertex],xyEdges:List[(Vertex,Vertex)]){
    val graph = new SimpleGraph[Vertex, DefaultEdge](classOf[DefaultEdge])
    vertices.foreach(v=>graph.addVertex(v))
    xyEdges.foreach{ case(v1,v2) =>
            graphg.addEdge(v1,v2)
    }
    lazy val cliques= {
        val c =  new BronKerboschCliqueFinder(graph)
        val setVertices = c.getAllMaximalCliques().asScala
        setVertices.toList
    }
}

在 build.sbt 文件中，您需要导入库：

libraryDependencies += "org.jgrapht" % "jgrapht-dist" % "0.9.0"
于 2015-07-06T11:38:30.350 回答