LightGraphs for Luby's algorithm

General Usage
2

If you are willing to use a different graph theory package, I can offer this solution:

using SimpleGraphs

"""
`maximal_indep_set(G)` returns a maximal independent set 
of vertices of `G`.
"""
function maximal_indep_set(G::SimpleGraph{T}) where T
    S = Set{T}()           # place to hold the answer
    GG = deepcopy(G)       # copy of G to destroy
    while NV(GG)>0
        v = first(GG.V)    # get a vertex
        Nv = GG[v]         # and its neighbors
        push!(S,v)         # add v to the set S
        delete!(GG,v)      # remove v and its neighbors
        for w in Nv
            delete!(GG,w)
        end
    end
    return S
end

Note that a maximal independent set is not necessarily a maximum independent set. For example:

julia> G = Cycle(12)
Cycle (n=12, m=12)

julia> maximal_indep_set(G)
Set{Int64} with 5 elements:
  7
  9
  4
  2
  11

For a maximum independent set, try this:

julia> using SimpleGraphAlgorithms

julia> max_indep_set(G)

# verbose output from Cbc omitted

Set{Int64} with 6 elements:
  4
  10
  2
  8
  6
  12
2 Likes