attachment:dcomp-poset-eric.sage of days30_projects

   1 ############################################################################
   2 ################### Function to append poset elements to x #################
   3 ############################################################################
   4  
   5 def build_line(x,s,f):
   6     p=list(s)
   7     q=list(f)
   8     if s[0]>f[0] or s[1]>f[1]:
   9         return
  10     x.append(tuple(p))
  11     while p!=q:
  12         if p[0]<q[0]:
  13             p[0]+=1
  14         if p[1]<q[1]:
  15             p[1]+=1
  16         x.append(tuple(p))
  17     return
  18 
  19 ############################################################################
  20 ########### Function to append lines of elements of poset to x #############
  21 ############################################################################
  22 
  23 def build_block(x,sc,fc):
  24     if fc[1]-sc[1] > fc[0]-sc[0]:
  25         for i in range(sc[0],fc[0]+1):
  26             build_line(x,(i,sc[1]),(i,fc[1]))
  27     else:
  28         for i in range(sc[1],fc[1]+1):
  29             build_line(x,(sc[0],i),(fc[0],i))
  30     return
  31     
  32 ############################################################################
  33 ################### Relations between elements a and b #####################
  34 ############################################################################
  35 
  36 def relations(a,b,p1=None,q1=None,p2=None,q2=None):
  37     if a[0]==b[0]:
  38         if b[1]==p1 and a[0]==q1:
  39             return False
  40         if a[1]+1==b[1]:
  41             return True
  42     elif a[1]==b[1]:
  43         if b[1]==p2 and a[0]==q2:
  44             return False
  45         if a[0]+1==b[0]:
  46             return True
  47     elif p1 is not None and p2 is not None:
  48         if b[0]>q1-1 and b[1]>p1-1:
  49             if a[0]+1==b[0] and a[1]+1==b[1]:
  50                 return True
  51     return False
  52 
  53 ############################################################################
  54 ############# Function to return d-complete poset of class 1 ###############
  55 ############################################################################
  56 
  57 def poset_1(part): # part = [base,height,hline1,...,hline_n]
  58 		
  59     if len(part)>part[1]+2:
  60         raise ValueError("part can have a maximum length of part[1] (height=%s).\nThere can be a maximum of %s hlines."%(str(part[1]),str(part[1])))
  61 
  62     for i in range(2,len(part)):
  63         if part[i]+2>part[0]:
  64             raise ValueError("part[%s] (hline%s) is too long. It can have a maximum length of %s."%(str(i),str(i-1),str(part[0]-2)))
  65 
  66     x=[]
  67     
  68     build_block(x,(0,0),(1,part[0]-1))
  69     
  70     build_block(x,(2,0),(part[1]-1,1))
  71 
  72     ### Optional parts ###
  73     
  74     for i in range(2,len(part)):
  75         build_line(x,(i,2),(i,part[i]+1))
  76         
  77     def rel(a,b):
  78         return relations(a,b)
  79                  
  80     return Poset((x,rel),cover_relations=True)
  81     
  82 ############################################################################
  83 ############# Function to return d-complete poset of class 2 ###############
  84 ############################################################################
  85 
  86 def poset_2(part): # part = [base,vline1,...,vline_n]
  87 
  88     #if not all(x>y and x>0 and y>0 for x, y in zip(part, part[1:])):
  89     #    raise ValueError('part must be strictly decreasing and no zeros')
  90     #if part[0] > 1:
  91     #    if len(part) < 2:
  92     #        raise ValueError('part does not have enough elements')
  93     #    if part[1] != part[0]-1:
  94     #        raise ValueError('second element of part must be one less than first')    
  95     #elif part[0] > 2:
  96     #    if len(part) < 3:
  97     #        raise ValueError('part does not have enough elements')
  98     #    if part[2] < 1:
  99     #        raise ValueError('third element of part must be at least one') 
 100 
 101     x=[]
 102     
 103     x.append((0,0))
 104     
 105     build_block(x,(0,1),(1,part[0]-1))
 106     
 107     x.append((2,2))
 108     
 109     ### Optional parts ###
 110     
 111     for i in range(1,len(part)):
 112         build_line(x,(i+1,i+2),(i+part[i],i+2))
 113         
 114     def rel(a,b):
 115         return relations(a,b)
 116                  
 117     return Poset((x,rel),cover_relations=True)
 118 
 119 ############################################################################
 120 ############# Function to return d-complete poset of class 3 ###############
 121 ############################################################################
 122 
 123 def poset_3(part): # part = [htail1,base,height,dtail1]
 124     
 125     x=[]
 126     
 127     build_line(x,(0,0),(0,part[0]-1))
 128     
 129     build_block(x,(0,part[0]),(1,part[1]-1))
 130     
 131     build_block(x,(2,part[0]),(part[2]-1,part[0]+1))
 132     
 133     build_line(x,(2,part[0]+2),(part[3]+1,part[3]+1+part[0]))
 134          
 135     def rel(a,b):
 136         return relations(a,b,part[0]+2,2,part[0]+2,1)
 137     
 138     return Poset((x,rel),cover_relations=True)
 139     
 140 ############################################################################
 141 ############# Function to return d-complete poset of class 4 ###############
 142 ############################################################################
 143 
 144 def poset_4(part): # part = [htail1,base,height,vline1,...,vline_n]
 145   
 146     x=[]
 147     
 148     build_line(x,(0,0),(0,part[0]-1))
 149     
 150     build_block(x,(0,part[0]),(1,part[1]-1))
 151     
 152     build_line(x,(2,part[0]+1),(part[2]-1,part[0]+1))
 153     
 154     ### Optional parts ###
 155     
 156     for i in range(3,len(part)):
 157         build_line(x,(2,part[0]+i-1),(part[i]+1,part[0]+i-1))         
 158 
 159     def rel(a,b):
 160         return relations(a,b)
 161         
 162     return Poset((x,rel),cover_relations=True)
 163     
 164 ############################################################################
 165 ############# Function to return d-complete poset of class 5 ###############
 166 ############################################################################
 167 
 168 def poset_5(part): # part = [htail1,base,height,hline1,vline1]
 169     
 170     x=[]
 171     
 172     build_line(x,(0,0),(0,part[0]-1))
 173     
 174     build_block(x,(0,part[0]),(1,part[1]-1))
 175 
 176     build_line(x,(2,part[0]+1),(2,part[2]-1))
 177 
 178     build_line(x,(2,part[0]+2),(3,part[0]+3))
 179  
 180     ### Optional parts ###
 181     
 182     for i in range(3,len(part)-1):
 183         build_line(x,(3,part[0]+i-1),(2+part[i],part[0]+i-1))
 184 
 185     def rel(a,b):
 186         return relations(a,b,part[0]+3,3,part[0]+3,2)
 187         
 188     return Poset((x,rel),cover_relations=True)
 189     
 190 ############################################################################
 191 ############# Function to return d-complete poset of class 6 ###############
 192 ############################################################################
 193 
 194 def poset_6(part): # part = [htail1,base,height,hline1,hline2]
 195      
 196     x=[]
 197     
 198     build_line(x,(0,0),(0,part[0]-1))
 199     
 200     build_block(x,(0,part[0]),(1,part[1]-1))
 201     
 202     for i in range(2,4):
 203         build_line(x,(i,part[0]+1),(i,part[0]+3))
 204         
 205     build_line(x,(3,part[0]+1),(part[2]-1,part[0]+1))
 206      
 207     ### Optional parts ###
 208     
 209     for i in range(3,len(part)):
 210         build_line(x,(i-1,part[0]+4),(i-1,part[0]+3+part[i]))
 211         
 212     def rel(a,b):
 213         return relations(a,b,p1=part[0]+2,q1=3)
 214         
 215     return Poset((x,rel),cover_relations=True)
 216 
 217 ############################################################################
 218 ############# Function to return d-complete poset of class 7 ###############
 219 ############################################################################
 220 
 221 def poset_7(part): # part = [htail1,base,height,vline1,vline2]
 222      
 223     x=[]
 224     
 225     build_line(x,(0,0),(0,part[0]-1))
 226     
 227     build_block(x,(0,part[0]),(1,part[1]-1))
 228 
 229     build_block(x,(2,part[0]+1),(3,part[0]+3))
 230     
 231     build_line(x,(4,part[0]+1),(part[2]-1,part[0]+1))
 232     
 233     ## Optional parts ###
 234     
 235     for i in range(2,len(part)-1):
 236         build_line(x,(4,part[0]+i),(part[i+1]+3,part[0]+i))
 237              
 238     def rel(a,b):
 239         return relations(a,b,p2=part[0]+3,q2=1)
 240         
 241     return Poset((x,rel),cover_relations=True)
 242     
 243 ############################################################################
 244 ############# Function to return d-complete poset of class 8 ###############
 245 ############################################################################
 246 
 247 def poset_8(part): # part = [base,height,vline1,...,vline4]
 248      
 249     x=[]
 250     
 251     build_line(x,(0,0),(0,part[0]-4))
 252     
 253     build_block(x,(0,part[0]-3),(1,part[0]-1))
 254 
 255     build_block(x,(2,part[0]-2),(3,part[0]))
 256     
 257     build_line(x,(4,part[0]-2),(part[1]-1,part[0]-2))
 258     
 259     ### Optional parts ###
 260     
 261     for i in range(2,len(part)):
 262         if i < 4:
 263             build_line(x,(4,part[0]+i-3),(part[i]+3,part[0]+i-3))
 264         else:
 265             build_line(x,(3,part[0]+i-3),(part[i]+2,part[0]+i-3))
 266                      
 267     def rel(a,b):
 268         return relations(a,b)
 269         
 270     return Poset((x,rel),cover_relations=True)
 271     
 272 ############################################################################
 273 ############# Function to return d-complete poset of class 9 ###############
 274 ############################################################################
 275 
 276 def poset_9(part): # part = [base,height,vline1,...,vline4]
 277      
 278     x=[]
 279     
 280     build_line(x,(0,0),(0,part[0]-4))
 281     
 282     build_block(x,(0,part[0]-3),(1,part[0]-1))
 283 
 284     build_block(x,(2,part[0]-2),(3,part[0]))
 285 
 286     build_block(x,(3,part[0]-2),(4,part[0]+1))
 287  
 288     build_line(x,(5,part[0]-2),(part[1]-1,part[0]-2))
 289     
 290     for i in range(2,len(part)):
 291         if i == 5:
 292             build_line(x,(3,part[0]+2),(part[5]+2,part[0]+2))
 293         else:
 294             build_line(x,(5,part[0]+i-3),(part[i]+4,part[0]+i-3))
 295 
 296     build_line(x,(4,part[0]+1),(5,part[0]+2))
 297             
 298     def rel(a,b):
 299         return relations(a,b,part[0]+2,5,part[0]+2,4)
 300         
 301     return Poset((x,rel),cover_relations=True)
 302     
 303 ############################################################################
 304 ############ Function to return d-complete poset of class 10 ###############
 305 ############################################################################
 306 
 307 def poset_10(part): # part = [base,height,vline1,...,vline4]
 308      
 309     x=[]
 310     
 311     build_line(x,(0,0),(0,part[0]-4))
 312     
 313     build_block(x,(0,part[0]-3),(1,part[0]-1))
 314 
 315     build_block(x,(2,part[0]-2),(3,part[0]))
 316 
 317     build_block(x,(4,part[0]-2),(5,part[0]+2))
 318     
 319     build_line(x,(3,part[0]+1),(3,part[0]+2))
 320     
 321     build_line(x,(6,part[0]-2),(part[1]-1,part[0]-2))
 322     
 323     ### Optional parts ###
 324     
 325     for i in range(2,len(part)):
 326         build_line(x,(6,part[0]+i-3),(part[i]+5,part[0]+i-3))
 327     
 328     def rel(a,b):
 329         return relations(a,b,p2=part[0]+2,q2=3)
 330         
 331     return Poset((x,rel),cover_relations=True)
 332     
 333 ############################################################################
 334 ############ Function to return d-complete poset of class 11 ###############
 335 ############################################################################
 336 
 337 def poset_11(part): # part = [base,height,vline1,...,vline_n]
 338      
 339     x=[]
 340     
 341     build_line(x,(0,0),(0,part[0]-4))
 342     
 343     build_block(x,(0,part[0]-3),(1,part[0]-1))
 344 
 345     build_block(x,(2,part[0]-2),(3,part[0]))
 346 
 347     x.append((3,part[0]+1))
 348     
 349     build_block(x,(4,part[0]-2),(5,part[0]+2))
 350     
 351     build_line(x,(6,part[0]-2),(part[1]-1,part[0]-2))
 352     
 353     for i in range(2,len(part)):
 354         build_line(x,(6,part[0]+i-3),(part[i]+5,part[0]+i-3))
 355     
 356     def rel(a,b):
 357         return relations(a,b)
 358         
 359     return Poset((x,rel),cover_relations=True)
 360     
 361 ############################################################################
 362 ############ Function to return d-complete poset of class 12 ###############
 363 ############################################################################
 364 
 365 def poset_12(part): # part = [base,height,vline1,vline2]
 366      
 367     x=[]
 368     
 369     build_line(x,(0,0),(0,part[0]-4))
 370     
 371     build_block(x,(0,part[0]-3),(1,part[0]-1))
 372 
 373     build_block(x,(2,part[0]-2),(3,part[0]))
 374 
 375     build_block(x,(3,part[0]-2),(4,part[0]+2))
 376     
 377     build_line(x,(5,part[0]+1),(5,part[0]+2))
 378     
 379     build_line(x,(5,part[0]-2),(part[1]-1,part[0]-2))
 380     
 381     ### Optional parts ###
 382     
 383     for i in range(2,len(part)):
 384         build_line(x,(5,part[0]+i-3),(part[i]+4,part[0]+i-3))
 385     
 386     def rel(a,b):
 387         return relations(a,b,p1=part[0]+1,q1=5)
 388         
 389     return Poset((x,rel),cover_relations=True)
 390     
 391 ############################################################################
 392 ############ Function to return d-complete poset of class 13 ###############
 393 ############################################################################
 394 
 395 def poset_13(part): # part = [base,height,vline1]
 396      
 397     x=[]
 398     
 399     build_line(x,(0,0),(0,part[0]-4))
 400     
 401     build_block(x,(0,part[0]-3),(1,part[0]-1))
 402 
 403     build_block(x,(2,part[0]-2),(3,part[0]))
 404 
 405     build_block(x,(3,part[0]-2),(4,part[0]+2))
 406     
 407     build_line(x,(5,part[0]+1),(5,part[0]+2))
 408 
 409     build_line(x,(5,part[0]-2),(part[1]-1,part[0]-2))
 410             
 411     x.append((6,part[0]+2))
 412     
 413     ### Optional part ###
 414     
 415     for i in range(2,len(part)):
 416         build_line(x,(5,part[0]+i-3),(part[i]+4,part[0]+i-3))
 417     
 418     def rel(a,b):
 419         return relations(a,b)
 420         
 421     return Poset((x,rel),cover_relations=True)
 422     
 423 ############################################################################
 424 ############ Function to return d-complete poset of class 14 ###############
 425 ############################################################################
 426 
 427 def poset_14(part): # part = [base,height]
 428      
 429     x=[]
 430     
 431     build_line(x,(0,0),(0,part[0]-4))
 432     
 433     build_block(x,(0,part[0]-3),(1,part[0]-1))
 434 
 435     build_block(x,(2,part[0]-2),(3,part[0]+1))
 436 
 437     build_block(x,(3,part[0]-2),(4,part[0]+2))
 438     
 439     build_line(x,(5,part[0]+1),(5,part[0]+2))
 440     
 441     build_line(x,(6,part[0]+2),(7,part[0]+2))
 442     
 443     build_line(x,(5,part[0]-2),(part[1]-1,part[0]-2))
 444     
 445     def rel(a,b):
 446         return relations(a,b)
 447         
 448     return Poset((x,rel),cover_relations=True)
 449     
 450 ############################################################################
 451 ############ Function to return d-complete poset of class 15 ###############
 452 ############################################################################
 453 
 454 def poset_15(): # only one ideal: itself
 455      
 456     x=[]
 457 
 458     build_line(x,(0,0),(0,2))
 459     
 460     build_block(x,(0,3),(1,4))
 461 
 462     build_block(x,(2,4),(3,6))
 463 
 464     build_block(x,(3,4),(4,8))
 465     
 466     build_line(x,(5,7),(5,8))
 467     
 468     build_line(x,(6,8),(8,8))
 469     
 470     def rel(a,b):
 471         return relations(a,b)
 472         
 473     return Poset((x,rel),cover_relations=True)
 474     
 475 ############################################################################
 476 ######## Function to return d-complete poset of class classification #######
 477 ############################################################################
 478 
 479 def dCompletePoset(classification,description):
 480     
 481     if classification < 1 or classification > 15:
 482         raise ValueError('classification must be integer between 1 and 15')
 483         
 484     return dCompletePoset_class(classification, description)
 485 
 486 ############################################################################
 487 ######################## d-complete poset class ############################
 488 ############################################################################
 489 
 490 from sage.combinat.posets.posets import FinitePoset,PosetElement
 491 
 492 class dCompletePoset_class(FinitePoset):
 493 
 494     def __init__(self, classification, description):
 495     
 496         if classification==1:
 497             p = poset_1(description)
 498         if classification==2:
 499             p = poset_2(description)
 500         if classification==3:
 501             p = poset_3(description)
 502         if classification==4:
 503             p = poset_4(description)
 504         if classification==5:
 505             p = poset_5(description)
 506         if classification==6:
 507             p = poset_6(description)
 508         if classification==7:
 509             p = poset_7(description)
 510         if classification==8:
 511             p = poset_8(description)
 512         if classification==9:
 513             p = poset_9(description)
 514         if classification==10:
 515             p = poset_10(description)
 516         if classification==11:
 517             p = poset_11(description)
 518         if classification==12:
 519             p = poset_12(description)
 520         if classification==13:
 521             p = poset_13(description)
 522         if classification==14:
 523             p = poset_14(description)
 524         if classification==15:
 525             p = poset_15(description)
 526     
 527         FinitePoset.__init__(self,p)
 528 
 529         # This defines the type (class) of elements of poset.
 530         _element_type = PosetElement
 531         
 532