struct GreedyClique
    vertices::BitArray
    mutuals::BitArray
end

Arguments

• vertices::BitArray: Vertices in the subgraph that defines a clique. BitVector ranging over the number of vertex in the full graph that are true if identifies as a member of the clique and false otherwise.
• mutuals::BitArray: Vertices that neighbour the clique (potential clique members)

union(c1::GreedyClique, c2::GreedyClique) -> GreedyClique

Merges two cliques.

anymaxclique(A::AbstractMatrix{Bool})

Finds any maximal clique in the adjacency matrix. To find a maximal clique, it sorts the nodes by number of neighbours then if the node can be added to the clique, it adds it to the clique. Note that this is not the maximum clique.

Arguments

• A::AbstractMatrix{Bool}: Adjacency Matrix.

Returns

• Clique: One of the maximal cliques in the adjaceny matrix.

greedycliquing(A::AbstractMatrix{Bool},  minsize::Int)
greedycliquing!(A::AbstractMatrix{Bool},  minsize::Int)

Greedy Cliquing Algorithm based off of: https://gitlab.invenia.ca/invenia/autopredictor/blob/develop/Tools/PreProcessing/GreedyCliquing.m

Splits an adjacency matrix into cliques [1] and remaining non-cliquable nodes. Compared to a previous version that acheives maximum node set reduction through optimal cliquing, this version finds a maximal clique, removes its nodes from the adjacency matrix, and repeats until no cliques can be found. More discussion can be found in this [2] Google doc.

[1] http://en.wikipedia.org/wiki/Clique(graphtheory) [2] https://docs.google.com/a/invenia.ca/document/d/1lLRfQTTFJi1bTfIujGxDs1u9A9HYKX5s4Zta3VRNg/edit?usp=sharing

Arguments

• A::AbstractMatrix{Bool}: Adjacency Matrix
• minsize::Int: Min greedyclique size

Returns

• cliques::Array{Clique}: Vector array of type Clique
• singletons::Vector{Bool}: Vector array of Bool. These indicate nodes not in a clique

mergeable(c1::GreedyCliqye, c2::GreedyClique) -> Bool

Compare two cliques. They can be merged if the mutuals (neighbours) of one clique (C1) AND the vertices of the other clique (c2) match the vertices of c2.

mutuals(c::GreedyClique) -> BitArray

Return mutual neighbours (potential clique members) as a logical vector.

vertices(c::GreedyClique) -> BitArray

Return vertices of a clique as a logical vector.