CODEWITHSUNDEEP
scalaapache-sparkspark-graphx
John Lui
John Lui

Reputation: 1464

Finding cliques or strongly connected components in Apache Spark using Graphx

A clique, C, in an undirected graph G = (V, E) is a subset of the vertices, C ⊆ V, such that every two distinct vertices are adjacent. This is equivalent to the condition that the subgraph of G induced by C is complete. In some cases, the term clique may also refer to the subgraph directly.

So, I am using GraphX with Apache-Spark. I read its documentation guide, and they provide a way to find out connected components in a graph, but not the cliques/strongly connected components. How can I do that using Scala? Thanks!

Edit: As suggested in comments, a piece of code that I wrote in R for doing the same task is as follows: (The problem in using this code with Spark is that the recently released SparkR through which I can use R with Spark has limited support in terms of libraries (for example, igraph). Therefore, I started using GraphX and Scala) in which I now need the algorithm. 

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)

Upvotes: 4

Views: 2975

Answers (1)

ravi
ravi

Reputation: 391

We've recently used jgrapht, the same as mentioned by @marios above in comment. Sample code on how to use it, here Vertex is the custom Vertex class and cliques give you list of all cliques present in the graph:

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

In you build.sbt file you need to import the library:

libraryDependencies += "org.jgrapht" % "jgrapht-dist" % "0.9.0"

Upvotes: 2

Related Questions