Help:=proc(): print(`MtoG(M,c) , Neig1(G,v) , CC(G,v)`):
print(`CCD(G),IsCG(G), GraphNeigh(G,a,b) `):
 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:

#IsCG(G): Is the graph G=[V,E] a disjoint union of cliques?
IsCG:=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
GraphNeig:=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: