#################################################################### # Bergman complexes of matroids from abstract nested set complexes # #################################################################### # This scripts constructs the nested set complex N(M,Irr) associated to a matroid and the minimal building set of all proper irreducible flats, whenever there is a group acting on M and the lattice of flats. It is specially well suited for matroids arrising from reflection arrangments, such as E6. # The algorithm works in an inductive way and takes advantage of the group action and the adjacencies of vertices. It requires the following input: #0) the ground set of the matroid. We use "pos" (the list of positive roots expresses as linear combinations of the basis) #1) a basis of the matroid. We use "alpha" (the dictionary of simple roots of E6). #2) the information of the coordinate-vectors of each element in the ground set with respect to the fixed basis of the matroid. We use "vectorPosCoordsAlpha". #3) the list of all proper irreducible flats, separated by rank. Each flat is described as the list of the indices of all the elements of the ground set it contains. We use "rankE6". #4) a list of the vertices of the complex (i.e. the irreducible flats of the matroid). Here, each vertex is describe by the flat: the list of the indices of all the elements of the ground set contained in the flat. We use "vertexIndexListE6". #5) A collection of orbit representatives of vertices, to take advantage of the group action. We use repsVert. #6) A dictionary encoding the action of the group generators on the list of vertices of the nested set complex. Each element of the dictionary is again a dictionary. We use "dict" computed in "settingsE6.sage" #7) the list of adjacencies between the vertices. This is done by constructing the edges of the nested set complex. We use "adjacencies" constructed in "BergmanFanE6.sage" using the function "adjacentVertices" from this file. # Recall the construction of nested sets given the adjacencies of vertices. # Given a representative of an l-dimensional cells C (given as a list of indices{i_1,..., i_k} of the vertices it contains) and a list of indices of potential vertices to add to C, it checks which ones of these vertices {i_{k+1}} satisfy the following: # The vertex i_{k+1} must be in the intersection of all lists adjacency[j] for al j in C. # All k-subsets of {i_1,...., i_{k+1}} of C U {i_{k+1}} must NOT give proper irreducible flats. Note that we already know that the subset C works. # The algorithm involves several functions: # (1) "joinOfCellAndVertex" constructs the join of a cell and a vertex (or give an empty cell when the join is not defined). The function does not check for the antichain condition. # (2) "pickAntichain" constructs a maximal antichain in a fixed cell containing a given vertex. It starts from the fixed cell and removes the vertices that are comparable to the reference vertex. # (3) "BuildCellsFromLowerCellsAndEdges" constructs a list of pairs [(x, vertices to attach to x): x in list] of potential representatives of l-dimensional cells from a list of cells of dimension (l-1)-cells, with the extra information of the edges in a simplicial complex. The function is typically used when the lower cells are representatives of distinct orbits. The nested set condition is checked later in the algorithm. # (4) "newCells" constructs cells of dimension l from a single (l-1)-dimensional cell and the list of all vertices in the nested set complex. For each vertex, it checks if the top cell is an antichain. If so, it checks the nested set proper of the top cell. In addition as well as the (l-1) cells obtains by swaping one vertex in the old cell with the reference vertex. The output may include more that one repr. per orbit. # (5) "buildCells" constructs higher-dimensional cells from a fixed cell of dimension l and the list of all (l-1)-cells. # (6) "newCellsFromCandidate" certifies which candidates cells give actual cells in the nested set complex associated to the proper irreducible flats. # (7) "newCellsFromBuildCells" constructs candidate cells in higher dimensions from a tuple (x,newx) of a cell x and a list newx of potential vertices to attach to each cell. # (8) "buildComplexFromRepsVertices" constructs the nested set complex inductively. At each step, the new cells include representatives of all higher-dimensional orbits, but there may include several representatives of the same orbit. The function "computeOrbitDecomposition" generates all cells of that dimension and avoids repetitions of orbits. # #(3) "RemoveComparables": allows us to only consider antichains including a given proper irreducible flat and flats in a fixed cell. We will remove the comparable ones to ensure the tests are performed on antichains of proper irreducible flats. ############################## # Auxiliary useful functions # ############################## import copy ################################## # 1) Coordinate vectors and back # ################################## # The following functions computes the coordinate-vector of all vectors in a list in terms of a given basis (labelleing 1 through len(basis)). The output is a list of lists or a list of vectors, respectively # begin is a list of linear combinations of elements in basis. # basis is given as a finite dictionary, e.g. {1: alpha[1], 2: alpha[2], 3: alpha[3], 4: alpha[4], 5: alpha[5], 6: alpha[6], 7: alpha[7]} def coordinateOfRoots(begin,basis): return [[v.coefficient(i) for i in range(1,len(basis)+1)] for v in begin] def coordinateOfRootsV(begin,basis): return [vector([v.coefficient(i) for i in range(1,len(basis)+1)]) for v in begin] # In order to simplify our calculations, we construct the list of vectors associated to the elements on a flat (given as a list of their indices in the ground set) #begin is an ordered list of numbers: # listOfPos is the list encoding the ground set # basis is a fixed basis of the matroid. def vectorsFromPosRootIndices(begin, listOfPos,basis): return coordinateOfRoots(numbersToPosRoots(begin,listOfPos),basis) # Conversely, the following function constructs vectors from coordinate vectors with respect to a fixes basis, as linear combinations of the basis. #begin is a list of vectors in Z^n #basis is a list of size n (the basis of R^n) #Output is a SET def rootsFromCoordinates(begin,basis): # return [(v,sum(v[i]*alpha[i+1] for i in range(0, len(alpha)))) for v in begin] return set([sum(v[i]*alpha[i+1] for i in range(0, len(alpha))) for v in begin]) ############################### # 2) Joint elements of a list # ############################### #The following function joins several lists into a single sorted list (after removing elements that appear more than once) # begin is a list of lists. def joinElements(begin): L = [] allLists= copy.copy(begin) while len(allLists)>0: oneList = allLists.pop() for x in oneList: if x not in L: L.append(x) # if x in L: # # print str(x) + ' was in the previous lists' # else: # L.append(x) return sorted(L) ######################################################### # 3) From subsets of the ground set to indices and back # ######################################################### # The following function converts a set of elements of the ground set to a sorted list of the the indices of these elements in the ground set. # begin is a set; # listOfPos is the ground set. def posRootsToNumbers(begin,listOfPos): return sorted(list(set([i for i in range(0,len(listOfPos)) for x in begin if x==listOfPos[i]]))) # The following function reverses the effect of the previous function: it gives the ground set elements from the list of indices #begin is a sorted list of numbers (indices for positive roots). def numbersToPosRoots(begin, listOfPos): return set([listOfPos[i] for i in begin]) ############################### # 4) Check elements in orbits # ############################### # The following function checks if a cell is in any orbit. # "begin" is a cell (described as a list of its vertices, i.e. indices of vertices) # "allm1Cells" is a list of all orbits of cells of dimension = len(begin)-1. # The output is True if begin is in one of the orbits or False if not. def checkOrbits(begin, allm1Cells): # we check that the lenths of the cell is the same as any cell in the orbit decomposition if len(allm1Cells[0][0]) != len(begin): return False checkMembership = set([]) for x in allm1Cells: if begin in x: return True else: print 'Keep checking' return False ######################################################################### # 4) From collections of flats to cells in the Bergman complex and back # ######################################################################### # The following functions allow us to rewrite flats as the indices of positive roots contained in them or as the positive roots contained in them. # These functions are used in "ListOfFlatsE6.sage" to construct the dictionary "E6Numbers" associated to the 7 proper irreducible flats of E6. # "vertexIndexList" contains the indices of all the positive roots in the irreducible flat associated to each vertex; # Cells are encoded as the indices of their constituent vertices. # "begin" is a list of indices in range(0, total number of vertices+1); def fromCellsToFlatNumbers(begin,vertexIndexList): return sorted([vertexIndexList.index(x) for x in begin]) # "begin" is a list of all the elements in the ground set of the matroid contained in a given flat; def fromFlatNumbersToCells(begin,vertexIndexList): return sorted([vertexIndexList[x] for x in begin]) # The next function gives an ordered list of all the positive roots in a collection of flats. The result need not be a flat. def joinRootsOfCells(begin,vertexIndexList): return joinElements(fromFlatNumbersToCells(begin,vertexIndexList)) #################################### # 5) Build adjacencies of vertices # #################################### # The following function decomposes the list of all vertices of the nested set complex into adjacent families. The dictionary of adjacencies will reduce the number of candidate vertices to be attached to a lower dimensional cell: they should form edges will all the vertices of the cell. This is precisely the information encoded in the adjacencies. # The output is a family (dictionary) whose kth entry is the list of vertices adjacent to the vertexof index k in the list of all Vertices. # CAUTION: The function is very slow. # "n" is the total number of vertices. We use "len(Vertices)" where "Vertices" is the list of all vertices (given as lists with one element). # "AllEdges" is the list of all edges of the nested set complex. They are computed using the function "buildCells" (at the end of this file) with the following input: # 1) "begin"= representatives of orbits of vertices; # 2) dimCells =2 def adjacentVertices(n,AllEdges): sepEdges = {} for k in range(0,n): print str(k) sepEdges[k] = [v for v in range(0,n) if sorted([k,v]) in AllEdges] return sepEdges ############################################### # ACTION OF A GROUP ON THE NESTED SET COMPLEX # ############################################### # We give 4 functions involving the action of a group on the nested set complex # (1) one describing the action on the vertices # (2) one describing the action on a cone (uses (1)) # (3) decomposition of a collection of cones into orbits. Typically, the collection consists of a list containing all representatives of orbits of cells in the nested set complex of the same (fixed) dimension. The list may contain more than one representative of the same orbit. # (4) a function that selects a representative of an orbit. ############################################################# # 1) Group action on the vertices of the nested set complex # ############################################################# # The following functions allows to compute the action of a group on the nested set complex by precalculating the action on the vertices. This function is used in "settingsE6.sage". # The function works as follows. Each generator s_j of the group W acting on the set of proper irreducible flats of a matroid (by acting on the ground set in a way compatible with the rank function) will be enconded as a list that has at position i the flat number of s_j[flat[i]]. # Here: flat number refers to the index of the associated vertex of the nested set complex. # "vertices" is a list. each entry of this list is a list of indices of elements in the ground set contained in the proper irreducible flat associated to that vertex. We use "vertexIndexListE6" computed in "settingsE6.sage" # "listPos" is the list of elements in the ground set. We use "pos" computed in "settingsE6.sage" # "basis" is a finite family (dictionary) associated to a fixed basis of the matroid. We use "alpha" computed in "settingsE6.sage". # "homs" is the list of homomorphisms obtained by the action of the generators of a group. We use "homsStdE6" computed in "settingsE6.sage" # Example: # homsStdE6[1](alpha[1]) # -alpha[1] # In the case of reflection arrangements, W is the Weyl group. For the reflection arrangement of E6, the Weyl group W(E6) acts on the list of roots, so a homomorphism may send a positive root to a negative root. For this reason, when acting on the flat, we need to record the sign of the root in the image. We do that by summing the coordinates of the image s(k) of the kth root w.r.t. the basis of simple roots, since all the coordinates have the same sign (unless they are 0). # If the sign is 1, then s(k) is already a positive root and s(k)*sign is a positive root. # If the sign is -1, then s(k)*sign will be a positive root. # This function can be adapted to other matroids when the action is not on the ground set but on the set = (ground set) U (-ground set). We should use the signs to have an honest action on the ground set. def computeHomsOnVertices(vertices,listPos,basis,homs): n = len(basis) # the list map will contain n lists: each of which records the action of each of the n simple reflections. map = [] for s in homs: # We set the list associated to a given homomorphism to be the empty list listForM = [] for j in range(0,len(vertices)): print str(j) # We pick the indices of all the positive roots of the proper irreducible flat associated to the jth vertex. x = vertices[j] # We convert the list of indices of positive roots describing the irreducible flat to the corresponding list of elements in the ground set. y = list(numbersToPosRoots(x,listPos)) # We need to take care of the signs to ensure the action gives back an element in the ground set. listForM.append(vertices.index(sorted(posRootsToNumbers(set(sorted([s(k)*sign(sum([coordinateOfRoots([s(k)],basis)[0][i] for i in range(0,n)])) for k in y])),listPos)))) map.append(listForM) return map # The output is a list of size = size(homs). The kth entry is the list corresponding to the action of the simple reflection s[k+1]. It is recorded as an action on the indices of vertices. # In "settingsE6.sage" we record the homs on vertices as |gens(W)| different lists and then create a list "dict" of dictionaries. This encoding allow us to easily compute orbits of sorted vertices in a valid cone. We will use use s[ ] for s one of the elements in the list of dictionaries ################################################ # 2) Orbits of cells in the nested set complex # ################################################ # The following function calculates the orbit of a cell in the nested set complex N(M,Irr). Each cell is describe by the indices of its constituent vertices (with respect to the list of vertices) # "begin" is a list of indices of vertices in the cell. Example [714] is the cell that has 1 vertex, namely the one indexed by 714. # "listOfPos" are the elements on the ground set of the matroid (in our case, the positive roots of the root system or the hyperplane numbers in the reflection arrangement). We use "pos". # "basis" is a finite family (dictionary) associated to a fixed basis of the matroid. We use "alpha" computed in "settingsE6.sage". # "homs" is given as list of dictionaries. The length of the list is the number of generators of the Group and homs[i] corresponds to the action of the ith-generator. Each homs[i] is a dictionary indicating the action on vertices of the nested set complex. The action is recorded in terms of the indices of a vertex in the list of vertices. We use "dict", computed in "settingsE6.sage" and recorded in "Input/listsE6.sage" def computeOrbitOfCell(begin,vertexIndexList,listPos,basis, homs): n = len(basis) # print n # "Symmetrizing" cell means adding to the list above the cells obtained by applying the actions in homs to the cell. #begin = sorted list of vertexIndices # basis will be alpha (finite family of simple roots) #homs will be dictionaries for homsStdE6 or homsStdE7 obtained from the list of flats: #We first convert the cone to the list of vertex numbers # toSymmetrize keeps a list of cells (vertex numbers) that are yet to be symmetrized in this way. In the beginning, it is just a copy of the singleton list given as begin input. #We keep the flats of each vertex in terms of expressions in the alphas because we can easily evaluate the simple-reflections on them. # beginNumbers = fromCellsToFlatNumbers(begin,vertexIndexList) cells = [copy.copy(begin)] toSymmetrize = [copy.copy(begin)] # print cells # print toSymmetrize # print toSymmetrize[-1] symmetrized =[] # print len(toSymmetrize) while len(toSymmetrize)>0: # Pick the first flat to be symmetrized cell = toSymmetrize.pop(-1) # print cell # print cell[0] # Add to cells the (previously unseen) cells obtained by applying the homomorphisms to its constituent vertices (we use the simple_reflections). #Here, previously unseen meens that we have not encounter this cell . Also add to toSymmetrize these cells for h in homs: newCell = sorted([h[k] for k in cell]) print str(newCell) if newCell not in cells: cells.append(newCell) if newCell not in toSymmetrize and newCell not in symmetrized: toSymmetrize.append(newCell) #Add cell to the list of symmetrized cells symmetrized.append(cell) print "Found: " + str(len(cells)) print "To symmetrize: " + str(len(toSymmetrize)) print "Symmetrized: " + str(len(symmetrized)) print " " return sorted(cells) # We test that we get the same output on each W(E6) representative of proper irreducible flats. The difference is that in orbitOfFlats each element is a flat (given by the index of the vertex), whereas we think of each vertex is a cell containing just one vertex. # listIrr = [[E6_1_Numbers[1]], [E6_2_Numbers[1]], [E6_4_Numbers[1]],[E6_7_Numbers[1]], [E6_8_Numbers[1]], [E6_12_Numbers[1]], [E6_13_Numbers[1]]] # trials = {} # orbitInNumbers= {} # for k in range(0,len(repsVert)): # print str(k) # trials[k] = computeOrbitOfCell(repsVert[k],vertexIndexListE6,pos,alpha,dict) # print len(trials[k]) # orbitInNumbers[k]=sorted([fromCellsToFlatNumbers([x], vertexIndexListE6) for x in listIrr[-1-k][0]]) # all([orbitInNumbers[k] == trials[k] for k in range(0,len(repsVert))]) # True ############################################################################################################################### # 3) Orbit decomposition from a list containing representatives of all the cells of fixed dimension of the nested set complex # ############################################################################################################################### # beginList is again a list of cells (lists of elements in vertexIndexList). It contains representatives of all orbits (although perhaps more than one). For example, to compute the orbit decomposition of all vertices we use "repsVert" computed in BergmanFanE6.sage. We can also use "Vertices". The result is exactly the same. # vertexIndexList is the list of vertices (as indices of elements of the ground set on the proper irreducible flat corresponding to each vertex) # listOfPos are the elements on the ground set of the matroid (in our case, the positive roots of the root system or the hyperplane numbers in the reflection arrangement) # "basis" is a finite family (dictionary) associated to a fixed basis of the matroid. We use "alpha" computed in "settingsE6.sage". # homs is a list of dictionaries recording the action of the generators of the group on the vertices of the nested set complex. It is used as an input for the function "computeOrbitOfCell". We us "dict" computed in "settingsE6.sage". # In our applications of this function, the elements of beginList consist of the join of all lists of found cones in a given dimension) def computeOrbitDecomposition(beginList,vertexIndexList,listOfPos,basis,homs): setOfTuplesToSymmetrize = copy.copy(beginList) # setOfTuplesToSymmetrize = [[x] for x in beginList] print setOfTuplesToSymmetrize Orbit = [] while len(setOfTuplesToSymmetrize)>0: #Pick the first tuple to be symmetrized tuple = setOfTuplesToSymmetrize.pop() Orbit.append(computeOrbitOfCell(tuple,vertexIndexList,listOfPos,basis,homs)) setOfTuplesToSymmetrize = [x for x in setOfTuplesToSymmetrize if x not in Orbit[-1]] return sorted(Orbit) # Test: # We get the same lenghts and orbits as for each vertex representative, up to permutations: #trial = computeOrbitDecomposition(repsVert,vertexIndexListE6,pos,alpha,dict) # [len(trial[k]) for k in range(0, len(trial))] # [36, 120, 270, 45, 216, 27, 36] # trial[0]==computeOrbitOfCell(repsVert[6],vertexIndexListE6,pos,alpha,dict) # True # trial[1]== computeOrbitOfCell(repsVert[5],vertexIndexListE6,pos,alpha,dict) # True # trial[2]== computeOrbitOfCell(repsVert[4],vertexIndexListE6,pos,alpha,dict) # True # trial[3]== computeOrbitOfCell(repsVert[3],vertexIndexListE6,pos,alpha,dict) # True # trial[4]== computeOrbitOfCell(repsVert[2],vertexIndexListE6,pos,alpha,dict) # True # trial[5]== computeOrbitOfCell(repsVert[1],vertexIndexListE6,pos,alpha,dict) # True # trial[6]== computeOrbitOfCell(repsVert[0],vertexIndexListE6,pos,alpha,dict) # True ############################ # 4) Orbit Representatives # ############################ # begin should be a list of lists (list of all orbits of cells of a fixed dimension) # fromCellsToFlatNumbers is sorted (lexicographically) so we can pick the first element in the list as a representative #Given a list (begin), the function picks its first element as a representative for the list. Our list is usually sorted in some way which makes the choice of representative more meaningful. def pickRepresentativeOfOrbit(begin): return [x[0] for x in begin] #################################################### # INDUCTIVE CONSTRUCTION OF THE NESTED SET COMPLEX # #################################################### # The following functions are used to construct W-representatives of all cells of a fixed dimension l in the nested set complex starting from a list of (l-1)-dimensional orbit representatives. These functions allow us to build the nested set complex inductively, starting from the vertex representatives. Intermediate functions (with a stopping step) allow to construct the edges, and give adjacency of vertices. This information speeds up the construction of higher dimensional cones. # The following are the necessary steps to construct the nested set complex with respect to the list of proper irreducible flats. # (1) Nested set complexes are constructed from antichains and give proper irreducible flats, so the first think we need to do is check for comparable elements between a reference vertex and the vertices of a lower dimensional cone. We will remove the comparable ones to ensure the tests are performed on antichains of proper irreducible flats. # (2) we construct the join of a cell and a vertex (or give an empty cell when the join is not defined). The join involves non-comparable vertices. # (3) we construct higher-dimensional cells from a fixed cell of dimension l and the list of all (l-1)-cells. # (4) we construct higher dimensional cells from a list of orbit-representatives of all the cells of dimension (l-1) and the list of all. The new cells include representatives of all higher-dimensional orbits, but there may include several representatives of the same orbit. # WARNING: if we choose a differente building set, the algorithm might fail since the nested set complex need not be simplicial. ############################################################### # (1) Check the antichain condition on a cell against a vertex # ############################################################### # The following function checks the antichain condition for a vertex v against each vertex in a cell C. It outputs the maximal antichain in v U C containing v. We will use it when we apply the function "joinOfCellAndVertex" in case this antichain is just {v}. # "begin" is a cell of the nested set complex, given as a list of flat numbers (i.e. vertex indices). # "vertex" is an order list of numbers (corresponding to the indices of all positive roots in the flat). We use "vertexIndexListE6[k]" for any k in range(0,750). # "vertexIndexList" is the list of vertices of the nested set complex, each of which is described as vertex. We use "vertexIndexListE6". # "rankVector" is a list, whose kth. entry is the list of all vertices (i.e. their associated proper irreducible flats) of that rank. The entries of each list are encoded as vertex. We use "rankE6". # "vectorPos" is the list of coordinate vectors (written as lists) of all the elements of the ground set in terms of a fixed basis of the matroid. We use the output of the function "coordinateOfRoots", namely "vectorPosCoordsAlpha". # "listOfPos" is the list of elements of the ground set. We use "pos". # "basis" is a fixed basis of the matroid. We use "alpha". # Note that the output is a sublist of begin. When calling this function we typically must add the index of vertex by hand. def pickAntichain(begin,vertex, vertexIndexList): # We start by copying the list begin (of vertex indices in the cell) since we'll remove each vertex (one at a time) and test for comparability against the reference vertex. test = copy.copy(begin) # We start a list of elements in begin not comparable to vertex, test each vertex in begin against our reference vertex and add it to the list whenever these two are not comparable. notcomparable = [] # print test while len(test)>0: vv = test.pop(-1) # print vv # We covert the vertex we remove from test to the list of indices of elements in the ground set that are contained in the associated flat, since this is the format we have for "vertex" and it makes it easier to compare. v = vertexIndexList[vv] if set(v).issubset(set(vertex)) or set(vertex).issubset(set(v)): print 'The vertex ' + str(vv)+ ' fails the antichain condition' # we add the vertex to the list of comparable elements to "vertex" else: notcomparable.append(vv) if len(notcomparable) == len(begin): print 'Passes antichain condition' else: w = len(begin)-len(notcomparable) print str(w) + ' many elements fail the antichain condition' return sorted(notcomparable) # # Tests for E6: # vertexIndexListE6[10] # [10] # vertexIndexListE6[36] # [0, 2, 9] # vertexIndexListE6[47] # [1, 6, 15] # vertexIndexListE6[159] # [0, 2, 3, 6, 9, 12] # pickAntichain([159],vertexIndexListE6[36],vertexIndexListE6) # The vertex 159 fails the antichain condition # 1 fail the antichain condition # [] # pickAntichain([36,10],vertexIndexListE6[47],vertexIndexListE6) # Passes antichain condition # [10, 36] # pickAntichain([36,10],vertexIndexListE6[159],vertexIndexListE6) # The vertex 36 fails the antichain condition # 1 fail the antichain condition # [10] # pickAntichain([47],vertexIndexListE6[159],vertexIndexListE6) # Passes antichain condition # [47] ####################################### # (2) Join of a cell and a new vertex # ####################################### # Our first routine constructs higher dimensional cells from two inputs: # 1) an ordered list of vertex indices (a low dimensional cone); # 2) an a new vertex. The vertex is enconded as a list of indices of pos roots in each flat. # "begin" is a cell of the nested set complex, given as a list of flat numbers (i.e. vertex indices). # "vertex" is an order list of numbers (corresponding to the indices of all positive roots in the flat). We use an element of "vertexIndexListE6". # "vertexIndexList" is the list of vertices of the nested set complex, each of which is described as vertex. We use "vertexIndexListE6". # "rankVector" is a list, whose kth. entry is the list of all vertices (i.e. their associated proper irreducible flats) of that rank. The entries of each list are encoded as vertex. Each rankVecto[k] is ordered lexicographically. In particular, the length of the vector is the rank of the ground set. We use "rankE6". # "vectorPos" is the list of coordinate vectors (written as lists) of all the elements of the ground set in terms of a fixed basis of the matroid. We use the output of the function "coordinateOfRoots" # "listOfPos" is the list of elements of the ground set. We use "pos". # "basis" is a fixed basis of the matroid (given as a finite family). We use "alpha". # We assume the ground set is an irreducible flat. # The output is an irreducible flat (and its rank) obtained as the join or empty if: # (i) the rank is not maximal (so the flat is not proper), and # (ii) the join is not among the list of all proper irreducible flats. # NOTE: we don't check the antichain condition in the function "joinOfCellAndVertex" since we will use this function mainly for maximal antichains. # We output [r, list]. We will only care when "list" = [], that is when the flat of the join is proper but not irreducible. This will be the case when we will have a nested set. def joinOfCellAndVertex(begin,vertex, vertexIndexList,rankVector,vectorPos,listOfPos,basis): # begin is a single cell (given as a list of vertex indices) # vertex is an ordered list of numbers (the corresponding to the indices of all elements in the ground set that belong to the flat) # rank Vector is a list when on each entry we have the lists of all irreducibles flats (grouped by orbits) of that rank. Each flat is encoded by the indices of all elements of the ground set that belog to the flat. # listOfPos is the list of all positive vectors # basis is a fixed basis (finite family (alpha)) # output: irreducible flat obtained as the join or empty if rank is max or join is not irreducible. We also output the rank. # candidate is a collection of all the elements inside the vertices of the potential new cell. It need not be a flat since it need not be closed. # convert the cell in begin into a list of lists of ground set indices (like vertex is) oldCone = [vertexIndexList[x] for x in begin] candidate=sorted(list(set(joinElements(oldCone +[vertex])))) print candidate r = rank(matrix(vectorsFromPosRootIndices(candidate,listOfPos,basis))) print r # # check if there is no antichain containing the vertex and included in begin. The resulting candidate cell is valid and must be output. # print oldCone # print vertex antichainInBegin = pickAntichain(begin,vertex, vertexIndexList) print antichainInBegin if antichainInBegin ==[]: return [r,[]] # The length of the rank Vector is the rank of the matroid. Since we want to consider proper flats, we must check if r < rank of the matroid. if r=0 because the rank r was not maximal, so there is a proper flat containing candidate. If len(B) = 0 it is because there is no irreducible proper flat. if len(B)>1: print B print 'the pair' + str((begin,vertex)) + 'indicates a bug' return elif len(B)==1: print B candidate = B print 'the join is proper and irreducible' # return [r,B] else: B=[] candidate = B print 'the flat is proper but not irreducible' # We reach this point if the rank was maximal, so the only flat containing candidate is the ground set. else: B = range(0,len(pos)) candidate = B print 'the flat is not proper' return [r,candidate] # Tests: we check the antichain condition but only consider it whenever there is no antichain except for the one considering the reference vertex. This works well for vertices that are comparible and yield edges. If we did not check the antichain condition, we would not output this vertex. #Example 1: the vertices 36 (coming from FF[2]) and 159 (coming from FF[4]) do form a nested set since FF[2] is a subset of FF[4] and their rank is not maximal (it equals 3) # load("ListOfFlatsE6.sage") # posRootsToNumbers(FF[2],pos) # [0, 2, 9] # vertexIndexListE6[159] # [0, 2, 3, 6, 9, 12] # edge36_159 = joinOfCellAndVertex([vertexIndexListE6.index(posRootsToNumbers(FF[2],pos))], vertexIndexListE6[159], vertexIndexListE6, rankE6,coordinateOfRoots,pos,alpha) # print edge36_159 # [3, []] # antichain # Example 2: # joinOfCellAndVertex([0],vertexIndexListE6[702], vertexIndexListE6, rankE6,coordinateOfRoots,pos,alpha) # The join flat is not proper. We shouldn't have a edge here and indeed, the answer is: # [6, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35]] ################################################################################ # (3) Check vertices of a cell that are not comparable with a reference vertex # ################################################################################ # The following function checks if a given lower dimensional cell of fixed dimension l given as an ordered list of vertex indices (begin) does not produce a proper irreducible flat when attached to a given vertex. It returns the maximal antichain of vertices of the cell that can be added to the reference vertex. This function will allow to restrict the test of nested sets to antichains involving the extra vertex. For this reason we call them noncomparable. # "begin" is a cell of the nested set complex, given as a list of irreducible flats (i.e. the list of index of elements in the ground set). # "vertex" is an order list of numbers (corresponding to the indices of all positive roots in the flat). We use "vertexIndexListE6[k]" for any k in range(0,750). # "vertexIndexList" is the list of vertices of the nested set complex, each of which is described as vertex. We use "vertexIndexListE6". # "rankVector" is a list, whose kth. entry is the list of all vertices (i.e. their associated proper irreducible flats) of that rank. The entries of each list are encoded as vertex. We use "rankE6". # "vectorPos" is the list of coordinate vectors (written as lists) of all the elements of the ground set in terms of a fixed basis of the matroid. We use the output of the function "coordinateOfRoots", namely "vectorPosCoordsAlpha". # "listOfPos" is the list of elements of the ground set. We use "pos". # "basis" is a fixed basis of the matroid. We use "alpha". # def removeComparables(begin,vertex, vertexIndexList,rankVector,vectorPos,listOfPos,basis): # n = len(basis) # # print n # toTest = copy.copy(begin) # # we replace the cell with a maximal antichain containing vertex and contained in begin. # not comparable = pickAntichain(toTest,vertex, vertexIndexList) # return sorted(notComparable) # # notComparable = [] # # # We record the index of the vertex in the list of vertices # # index = vertexIndexList.index(vertex) # # # print index # # while len(toTest)>0: # # # We remove one vertex of the cell at a time and see if we always get a flat outside the list of proper irreducible flats from the join of the vertex we removed and the fixed reference vertex. # # newToTest = toTest.pop() # # # Next we encode the potentical edge to test by the vertices rather than flats to be able to compute the join of the subcell and the vertex # # newCellToTest = fromFlatNumbersToCells(sorted([newToTest]),vertexIndexList) # # print newCellToTest # # # We join the vertex to the maximal antichain and test if the resulting flat is valid or not. If valid, we check the nested set proper for the maximal antichain. # # C = joinOfCellAndVertex(newCellToTest,vertex, vertexIndexList,rankVector,vectorPos,listOfPos,basis) # # print C # # # If the join gives [] is because the resulting flat was the whole ground set or it was not irreducible, so the join gives a flat we want and hence the set is nested. # # if C[1] == []: # # notComparable.append(newToTest) # # else: # # # # In this case, the join is a proper irreducible flat and we obtain a new high dimensional cell. We record the new cell as its sorted list of vertices. # # D = fromCellsToFlatNumbers(C[1], vertexIndexList) # # # print D # # # if the new cell is not the edge joining the original vertex with the vertex we are testing, then we declare the testing vertex to be not comparable # # if D[0] != index and D[0]!=newToTest: # # notComparable.append(newToTest) # # else: # # print str(newToTest) + " elements comparable with the given vertex" # # return sorted(notComparable) ############################################## # (3) Build candidate cells from adjacencies # ############################################## # The following function builds candidate k-dimensional cells in the nested set complex from a list of (k-1)-dimensional cells (begin) and the adjacency list (adjacent) # "begin" is a list of cells ( = list of indices of constituent vertices) # adjacent is a list of length = total number of vertices. Each entry of adjacent is a list of indices of vertices adjacent to a given one. # The output is a list of tuples (x, newx), where newx is a list of indices of vertices. # The candidate cells are later checked to be cells in the nested set complex. # The output is a list of tuples (x,neww), where both variables are lists of vertex indices. def BuildCellsFromLowerCellsAndEdges(begin,adjacent): reps = copy.copy(begin) conesHigher = [] p = len(reps[0]) while len(reps)>0: x = reps.pop() print str(x) # We check which vertices we can add to a representative cell x in begin by intersecting all possible adjacencies newx = set(adjacent[x[0]]) for k in range(1,p): newx = newx.intersection(set(adjacent[x[k]])) # newx is the list of all indices of vertices we can potential append to x. We must check the nested property, as well as the antichain condition of the output. newCellCandidates = (x,newx) conesHigher.append(newCellCandidates) return conesHigher ################################################################################################################################# # (4) Higher dimensional cells from a fixed cell of dimension l and the list of all (l-1)-cells without adjacencies information # ################################################################################################################################# # The following function starts from a cell and a list of potential vertices (each given as the flat information (indices of all ground set elements in the flat)), and constructs higher-dimensional cells. If we don't have information about adjacencies among vertices, then the potential vertices will be all vertices. If we have the adjacenty information, the list of potential vertices will be much smaller. # We run over the list of potential vertices. For each vertex on the list, which we call "reference vertex", we construct: # new cell = old cell U reference vertex # We test the nested set property of the new cell in two steps. # 1) we check if the whole new cell is an antichain. If so, it checks that the join is not a proper irreducible flat. # 2) Secondly it swaps one vertex of the cell with the reference vertex and checks if the resulting cells of lower dimension are in the list of all lower dimensional cells. This will automatically certify the nested set property for subsets. It doesn't check the original cell since it is assumed it satisfies the nested property. Indeed, we will only use this function in the inductive construction so the input is always a cell in the nested set complex. # 3) if the whole new cell is not an antichain, it checks (2) as well. # Note: The function It is used in the function "buildCells" which allows to construct the edges and the list of adjacencies. # "begin" is a cell of dimension l in the nested set complex. It is encoded as a list of flat numbers (the vertices of the input cone), which we transform into list of ordered list of numbers (i.e. the flat!) # "vertexIndexList" is the list of vertices of the nested set complex, each of which is described as an ordered list of numbers (corresponding to the indices of the ground set elements in the flat). We use "vertexIndexListE6". # "rankVector" is a list, whose kth. entry is the list of all vertices (i.e. their associated proper irreducible flats) of that rank. The entries of each list are encoded as vertex. We use "rankE6". # "vectorPos" is the list of coordinate vectors (written as lists) of all the elements of the ground set in terms of a fixed basis of the matroid. We use the output of the function "coordinateOfRoots" # "listOfPos" is the list of elements of the ground set. We use "pos". # "basis" is a fixed basis of the matroid. We use "alpha". # "allm1Cells" is the list of all orbits of cells of dimension l in the nested set complex. Each cell is encoded as a list of vertex indices. # "dimCells" should be l+1 = the dimension of the new cell we obtain by attaching a vertex to begin. def newCells(begin,listOfPotentialVertices, vertexIndexList, rankVector,vectorPos,listOfPos,basis,allm1Cells,dimCells): # begin is a single cell = a list of vertices which we transform into a list of ordered list of numbers of ground set indices (i.e. the associated flats!) # We first check that we expect to get a cell of dimension 1 higher. If not, we exit without further computations. We check this condition since we will use it in the inductive step. print begin if dimCells != len(begin)+1: return else: n = len(basis) # We copy the list of vertices, since we will pop one vertex at a time to check if we can attach it to the cell begin. Each vertex is described as an ordered list of numbers (corresponding to the indices of the ground set elements in the flat) listOfVertices = copy.copy(listOfPotentialVertices) # We use the variable "cellsFromlowDim" to record the higher dimensional cells we obtain from begin. We start with the empty list and append a new cell each time we find one. cellsFromLowDim = [] # print str(cellsFromLowDim) # print begin # We construct all subcells of the given cell of dimension dimCells-1 (it is simplicial). The result is a sorted list of lists. If dimCells-2 = 0, it has a single element: the empty cell. powersOfBegin = Combinations(begin, dimCells-2).list() print powersOfBegin # We go over all vertices in the list "vertexList" and see which ones we can attach to the cell "begin". while len(listOfVertices)>0: v=listOfVertices.pop() # print v # We convert the flat to its corresponding index in the vertexIndexList, i.e. the vertex number in the nested set complex. w =vertexIndexList.index(v) if w in begin: print "vertex was in the cell" else: # First, we check the nested set proper if begin U v is an antichain. maxAntichain = pickAntichain(begin,v, vertexIndexList) print maxAntichain if len(maxAntichain) == len(begin): print 'Must check the nested set property for the big cell' print v print begin newCell = joinOfCellAndVertex(begin, v, vertexIndexList,rankVector,vectorPos,listOfPos,basis) # We check if the join of all the flats is not valid (gives []) to move on. if newCell[1] != []: print 'the maximal cell was not valid. Move on the the next vertex' else: # Finally, check the nested set property on the potential l=len(begin)-1 dimensional cells. checkSubsets = [sorted(x+[w]) for x in powersOfBegin] print checkSubsets if all([checkOrbits(y,allm1Cells) for y in checkSubsets]): D = sorted(begin+[w]) # print D print begin cellsFromLowDim.append(D) else: print 'One facet failed. Try next vertex' # #If the maximal cell was not an antichain, need only ceck lower cells: The code is the same as above but we do not repeat the computations. else: print 'No need to check maximal set' # Finally, check the nested set property on the potential l=len(begin)-1 dimensional cells. checkSubsets = [sorted(x+[w]) for x in powersOfBegin] print checkSubsets if all([checkOrbits(y,allm1Cells) for y in checkSubsets]): D = sorted(begin+[w]) # print D print begin cellsFromLowDim.append(D) else: print 'one facet failed. Try next vertex' return sorted(cellsFromLowDim) ################################################################ # (5) Build higher dimensional cones from cell representatives # ################################################################ # The next function picks a list of cones of fixed dimension and constructs all new cones of one dimension higher. It uses no information from adjacencies. It will be used, in particular, to construct the edges of the nested set complex and, hence construct the adjacencies. # "begin" is a list of orbit representatives of cells of dimension l. Each cell is given as its list of vertices. # "vertexIndexList" is the list of vertices of the nested set complex, each of which is described as an ordered list of numbers (corresponding to the indices of the ground set elements in the flat). We use vertexIndexListE6. # "rankVector" is a list, whose kth. entry is the list of all vertices (i.e. their associated proper irreducible flats) of that rank. The entries of each list are encoded as vertex. We use rankE6. # "vectorPos" is the list of coordinate vectors (written as lists) of all the elements of the ground set in terms of a fixed basis of the matroid. We use the output of the function "coordinateOfRoots" # "listOfPos" is the list of elements of the ground set. We use pos. # "basis" is a fixed basis of the matroid. We use alpha. # oldCones is the list of all cells of dimension l in the nested set complex # "dimCells" is l+1, the dimension of the new cells obtained by attaching a vertex to a cell in begin. def buildCells(begin,vertexIndexList, rankVector,vectorPos,listOfPos,basis,oldCones,dimCells): # We first check that we expect to get a cell of dimension 1 higher. If not, we exit without further computations. We check this condition on any element of the list begin. if dimCells != len(begin[0])+1: return else: # We start by copying the list of representatives of cells begin since we will pop elements of it and we do not want to modify the variable "begin" reps = copy.copy(begin) # conesHigher = [] allConesHigher =[] while len(reps)>0: # # We remove a cell from "reps" to build all new cells containing x of dimension dimCells = len(x). x = reps.pop() print str(x) # # We build all cells containing x of dimension dimCells = len(x). The function newCells ensures the output is a nested cell. newx = newCells(x,vertexIndexList,vertexIndexList, rankVector,vectorPos,listOfPos,basis,oldCones,dimCells) print str(newx) # We can uncomment the following line and the return line to check that newx indeed contains x. # conesHigher.append([(x,newx)]) print " " print "done with cell " + str(x) #str(vertexIndexList.index(x)) print " " allConesHigher.extend(newx) # We can uncomment the line to check that the higher dimensional cells contain the lower dimensional cells. # return conesHigher return allConesHigher ################################################################# # New cells from candidates cells obtained using adjacencies # ################################################################# # The following function certifies which candidate cells in higher dimensions are cells in the nested set complex. We use the function "newCells" but changing the data to feed to "newCells". # "begin" is a tuple the form(x,newx) obtained from BuildCellsFromLowerCellsAndEdges # "vertexIndexList" is the list of vertices of the nested set complex, each of which is described as an ordered list of numbers (corresponding to the indices of the ground set elements in the flat). We use vertexIndexListE6. # "rankVector" is a list, whose kth. entry is the list of all vertices (i.e. their associated proper irreducible flats) of that rank. The entries of each list are encoded as vertex. We use rankE6. # "vectorPos" is the list of coordinate vectors (written as lists) of all the elements of the ground set in terms of a fixed basis of the matroid. We use the output of the function "coordinateOfRoots" # "listOfPos" is the list of elements of the ground set. We use pos. # "basis" is a fixed basis of the matroid. We use alpha. # oldCones is the list of all cells of dimension l in the nested set complex # "allm1Cells" is the list of all orbits of cells of dimension l-1 = dim(x) in the nested set complex, where l is the dimension of the new cells obtained by attaching a vertex in newx to x. def newCellsFromCandidate(begin,vertexIndexList, rankVector,vectorPos,listOfPos,basis,allm1Cells): # vertexIndexList will be vertexRepsE6 or vertexRepsE7 (a list of lists) # "begin" is a tuple the form(x,newx) obtained from BuildCellsFromLowerCellsAndEdges. x is a list of indices and newx is a set of vertex indices. # vertex is a se ordered list of numbers # We record the length of the basis (the rank of the matroid) n = len(basis) # The dimension of the lower dimensional cells is obtained from any cell in allm1Cells[0] dimCells = len(allm1Cells[0][0])+1 # the list of potential vertices to attached to the cell begin[0] vertexList = copy.copy(begin[1]) flatsFromVertexList = sorted([vertexIndexList[x] for x in vertexList]) # print begin cellsFromLowDim = newCells(begin[0], flatsFromVertexList, vertexIndexList, rankVector,vectorPos,listOfPos,basis,allm1Cells,dimCells) return sorted(cellsFromLowDim) ################################################# # (8) Build cones from vertices and lower cones # ################################################# # This auxiliary function is required in the inductive step of the construction. It checkes which potential vertices will be attached to cell representatives in lower dimension. # "begin" is the list of all tuples the form (x,newx) obtained from BuildCellsFromLowerCellsAndEdges from the representatives of lower dimensional cells. # "vertexIndexList" is the list of vertices of the nested set complex, each of which is described as an ordered list of numbers (corresponding to the indices of the ground set elements in the flat). We use vertexIndexListE6. # "rankVector" is a list, whose kth. entry is the list of all vertices (i.e. their associated proper irreducible flats) of that rank. The entries of each list are encoded as vertex. We use rankE6. # "vectorPos" is the list of coordinate vectors (written as lists) of all the elements of the ground set in terms of a fixed basis of the matroid. We use the output of the function "coordinateOfRoots" # "listOfPos" is the list of elements of the ground set. We use pos. # "basis" is a fixed basis of the matroid. We use alpha. # oldCones is the list of all cells of dimension l in the nested set complex # "allm1Cells" is the list of all orbits of cells of dimension l-1 = dim(x) in the nested set complex, where l is the dimension of the new cells obtained by attaching a vertex in newx to x. def newCellsFromBuildCells(begin,vertexIndexList,rankVector,vectorPos,listOfPos,basis,allm1Cells): toTest = copy.copy(begin) allNewCones = [] while len(toTest)>0: x=toTest.pop() newCells = newCellsFromCandidate(x,vertexIndexList,rankVector,vectorPos,listOfPos,basis,allm1Cells) # print newCells allNewCones.extend(newCells) return sorted(allNewCones) ####################################################### # (9) Nested set complex via proper irreducible flats # ####################################################### # The following function constructs the nested set complex together with the orbit decomposition of the cells and the f-vector. # The result is a list containing 2 entries: # 1) the list encoding the f-vector of the complex (a vector with k entries) # 2) the list with k entries, each of which is the orbit decomposition of the cells of fix dimension. # Notice: We save the representative cells and the orbit decomposition of all intermmediate cells of fixed dimension as plain text files. #The required imput is the following: # 1) begin is a list of indices of orbit-representatives of vertices. We use "repsVert" in "BergmanFanE6.sage". # repsVert = [[714], [687], [471], [426], [156], [36], [0]] # 2) vertexIndexList is a list of the vertices of the complex (i.e. the irreducible flats of the matroid). Here, each vertex is describe by the flat: the list of the indices of all the elements of the ground set contained in the flat. We use "vertexIndexListE6". # 3) rankVector is the list of all proper irreducible flats, separated by rank. Each flat is described as the list of the indices of all the elements of the ground set it contains. We use "rankE6". # 4) vectorPos is a list of lists, each of which gives the coordinate-vectors of each element in the ground set with respect to the fixed basis of the matroid. We use "vectorPosCoordsAlpha". # 5) listOfPos is the list obtained from the ground set of the matroid. We use "pos" (the list of positive roots expresses as linear combinations of the basis). # 6) basis is a finite family (dictionary with keys =1, 2, ..., rank of the matroid) containing a fixed basis of the matroid. We use "alpha" (the dictionary of simple roots of E6). # 7) homs is a dictionary encoding the action of the group generators on the list of vertices of the nested set complex. Each element of the dictionary is again a dictionary. We use "dict" computed in "settingsE6.sage" # 8) adjacent is a list of length = len(vertexIndexList) encoding the adjacencies between the vertices. The kth entry contains the list of all indices of vertices adjacent to the kth.vertex. Each list is obtained using the function "adjacentVertices" defined earlier. def buildComplexFromRepsVertices(begin,vertexIndexList,rankVector,vectorPos,listOfPos,basis,homs,adjacent): n = len(basis) fvector = [1] # We copy the list of representatives since we will be removing one representative at a time. Since computeOrbitDecomposition uses the cell input, we must transform the vertices into cells. repsBegin = copy.copy(begin) # print repsBegin # We compute all vertices of the nested set complex from a list containing all orbit representatives (there could be more vertices than needed but the function takes care of that). DecompOrbits=[computeOrbitDecomposition(repsBegin,vertexIndexList,listOfPos,basis,homs)] # print DecompOrbits # We list the representatives of vertices obtained from the orbit decomposition we just computed. # representatives = list containing a copy the list of representatives of vertices(DecompOrbits). # The list will contain lists of all representatives, classified by dimension. representatives = [pickRepresentativeOfOrbit(DecompOrbits[0])] # allCells will be the list of all the cells computed at the kth step (they will have dimension k-1. Each cell is described as a list of its constituent vertices (in range(0, 750)). We will save the output as a sage object in case we need to restart the calculation at a given step. fvector.append(sum([len(x) for x in DecompOrbits[-1]])) # # We comment the following lines if we don't want to save the output as a plain text file: # # We record the orbit decomposition of all vertices in a plain text file. f = file('../Output/CellsOfDim'+ str(0)+'.txt', 'w') f.write('RepresentativesOrbitsAndCellsOfDim'+str(0) +'='+ str([representatives[-1],DecompOrbits[-1]])) f.close() # Since we know the adjacencies, we then can reconstruct the edges very fast. We just need to pick the adjacencies of vertex representatives and compute the orbits: candidateEdges = [] for x in begin: for y in adjacent[x[0]]: w = (sorted([x[0],y])) if w not in candidateEdges: candidateEdges.append(w) candidateEdges = sorted(list(candidateEdges)) allNewOrbits = computeOrbitDecomposition(candidateEdges,vertexIndexList,listOfPos,basis,homs) print len(allNewOrbits) DecompOrbits.append(allNewOrbits) newRepresentatives = pickRepresentativeOfOrbit(DecompOrbits[-1]) representatives.append(newRepresentatives) # #We can uncomment the next line if we want to save the representatives along the way, in case the computation runs out of memory. # save(newRepresentatives,'OrbitRepsOfDim'+str(1)+'.sobj') fvector.append(sum([len(x) for x in DecompOrbits[-1]])) # We comment the following lines if we don't want to save the output as a plain text file: # # We record the orbit decomposition of all vertices in a plain text file. f = file('../Output/CellsOfDim'+ str(1)+'.txt', 'w') f.write('RepresentativesOrbitsAndCellsOfDim'+str(1) +'='+ str([representatives[-1],DecompOrbits[-1]])) f.close() # We construct the cells of each dimension k+1, pick representatives and compute the orbits. Our stopping point will be when k+1 = n-2 = dim(nested set complex) for k in range(1,n-2): print representatives[-1] # We build a list of pairs [(x,potentialverticesToAttachTox): x in representatives[-1]] where the second entry is the list of all vertices that are adjacent to all vertices in x. These are all the candidate cells in dimension k+1 that we will need to check satisfy the nested set property. newCandidates = BuildCellsFromLowerCellsAndEdges(representatives[-1],adjacent) print str(newCandidates) print fvector higherInput = newCellsFromBuildCells(newCandidates,vertexIndexList, rankVector,vectorPos,pos,alpha,allNewOrbits) # print str(higherInput) # print len(higherInput) allNewOrbits = computeOrbitDecomposition(higherInput,vertexIndexList,listOfPos,basis,homs) print len(allNewOrbits) DecompOrbits.append(allNewOrbits) # # The following lines check that we have added the new orbit decomposition correctly # if allNewOrbits== DecompOrbits[-1]: # print "True" # else: # print "Not append correctly" newRepresentatives = pickRepresentativeOfOrbit(DecompOrbits[-1]) representatives.append(newRepresentatives) # We can uncomment the next line if we want to save the representatives along the way, in case the computation runs out of memory. # save(newRepresentatives,'OrbitRepsOfDim'+str(k+1)+'.sobj') # print representatives[-1] # print DecompOrbits[-1][-1] fvector.append(sum([len(x) for x in DecompOrbits[-1]])) # #We uncomment the following lines if we want to save the output as a plain text file: # # We record the cells of dimension k+1 and their orbit decomposition in a plain text file. f = file('../Output/CellsOfDim'+ str(k+1)+'.txt', 'w') f.write('RepresentativesOrbitsAndCellsOfDim'+str(k+1) +'='+ str([representatives[-1],DecompOrbits[-1]])) f.close() print fvector return [fvector,DecompOrbits]