GitHub

Cliquer.jl

Julia bindings for Cliquer. This finds cliques or independent sets in (possibly weighted) graphs. It is much faster than the clique finder in Graphs.jl.

# By default, it finds the maximum weight clique.
julia> find_single_clique(cycle_graph(5))
2-element Vector{Int64}:
 2
 3

# By default, it finds all maximum weight cliques.  This can be configured.
julia> find_all_cliques(cycle_graph(5))
5-element Vector{Vector{Int64}}:
 [2, 3]
 [3, 4]
 [4, 5]
 [1, 2]
 [1, 5]

Reference

Cliquer.find_all_cliques — Method
find_all_cliques(f::Function, g::Graphs.AbstractSimpleGraph; verbose::Union{Bool,Function}=false, minweight::Integer=0, maxweight::Integer=0, maximal::Bool=true, weights::Vector{<:Integer}=Vector{Int32}())::Int64

Finds and all cliques meeting the given criteria (by default, the maximum cliques). Calls the given callback for each clique. Returns the number of cliques found.

If minweight=0, it searches for maximum-weight cliques. If maxweight=0, there is no upper limit. If verbose=true, progess messages will display; if verbose is a function, that function gets called for every recursion with a named tuple of status fields.

source
Cliquer.find_all_cliques — Method
find_all_cliques(g::Graphs.AbstractSimpleGraph; verbose::Union{Bool,Function}=false, minweight::Integer=0, maxweight::Integer=0, maximal::Bool=true, weights::Vector{<:Integer}=Vector{Int32}())::Vector{Vector{Int64}}

Finds and returns all cliques meeting the given criteria (by default, the maximum cliques).

If minweight=0, it searches for maximum-weight cliques. If maxweight=0, there is no upper limit. If verbose=true, progess messages will display; if verbose is a function, that function gets called for every recursion with a named tuple of status fields.

source
Cliquer.find_all_independent_sets — Method
find_all_independent_sets(f::Function, g::Graphs.AbstractSimpleGraph; verbose::Union{Bool,Function}=false, minweight::Integer=0, maxweight::Integer=0, maximal::Bool=true, weights::Vector{<:Integer}=Vector{Int32}())::Int64

Equivalent to find_all_cliques(f, complement(g)).

source
Cliquer.find_all_independent_sets — Method
find_all_independent_sets(g::Graphs.AbstractSimpleGraph; verbose::Union{Bool,Function}=false, minweight::Integer=0, maxweight::Integer=0, maximal::Bool=true, weights::Vector{<:Integer}=Vector{Int32}())::Vector{Vector{Int64}}

Equivalent to find_all_cliques(complement(g)).

source
Cliquer.find_single_clique — Method
find_single_clique(g::Graphs.AbstractSimpleGraph; verbose::Union{Bool,Function}=false, minweight::Integer=0, maxweight::Integer=0, maximal::Bool=true, weights::Vector{<:Integer}=Vector{Int32}())

Finds and returns a single clique meeting the given criteria (by default, a maximum clique).

If minweight=0, it searches for maximum-weight cliques. If maxweight=0, there is no upper limit. If verbose=true, progess messages will display; if verbose is a function, that function gets called for every recursion with a named tuple of status fields.

source
Cliquer.find_single_independent_sets — Method
find_single_independent_sets(g::Graphs.AbstractSimpleGraph; verbose::Union{Bool,Function}=false, minweight::Integer=0, maxweight::Integer=0, maximal::Bool=true, weights::Vector{<:Integer}=Vector{Int32}())

Equivalent to find_single_clique(complement(g)).

source