#Corrupted clique by Brute Force Help1:=proc(): print(`MtoG(M,c) , Neig1(G,v) , CC(G,v)`): print(`CCD(G),IsQG(G), GraphNeigh1(G,a,b), GraphNeig(G,c) , BfCC(G)`): end: with(combinat): #MtoG(M,c): Inputs a distance matrix M (as a list of lists) #and outputs the graph [V,E] where V={1,2, ..., nops(M)} #and G is the set of edges where u and v are joined iff #their distance is <=c MtoG:=proc(M,c) local V,E,i,j,n: n:=nops(M): V:={seq(i,i=1..n)}: E:={}: for i from 1 to n do for j from 1 to i-1 do if M[i][j]<=c then E:=E union {{i,j}}: fi: od: od: [V,E]: end: #Neig1(G,v): the set of neighbors of vertex v in G Neig1:=proc(G,v) local S,e,V,E: S:={}: V:=G[1]: E:=G[2]: for e in E do if member(v,e) then S:=S union {(e minus {v})[1]} : fi: od: S: end: #Neig(G,S): the set of all neighbors of set of vertices S Neig:=proc(G,S) local V,s: {seq(op(Neig1(G,s)), s in S)}: end: ##CC(G,v): Inputs a simple graph G and a vertex v #outputs the set of vertices that can be reached from v CC:=proc(G,v) local V,E,S1,S2: V:=G[1]: E:=G[2]: S1:={v}: S2:= {v} union Neig(G,S1): while S1<>S2 do S1:=S2: S2:=S2 union Neig(G,S2): od: S2: end: #CCD(G): inputs a graph and outputs its set of connected #components CCD:=proc(G) local V,E,S,cc,v: V:=G[1]: E:=G[2]: S:={}: while V<>{} do v:=V[1]: cc:=CC(G,v): S:= S union {cc}: V:= V minus cc: od: S: end: #IsQG(G): Is the graph G=[V,E] a disjoint union of cliques? IsQG:=proc(G) local S,i,j,k: S:=CCD(G): evalb(G[2]= {seq(seq(seq({S[k][i],S[k][j]},i=1..j-1),j=1..nops(S[k])), k=1..nops(S))}): end: #The set of all graphs on V:=G[1] obtained from G #by adding a edges and deleting b edges GraphNeig1:=proc(G,a,b) local V,E,E1,i,j,LoveToHate, HateToLove: V:=G[1]: E:=G[2]: E1:=choose(V,2) minus E: LoveToHate:=choose(E,b): HateToLove:=choose(E1,a): {seq(seq([V,(E minus LoveToHate[i]) union HateToLove[j]], i=1..nops(LoveToHate)),j=1..nops(HateToLove))}: end: #The set of all graphs on V:=G[1] obtained from G #by doing c changes GraphNeig:=proc(G,c) local a,S: S:={}: for a from 0 to c do S:=S union GraphNeig1(G,a,c-a): od: S: end: #BfCC(G): inputs a simple graph G=[V,E] and outputs #the "closest" clique graph (disjoint union of cliques) BfCC:=proc(G) local c,S,G1: for c from 0 to min(nops(G[2]),binomial(nops(G[1]),2)-nops(G[2])) do S:=GraphNeig(G,c): for G1 in S do if IsQG(G1) then RETURN(G1): fi: od: od: end: