#its ok to post
#TaerimKim,11/15/2020,Assignment 19

#1.

AllKComponentsGraphs := proc(n, k) local S, s, C; 
S := AllGraphs(n); 
C := {}; 
for s in S do 
if nops(CCs(s)) = k then 
C := C union {s}; 
end if; 
end do; 

C; 
end proc;

NuKcomponentsGraphs := proc(N, K) local n1; 
[seq(nops(AllKComponentsGraphs(n1, K)), n1 = 1 .. N)]; 

end proc;

#Now lets evaluate under N<6 with NuConG

NuKcomponentsGraphs(1, 1);
                              [1]
NuConG(1);
                              [1]
NuKcomponentsGraphs(2, 1);
                             [1, 1]
NuConG(2);
                             [1, 1]
NuKcomponentsGraphs(3, 1);
                           [1, 1, 4]
NuConG(3);
                           [1, 1, 4]
seq(NuKcomponentsGraphs(i, 1), i = 1 .. 4);
             [1], [1, 1], [1, 1, 4], [1, 1, 4, 38]
seq(NuConG(i), i = 1 .. 4);
             [1], [1, 1], [1, 1, 4], [1, 1, 4, 38]
evalb(% = `%%`);
                              true

#Seems good!

#NuKcomponentsGraphs(5, 2);
#                       [0, 1, 3, 19, 230]       -> A323875,Number of labeled graphs on n nodes with two connected components.
#NuKcomponentsGraphs(5, 3);
#                        [0, 0, 1, 6, 55]        -> A323876,Number of labeled graphs on n nodes with three connected components.


#Good

################################################################

#2. Using the RandGr and CCs function,

AveNuCC:=proc(n,K,M) local Count, A, C, Ans :

Count:=M;
A:={};

#initiate M random graphs
while Count <> 0 do
    A := A union {RandGr(n, K)};
    Count := Count - 1;
od: 

#Sum the # of components of each graphs using nops and CCs function
C := add(nops(CCs(A[i])), i = 1 .. M);

#finally, output average
Ans := evalf(C/M);

end:


#lets try the n=30, M=1000 on various cases
#when K=10
#AveNuCC(30, 10, 1000);
                          20.05700000
AveNuCC(30, 10, 1000);
                          20.06000000
AveNuCC(30, 10, 1000);
                          20.05100000
AveNuCC(30, 10, 1000);
                          20.04300000
AveNuCC(30, 10, 1000);
                          20.03600000

#we can see it is converging to the average of 20

#when K=29
AveNuCC(30, 29, 1000);
                          5.599000000
AveNuCC(30, 29, 1000);
                          5.667000000
AveNuCC(30, 29, 1000);
                          5.637000000
AveNuCC(30, 29, 1000);
                          5.555000000
AveNuCC(30, 29, 1000);
                          5.503000000

#it is also converging to the average of 5.6



##############################################################################


#3. Using the AveNuCC,
#we will use it to estimate K when AveNuCC becomes less than 1.05

EstimateCutOff:=proc(n,M) local K, Ave ;

#We know from above function that average # of connect component when vertices are same as edges(n=k) are rougly 5, which is way above the wanted result
#So we will initiate the initial condition when vertices = edges
K:=n;
Ave:=AveNuCC(n,K,M);

while Ave >= 1.05 do
Ave:=AveNuCC(n,K+1,M);
K++;
od:

#when the loop ends, K is the value when average is less than 1.05
K;

end:

#lets check
EstimateCutOff(30, 100);
                               81

AveNuCC(30, 81, 100);
                          1.040000000
#Seems fair

EstimateCutOff(30, 1000);
                               83

#this is also valid as 
AveNuCC(30, 83, 1000);
                          1.043000000