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<int> 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)

Full name: Microsoft.FSharp.Collections.Set.add
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
Raw view Test code New version

More information

Link:http://fssnip.net/jg
Posted:11 years ago
Author:Lakret
Tags: graphs , cliques , algorithms