[sage-support] Re: Graph canonical form directly on matrices
Ultimately, the classical canonical form/isomorphism implementations run on (di)graphs represented by 0-1 matrices, often with bit entries. So that's how bliss_digraph is represented too. Constructing it directly might be beneficial, especially if you have a problem of doing this on many small matrices (20x20 would still be quite small; isomorphism complexity usually starts to kick in with, say, 100x100 matrices) Anyhow, the main inefficiency in your approach is coming from constructing unnecessarily big graphs. In fact, to encode an edge-coloured (say, k colours) n-vertex graph as an equivalent vertex-coloured graph you only need O(n log k) vertices in the new graph. See Sect 14 in http://pallini.di.uniroma1.it/Guide.html on how this can be done. If you implemented this in Sage, it would be a great contribution! Also, I am not sure whether bliss is faster than nauty (nauty also is a Sage standard package, but lacks a cython interface) But this is another story. Dima On Tuesday, March 6, 2018 at 4:18:07 PM UTC, Christian Stump wrote: > > Hi Simon, > > Thanks for trying! I was actually hoping for a way to completely avoid > creating this sage DiGraph. But either to get the matrix directly into the > algorithm (which currently seems impossible), or at least to directly > construct some internal graph data structure. > > Looking at the code of sage.graphs.bliss.canonical_form, you see that the > input digraph is turned into a bliss_digraph (whatever that is). So I > believe that there is, in principle, a way to bypass the DiGraph creation... > > Thanks again, Christian > -- 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 https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
[sage-support] Re: cannot install sage: gfortran-7.2.0 failed to build
On Tuesday, March 6, 2018 at 11:56:59 PM UTC, Matthew Lancellotti wrote: > > sage: latest version (8.1) (from https://github.com/sagemath/sage, last > updated Dec 17, 2017). tried both master branch and develop branch. > OS: Mac OSX 10.13.3 > Xcode version 9.0.1 > > > I cloned the latest version of sage from the git repository. When > attempting to `make` sage, I run into the error `The following package(s) > may have failed to build...gfortran-7.2.0`. I will attach the log file > shortly. Near the bottom of the file it says: > > The directory that should contain system headers does not exist: > /usr/include > make[5]: *** [stmp-fixinc] Error 1 > make[5]: *** Waiting for unfinished jobs > rm gcc.pod gfortran.pod > make[4]: *** [all-gcc] Error 2 > make[3]: *** [all] Error 2 > > I tried using brew to manually install gfortran. Brew said that it ships > with gcc. I used brew to update my system to the latest version of gcc. > It didn't help. Currently, I am updating my Xcode to 9.2 to see if that > helps. Also, should my "system headers" exist? If so, where are they? > System headers should be in /usr/include You also need XCode's command line tools to be installed. It could be that presence of Homebrew in your PATH breaks things. As well, please tell us the sequence of commands you executed. Did you run ./bootstrap and ./configure (with what parameters?) before running make? -- 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 https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
[sage-support] Re: cannot install sage: gfortran-7.2.0 failed to build
Here is the log file: https://drive.google.com/file/d/1zHxRRCueBxlHHI1qp4wfkHAT9yjwaxUG/view?usp=sharing On Tuesday, March 6, 2018 at 6:56:59 PM UTC-5, Matthew Lancellotti wrote: > > sage: latest version (8.1) (from https://github.com/sagemath/sage, last > updated Dec 17, 2017). tried both master branch and develop branch. > OS: Mac OSX 10.13.3 > Xcode version 9.0.1 > > > I cloned the latest version of sage from the git repository. When > attempting to `make` sage, I run into the error `The following package(s) > may have failed to build...gfortran-7.2.0`. I will attach the log file > shortly. Near the bottom of the file it says: > > The directory that should contain system headers does not exist: > /usr/include > make[5]: *** [stmp-fixinc] Error 1 > make[5]: *** Waiting for unfinished jobs > rm gcc.pod gfortran.pod > make[4]: *** [all-gcc] Error 2 > make[3]: *** [all] Error 2 > > I tried using brew to manually install gfortran. Brew said that it ships > with gcc. I used brew to update my system to the latest version of gcc. > It didn't help. Currently, I am updating my Xcode to 9.2 to see if that > helps. Also, should my "system headers" exist? If so, where are they? > > -- 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 https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
[sage-support] cannot install sage: gfortran-7.2.0 failed to build
sage: latest version (8.1) (from https://github.com/sagemath/sage, last updated Dec 17, 2017). tried both master branch and develop branch. OS: Mac OSX 10.13.3 Xcode version 9.0.1 I cloned the latest version of sage from the git repository. When attempting to `make` sage, I run into the error `The following package(s) may have failed to build...gfortran-7.2.0`. I will attach the log file shortly. Near the bottom of the file it says: The directory that should contain system headers does not exist: /usr/include make[5]: *** [stmp-fixinc] Error 1 make[5]: *** Waiting for unfinished jobs rm gcc.pod gfortran.pod make[4]: *** [all-gcc] Error 2 make[3]: *** [all] Error 2 I tried using brew to manually install gfortran. Brew said that it ships with gcc. I used brew to update my system to the latest version of gcc. It didn't help. Currently, I am updating my Xcode to 9.2 to see if that helps. Also, should my "system headers" exist? If so, where are they? -- 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 https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
[sage-support] Re: Graph canonical form directly on matrices
Hi Simon, Thanks for trying! I was actually hoping for a way to completely avoid creating this sage DiGraph. But either to get the matrix directly into the algorithm (which currently seems impossible), or at least to directly construct some internal graph data structure. Looking at the code of sage.graphs.bliss.canonical_form, you see that the input digraph is turned into a bliss_digraph (whatever that is). So I believe that there is, in principle, a way to bypass the DiGraph creation... Thanks again, Christian -- 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 https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
[sage-support] Re: Graph canonical form directly on matrices
PS: On 2018-03-06, Simon King wrote: > On 2018-03-06, Christian Stump wrote: > I haven't really been able to work around the bottle neck, but got a > minor improvement (4%) as follows: > ... > And of course using cython helps as well. With the following Cython code, I am > down to 272 µs per loop, while your original Python code gave me 325 µs > per loop: Sorry for having been unclear. Your original code gave 339 µs, my code in python gave 325 µs (that's 4% improvement), and my code in cython is of course still faster (that's 272 µs, thus almost 20% improvement in total). Cheers, Simon -- 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 https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
[sage-support] Re: Graph canonical form directly on matrices
Hi Christian, On 2018-03-06, Christian Stump wrote: > Let me add that the situations I care about are n,m <= 20, the entries are ><=5 and the matrices are sparsely filled. An random and typical example is That matrix seems far too small to say anything substantial about timings. However, profiling the hash computation in a loop, it seems that the method add_edge is called quite frequently. However, I don't really see where the time spent in the function _matrix_to_digraph (which seems to be the bottle neck here) is spent. I haven't really been able to work around the bottle neck, but got a minor improvement (4%) as follows: add_edges is frequently used, so, I tried to not create an empty graph and then add edges to it, but instead create the list of vertices and edges and then create the graph from these lists. However, there is no gain at all, as DiGraph.__init__ calls add_edges basically in the same way as you do. I changed the use of the list edge_labels. You basically use it to tell at what point an edge label has been created, and do this by frequently computing the index. It seems slightly better to me to to store the same information in a dict. So, replace edge_labels.index((i,j)) and the error catching by edge_labels.setdefault((i,j), ...). Also, it seems slightly faster to obtain the hash of a frozen set than of a sorted tuple: sage: dg_canon = dg.canonical_label(partition=partition, algorithm="bliss", return_graph=False) sage: %timeit hash(frozenset(dg_canon)) 10 loops, best of 3: 2.79 µs per loop sage: %timeit hash(tuple(sorted(dg_canon))) 10 loops, best of 3: 4.57 µs per loop And of course using cython helps as well. With the following Cython code, I am down to 272 µs per loop, while your original Python code gave me 325 µs per loop: ## def matrix_canonical_hash(M, n, m): dg,partition = _matrix_to_digraph(M, n, m) dg_canon = dg.canonical_label(partition=partition, algorithm="bliss", return_graph=False) return hash(frozenset(dg_canon)) from sage.matrix.matrix0 cimport Matrix from sage.all import matrix, DiGraph cpdef _matrix_to_digraph(Matrix M, int n, int m): cdef dict edge_labels = dict() cdef int n_labels = 0 cdef int new_vertex = n+m cdef list Edges = [] cdef list new_partition = [] cdef int i,j for i,j in M.nonzero_positions(): a = M.get_unsafe(i,j) if i < n: b = M.get_unsafe(j,i) else: b = -M.get_unsafe(i, j) if a > 0: if a == 1 and b == -1: Edges.append((i,j)) else: x = edge_labels.setdefault((a,b), n_labels) if n_labels < len(edge_labels): new_partition.append([]) n_labels += 1 Edges.append((i,new_vertex)) Edges.append((new_vertex,j)) new_partition[x].append(new_vertex) new_vertex += 1 elif i >= n: if a == -1 and b == 1: Edges.append((j,i)) else: a = -a b = -b x = edge_labels.setdefault((a,b), n_labels) if n_labels < len(edge_labels): new_partition.append([]) n_labels += 1 Edges.append((j,new_vertex)) Edges.append((new_vertex,i)) new_partition[x].append(new_vertex) new_vertex += 1 cdef list partition = [list(range(n))] if m > 0: partition.append(list(range(n,n+m))) if new_partition: partition.extend(new_partition) return DiGraph([range(new_vertex),Edges],sparse=True), partition M = matrix([(0, -1, 0, 0, 0, 0, 0, 1), (1, 0, 1, 0, 0, 0, 0, 0), (0, -1, 0, 0, 1, 0, 0, 0), (0, 0, 0, 0, 0, 1, 0, 0), (0, 0, -1, 0, 0, 0, 1, 0), (0, 0, 0, -1, 0, 0, -1, 0), (0, 0, 0, 0, -1, 1, 0, 0), (-2, 0, 0, 0, 0, 0, 0, 0), (-1, 1, 0, 0, 0, 0, 0, 0), (0, 1, 0, 0, 0, 0, 0, -1), (0, 1, 0, 1, 0, -1, 0, -1), (0, 2, -1, 1, 0, -1, 0, -1), (0, 2, -1, 0, 0, -1, 0, -1), (0, 2, 0, 0, -1, -1, 0, -1), (0, 2, 0, 0, -1, 0, -1, -1), (0, 2, 0, 0, 0, 0, -2, -1)] ) ### Best regards, Simon -- 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 https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
Re: [sage-support] Graph canonical form directly on matrices
Dear Johan, > The most inefficient part of _matrix_to_digraph seems to be the > following line: > > > x = edge_labels.index((a,b)) > you are totally right, thanks for this suggestion! (Unfortunately, this will not change anything in practice, because the list edge_labels will usually be at most of length 2, and never be longer than 5 in my case, independent of n and m.) Cheers, Christian -- 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 https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
Re: [sage-support] Graph canonical form directly on matrices
Hi Christian, The most inefficient part of _matrix_to_digraph seems to be the following line: > x = edge_labels.index((a,b)) which runs in linear time on the length of edge_labels. If all the pairs (a,b) are different on your input matrix, that gives an n^3 running time for this line alone. Compared to the asymptotics on Graph Isomorphism, that's of course fine, but in practice it might be nasty. To optimise the line above, you should replace the lists edge_labels and new_partition with a dict from the pairs (a,b) directly to the partitions, i.e. something like edges_to_partitions = dict() ... try: p = edge_to_partitions[(a,b)] except ValueError: p = [] edge_to_partitions[(a,b)] = p finally: dg.add_vertex(new_vertex) dg._backend.add_edge(i,new_vertex,None,True) dg._backend.add_edge(new_vertex,j,None,True) p.append(new_vertex) new_vertex += 1 Best, Johan Christian Stump writes: > (This question is about speed improvements of an existing approach, not > about finding a first toy solution.) > > Let A, B be two ( (n+m) x n ) integer matrices. Say that these are > isomorphic if they coincide up to *simultaneous* row and column > permutations of the indices 0,...,n-1. > > Example: [[1,0],[0,0]] and [[0,0],[0,1]] are isomorphic because > interchanging rows 0 and 1 and also columns 0 and 1 interchange the two. > NonExample: [[1,0],[0,0]] and [[0,1],[0,0]] are not isomorphic. > > I would now like to obtain a canonical form CF : Mat( (n+m) x n) -> Mat( > (n+m) x n) for each isomorphism class. This is CF(M1) == CF(M2) if and only > if M1 and M2 are isomorphic. I actually do not care if the canonical form > is a matrix, a canonical hash function is enough and what I do use below. > > This is almost the graph canonical form because two graphs are isomorphic > if and only if their adjacency matrices are isomorphic in the above sense. > > So what I do currently is > > * turn my integer matrix into a directed, edge-labelled graph > * turn this edge-labelled graph into an unlabelled graph by replacing each > non-one-label into a new vertex and keep track which new vertices represent > the same edge label > * use the canonical form algorithm in Sage to compute a canonical form (I > use the bliss version, because it allows me to not get back a graph, but > only a list of edges which is good enough to compute a canonical hash). > > The code is > > def matrix_canonical_hash(M, n, m): > dg,partition = _matrix_to_digraph(M, n, m) > dg_canon = dg.canonical_label(partition=partition, algorithm="bliss", > return_graph=False) > return hash(tuple(sorted(dg_canon))) > > def _matrix_to_digraph(M, n, m): > dg = DiGraph(sparse=True) > dg.add_vertices(range(n+m)) > > edge_labels = [] > new_vertex = n+m > > new_partition = [] > > for i, j in M.nonzero_positions(): > if i < n: > a, b = M[i, j], M[j, i] > else: > a, b = M[i, j], -M[i, j] > if a > 0: > if a == 1 and b == -1: > dg._backend.add_edge(i,j,None,True) > else: > try: > x = edge_labels.index((a,b)) > except ValueError: > x = len(edge_labels) > edge_labels.append((a,b)) > new_partition.append([]) > finally: > dg.add_vertex(new_vertex) > dg._backend.add_edge(i,new_vertex,None,True) > dg._backend.add_edge(new_vertex,j,None,True) > new_partition[x].append(new_vertex) > new_vertex += 1 > elif i >= n: > if a == -1 and b == 1: > dg._backend.add_edge(j,i,None,True) > else: > a = -a > b = -b > try: > x = edge_labels.index((a,b)) > except ValueError: > x = len(edge_labels) > edge_labels.append((a,b)) > new_partition.append([]) > finally: > dg.add_vertex(new_vertex) > dg._backend.add_edge(j,new_vertex,None,True) > dg._backend.add_edge(new_vertex,i,None,True) > new_partition[x].append(new_vertex) > new_vertex += 1 > partition = [list(range(n))] > if m > 0: > partition.append(list(range(n,n+m))) > if new_partition: > partition.extend(new_partition) > return dg, partition > > def fast_copy(M, n, m): > Mnew = zero_matrix(n+m,n) > for (i,j),val in M.dict().iteritems(): > Mnew[i,j] = val > return M
[sage-support] Re: Graph canonical form directly on matrices
Let me add that the situations I care about are n,m <= 20, the entries are <=5 and the matrices are sparsely filled. An random and typical example is sage: M = matrix([(0, -1, 0, 0, 0, 0, 0, 1), : (1, 0, 1, 0, 0, 0, 0, 0), : (0, -1, 0, 0, 1, 0, 0, 0), : (0, 0, 0, 0, 0, 1, 0, 0), : (0, 0, -1, 0, 0, 0, 1, 0), : (0, 0, 0, -1, 0, 0, -1, 0), : (0, 0, 0, 0, -1, 1, 0, 0), : (-2, 0, 0, 0, 0, 0, 0, 0), : (-1, 1, 0, 0, 0, 0, 0, 0), : (0, 1, 0, 0, 0, 0, 0, -1), : (0, 1, 0, 1, 0, -1, 0, -1), : (0, 2, -1, 1, 0, -1, 0, -1), : (0, 2, -1, 0, 0, -1, 0, -1), : (0, 2, 0, 0, -1, -1, 0, -1), : (0, 2, 0, 0, -1, 0, -1, -1), : (0, 2, 0, 0, 0, 0, -2, -1)] : ) sage: M [ 0 -1 0 0 0 0 0 1] [ 1 0 1 0 0 0 0 0] [ 0 -1 0 0 1 0 0 0] [ 0 0 0 0 0 1 0 0] [ 0 0 -1 0 0 0 1 0] [ 0 0 0 -1 0 0 -1 0] [ 0 0 0 0 -1 1 0 0] [-2 0 0 0 0 0 0 0] [-1 1 0 0 0 0 0 0] [ 0 1 0 0 0 0 0 -1] [ 0 1 0 1 0 -1 0 -1] [ 0 2 -1 1 0 -1 0 -1] [ 0 2 -1 0 0 -1 0 -1] [ 0 2 0 0 -1 -1 0 -1] [ 0 2 0 0 -1 0 -1 -1] [ 0 2 0 0 0 0 -2 -1] sage: matrix_canonical_hash(M, 8, 8) 2718289463783950847 -- 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 https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
[sage-support] Graph canonical form directly on matrices
(This question is about speed improvements of an existing approach, not about finding a first toy solution.) Let A, B be two ( (n+m) x n ) integer matrices. Say that these are isomorphic if they coincide up to *simultaneous* row and column permutations of the indices 0,...,n-1. Example: [[1,0],[0,0]] and [[0,0],[0,1]] are isomorphic because interchanging rows 0 and 1 and also columns 0 and 1 interchange the two. NonExample: [[1,0],[0,0]] and [[0,1],[0,0]] are not isomorphic. I would now like to obtain a canonical form CF : Mat( (n+m) x n) -> Mat( (n+m) x n) for each isomorphism class. This is CF(M1) == CF(M2) if and only if M1 and M2 are isomorphic. I actually do not care if the canonical form is a matrix, a canonical hash function is enough and what I do use below. This is almost the graph canonical form because two graphs are isomorphic if and only if their adjacency matrices are isomorphic in the above sense. So what I do currently is * turn my integer matrix into a directed, edge-labelled graph * turn this edge-labelled graph into an unlabelled graph by replacing each non-one-label into a new vertex and keep track which new vertices represent the same edge label * use the canonical form algorithm in Sage to compute a canonical form (I use the bliss version, because it allows me to not get back a graph, but only a list of edges which is good enough to compute a canonical hash). The code is def matrix_canonical_hash(M, n, m): dg,partition = _matrix_to_digraph(M, n, m) dg_canon = dg.canonical_label(partition=partition, algorithm="bliss", return_graph=False) return hash(tuple(sorted(dg_canon))) def _matrix_to_digraph(M, n, m): dg = DiGraph(sparse=True) dg.add_vertices(range(n+m)) edge_labels = [] new_vertex = n+m new_partition = [] for i, j in M.nonzero_positions(): if i < n: a, b = M[i, j], M[j, i] else: a, b = M[i, j], -M[i, j] if a > 0: if a == 1 and b == -1: dg._backend.add_edge(i,j,None,True) else: try: x = edge_labels.index((a,b)) except ValueError: x = len(edge_labels) edge_labels.append((a,b)) new_partition.append([]) finally: dg.add_vertex(new_vertex) dg._backend.add_edge(i,new_vertex,None,True) dg._backend.add_edge(new_vertex,j,None,True) new_partition[x].append(new_vertex) new_vertex += 1 elif i >= n: if a == -1 and b == 1: dg._backend.add_edge(j,i,None,True) else: a = -a b = -b try: x = edge_labels.index((a,b)) except ValueError: x = len(edge_labels) edge_labels.append((a,b)) new_partition.append([]) finally: dg.add_vertex(new_vertex) dg._backend.add_edge(j,new_vertex,None,True) dg._backend.add_edge(new_vertex,i,None,True) new_partition[x].append(new_vertex) new_vertex += 1 partition = [list(range(n))] if m > 0: partition.append(list(range(n,n+m))) if new_partition: partition.extend(new_partition) return dg, partition def fast_copy(M, n, m): Mnew = zero_matrix(n+m,n) for (i,j),val in M.dict().iteritems(): Mnew[i,j] = val return Mnew My matrices have a few more properties which I use in _matrix_to_digraph (namely that M[i,j] and M[j,i] have opposite signs and M[i,j] > 0 for i >= n). Since I have to do many of such test, it needs to be fast. Currently, only 1/3 of the time is spent doing the bliss algorithm. My questions thus are: 1. Does anyone know if there is a (similarly optimized) version of the canonical form algorithms that do the canonical forms on matrices rather than on graphs? 2. Does anyone see how I can speed the construction of the canonical form input graph from a given matrix ? Many thanks for your help -- any improvements will make their way into the cluster algebra and quiver mutation functionality in main Sage, Christian -- 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 https://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
