LightGraphs for Luby's algorithm

General Usage
1

I am trying to use the LightGraphs and associated packages to implement Maximal-Independent-Set algorithms: Luby, Blelloch

Both algorithms work by iterating over vertices and based on a relation between a vertex and its neighbors, add the vertex to the MIS (maximal independent set) and mark that vertex and its neighbors as “inactive” (ignoring them in the following iterations of the algorithm)

I tried to create a copy of the graph (squash / copy) in the beginning of the function, and remove inactive vertices making the graph gradually smaller (focusing on a sequential implementation of these algorithms)

However, removing vertices from the graph (rem_vertex!, rem_vertices!) relabels the vertices of the graph, thus the algorithms fails

My “solution” was to convert the copy of the graph to a MetaGraph and add an :active property (initially true).
This works, but it is not elegant, and worse it is very inefficient since as the algorithm progresses it has to iterate over all vertices skipping the ones marked as inactive

Is there a way to remove vertices from a graph while maintaining the original vertex numbers?

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