# LightGraphs for Luby's algorithm

**URL:** <https://discourse.julialang.org/t/lightgraphs-for-lubys-algorithm/52306>\
**Category:** General Usage\
**Created:** [December 23, 2020, 11:42pm UTC](https://discourse.julialang.org/t/lightgraphs-for-lubys-algorithm/52306 "2020-12-23T23:42:06Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![hros](https://avatars.discourse-cdn.com/v4/letter/h/97f17d/32.png) [@hros](https://discourse.julialang.org/u/hros)\
**Post date:** [December 23, 2020, 11:42pm UTC](https://discourse.julialang.org/t/lightgraphs-for-lubys-algorithm/52306/1 "2020-12-23T23:42:06Z")

</div>

I am trying to use the LightGraphs and associated packages to implement Maximal-Independent-Set algorithms: [Luby](https://en.wikipedia.org/wiki/Maximal_independent_set#Random-selection_parallel_algorithm_%5BLuby's_Algorithm%5D), [Blelloch](https://en.wikipedia.org/wiki/Maximal_independent_set#Random-permutation_parallel_algorithm_%5BBlelloch's_Algorithm%5D)

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?

---

<div class="post-metadata">

**Author:** ![scheinerman](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/scheinerman/32/35303_2.png) [@scheinerman](https://discourse.julialang.org/u/scheinerman)\
**Post date:** [December 24, 2020, 12:12pm UTC](https://discourse.julialang.org/t/lightgraphs-for-lubys-algorithm/52306/2 "2020-12-24T12:12:46Z")

</div>

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

```julia
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
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
julia> using SimpleGraphAlgorithms

julia> max_indep_set(G)

# verbose output from Cbc omitted

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

```