Liking cljdoc? Tell your friends :D

# Clojure implementaion of the Bron-Kerbosch algorithm

A clojure implementation of the Bron-Kerbosch algorithm for finding maximum cliques. More information about the algorithm can be found on its wikipedia entry.

## Installation

Available as a lein module from clojars. Simply us

``````[bron-kerbosch "1.0.0-SNAPSHOT"]
``````

in you `project.clj` dependencies. The jar filed is compiled using clojure 1.2 and clojure-contrib 1.2, but it should be possible to compile it under 1.1.

## Usage

The program needs a graph defined by a collection of nodes and a neighbor function which takes a node and returns a collection of nodes. For example, the example graph from the Wikipedia entry on the Bron-Kerbosch algorithm which looks like this

can be represented by the node vector `[1 2 3 4 5 6]` and a map based neighbor function:

``````{1 [2 5]
2 [1 3 5]
3 [2 4]
4 [3 5 6]
5 [1 2 4]
6 [4]}
``````

To run the Bron-Kerbosch algorithm call the function `maximum-cliques` on the nodes and the neighbor function

``````user> (maximum-cliques [1 2 3 4 5 6]
{1 [2 5]
2 [1 3 5]
3 [2 4]
4 [3 5 6]
5 [1 2 4]
6 [4]})
(#{1 2 5} #{2 3} #{3 4} #{4 5} #{4 6})
``````

This will generate the maximum cliques in the graph. To get the maximum cliques of the maximum cliques use the function `maximum-cliques-of-maximum-cliques`

``````user> (maximum-cliques-of-maximum-cliques [1 2 3 4 5 6]
{1 [2 5]
2 [1 3 5]
3 [2 4]
4 [3 5 6]
5 [1 2 4]
6 [4]})
((#{2 3} #{4 5}) (#{2 3} #{4 6}) (#{3 4} #{1 2 5}) (#{4 6} #{1 2 5}))
``````

## To dos

• Implement the pivot based Bron-Kerbosch algorithm.

Can you improve this documentation?Edit on GitHub

cljdoc is a website building & hosting documentation for Clojure/Script libraries

× close