%----------------------------------------------- Dafna Talmor, 1995. This file contains an implementation of the algorithm described in: Michael Luby. A Simple Parallel Algorithm for the Maximal Independent Set Problem. Proceedings ACM Symposium on Theory of Computing, May 1985. In this implementation a graph is represented as a sequence of (ID,EDGES) pairs, one per vertex of the graph, where ID is the identifier of the vertex (can be any type), and EDGES is a sequence of indices of the neighbors of the vertex. The indices in EDGES are relative to the full sequences. -------------------------------------------------- % %----------------------------------------------- Retrieves values V from the neighbors of a graph G -------------------------------------------------- % function get_from_neighbors(G,V) = let ids,edges = unzip(G) in partition(V->flatten(edges),{#edges:edges}) $ %----------------------------------------------- Takes a graph G and a sequence of flags (one per vertex) and returns the subgraph containing the flagged vertices. It relabels the edges to account the movement of the vertices. -------------------------------------------------- % function compress_graph(G, flags) = let % The new positions of the remaining vertices % new_labels = {if flag then i else -1 : i in enumerate(flags) ; flag in flags}; new_G = {G; flags | flags}; new_edge_labels = get_from_neighbors(new_G, new_labels); % Update edges and remove if they point to a deleted vertex % new_G = {i, {e in ne | e >= 0} : ne in new_edge_labels ; i, _ in new_G }; in new_G $ %---------------------------------------------------- This is the body of the algorithm. It returns the vertex identifiers of a maximal independent set. It works recursively and with high probability finishes after O(lg n) recursive calls. ----------------------------------------------------% function luby_maximal_independent_set(G) = if #G==0 then []int else let % Toss a coin with weight inversely proportional to the degree to select the active vertices. % active_flags = {(float(#adj) * rand(x) < 0.5) : (i,adj) in G ; x in dist(1.0,#G)}; % Generate a unique rank for each active vertex such that vertices with higher degree will have a larger rank. Inactive vertices have rank 0. % rank = {if active then float(#adj) + 1.0/float(1+i) else 0.0 : active in active_flags ; (i,adj) in G}; % Vertices are added to the maximal-independent set if they are active and have a larger rank than any neighbor % MIS_flags = {active and (my_rank > max_val(ngh_rank)) : active in active_flags ; ngh_rank in get_from_neighbors(G, rank) ; my_rank in rank}; (MIS_i, MIS_adj) = unzip({G ; fl in MIS_flags | fl}); % remove MIS vertices and their neighbors from the graph % remove_flags = MIS_flags<-{(i,t) : i in flatten(MIS_adj)}; new_G = compress_graph(G, {not(fl) : fl in remove_flags}); % Recurse. % in MIS_i ++ luby_maximal_independent_set(new_G) $