# generate a list of all maximal independent sets in a graph G with
# vertex set X. The sets are sorted by decreasing size.


maxset:=proc(G,X) local x,i,j,m,cc,T,N,Cstack,Ostack,Rank;
  Rank:=0; Cstack:=table(); Ostack:=table(); N:=table();
  for i in X do N[i]:=subs(i=NULL,X) od;
  for j in G do
    N[j[1]]:=subs(j[2]=NULL,N[j[1]]);
    N[j[2]]:=subs(j[1]=NULL,N[j[2]])
  od;
  x:={},X; m:=0; T:=table();
  do
    cc:=map(proc(u,v) if u<v then u fi end,x[2],min(op(x[1])));
    if nops(cc)=0 then
      if nops(x[2])=0 then m:=m+1; T[m]:=x[1] fi;
      do cc:=Cstack[Rank];
        if nops(cc)=0 then Rank:=Rank-1 else break fi;
      od;
      if Rank=0 then break else x:=Ostack[Rank] fi;
    else
      Rank:=Rank+1; Ostack[Rank]:=x;
    fi;
    x:={op(x[1]),cc[1]},x[2] intersect N[cc[1]];
    Cstack[Rank]:=subsop(1=NULL,cc);
  od;
  sort([seq(T[i],i=1..m)],(u,v)->evalb(nops(u)>=nops(v)));
end: