Guest User

Matroid Union working

a guest
Feb 15th, 2014
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.65 KB | None | 0 0
  1. #!/usr/bin/env sage -python
  2.  
  3. import sys
  4. from sage.all import *
  5.  
  6.  
  7. #Let Mi = (Si,Ii)
  8. #Matroid Union M = M1 v M2 v M3 v ... v Mk is defined as (S1 U S2 U S3 U ... U Sk,I1 v I2 v I3 v ... v Ik )
  9. #where I1 v I2 v I3 v ... v Ik = {i1 U i2 U i3 U ... U ik | ij \in Ij }
  10.  
  11. def MatroidUnion(*matroids):
  12.    
  13.     #Checking if the arguments given are valid
  14.  
  15.     if len(matroids) < 2:
  16.         raise ValueError("Atleast two arguments expected")
  17.  
  18.     for i in range(len(matroids)):
  19.         if not (isinstance(matroids[i],sage.matroids.matroid.Matroid) and matroids[i].is_valid()):
  20.             raise ValueError("Argument "+str(i+1)+" doesn't seem to be a matroid")
  21.         # if not (matroids[i].base_ring == ZZ or matroids[i].base_ring().is_field()):
  22.         #   raise NotImplementedError("MatroidUnion is only implemented for fields or integer ring")
  23.  
  24.     #Creating a matroid using the independent sets
  25.  
  26.     prev_ind_sets = set([])
  27.  
  28.     prev_matroid = matroids[0]
  29.     rank = prev_matroid.rank()
  30.    
  31.  
  32.     for r in range(rank+1):
  33.         for it in prev_matroid.independent_r_sets(r):
  34.             prev_ind_sets.add(it)  #Adding bases of first matroid
  35.  
  36.  
  37.     temp_ind_sets = set([]) #Using Set to eliminate duplicates
  38.    
  39.  
  40.     index=1
  41.  
  42.     while index < len(matroids):
  43.         curr_matroid = matroids[index]
  44.         rank = curr_matroid.rank()
  45.         for r in range(rank+1):
  46.             for it in curr_matroid.independent_r_sets(r):
  47.                 for s in prev_ind_sets:
  48.                     n = frozenset(set(s).union(it))
  49.                     temp_ind_sets.add(n)
  50.  
  51.  
  52.         prev_ind_sets=prev_ind_sets.union(temp_ind_sets)
  53.  
  54.  
  55.         index = index + 1
  56.  
  57.     M = Matroid(independent_sets=prev_ind_sets)
  58.     return M
  59.  
  60. ##Testing
  61. # M1=matroids.named_matroids.Fano()
  62. # M2=matroids.named_matroids.Vamos()
  63. # M=MatroidUnion(M1,M2)
Advertisement
Add Comment
Please, Sign In to add comment