Best data structure for mapping between nodes and (known) cliques in a graph, that is easily updated after bisection?

Specific Domains Data
4

Then, in your graph, maximum cliques are the same as maximal cliques :slight_smile:

Tedious, as in “not a 1-liner”, is not the same as “efficient”, as in “runs quickly”.

To give an example:

struct VertexAndCliques{T <: AbstractSet{Int}}
  cliques::Vector{T} # cliques[i] is the set of clique-ids that contain vertex i
  vertices::Vector{T} # vertices[i] is the set of vertices in clique i
  scratch_space::T # a way to re-use allocations. 
end

#returns -1 on error, otherwise returns the number of new cliques
function split!(data::VertexAndCliques, i, j)
  i != j || i > length(data.cliques) || j > length(data.cliques)  || return -1
  
  intersect!(data.scratch_space, data.cliques[i], data.cliques[j])
  shared_cliques_frozen = data.scratch_space
  
  isempty(shared_cliques_frozen) && return -1
  
  shared_cliques = copy(shared_cliques_frozen)
  
  #register the new node
  push!(data.cliques, shared_cliques)
  newnode = length(vertices)

  for cid in shared_cliques_frozen
    vs = data.vertices[cid]
    vs2 = copy(vs)
    push!(data.vertices, vs2)
    cid2 = length(data.vertices)

    #need to replace j->newnode in vs, i->newnode in vs2
    pop!(vs, j); push!(vs, newnode);
    pop!(vs2, i); push!(vs2, newnode);
  
   #we doubled the clique, and corrected their membership list.
   #Next need fix up the list of cliques for each vertex.
   for vid in vs
      vid != i && push!(data.cliques[vid], cid2)
    end
  end
  return length(shared_cliques_frozen)
end

You can benchmark that with hash-table Set{Int} and with BitSet, which I guess will be much faster.

That being said, you can probably get a lot of mileage out of fixing N, the size of all your cliques, as a type parameter, and encoding a clique as NTuple{N,Int16}, i.e.

struct VertexAndCliques{T <: AbstractSet{Int}, N}
  cliques::Vector{T} # cliques[i] is the set of clique-ids that contain vertex i
  vertices::Vector{NTuple{N, Int16}} # vertices[i] is the set of vertices in clique i
  scratch_space::T # a way to re-use allocations. 
end

That’s because your bipartite graph has the property that the degree of each clique is the same (N), and you will never be able to represent a structure with more than 2^15 vertices anyways (you can probably get away with UInt8).

1 Like