3

無向グラフ G = (V, E) のクリーク C は、頂点のサブセット C ⊆ V であり、2 つの異なる頂点がすべて隣接しています。これは、C によって誘導される G のサブグラフが完全であるという条件と等価です。場合によっては、クリークという用語がサブグラフを直接参照することもあります。

だから、私は Apache-Spark で GraphX を使用しています。ドキュメンテーション ガイドを読みましたが、グラフ内の連結成分を見つける方法は提供されていますが、クリーク/強連結成分は提供されていません。Scalaを使用してそれを行うにはどうすればよいですか? ありがとう！

編集: コメントで示唆されているように、同じタスクを実行するために R で記述したコードは次のとおりです: (このコードを Spark で使用する際の問題は、Spark で R を使用できる最近リリースされた SparkR が制限されていることです。ライブラリの面でのサポート (たとえば、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

上記の@mariosのコメントと同じように、最近jgraphtを使用しました。使用方法のサンプル コード。ここで Vertex はカスタム Vertex クラスで、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 に答える