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
<etc>
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 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.
