1 people like it.

# Bron–Kerbosch maximal cliques algorithm

Bron–Kerbosch algorithm is an algorithm for finding maximal cliques in an undirected graph http://en.wikipedia.org/wiki/Bron%E2%80%93Kerbosch_algorithm

 ``` 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: ``` ``````open System type Graph = (int * (int list)) list let testGraph : Graph = [ (1, [2; 5]) (2, [1; 5; 3]) (3, [2; 4]) (4, [3; 5; 6]) (5, [1; 2; 4]) (6, [4]) ] let rec bronKerbosch R P X graph = let neighbors vertex = graph |> List.find (fun (v, _) -> v = vertex) |> snd |> set seq { if (Set.isEmpty P) && (Set.isEmpty X) then yield (Set.toSeq R) let vPX = Seq.unfold (function | (v::tailP as P, currX) -> let newX = Set.add v currX Some((v, set <| P, currX), (tailP, newX)) | ([], _) -> None) (P |> Set.toList, X) for (v, P, X) in vPX do let n = neighbors v yield! bronKerbosch (Set.add v R) (Set.intersect P n) (Set.intersect X n) graph } let findMaxCliques graph = bronKerbosch Set.empty (graph |> List.map fst |> set) Set.empty graph //findMaxCliques testGraph;; //val it : seq list = // [set [1; 2; 5]; set [2; 3]; set [3; 4]; set [4; 5]; set [4; 6]] ``````
namespace System
type Graph = (int * int list) list

Full name: Script.Graph
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val testGraph : Graph

Full name: Script.testGraph
val bronKerbosch : R:Set<'a> -> P:Set<'a> -> X:Set<'a> -> graph:('a * #seq<'a>) list -> seq<seq<'a>> (requires comparison)

Full name: Script.bronKerbosch
val R : Set<'a> (requires comparison)
val P : Set<'a> (requires comparison)
val X : Set<'a> (requires comparison)
val graph : ('a * #seq<'a>) list (requires comparison)
val neighbors : ('a -> Set<'a>) (requires comparison)
val vertex : 'a (requires comparison)
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
| ( [] )
| ( :: ) of Head: 'T * Tail: 'T list
interface IEnumerable
interface IEnumerable<'T>
member Head : 'T
member IsEmpty : bool
member Item : index:int -> 'T with get
member Length : int
member Tail : 'T list
static member Cons : head:'T * tail:'T list -> 'T list
static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val find : predicate:('T -> bool) -> list:'T list -> 'T

Full name: Microsoft.FSharp.Collections.List.find
val v : 'a (requires comparison)
val snd : tuple:('T1 * 'T2) -> 'T2

Full name: Microsoft.FSharp.Core.Operators.snd
val set : elements:seq<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.set
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
Multiple items
module Set

from Microsoft.FSharp.Collections

--------------------
type Set<'T (requires comparison)> =
interface IComparable
interface IEnumerable
interface IEnumerable<'T>
interface ICollection<'T>
new : elements:seq<'T> -> Set<'T>
member Add : value:'T -> Set<'T>
member Contains : value:'T -> bool
override Equals : obj -> bool
member IsProperSubsetOf : otherSet:Set<'T> -> bool
member IsProperSupersetOf : otherSet:Set<'T> -> bool
...

Full name: Microsoft.FSharp.Collections.Set<_>

--------------------
new : elements:seq<'T> -> Set<'T>
val isEmpty : set:Set<'T> -> bool (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.isEmpty
val toSeq : set:Set<'T> -> seq<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.toSeq
val vPX : seq<'a * Set<'a> * Set<'a>> (requires comparison)
module Seq

from Microsoft.FSharp.Collections
val unfold : generator:('State -> ('T * 'State) option) -> state:'State -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.unfold
val tailP : 'a list (requires comparison)
val P : 'a list (requires comparison)
val currX : Set<'a> (requires comparison)
val newX : Set<'a> (requires comparison)
val add : value:'T -> set:Set<'T> -> Set<'T> (requires comparison)

union case Option.Some: Value: 'T -> Option<'T>
union case Option.None: Option<'T>
val toList : set:Set<'T> -> 'T list (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.toList
val n : Set<'a> (requires comparison)
val intersect : set1:Set<'T> -> set2:Set<'T> -> Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.intersect
val findMaxCliques : graph:('a * #seq<'a>) list -> seq<seq<'a>> (requires comparison)

Full name: Script.findMaxCliques
val empty<'T (requires comparison)> : Set<'T> (requires comparison)

Full name: Microsoft.FSharp.Collections.Set.empty
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val fst : tuple:('T1 * 'T2) -> 'T1

Full name: Microsoft.FSharp.Core.Operators.fst