[sage-support] matchings bipartite graphs
I want to implement a not so slow function for counting/generating all placements of non-attacking rooks in a board. Currently I am generating all partial permutations and checking whether they are in the board. An alternative would be to encode the board belonging to an n x n grid as a bipartite graph ( I the cell (i,j) is in the board then I have the edge (i,j) ). Then rook placements are just matchings on this graph. I coud not find an implementation of matchings in the Graph Theory functions. -- You received this message because you are subscribed to the Google Groups sage-support group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-support] Re: LLL_gram of matrices with 0 eigenvalues
On 2013-03-19, Victor Miller victorsmil...@gmail.com wrote: --=_Part_554_9793948.1363718282627 Content-Type: text/plain; charset=ISO-8859-1 Suppose that A is an m by n integer matrix. Its Gram matrix is G = A*A^t. If A is not full rank, then G has some eigenvalues of 0. If I do G.LLL_gram() I get a somewhat uniformative error message like: Value Error: ma matrix from Full MatrixSpace of 10 by 2 dense matrices over Integer Ring cannot be converted to a matrix in Full MatrixSpace of 10 by 10 dense matrices over Integer Ring! I understand that pari (which is what I understand, actually computes LLL_gram) doesn't like non-definite matrices. But, in this case it looks like it returned something to SAGE of lower dimension (what?) and SAGE didn't know what to do with it. Can the error message at least be changed to something more informative. This is certainly easy to fix, but here is a workaround that seems to work. Let's make a low rank, say, 3x3 matrix: sage: A=matrix([[1,2,3]]) sage: G=A.T*A; G [1 2 3] [2 4 6] [3 6 9] sage: x=G._pari_(); x # this is what PARI will get [1, 2, 3; 2, 4, 6; 3, 6, 9] sage: x.lllgram() # compute its LLL in PARI [1; 0; 0] HTH, Dmitrii I've found a work around for some of my matrices: Let N be some big integer, and let G'= N*G + identity_matrix(G.nrows()). This perturbs G a little so that the 0 eigenvalues go away. Victor -- You received this message because you are subscribed to the Google Groups sage-support group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-support] Re: LLL_gram of matrices with 0 eigenvalues
Thanks Dima and John, In the meantime, since I have Magma available to me I tried to use magma's functions. What I'm really interested is getting the unimodular (when it makes sense to use that term) transition matrix needed to put a matrix in reduced form. It looks like, but correct me if I'm wrong, that the only sage function which returns this is LLL_gram. I looked at the Magma documentation, and saw the the LLL function in Magma returns 3 things: the reduced matrix, the transition matrix, and the rank. However, when I do that I get a traceback from sage, plus at the end TypeError: Error evaluating Magma code: IN:_sage[1]:=[_a : _a in _sage[2]]; OUT: _sage_[1]:=[_a : _a in _sage[2]]; ^ Runtime error in for: Iteration is not possible over this object When I look at the returned value of magma.LLL it only has the reduced matrix. Is there a way of getting the entire tuple of returned values from magma? Victor B,U,rk = magma.LLL(A) I get a message from sage (it's pretty obscure) saying that it On Tuesday, March 19, 2013 2:38:02 PM UTC-4, Victor Miller wrote: Suppose that A is an m by n integer matrix. Its Gram matrix is G = A*A^t. If A is not full rank, then G has some eigenvalues of 0. If I do G.LLL_gram() I get a somewhat uniformative error message like: Value Error: ma matrix from Full MatrixSpace of 10 by 2 dense matrices over Integer Ring cannot be converted to a matrix in Full MatrixSpace of 10 by 10 dense matrices over Integer Ring! I understand that pari (which is what I understand, actually computes LLL_gram) doesn't like non-definite matrices. But, in this case it looks like it returned something to SAGE of lower dimension (what?) and SAGE didn't know what to do with it. Can the error message at least be changed to something more informative. I've found a work around for some of my matrices: Let N be some big integer, and let G'= N*G + identity_matrix(G.nrows()). This perturbs G a little so that the 0 eigenvalues go away. Victor -- You received this message because you are subscribed to the Google Groups sage-support group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-support] Re: LLL_gram of matrices with 0 eigenvalues
Aha, I found the nvals= option to magma commands. So for now I'll use that. I would like to ask that LLL optionally return the transition matrix (and also BKZ if that's possible). Victor On Tuesday, March 19, 2013 2:38:02 PM UTC-4, Victor Miller wrote: Suppose that A is an m by n integer matrix. Its Gram matrix is G = A*A^t. If A is not full rank, then G has some eigenvalues of 0. If I do G.LLL_gram() I get a somewhat uniformative error message like: Value Error: ma matrix from Full MatrixSpace of 10 by 2 dense matrices over Integer Ring cannot be converted to a matrix in Full MatrixSpace of 10 by 10 dense matrices over Integer Ring! I understand that pari (which is what I understand, actually computes LLL_gram) doesn't like non-definite matrices. But, in this case it looks like it returned something to SAGE of lower dimension (what?) and SAGE didn't know what to do with it. Can the error message at least be changed to something more informative. I've found a work around for some of my matrices: Let N be some big integer, and let G'= N*G + identity_matrix(G.nrows()). This perturbs G a little so that the 0 eigenvalues go away. Victor -- You received this message because you are subscribed to the Google Groups sage-support group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-support] Re: matchings bipartite graphs
I found the matching_polynomial http://www.sagemath.org/doc/reference/graphs/sage/graphs/matchpoly.html#sage.graphs.matchpoly.matching_polynomial On Wednesday, March 20, 2013 11:17:37 AM UTC-4, Alejandro Morales wrote: I want to implement a not so slow function for counting/generating all placements of non-attacking rooks in a board. Currently I am generating all partial permutations and checking whether they are in the board. An alternative would be to encode the board belonging to an n x n grid as a bipartite graph ( I the cell (i,j) is in the board then I have the edge (i,j) ). Then rook placements are just matchings on this graph. I coud not find an implementation of matchings in the Graph Theory functions. -- You received this message because you are subscribed to the Google Groups sage-support group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-support] matchings bipartite graphs
I use the following to iterate over all matchings and perfect matchings. def matchings(G): edges = G.edges(labels = False) verts = [[v] for v in G] m = len(edges) for match in DLXCPP(edges+verts): yield [edges[t] for t in match if t m] def perfect_matchings(G): edges = G.edges(labels = False) for match in DLXCPP(edges): yield [edges[t] for t in match] -- You received this message because you are subscribed to the Google Groups sage-support group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-support] matchings bipartite graphs
Note that that code only works for graphs whose vertices are labeled [0...n]. On Wed, Mar 20, 2013 at 1:03 PM, Tom Boothby tomas.boot...@gmail.com wrote: I use the following to iterate over all matchings and perfect matchings. def matchings(G): edges = G.edges(labels = False) verts = [[v] for v in G] m = len(edges) for match in DLXCPP(edges+verts): yield [edges[t] for t in match if t m] def perfect_matchings(G): edges = G.edges(labels = False) for match in DLXCPP(edges): yield [edges[t] for t in match] -- You received this message because you are subscribed to the Google Groups sage-support group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-support] matchings bipartite graphs
H... If you want to enumerate all partial permutations then you have much better to do. If you have a n x m matrix with nm what you should do it take all subsets of n elements of n, and enumerate all permutations using those n columns among m. Even if I would LOVE to have a way to enumerate all matchings of a bipartite graph. It remains that when your graph is the complete bipartite graph the problem is a bit easier :-P Nathann On Wednesday, March 20, 2013 9:05:54 PM UTC+1, Tom Boothby wrote: Note that that code only works for graphs whose vertices are labeled [0...n]. On Wed, Mar 20, 2013 at 1:03 PM, Tom Boothby tomas@gmail.comjavascript: wrote: I use the following to iterate over all matchings and perfect matchings. def matchings(G): edges = G.edges(labels = False) verts = [[v] for v in G] m = len(edges) for match in DLXCPP(edges+verts): yield [edges[t] for t in match if t m] def perfect_matchings(G): edges = G.edges(labels = False) for match in DLXCPP(edges): yield [edges[t] for t in match] -- You received this message because you are subscribed to the Google Groups sage-support group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
Re: [sage-support] matchings bipartite graphs
I'm sure it's not fast, but in the file devel/sage/sage/homology/examples.py, there is a function matching which gets used in simplicial_complexes.ChessboardComplex(...). Well, obviously there is a matching function in the Graph class. But nothing to enumerate them. Oh. Now that I think of it, actually there is. I wrote a patch to enumerate all independent sets of a graph, just there : http://trac.sagemath.org/sage_trac/ticket/13917 If you have it applied, then running : g = graphs.PetersenGraph() g = g.line_graph(labels = False) from sage.graphs.independent_sets import IndependentSets for m in IndependentSets(g): print Here is a matching,m So actually, this enumerates all possible matchings :-P Well, it works but it would be nice to have something for matching especially. This function can be slow sometimes. You can also filter the (inclusionwise) maximal matchings if you want. Well, I think it answers the question. But the trick I gave above is cleaner :-P Nathann -- You received this message because you are subscribed to the Google Groups sage-support group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
[sage-support] Re: matchings bipartite graphs
Thank you very much for all the suggestions. A little bit more of background. I am working on this patch http://trac.sagemath.org/sage_trac/ticket/14127 and would like to have an efficient way of generating the rook placements. On Wednesday, March 20, 2013 11:17:37 AM UTC-4, Alejandro Morales wrote: I want to implement a not so slow function for counting/generating all placements of non-attacking rooks in a board. Currently I am generating all partial permutations and checking whether they are in the board. An alternative would be to encode the board belonging to an n x n grid as a bipartite graph ( I the cell (i,j) is in the board then I have the edge (i,j) ). Then rook placements are just matchings on this graph. I coud not find an implementation of matchings in the Graph Theory functions. -- You received this message because you are subscribed to the Google Groups sage-support group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support?hl=en. For more options, visit https://groups.google.com/groups/opt_out.
