Attachment 'quiver.py'
Download 1 r"""
2 Quiver
3
4 A *quiver* is an oriented graphs without loops, two-cycles, or multiple edges. The edges are labelled by pairs `(i,-j)`
5 such that the matrix `M = (m_{ab})` with `m_{ab} = i, m_{ba} = -j` for an edge `(i,-j)` between vertices `a` and `b` is skew-symmetrizable.
6
7 For the compendium on the cluster algebra and quiver package see
8
9 http://arxiv.org/abs/1102.4844
10
11 AUTHORS:
12
13 - Gregg Musiker
14 - Christian Stump
15 """
16
17 #*****************************************************************************
18 # Copyright (C) 2011 Gregg Musiker <[email protected]>
19 # Christian Stump <[email protected]>
20 # 2012 Franco Saliola < ... >
21 #
22 # Distributed under the terms of the GNU General Public License (GPL)
23 # http://www.gnu.org/licenses/
24 #*****************************************************************************
25 from sage.structure.sage_object import SageObject
26 from copy import copy
27 from sage.interfaces.gap import gap
28 from sage.structure.unique_representation import UniqueRepresentation
29 from sage.misc.all import cached_method
30 from sage.rings.all import ZZ, QQ, CC, infinity
31 from sage.graphs.all import Graph, DiGraph
32 from sage.combinat.cluster_algebra_quiver.all import QuiverMutationType, QuiverMutationType_Irreducible, QuiverMutationType_Reducible
33 from sage.combinat.cluster_algebra_quiver.mutation_class import _edge_list_to_matrix, _principal_part, _digraph_mutate, _matrix_to_digraph, _mutation_class_iter, _dg_canonical_form, _digraph_to_dig6
34 from sage.combinat.cluster_algebra_quiver.mutation_type import _connected_mutation_type, _mutation_type_from_data
35 from sage.combinat.graph_path import GraphPaths
36 from sage.groups.perm_gps.permgroup import PermutationGroup
37 from sage.sets.family import Family
38 from sage.combinat.free_module import CombinatorialFreeModule
39 from sage.misc.lazy_attribute import lazy_attribute
40 from sage.categories.finite_dimensional_algebras_with_basis import FiniteDimensionalAlgebrasWithBasis
41
42 class Quiver(SageObject):
43 """
44 The *quiver* associated to an *exchange matrix*.
45
46 INPUT:
47
48 - ``data`` -- can be any of the following::
49
50 * QuiverMutationType
51 * str - a string representing a QuiverMutationType
52 * Quiver
53 * Matrix - a skew-symmetrizable matrix
54 * DiGraph - must be the input data for a quiver
55 * List of edges - must be the edge list of a digraph for a quiver
56
57 EXAMPLES::
58
59 sage: Q = Quiver(['A',5]); Q
60 Quiver on 5 vertices of type ['A', 5]
61
62 sage: Q = Quiver(['A',[2,5],1]); Q
63 Quiver on 7 vertices of type ['A', [2, 5], 1]
64
65 sage: T = Quiver( Q ); T
66 Quiver on 7 vertices of type ['A', [2, 5], 1]
67
68 sage: T = Quiver( Q._M ); T
69 Quiver on 7 vertices
70
71 sage: T = Quiver( Q._digraph ); T
72 Quiver on 7 vertices
73
74 sage: T = Quiver( Q._digraph.edges() ); T
75 Quiver on 7 vertices
76 """
77 def __init__( self, data, frozen=0 ):
78 """
79 TESTS::
80
81 sage: Q = Quiver(['A',4])
82 sage: TestSuite(Q).run()
83 """
84 from cluster_seed import ClusterSeed
85 from sage.matrix.matrix import Matrix
86
87 # constructs a quiver from a mutation type
88 if type( data ) in [QuiverMutationType_Irreducible,QuiverMutationType_Reducible]:
89 if frozen:
90 print 'The input data is a quiver, therefore the additional parameter frozen is ignored.'
91
92 mutation_type = data
93 self.__init__( mutation_type.standard_quiver() )
94
95 # constructs a quiver from string representing a mutation type
96 elif type( data ) in [list,tuple] and ( type( data[0] ) is str or all(type( comp ) in [list,tuple] and type( comp[0] ) is str for comp in data) ):
97 if frozen:
98 print 'The input data is a quiver, therefore the additional parameter frozen is ignored.'
99 mutation_type = QuiverMutationType( data )
100 self.__init__( mutation_type.standard_quiver() )
101
102 # constructs a quiver from a quiver
103 elif type(data) is ClusterSeed:
104 self.__init__( data.quiver() )
105
106 # constructs a quiver from a quiver
107 elif type(data) is Quiver:
108 if frozen:
109 print 'The input data is a quiver, therefore the additional parameter frozen is ignored.'
110
111 self._M = copy(data._M)
112 self._n = data._n
113 self._m = data._m
114 self._digraph = copy( data._digraph )
115 self._mutation_type = data._mutation_type
116 self._description = data._description
117
118 # constructs a quiver from a matrix
119 elif isinstance(data, Matrix):
120 if not _principal_part(data).is_skew_symmetrizable( positive=True ):
121 raise ValueError, 'The principal part of the matrix data must be skew-symmetrizable.'
122 if frozen:
123 print 'The input data is a matrix, therefore the additional parameter frozen is ignored.'
124
125 self._M = copy(data).sparse_matrix()
126 self._n = n = self._M.ncols()
127 self._m = m = self._M.nrows() - self._n
128 self._digraph = _matrix_to_digraph( self._M )
129 self._mutation_type = None
130 if n+m == 0:
131 self._description = 'Quiver without vertices' %(n+m)
132 elif n+m == 1:
133 self._description = 'Quiver on %d vertex' %(n+m)
134 else:
135 self._description = 'Quiver on %d vertices' %(n+m)
136
137 # constructs a quiver from a digraph
138 elif type(data) is DiGraph:
139 m = self._m = frozen
140 n = self._n = data.order() - m
141 dg = copy( data )
142 if not set(dg.vertices()) == set(range(n+m)):
143 dg.relabel()
144 if dg.has_multiple_edges():
145 multi_edges = {}
146 for v1,v2,label in dg.multiple_edges():
147 if label not in ZZ:
148 raise ValueError, "The input DiGraph contains multiple edges labeled by non-integers"
149 elif (v1,v2) in multi_edges:
150 multi_edges[(v1,v2)] += label
151 else:
152 multi_edges[(v1,v2)] = label
153 dg.delete_edge(v1,v2)
154 dg.add_edges( [ (v1,v2,multi_edges[(v1,v2)]) for v1,v2 in multi_edges ] )
155 for edge in dg.edge_iterator():
156 if edge[0] >= n and edge[1] >= n:
157 raise ValueError, "The input digraph contains edges within the frozen vertices"
158 if edge[2] is None:
159 dg.set_edge_label( edge[0], edge[1], (1,-1) )
160 edge = (edge[0],edge[1],(1,-1))
161 elif edge[2] in ZZ:
162 dg.set_edge_label( edge[0], edge[1], (edge[2],-edge[2]) )
163 edge = (edge[0],edge[1],(edge[2],-edge[2]))
164 elif type(edge[2]) == list and len(edge[2]) <> 2:
165 raise ValueError, "The input digraph contains an edge with the wrong type of list as a label."
166 elif type(edge[2]) == list and len(edge[2]) == 2:
167 dg.set_edge_label( edge[0], edge[1], (edge[2][0], edge[2][1]))
168 edge = (edge[0],edge[1],(edge[2][0],edge[2][1]))
169 elif ( edge[0] >= n or edge[1] >= n ) and not edge[2][0] == - edge[2][1]:
170 raise ValueError, "The input digraph contains an edge to or from a frozen vertex which is not skew-symmetric."
171 if edge[2][0] < 0:
172 raise ValueError, "The input digraph contains an edge of the form (a,-b) with negative a."
173
174 M = _edge_list_to_matrix( dg.edge_iterator(), n, m )
175 if not _principal_part(M).is_skew_symmetrizable( positive=True ):
176 raise ValueError, "The input digraph must be skew-symmetrizable"
177 self._digraph = dg
178 self._M = M
179 if n+m == 0:
180 self._description = 'Quiver without vertices' %(n+m)
181 elif n+m == 1:
182 self._description = 'Quiver on %d vertex' %(n+m)
183 else:
184 self._description = 'Quiver on %d vertices' %(n+m)
185 self._mutation_type = None
186
187 # otherwise, data is used to construct a digraph
188 else:
189 dg = DiGraph()
190 dg.add_edges( data )
191 self.__init__(data=dg, frozen=frozen )
192
193 def __eq__(self, other):
194 """
195 Returns True iff self any y represent the same quiver.
196
197 EXAMPLES::
198
199 sage: Q = Quiver(['A',5])
200 sage: T = Q.mutate( 2, inplace=False )
201 sage: Q.__eq__( T )
202 False
203 sage: T.mutate( 2 )
204 sage: Q.__eq__( T )
205 True
206 """
207 return type( other ) is Quiver and self._M == other._M
208
209 def _repr_(self):
210 """
211 Returns the description of self.
212
213 EXAMPLES::
214
215 sage: Q = Quiver(['A',5])
216 sage: Q._repr_()
217 "Quiver on 5 vertices of type ['A', 5]"
218 """
219 name = self._description
220 if self._mutation_type:
221 if type( self._mutation_type ) in [QuiverMutationType_Irreducible,QuiverMutationType_Reducible]:
222 name += ' of type ' + str(self._mutation_type)
223 else:
224 name += ' of ' + self._mutation_type
225 if self._m == 1:
226 name += ' with %s frozen vertex'%self._m
227 elif self._m > 1:
228 name += ' with %s frozen vertices'%self._m
229 return name
230
231 def plot(self, circular=True, center=(0,0), directed=True, mark=None, save_pos=False):
232 """
233 Returns the plot of the underlying digraph of self.
234
235 INPUT:
236
237 - ``circular`` -- (default:True) if True, the circular plot is chosen, otherwise >>spring<< is used.
238 - ``center`` -- (default:(0,0)) sets the center of the circular plot, otherwise it is ignored.
239 - ``directed`` -- (default: True) if True, the directed version is shown, otherwise the undirected.
240 - ``mark`` -- (default: None) if set to i, the vertex i is highlighted.
241 - ``save_pos`` -- (default:False) if True, the positions of the vertices are saved.
242
243 EXAMPLES::
244
245 sage: Q = Quiver(['A',5])
246 sage: pl = Q.plot()
247 sage: pl = Q.plot(circular=True)
248 """
249 from sage.plot.colors import rainbow
250 from sage.graphs.graph_generators import GraphGenerators
251 from sage.all import e,pi,I
252 graphs = GraphGenerators()
253 # returns positions for graph vertices on two concentric cycles with radius 1 and 2
254 def _graphs_concentric_circles(n,m):
255 g1 = graphs.CycleGraph(n).get_pos()
256 g2 = graphs.CycleGraph(m).get_pos()
257 for i in g2:
258 z = CC(g2[i])*e**(-pi*I/(2*m))
259 g2[i] = (z.real_part(),z.imag_part())
260 for i in range(m):
261 g1[n+i] = [2*g2[i][0], 2*g2[i][1]]
262 return g1
263
264 n, m = self._n, self._m
265 colors = rainbow(11)
266 color_dict = { colors[0]:[], colors[1]:[], colors[6]:[], colors[5]:[] }
267 if directed:
268 dg = DiGraph( self._digraph )
269 else:
270 dg = Graph( self._digraph )
271 for edge in dg.edges():
272 v1,v2,(a,b) = edge
273 if v1 < n and v2 < n:
274 if (a,b) == (1,-1):
275 color_dict[ colors[0] ].append((v1,v2))
276 else:
277 color_dict[ colors[6] ].append((v1,v2))
278 else:
279 if (a,b) == (1,-1):
280 color_dict[ colors[1] ].append((v1,v2))
281 else:
282 color_dict[ colors[5] ].append((v1,v2))
283 if a == -b:
284 if a == 1:
285 dg.set_edge_label( v1,v2,'' )
286 else:
287 dg.set_edge_label( v1,v2,a )
288 if mark is not None:
289 if mark < n:
290 partition = (range(mark)+range(mark+1,n),range(n,n+m),[mark])
291 elif mark > n:
292 partition = (range(n),range(n,mark)+range(mark+1,n+m),[mark])
293 else:
294 raise ValueError, "The given mark is not a vertex of self."
295 else:
296 partition = (range(n),range(n,n+m),[])
297 vertex_color_dict = {}
298 vertex_color_dict[ colors[0] ] = partition[0]
299 vertex_color_dict[ colors[6] ] = partition[1]
300 vertex_color_dict[ colors[4] ] = partition[2]
301
302 options = {
303 'graph_border' : True,
304 'edge_colors': color_dict,
305 'vertex_colors': vertex_color_dict,
306 'edge_labels' : True,
307 'scaling_term' : 0.1
308 }
309 if circular:
310 pp = _graphs_concentric_circles( n, m )
311 for v in pp:
312 pp[v] = (pp[v][0]+center[0],pp[v][1]+center[1])
313 options[ 'pos' ] = pp
314 return dg.plot( **options )
315
316 def show(self, fig_size=1, circular=False, directed=True, mark=None, save_pos=False):
317 """
318 Shows the plot of the underlying digraph of self.
319
320 INPUT:
321
322 - ``fig_size`` -- (default: 1) factor by which the size of the plot is multiplied.
323 - ``circular`` -- (default: False) if True, the circular plot is chosen, otherwise >>spring<< is used.
324 - ``directed`` -- (default: True) if True, the directed version is shown, otherwise the undirected.
325 - ``mark`` -- (default: None) if set to i, the vertex i is highlighted.
326 - ``save_pos`` -- (default:False) if True, the positions of the vertices are saved.
327 """
328 n, m = self._n, self._m
329 plot = self.plot( circular=circular, directed=directed, mark=mark, save_pos=save_pos )
330 if circular:
331 plot.show( figsize=[fig_size*3*(n+m)/4+1,fig_size*3*(n+m)/4+1] )
332 else:
333 plot.show( figsize=[fig_size*n+1,fig_size*n+1] )
334
335 def interact(self, fig_size=1, circular=True):
336 """
337 Only in notebook mode. Starts an interactive window for cluster seed mutations.
338
339 INPUT:
340
341 - ``fig_size`` -- (default: 1) factor by which the size of the plot is multiplied.
342 - ``circular`` -- (default: False) if True, the circular plot is chosen, otherwise >>spring<< is used.
343 """
344 from sage.plot.plot import EMBEDDED_MODE
345 from sagenb.notebook.interact import interact, selector
346 from sage.misc.all import html,latex
347
348 if not EMBEDDED_MODE:
349 return "The interactive mode only runs in the Sage notebook."
350 else:
351 seq = []
352 sft = [True]
353 sss = [True]
354 ssm = [True]
355 ssl = [True]
356 @interact
357 def player(k=selector(values=range(self._n),nrows = 1,label='Mutate at: '), show_seq=("Mutation sequence:", True), show_matrix=("B-Matrix:", True), show_lastmutation=("Show last mutation:", True) ):
358 ft,ss,sm,sl = sft.pop(), sss.pop(), ssm.pop(), ssl.pop()
359 if ft:
360 self.show(fig_size=fig_size, circular=circular)
361 elif show_seq is not ss or show_matrix is not sm or show_lastmutation is not sl:
362 if seq and show_lastmutation:
363 self.show(fig_size=fig_size, circular=circular, mark=seq[len(seq)-1])
364 else:
365 self.show(fig_size=fig_size, circular=circular )
366 else:
367 self.mutate(k)
368 seq.append(k)
369 if not show_lastmutation:
370 self.show(fig_size=fig_size, circular=circular)
371 else:
372 self.show(fig_size=fig_size, circular=circular,mark=k)
373 sft.append(False)
374 sss.append(show_seq)
375 ssm.append(show_matrix)
376 ssl.append(show_lastmutation)
377 if show_seq: html( "Mutation sequence: $" + str( [ seq[i] for i in xrange(len(seq)) ] ).strip('[]') + "$" )
378 if show_matrix:
379 html( "B-Matrix:" )
380 m = self._M
381 #m = matrix(range(1,self._n+1),sparse=True).stack(m)
382 m = latex(m)
383 m = m.split('(')[1].split('\\right')[0]
384 html( "$ $" )
385 html( "$\\begin{align*} " + m + "\\end{align*}$" )
386 #html( "$" + m + "$" )
387 html( "$ $" )
388
389 def save_image(self,filename,circular=False):
390 """
391 Saves the plot of the underlying digraph of self.
392
393 INPUT:
394
395 - ``filename`` -- the filename the image is saved to.
396 - ``circular`` -- (default: False) if True, the circular plot is chosen, otherwise >>spring<< is used.
397 """
398 graph_plot = self.plot( circular=circular )
399 graph_plot.save( filename=filename )
400
401 def b_matrix(self):
402 """
403 Returns the b-matrix of self.
404
405 EXAMPLES::
406
407 sage: Quiver(['A',4]).b_matrix()
408 [ 0 1 0 0]
409 [-1 0 -1 0]
410 [ 0 1 0 1]
411 [ 0 0 -1 0]
412
413 sage: Quiver(['B',4]).b_matrix()
414 [ 0 1 0 0]
415 [-1 0 -1 0]
416 [ 0 1 0 1]
417 [ 0 0 -2 0]
418
419 sage: Quiver(['D',4]).b_matrix()
420 [ 0 1 0 0]
421 [-1 0 -1 -1]
422 [ 0 1 0 0]
423 [ 0 1 0 0]
424
425 sage: Quiver(QuiverMutationType([['A',2],['B',2]])).b_matrix()
426 [ 0 1 0 0]
427 [-1 0 0 0]
428 [ 0 0 0 1]
429 [ 0 0 -2 0]
430 """
431 return copy( self._M )
432
433 def digraph(self):
434 """
435 Returns the underlying digraph of self.
436
437 EXAMPLES::
438
439 sage: Quiver(['A',1]).digraph()
440 Digraph on 1 vertex
441 sage: Quiver(['A',1]).digraph().vertices()
442 [0]
443 sage: Quiver(['A',1]).digraph().edges()
444 []
445
446 sage: Quiver(['A',4]).digraph()
447 Digraph on 4 vertices
448 sage: Quiver(['A',4]).digraph().edges()
449 [(0, 1, (1, -1)), (2, 1, (1, -1)), (2, 3, (1, -1))]
450
451 sage: Quiver(['B',4]).digraph()
452 Digraph on 4 vertices
453 sage: Quiver(['A',4]).digraph().edges()
454 [(0, 1, (1, -1)), (2, 1, (1, -1)), (2, 3, (1, -1))]
455
456 sage: Quiver(QuiverMutationType([['A',2],['B',2]])).digraph()
457 Digraph on 4 vertices
458
459 sage: Quiver(QuiverMutationType([['A',2],['B',2]])).digraph().edges()
460 [(0, 1, (1, -1)), (2, 3, (1, -2))]
461 """
462 return copy( self._digraph )
463
464 def n(self):
465 """
466 Returns the number of free vertices of self.
467
468 EXAMPLES::
469
470 sage: Quiver(['A',4]).n()
471 4
472 sage: Quiver(['A',(3,1),1]).n()
473 4
474 sage: Quiver(['B',4]).n()
475 4
476 sage: Quiver(['B',4,1]).n()
477 5
478 """
479 return self._n
480
481 def m(self):
482 """
483 Returns the number of frozen vertices of self.
484
485 EXAMPLES::
486
487 sage: Q = Quiver(['A',4])
488 sage: Q.m()
489 0
490
491 sage: T = Quiver( Q.digraph().edges(), frozen=1 )
492 sage: T.n()
493 3
494 sage: T.m()
495 1
496 """
497 return self._m
498
499 def vertices(self):
500 return self._digraph.vertices()
501
502 def edges(self):
503 return self._digraph.edges(labels=False)
504
505 def copy(self):
506 return Quiver(self._digraph)
507
508 def canonical_label( self, certify=False ):
509 """
510 Returns the canonical labelling of self, see sage.graphs.graph.GenericGraph.canonical_label.
511
512 INPUT:
513
514 - ``certify`` -- (default: False) if True, the dictionary from self.vertices() to the vertices of the returned quiver is returned as well.
515
516 EXAMPLES::
517
518 sage: Q = Quiver(['A',4]); Q.digraph().edges()
519 [(0, 1, (1, -1)), (2, 1, (1, -1)), (2, 3, (1, -1))]
520
521 sage: T = Q.canonical_label(); T.digraph().edges()
522 [(0, 3, (1, -1)), (1, 2, (1, -1)), (1, 3, (1, -1))]
523
524 sage: T,iso = Q.canonical_label(certify=True); T.digraph().edges(); iso
525 [(0, 3, (1, -1)), (1, 2, (1, -1)), (1, 3, (1, -1))]
526 {0: 0, 1: 3, 2: 1, 3: 2}
527
528 sage: Q = Quiver(QuiverMutationType([['B',2],['A',1]])); Q
529 Quiver on 3 vertices of type [ ['B', 2], ['A', 1] ]
530
531 sage: Q.canonical_label()
532 Quiver on 3 vertices of type [ ['A', 1], ['B', 2] ]
533
534 sage: Q.canonical_label(certify=True)
535 (Quiver on 3 vertices of type [ ['A', 1], ['B', 2] ], {0: 1, 1: 2, 2: 0})
536 """
537 n = self._n
538 m = self._m
539
540 # computing the canonical form respecting the frozen variables
541 dg = copy( self._digraph )
542 iso, orbits = _dg_canonical_form( dg, n, m )
543 Q = Quiver( dg )
544 # getting the new ordering for the mutation type if necessary
545 if self._mutation_type:
546 if dg.is_connected():
547 Q._mutation_type = self._mutation_type
548 else:
549 CC = sorted( self._digraph.connected_components() )
550 CC_new = sorted( zip( [ sorted( [ iso[i] for i in L ] ) for L in CC ], range( len( CC ) ) ) )
551 comp_iso = [ L[1] for L in CC_new ]
552 Q._mutation_type = []
553 for i in range( len( CC_new ) ):
554 Q._mutation_type.append( copy( self._mutation_type.irreducible_components()[ comp_iso[i] ] ) )
555 Q._mutation_type = QuiverMutationType( Q._mutation_type )
556 if certify:
557 return Q, iso
558 else:
559 return Q
560
561 def is_acyclic(self):
562 """
563 Returns true if self is acyclic.
564
565 EXAMPLES::
566
567 sage: Quiver(['A',4]).is_acyclic()
568 True
569
570 sage: Quiver(['A',[2,1],1]).is_acyclic()
571 True
572
573 sage: Quiver([[0,1],[1,2],[2,0]]).is_acyclic()
574 False
575 """
576 return self._digraph.is_directed_acyclic()
577
578 def is_bipartite(self,return_bipartition=False):
579 """
580 Returns true if self is bipartite.
581
582 EXAMPLES::
583
584 sage: Quiver(['A',[3,3],1]).is_bipartite()
585 True
586
587 sage: Quiver(['A',[4,3],1]).is_bipartite()
588 False
589 """
590 dg = copy( self._digraph )
591 dg.delete_vertices( range(self._n,self._n+self._m) )
592 innie = dg.in_degree()
593 outie = dg.out_degree()
594 is_bip = sum( [ innie[i]*outie[i] for i in range(len(innie)) ] ) == 0
595 if not is_bip:
596 return False
597 else:
598 if not return_bipartition:
599 return True
600 else:
601 g = dg.to_undirected()
602 return g.bipartite_sets()
603
604 def principal_restriction(self):
605 """
606 Returns the restriction to the principal part of self. I.e., the subquiver obtained by deleting the frozen vertices of self.
607
608 EXAMPLES::
609
610 sage: Q = Quiver(['A',4])
611 sage: T = Quiver( Q.digraph().edges(), frozen=1 )
612 sage: T.digraph().edges()
613 [(0, 1, (1, -1)), (2, 1, (1, -1)), (2, 3, (1, -1))]
614
615 sage: T.principal_restriction().digraph().edges()
616 [(0, 1, (1, -1)), (2, 1, (1, -1))]
617 """
618 dg = DiGraph( self._digraph )
619 dg.delete_vertices( range(self._n,self._n+self._m) )
620 Q = Quiver( dg )
621 Q._mutation_type = self._mutation_type
622 return Q
623
624 def principal_extension(self):
625 """
626 Returns the principal extension of self if self does not have any frozen vertices. I.e., the quiver obtained by adding an outgoing edge to every vertex of self.
627
628 EXAMPLES::
629
630 sage: Q = Quiver(['A',2])
631 sage: T = Q.principal_extension()
632 sage: Q.digraph().edges()
633 [(0, 1, (1, -1))]
634 sage: T.digraph().edges()
635 [(0, 1, (1, -1)), (2, 0, (1, -1)), (3, 1, (1, -1))]
636
637 """
638 if self._m > 0:
639 raise ValueError, "Quiver contains frozen vertices"
640 dg = DiGraph( self._digraph )
641 dg.add_edges( [(self._n+i,i) for i in range(self._n)] )
642 Q = Quiver( dg, frozen=self._n )
643 Q._mutation_type = self._mutation_type
644 return Q
645
646 def mutate(self, data, inplace=True):
647 """
648 Mutates self at a sequence of vertices.
649
650 INPUT:
651
652 - ``sequence`` -- a vertex of self or an iterator of vertices of self.
653 - ``inplace`` -- (default: True) if False, the result is returned, otherwise self is modified.
654
655 EXAMPLES::
656
657 sage: Q = Quiver(['A',4]); Q.b_matrix()
658 [ 0 1 0 0]
659 [-1 0 -1 0]
660 [ 0 1 0 1]
661 [ 0 0 -1 0]
662
663 sage: Q.mutate(0); Q.b_matrix()
664 [ 0 -1 0 0]
665 [ 1 0 -1 0]
666 [ 0 1 0 1]
667 [ 0 0 -1 0]
668
669 sage: T = Q.mutate(0, inplace=False); T
670 Quiver on 4 vertices
671
672 sage: Q.mutate(0)
673 sage: Q == T
674 True
675
676 sage: Q.mutate([0,1,0])
677 sage: Q.b_matrix()
678 [ 0 -1 1 0]
679 [ 1 0 0 0]
680 [-1 0 0 1]
681 [ 0 0 -1 0]
682
683 sage: Q = Quiver(QuiverMutationType([['A',1],['A',3]]))
684 sage: Q.b_matrix()
685 [ 0 0 0 0]
686 [ 0 0 1 0]
687 [ 0 -1 0 -1]
688 [ 0 0 1 0]
689
690 sage: T = Q.mutate(0,inplace=False)
691 sage: Q == T
692 True
693 """
694 n = self._n
695 m = self._m
696 dg = self._digraph
697 V = range(n)
698
699 if data in V:
700 seq = [data]
701 else:
702 seq = data
703 if type( seq ) is tuple:
704 seq = list( seq )
705 if not type( seq ) is list:
706 raise ValueError, 'The quiver can only be mutated at a vertex or at a sequence of vertices'
707 if any( v not in V for v in seq ):
708 v = filter( lambda v: v not in V, seq )[0]
709 raise ValueError, 'The quiver cannot be mutated at the vertex ' + str( v )
710
711 for v in seq:
712 dg = _digraph_mutate( dg, v, n, m )
713 M = _edge_list_to_matrix( dg.edge_iterator(), n, m )
714 if inplace:
715 self._M = M
716 self._digraph = dg
717 else:
718 return Quiver( M )
719
720 def mutation_sequence(self, sequence, show_sequence=False, fig_size=1.2 ):
721 """
722 Returns a list containing the sequence of quivers obtained from self by a sequence of mutations on vertices.
723
724 INPUT:
725
726 - ``sequence`` -- a list or tuple of vertices of self.
727 - ``show_sequence`` -- (default: False) if True, a png containing the mutation sequence is shown.
728 - ``fig_size`` -- (default: 1.2) factor by which the size of the sequence is expanded.
729
730 EXAMPLES::
731
732 sage: Q = Quiver(['A',4])
733 sage: seq = Q.mutation_sequence([0,1]); seq
734 [Quiver on 4 vertices of type ['A', 4], Quiver on 4 vertices of type ['A', 4], Quiver on 4 vertices of type ['A', 4]]
735 sage: [T.b_matrix() for T in seq]
736 [
737 [ 0 1 0 0] [ 0 -1 0 0] [ 0 1 -1 0]
738 [-1 0 -1 0] [ 1 0 -1 0] [-1 0 1 0]
739 [ 0 1 0 1] [ 0 1 0 1] [ 1 -1 0 1]
740 [ 0 0 -1 0], [ 0 0 -1 0], [ 0 0 -1 0]
741 ]
742 """
743 from sage.plot.plot import Graphics
744 from sage.plot.text import text
745 n = self._n
746 m = self._m
747 if m == 0:
748 width_factor = 3
749 fig_size = fig_size*2*n/3
750 else:
751 width_factor = 6
752 fig_size = fig_size*4*n/3
753 V = range(n)
754
755 if type( sequence ) is tuple:
756 sequence = list( sequence )
757 if not type( sequence ) is list:
758 raise ValueError, 'The quiver can only be mutated at a vertex or at a sequence of vertices'
759 if any( v not in V for v in sequence ):
760 v = filter( lambda v: v not in V, sequence )[0]
761 raise ValueError, 'The quiver can only be mutated at the vertex ' + str( v )
762
763 quiver = copy( self )
764 quiver_sequence = []
765 quiver_sequence.append( copy( quiver ) )
766
767 for v in sequence:
768 quiver.mutate( v )
769 quiver_sequence.append( copy( quiver ) )
770
771 if show_sequence:
772 def _plot_arrow( v, k, center=(0,0) ):
773 return text("$\longleftrightarrow$",(center[0],center[1]), fontsize=25) + text("$\mu_"+str(v)+"$",(center[0],center[1]+0.15), fontsize=15) \
774 + text("$"+str(k)+"$",(center[0],center[1]-0.2), fontsize=15)
775 plot_sequence = [ quiver_sequence[i].plot( circular=True, center=(i*width_factor,0) ) for i in range(len(quiver_sequence)) ]
776 arrow_sequence = [ _plot_arrow( sequence[i],i+1,center=((i+0.5)*width_factor,0) ) for i in range(len(sequence)) ]
777 sequence = []
778 for i in xrange( len( plot_sequence ) ):
779 if i < len( arrow_sequence ):
780 sequence.append( plot_sequence[i] + arrow_sequence[i] )
781 else:
782 sequence.append( plot_sequence[i] )
783 plot_obj = Graphics()
784 for elem in sequence:
785 plot_obj += elem
786 plot_obj.show(axes=False, figsize=[fig_size*len(quiver_sequence),fig_size])
787 return quiver_sequence
788
789 def reorient( self, data ):
790 """
791 Reorients self with respect to the given total order, or with respect to an iterator of edges in self to be reverted.
792
793 WARNING::
794
795 This operation might change the mutation type of self.
796
797 INPUT:
798
799 - ``data`` -- an iterator defining a total order on self.vertices(), or an iterator of edges in self to be reoriented.
800
801 EXAMPLES::
802
803 sage: Q = Quiver(['A',(2,3),1])
804 sage: Q.mutation_type()
805 ['A', [2, 3], 1]
806
807 sage: Q.reorient([(0,1),(1,2),(2,3),(3,4)])
808 sage: Q.mutation_type()
809 ['D', 5]
810
811 sage: Q.reorient([0,1,2,3,4])
812 sage: Q.mutation_type()
813 ['A', [1, 4], 1]
814 """
815 if all( 0 <= i and i < self._n + self._m for i in data ) and len( set( data ) ) == self._n+self._m :
816 dg_new = DiGraph()
817 for edge in self._digraph.edges():
818 if data.index( edge[0] ) < data.index( edge[1] ):
819 dg_new.add_edge( edge[0],edge[1],edge[2] )
820 else:
821 dg_new.add_edge( edge[1],edge[0],edge[2] )
822 self._digraph = dg_new
823 self._M = _edge_list_to_matrix( dg_new.edges(), self._n, self._m )
824 self._mutation_type = None
825 elif all( type(edge) in [list,tuple] and len(edge)==2 for edge in data ):
826 edges = self._digraph.edges(labels=False)
827 for edge in data:
828 if (edge[1],edge[0]) in edges:
829 label = self._digraph.edge_label(edge[1],edge[0])
830 self._digraph.delete_edge(edge[1],edge[0])
831 self._digraph.add_edge(edge[0],edge[1],label)
832 self._M = _edge_list_to_matrix( self._digraph.edges(), self._n, self._m )
833 self._mutation_type = None
834 else:
835 raise ValueError, 'The order is no total order on the vertices of the quiver or a list of edges to be oriented.'
836
837 def mutation_class_iter( self, depth=infinity, show_depth=False, return_paths=False, data_type="quiver", up_to_equivalence=True, sink_source=False ):
838 """
839 Returns an iterator for the mutation class of self together with certain constrains.
840
841 INPUT:
842
843 - ``depth`` -- (default: infinity) integer, only quivers with distance at most depth from self are returned.
844 - ``show_depth`` -- (default: False) if True, the actual depth of the mutation is shown.
845 - ``return_paths`` -- (default: False) if True, a shortest path of mutation sequences from self to the given quiver is returned as well.
846 - ``data_type`` -- (default: "quiver") can be one of the following::
847 - "quiver", "matrix", "digraph", "dig6", "path"
848 - ``up_to_equivalence`` -- (default: True) if True, only quivers up to equivalence are considered.
849 - ``sink_source`` -- (default: False) if True, only mutations at sinks and sources are applied.
850
851 EXAMPLES::
852
853 sage: Q = Quiver(['A',3])
854 sage: it = Q.mutation_class_iter()
855 sage: for T in it: print T
856 Quiver on 3 vertices of type ['A', 3]
857 Quiver on 3 vertices of type ['A', 3]
858 Quiver on 3 vertices of type ['A', 3]
859 Quiver on 3 vertices of type ['A', 3]
860
861 sage: it = Q.mutation_class_iter(depth=1)
862 sage: for T in it: print T
863 Quiver on 3 vertices of type ['A', 3]
864 Quiver on 3 vertices of type ['A', 3]
865 Quiver on 3 vertices of type ['A', 3]
866
867 sage: it = Q.mutation_class_iter(show_depth=True)
868 sage: for T in it: pass
869 Depth: 1 found: 3 Time: ... s
870 Depth: 2 found: 4 Time: ... s
871
872 sage: it = Q.mutation_class_iter(return_paths=True)
873 sage: for T in it: print T
874 (Quiver on 3 vertices of type ['A', 3], [])
875 (Quiver on 3 vertices of type ['A', 3], [1])
876 (Quiver on 3 vertices of type ['A', 3], [0])
877 (Quiver on 3 vertices of type ['A', 3], [0, 1])
878
879 sage: it = Q.mutation_class_iter(up_to_equivalence=False)
880 sage: for T in it: print T
881 Quiver on 3 vertices of type ['A', 3]
882 Quiver on 3 vertices of type ['A', 3]
883 Quiver on 3 vertices of type ['A', 3]
884 Quiver on 3 vertices of type ['A', 3]
885 Quiver on 3 vertices of type ['A', 3]
886 Quiver on 3 vertices of type ['A', 3]
887 Quiver on 3 vertices of type ['A', 3]
888 Quiver on 3 vertices of type ['A', 3]
889 Quiver on 3 vertices of type ['A', 3]
890 Quiver on 3 vertices of type ['A', 3]
891 Quiver on 3 vertices of type ['A', 3]
892 Quiver on 3 vertices of type ['A', 3]
893 Quiver on 3 vertices of type ['A', 3]
894 Quiver on 3 vertices of type ['A', 3]
895
896 sage: it = Q.mutation_class_iter(return_paths=True,up_to_equivalence=False)
897 sage: for T in it: print T
898 (Quiver on 3 vertices of type ['A', 3], [])
899 (Quiver on 3 vertices of type ['A', 3], [2])
900 (Quiver on 3 vertices of type ['A', 3], [1])
901 (Quiver on 3 vertices of type ['A', 3], [0])
902 (Quiver on 3 vertices of type ['A', 3], [2, 1])
903 (Quiver on 3 vertices of type ['A', 3], [0, 1])
904 (Quiver on 3 vertices of type ['A', 3], [0, 1, 2])
905 (Quiver on 3 vertices of type ['A', 3], [0, 1, 0])
906 (Quiver on 3 vertices of type ['A', 3], [2, 1, 2])
907 (Quiver on 3 vertices of type ['A', 3], [2, 1, 0])
908 (Quiver on 3 vertices of type ['A', 3], [2, 1, 0, 2])
909 (Quiver on 3 vertices of type ['A', 3], [2, 1, 0, 1])
910 (Quiver on 3 vertices of type ['A', 3], [2, 1, 2, 1])
911 (Quiver on 3 vertices of type ['A', 3], [2, 1, 2, 0])
912 """
913 if data_type == "dig6":
914 return_dig6 = True
915 else:
916 return_dig6 = False
917 dg = DiGraph( self._digraph )
918 MC_iter = _mutation_class_iter( dg, self._n, self._m, depth=depth, return_dig6=return_dig6, show_depth=show_depth, up_to_equivalence=up_to_equivalence, sink_source=sink_source )
919 for data in MC_iter:
920 if data_type == "quiver":
921 Q = Quiver( data[0] )
922 Q._mutation_type = self._mutation_type
923 if return_paths:
924 yield ( Q, data[1] )
925 else:
926 yield Q
927 elif data_type == "matrix":
928 Q = Quiver( data[0] )
929 yield Q._M
930 elif data_type == "digraph":
931 yield data[0]
932 elif data_type == "dig6":
933 yield data[0]
934 elif dig6_or_path == "path":
935 yield data[1]
936 else:
937 raise ValueError, "The parameter for dig6_or_path was not recognized."
938
939 def mutation_class( self, depth=infinity, show_depth=False, return_paths=False, data_type="quiver", up_to_equivalence=True, sink_source=False ):
940 """
941 Returns the mutation class of self together with certain constrains.
942
943 INPUT:
944
945 - ``depth`` -- (default: infinity) integer, only seeds with distance at most depth from self are returned.
946 - ``show_depth`` -- (default: False) if True, the actual depth of the mutation is shown.
947 - ``return_paths`` -- (default: False) if True, a shortest path of mutation sequences from self to the given quiver is returned as well.
948 - ``data_type`` -- (default: "quiver") can be one of the following::
949 - "quiver" -- the quiver is returned
950 - "dig6" -- the dig6-data is returned
951 - "path" -- shortest paths of mutation sequences from self are returned
952 - ``sink_source`` -- (default: False) if True, only mutations at sinks and sources are applied.
953
954
955 EXAMPLES::
956
957 sage: Q = Quiver(['A',3])
958 sage: Ts = Q.mutation_class()
959 sage: for T in Ts: print T
960 Quiver on 3 vertices of type ['A', 3]
961 Quiver on 3 vertices of type ['A', 3]
962 Quiver on 3 vertices of type ['A', 3]
963 Quiver on 3 vertices of type ['A', 3]
964
965 sage: Ts = Q.mutation_class(depth=1)
966 sage: for T in Ts: print T
967 Quiver on 3 vertices of type ['A', 3]
968 Quiver on 3 vertices of type ['A', 3]
969 Quiver on 3 vertices of type ['A', 3]
970
971 sage: Ts = Q.mutation_class(show_depth=True)
972 Depth: 1 found: 3 Time: ... s
973 Depth: 2 found: 4 Time: ... s
974
975 sage: Ts = Q.mutation_class(return_paths=True)
976 sage: for T in Ts: print T
977 (Quiver on 3 vertices of type ['A', 3], [])
978 (Quiver on 3 vertices of type ['A', 3], [1])
979 (Quiver on 3 vertices of type ['A', 3], [0])
980 (Quiver on 3 vertices of type ['A', 3], [0, 1])
981
982 sage: Ts = Q.mutation_class(up_to_equivalence=False)
983 sage: for T in Ts: print T
984 Quiver on 3 vertices of type ['A', 3]
985 Quiver on 3 vertices of type ['A', 3]
986 Quiver on 3 vertices of type ['A', 3]
987 Quiver on 3 vertices of type ['A', 3]
988 Quiver on 3 vertices of type ['A', 3]
989 Quiver on 3 vertices of type ['A', 3]
990 Quiver on 3 vertices of type ['A', 3]
991 Quiver on 3 vertices of type ['A', 3]
992 Quiver on 3 vertices of type ['A', 3]
993 Quiver on 3 vertices of type ['A', 3]
994 Quiver on 3 vertices of type ['A', 3]
995 Quiver on 3 vertices of type ['A', 3]
996 Quiver on 3 vertices of type ['A', 3]
997 Quiver on 3 vertices of type ['A', 3]
998
999 sage: Ts = Q.mutation_class(return_paths=True,up_to_equivalence=False)
1000 sage: for T in Ts: print T
1001 (Quiver on 3 vertices of type ['A', 3], [])
1002 (Quiver on 3 vertices of type ['A', 3], [2])
1003 (Quiver on 3 vertices of type ['A', 3], [1])
1004 (Quiver on 3 vertices of type ['A', 3], [0])
1005 (Quiver on 3 vertices of type ['A', 3], [2, 1])
1006 (Quiver on 3 vertices of type ['A', 3], [0, 1])
1007 (Quiver on 3 vertices of type ['A', 3], [0, 1, 2])
1008 (Quiver on 3 vertices of type ['A', 3], [0, 1, 0])
1009 (Quiver on 3 vertices of type ['A', 3], [2, 1, 2])
1010 (Quiver on 3 vertices of type ['A', 3], [2, 1, 0])
1011 (Quiver on 3 vertices of type ['A', 3], [2, 1, 0, 2])
1012 (Quiver on 3 vertices of type ['A', 3], [2, 1, 0, 1])
1013 (Quiver on 3 vertices of type ['A', 3], [2, 1, 2, 1])
1014 (Quiver on 3 vertices of type ['A', 3], [2, 1, 2, 0])
1015
1016 """
1017 if depth is infinity:
1018 assert self.is_mutation_finite(), 'The mutation class can - for infinite mutation types - only be computed up to a given depth'
1019 return [ Q for Q in self.mutation_class_iter( depth=depth, show_depth=show_depth, return_paths=return_paths, data_type=data_type, up_to_equivalence=up_to_equivalence, sink_source=sink_source ) ]
1020
1021 def group_of_mutations( self ):
1022 """
1023 Returns the group generated by mutations on self.mutation_class(up_to_equivalence=False).
1024
1025 .. WARNING::
1026
1027 This group is very big, and can be computed only very small examples - see below.
1028
1029 EXAMPLES::
1030
1031 sage: Q = Quiver(['A',2])
1032 sage: Q.group_of_mutations()
1033 Permutation Group with generators [(1,2)]
1034
1035 sage: Q = Quiver(['A',3])
1036 sage: Q.group_of_mutations()
1037 Permutation Group with generators [(1,2)(3,4)(5,9)(6,7)(8,12)(10,11)(13,14), (1,3)(2,5)(4,6)(7,14)(8,11)(9,13)(10,12), (1,4)(2,3)(5,10)(6,8)(7,13)(9,14)(11,12)]
1038
1039 sage: Q = Quiver(['B',2])
1040 sage: Q.group_of_mutations()
1041 Permutation Group with generators [(1,2)]
1042 sage: Q = Quiver(['B',3])
1043 sage: Q.group_of_mutations()
1044 Permutation Group with generators [(1,2)(3,4)(5,6)(7,10)(8,9), (1,3)(2,6)(4,5)(7,9)(8,10), (1,4)(2,3)(5,7)(6,8)(9,10)]
1045
1046 sage: Q = Quiver(['A',1])
1047 sage: Q.group_of_mutations().cardinality()
1048 1
1049
1050 sage: Q = Quiver(['A',2])
1051 sage: Q.group_of_mutations().cardinality()
1052 2
1053
1054 sage: Q = Quiver(['A',3])
1055 sage: Q.group_of_mutations().cardinality()
1056 322560
1057 """
1058 assert self.is_mutation_finite(), 'The group of mutations can only be computed for finite types.'
1059 MC = self.mutation_class(up_to_equivalence=False)
1060 V = range( self._n )
1061 l = len( MC )
1062 gens = []
1063 for i in V:
1064 gen = [0]*l
1065 for j in range(l):
1066 if gen[j] == 0:
1067 S = MC[ j ]
1068 S_new = S.mutate( i, inplace=False )
1069 j_prime = MC.index( S_new )
1070 gen[ j ] = j_prime+1
1071 gen[ j_prime ] = j+1
1072 gens.append( gen )
1073 return PermutationGroup( gens )
1074
1075 def is_simply_laced( self ):
1076 return all( l == (1,-1) for l in self._digraph.edge_labels() )
1077
1078 def is_finite( self ):
1079 """
1080 Returns True if self is of finite type.
1081
1082 EXAMPLES::
1083
1084 sage: Q = Quiver(['A',3])
1085 sage: Q.is_finite()
1086 True
1087 sage: Q = Quiver(['A',[2,2],1])
1088 sage: Q.is_finite()
1089 False
1090 """
1091 mt = self.mutation_type()
1092 if type(mt) is str:
1093 return False
1094 else:
1095 return mt.is_finite()
1096
1097 def is_mutation_finite( self, nr_of_checks=None, return_path=False ):
1098 """
1099 Uses a non-deterministic method by random mutations in various directions. Can result in a wrong answer.
1100
1101 INPUT:
1102
1103 - ``nr_of_checks`` -- (default: None) number of mutations applied. Standard is 500*(number of vertices of self).
1104 - ``return_path`` -- (default: False) if True, in case of self not being mutation finite, a path from self to a quiver with an edge label (a,-b) and a*b > 4 is returned.
1105
1106 ALGORITHM:
1107
1108 A quiver is mutation infinite if and only if every edge label (a,-b) satisfy a*b > 4.
1109 Thus, we apply random mutations in random directions
1110
1111 EXAMPLES::
1112
1113 sage: Q = Quiver(['A',10])
1114 sage: Q._mutation_type = None
1115 sage: Q.is_mutation_finite()
1116 True
1117
1118 sage: Q = Quiver([(0,1),(1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,8),(2,9)])
1119 sage: Q.is_mutation_finite()
1120 False
1121 """
1122 if self._n <= 2:
1123 return True
1124 elif not return_path and self._mutation_type == 'undetermined infinite mutation type':
1125 return False
1126 elif type( self._mutation_type ) in [QuiverMutationType_Irreducible, QuiverMutationType_Reducible] and self._mutation_type.is_mutation_finite():
1127 return True
1128 elif not return_path and type( self._mutation_type ) in [QuiverMutationType_Irreducible, QuiverMutationType_Reducible] and not self._mutation_type.is_mutation_finite():
1129 return False
1130 else:
1131 import random
1132 n, m = self._n, self._m
1133 if nr_of_checks is None:
1134 nr_of_checks = 1000*n
1135 M = copy( self._M )
1136 k = 0
1137 path = []
1138 for i in xrange( nr_of_checks ):
1139 # this test is done to avoid mutating back in the same direction
1140 k_test = k
1141 while k_test == k:
1142 k = random.randint(0,n-1)
1143 M.mutate( k )
1144 path.append(k)
1145 for i,j in M.nonzero_positions():
1146 if i<j and M[i,j]*M[j,i] < -4:
1147 self._mutation_type = 'undetermined infinite mutation type'
1148 if return_path:
1149 return ( False, path )
1150 else:
1151 return False
1152 return True
1153
1154 def mutation_type( self ):
1155 """
1156 Returns the mutation_type of each connected component of self if it can be determined,
1157 otherwise, the mutation type of this component is set to be unknown.
1158
1159 The mutation types of the components are ordered by vertex labels.
1160
1161 WARNING:
1162
1163 - All finite types can be detected,
1164 - All affine types can be detected, EXCEPT affine type D (the algorithm is not yet implemented)
1165 - All exceptional types can be detected.
1166
1167 - Might fail to work if it is used within different Sage processes simultaneously (that happend in the doctesting).
1168
1169 EXAMPLES:
1170
1171 - finite types::
1172
1173 sage: Q = Quiver(['A',5])
1174 sage: Q._mutation_type = None
1175 sage: Q.mutation_type()
1176 ['A', 5]
1177
1178 sage: Q = Quiver([(0,1),(1,2),(2,3),(3,4)])
1179 sage: Q.mutation_type()
1180 ['A', 5]
1181
1182 - affine types::
1183
1184 sage: Q = Quiver(['E',8,[1,1]]); Q
1185 Quiver on 10 vertices of type ['E', 8, [1, 1]]
1186 sage: Q._mutation_type = None; Q
1187 Quiver on 10 vertices
1188 sage: Q.mutation_type()
1189 ['E', 8, [1, 1]]
1190
1191 - the not yet working affine type D::
1192
1193 sage: Q = Quiver(['D',4,1])
1194 sage: Q._mutation_type = None
1195 sage: Q.mutation_type()
1196 'undetermined finite mutation type'
1197
1198 - the exceptional types::
1199
1200 sage: Q = Quiver(['X',6,2])
1201 sage: Q._mutation_type = None
1202 sage: Q.mutation_type()
1203 ['X', 6, 2]
1204
1205 - infinite types::
1206
1207 sage: Q = Quiver(['GR',[4,9],3])
1208 sage: Q._mutation_type = None
1209 sage: Q.mutation_type()
1210 'undetermined infinite mutation type'
1211 """
1212 # checking if the mutation type is known alreadye
1213 if self._mutation_type is None:
1214 # checking mutation type only for the principal part
1215 if self._m > 0:
1216 dg = self._digraph.subgraph( range(self._n) )
1217 else:
1218 dg = self._digraph
1219
1220 # checking the type for each connected component
1221 mutation_type = []
1222 connected_components = dg.connected_components()
1223 connected_components.sort()
1224 for component in connected_components:
1225 dg_component = dg.subgraph( component )
1226 mut_type_part = _connected_mutation_type( dg_component )
1227 if mut_type_part == 'unknown':
1228 iso, orbits = _dg_canonical_form( dg_component, self._n, self._m )
1229 dig6 = _digraph_to_dig6( dg_component, hashable=True )
1230 mut_type_part = _mutation_type_from_data( dg_component.order(), dig6 )
1231 if mut_type_part == 'unknown':
1232 self.is_mutation_finite()
1233 if self._mutation_type is None:
1234 self._mutation_type = 'undetermined finite mutation type'
1235 return self._mutation_type
1236 mutation_type.append( mut_type_part )
1237
1238 # the empty quiver case
1239 if len( mutation_type ) == 0:
1240 mutation_type = QuiverMutationType( ['A',0] )
1241 # the connected quiver case
1242 elif len( mutation_type ) == 1:
1243 mutation_type = mutation_type[0]
1244 elif len( mutation_type ) > 1:
1245 mutation_type = QuiverMutationType( mutation_type )
1246
1247 self._mutation_type = mutation_type
1248 return self._mutation_type
1249
1250 # methods for path algebras for quivers
1251 def quiver_paths_from_source(self, v):
1252 assert self.is_simply_laced(), "Paths can only be considered for simply laced quivers."
1253 dg = self._digraph.copy()
1254 for a,b in dg.edges(labels=False):
1255 dg.set_edge_label(a,b,None)
1256 gp = GraphPaths(self._digraph)
1257 source_paths = [ [v] ]
1258 for e in gp.outgoing_edges(v):
1259 target = e[1]
1260 target_paths = self.quiver_paths_from_source(target)
1261 target_paths = [ (e,)+path for path in target_paths]
1262 source_paths += target_paths
1263 labelled_source_paths = []
1264 for path in source_paths:
1265 if len(path) > 1 and not isinstance(path[-1], tuple):
1266 labelled_source_paths.append(path[:-1])
1267 else:
1268 labelled_source_paths.append(path)
1269 assert len(labelled_source_paths) == len(source_paths)
1270 return map(tuple,labelled_source_paths)
1271
1272 def quiver_paths(self):
1273 paths = []
1274 for source in self.vertices():
1275 paths += self.quiver_paths_from_source(source)
1276 return paths
1277
1278 def quiver_paths_from_source_to_target(self, source, target):
1279 source_paths = self.quiver_paths_from_source(source)
1280 paths = []
1281 for path in source_paths:
1282 if isinstance(path[-1], tuple) and path[-1][1] == target:
1283 paths.append(path)
1284 else:
1285 if path[0] == target:
1286 paths.append(path)
1287 return paths
1288
1289 def quiver_paths_to_target(self, target):
1290 paths = []
1291 for path in self.quiver_paths():
1292 if isinstance(path[-1], tuple) and path[-1][1] == target:
1293 paths.append(path)
1294 else:
1295 if path[0] == target:
1296 paths.append(path)
1297 return paths
1298
1299 def quiver_path_length(self, path):
1300 return add(1 for edge in path if isinstance(edge, tuple))
1301
1302 def concatenate_paths_l2r(self, p, q):
1303 # p is a nontrivial path
1304 if isinstance(p[-1], tuple):
1305 if isinstance(q[0], tuple) and p[-1][1] == q[0][0]:
1306 return p + q
1307 elif p[-1][1] == q[0]:
1308 return p
1309 else: # p is a vertex
1310 if isinstance(q[0], tuple) and p[0] == q[0][0]:
1311 return q
1312 elif p[0] == q[0]:
1313 return p
1314 return None
1315
1316 def concatenate_paths_r2l(self, p, q):
1317 # q is a nontrivial path
1318 if isinstance(q[-1], tuple):
1319 if isinstance(p[0], tuple) and q[-1][1] == p[0][0]:
1320 return q + p
1321 elif q[-1][1] == p[0]:
1322 return q
1323 else: # q is a vertex
1324 if isinstance(p[0], tuple) and q[0] == p[0][0]:
1325 return p
1326 elif q[0] == p[0]:
1327 return q
1328 return None
1329
1330 def path_algebra(self, ring):
1331 return PathAlgebra(ring, self)
1332
1333 def to_gap_quiver(self, rename=True):
1334 r"""
1335 sage: Q = Quiver({0:[1,1,3],1:[2],2:[4],3:[4]})
1336 sage: Q.to_gap_quiver()
1337 sage: V = Family(dict([(v,i+1) for (i,v) in enumerate(Q.vertices())]))
1338 sage: arrows = [[V[p[0]], V[p[1]]] for p in Q.edges()]
1339
1340 ::
1341
1342 sage: Q = Quiver({'a':['b','b']})
1343 sage:
1344 gap> Quiver(len(V), arrows)
1345 """
1346 return GAPQuiver(self)
1347
1348 class PathAlgebra(CombinatorialFreeModule):
1349 @staticmethod
1350 def __classcall__(cls, ring, quiver):
1351 quiver = quiver.copy()
1352 quiver._immutable = True
1353 return super(PathAlgebra, cls).__classcall__(cls, ring, quiver)
1354
1355 def __init__(self, ring, quiver, prefix="Q"):
1356 self._quiver = quiver
1357 CombinatorialFreeModule.__init__(self,
1358 ring,
1359 quiver.quiver_paths(),
1360 prefix = prefix,
1361 category = FiniteDimensionalAlgebrasWithBasis(ring))
1362
1363 def _repr_(self):
1364 return "Path algebra of %s over %s" % (self._quiver, self.base_ring())
1365
1366 def quiver(self):
1367 return self._quiver
1368
1369 @cached_method
1370 def one(self):
1371 return self.sum_of_monomials((v,) for v in self._quiver.vertices())
1372
1373 @cached_method
1374 def product_on_basis(self, p, q):
1375 r"""
1376 Product of two basis elements.
1377
1378 EXAMPLES::
1379
1380 sage: A = Quiver({0:[1,2],1:[2]}).path_algebra(QQ)
1381 sage: a = A[(0,)], A[(1,)], A[((1,2,None),)]
1382 sage: b = A[(0,)], A[((0, 1, None),)]
1383 sage: for ai in a:
1384 for bi in b:
1385 print "%s * %s == %s" % (ai, bi, ai*bi)
1386 ....:
1387 A[(0,)] * A[(0,)] == A[(0,)]
1388 A[(0,)] * A[((0, 1, None),)] == 0
1389 A[(1,)] * A[(0,)] == 0
1390 A[(1,)] * A[((0, 1, None),)] == A[((0, 1, None),)]
1391 A[((1, 2, None),)] * A[(0,)] == 0
1392 A[((1, 2, None),)] * A[((0, 1, None),)] == A[((0, 1, None), (1, 2, None))]
1393
1394 """
1395 pq = self._quiver.concatenate_paths_r2l(p, q)
1396 return self.monomial_or_zero_if_none(pq)
1397
1398 def vertices(self):
1399 return tuple([self.monomial((v,)) for v in self._quiver.vertices()])
1400
1401 def arrows(self):
1402 return tuple([self.monomial((edge,)) for edge in self._quiver.edges()])
1403
1404 @cached_method
1405 def algebra_generators(self):
1406 return Family(self.vertices() + self.arrows())
1407
1408 def radical_basis(self):
1409 return self.arrows()
1410
1411 #def my_quotient(self, I):
1412 # I = self.submodule(I)
1413 # D = self.quotient(submodule=I, check=True, already_echelonized=False,
1414 # category=self.category().Subquotients())
1415 # D.rename("Quotient of %s" % (self,))
1416 # D._print_options['prefix'] = '%s/%s' % (self._print_options, 'I')
1417 # D._repr_option_bracket = False
1418 # return D
1419
1420 def projective_module(self, vertex):
1421 Q = self.quiver()
1422 v = vertex.support()[0][0]
1423 basis = [self.monomial(path) for path in Q.quiver_paths_to_target(v)]
1424 return self.submodule(basis, check=True, already_echelonized=False)
1425
1426 def projective_module_in_quotient(self, vertex, I):
1427 B = self.quotient(I)
1428 P = self.projective_module(v)
1429 return B.submodule([B.retract(p.lift()) for p in P.basis()])
1430
1431 def projective_module_in_quotient_decomposition(self, vertex, I):
1432 B = self.quotient(I)
1433 P = self.projective_module(v)
1434 M = B.submodule([B.retract(p.lift()) for p in P.basis()])
1435 Mx = {}
1436 for x in self.vertices():
1437 Mx[x] = M.submodule([M.retract(B.retract(m.lift().lift()*x)) for m in M.basis()])
1438 mats = {}
1439 for a in self.arrows():
1440 a_supp = a.support()[0][0]
1441 y, x = a_supp[:2]
1442 x = self.monomial((x,))
1443 y = self.monomial((y,))
1444 mat = []
1445 for mx in Mx[x].basis():
1446 mxa = Mx[y].retract(M.retract(B.retract(mx.lift().lift().lift()*a)))
1447 mat.append(vector(mxa))
1448 mats[a_supp] = matrix(mat)
1449 return mats
1450
1451 class QuiverMorphism(SageObject):
1452 def __init__(self, quiver, quiver_map_on_paths):
1453 self._quiver = quiver
1454 self._quiver_map_dict = quiver_map_on_paths
1455 self._codomain = quiver_map_on_paths.values()[0].parent()
1456
1457 def _repr_(self):
1458 return "Quiver map from %s to %s" % (self.quiver(), self.codomain())
1459
1460 def __iter__(self):
1461 Q = self.quiver()
1462 keys = sorted(self._quiver_map_dict.keys(),
1463 key=lambda x:Q.quiver_path_length((x,)))
1464 d = self._quiver_map_dict
1465 for key in keys:
1466 yield (key,d[key])
1467
1468 def quiver(self):
1469 return self._quiver
1470
1471 @cached_method
1472 def domain(self):
1473 ring = self.codomain().base_ring()
1474 return self.quiver().path_algebra(ring)
1475
1476 def codomain(self):
1477 return self._codomain
1478
1479 @lazy_attribute
1480 def algebra_morphism(self):
1481 return self.domain().module_morphism(on_basis=self.quiver_map_on_basis, codomain=self.codomain())
1482
1483 __call__ = algebra_morphism
1484
1485 def quiver_map_on_basis(self, path):
1486 qmapdict = self._quiver_map_dict
1487 if len(path) == 1:
1488 return qmapdict[path[0]]
1489 else:
1490 return self.codomain().prod(qmapdict[arrow] for arrow in path)
1491
1492 def quiver_relations_iter(self):
1493 quiver = self.quiver()
1494 for x in quiver.vertices():
1495 for y in quiver.vertices():
1496 for relation in self.quiver_relations(x,y):
1497 yield relation
1498
1499 def quiver_relations(self, x=None, y=None):
1500 if x is None and y is None:
1501 return list(self.quiver_relations_iter())
1502 quiver_paths = self.quiver().quiver_paths_from_source_to_target(x,y)
1503 kQ = self.domain()
1504 rows = []
1505 for path in quiver_paths:
1506 rows.append(self(kQ.monomial(path)).to_vector())
1507
1508 relations = []
1509 for relation in matrix(rows).kernel().basis():
1510 relations.append( kQ.sum_of_terms(zip(quiver_paths, relation)) )
1511 return relations
1512
1513 class GAPQuiver(SageObject):
1514 def __init__(self, quiver, rename=True):
1515 if gap.RequirePackage('"qpa"') != True:
1516 raise RuntimeError, "QPA package for GAP not installed"
1517 if rename is True:
1518 V = Family(dict([(v,i+1) for (i,v) in enumerate(quiver.vertices())]))
1519 gap_arrows = []
1520 to_gap_arrows = {}
1521 from_gap_arrows = {}
1522 for (i,p) in enumerate(quiver.edges()):
1523 label = '"a%s"'%(i+1,)
1524 gap_arrows.append([V[p[0]], V[p[1]], label])
1525 to_gap_arrows[p] = label
1526 from_gap_arrows[label] = p
1527 self._quiver = gap.Quiver(len(V), gap_arrows)
1528 self._to_gap_vertex = V
1529 self._from_gap_vertex = V.inverse_family()
1530 self._to_gap_arrow = to_gap_arrows
1531 self._from_gap_arrow = from_gap_arrows
1532 else:
1533 return NotImplemented
1534
1535 def vertices(self):
1536 return self._quiver.VerticesOfQuiver()
1537
1538 def arrows(self):
1539 return self._quiver.ArrowsOfQuiver()
1540
1541 def to_arrow(self, arrow):
1542 return self._to_gap_arrow[arrow]
1543
1544 def from_arrow(self, arrow):
1545 return self._from_gap_arrow['"%s"'%arrow]
1546
1547 def to_vertex(self, vertex):
1548 return self._to_gap_vertex[vertex]
1549
1550 @cached_method
1551 def path_algebra(self, ring=QQ):
1552 return gap.PathAlgebra(QQ, self._quiver)
1553
1554 def path_algebra_quotient(self, generators, ring=QQ):
1555 A = self.path_algebra(ring)
1556 I = self.ideal(generators)
1557 GBNPGroebnerBasis(I)
1558 return gap("%s/%s" % (A.name(), I.name()))
1559
1560 def path_algebra_element(self, element):
1561 r"""
1562 TESTS::
1563
1564 sage: time Q, I = go(n=4)
1565 sage: q = Q.to_gap_quiver()
1566 sage: p = I[0]
1567 sage: q.path_algebra_element(p)
1568 """
1569 A = self.path_algebra()
1570 z = gap.Zero(A)
1571 for (path, coeff) in element:
1572 z += coeff * gap('*'.join('%s.%s' %
1573 (A.name(),str(self.to_arrow(arrow)).replace('"',''))
1574 for arrow in path))
1575 return z
1576
1577 def path_algebra_vertex(self, vertex):
1578 r"""
1579 TESTS::
1580
1581 sage: time Q, I = go(n=4)
1582 sage: q = Q.to_gap_quiver()
1583 sage: q.path_algebra_vertex(Q.vertices()[-2])
1584 """
1585 A = self.path_algebra()
1586 return gap.get_record_element(A, "v"+str(self.to_vertex(vertex)))
1587
1588 def ideal(self, generators):
1589 r"""
1590 TESTS::
1591
1592 sage: time Q, I = go(n=4)
1593 sage: q = Q.to_gap_quiver()
1594 sage: q.ideal(I)
1595 """
1596 elems = map(self.path_algebra_element, generators)
1597 return gap.Ideal(self.path_algebra(), elems)
1598
1599 def projective_indecomposable(self, vertex, generators):
1600 r"""
1601 TESTS::
1602
1603 sage: time Q, I = go(n=4)
1604 sage: q = Q.to_gap_quiver()
1605 sage: v = Q.vertices()[-1]; v
1606 sage: q.projective_indecomposable(v, I)
1607
1608 GAP code for our example::
1609
1610 Q := Quiver( ["v1","v2","v3","v4","v5","v6","v7","v8","v9","v10","v11","v12","v13","v14","v15","v16"], [["v1","v5","a1"],["v1","v12","a2"],["v2","v4","a3"],["v5","v15","a4"],["v8","v10","a5"],["v12","v15","a6"],["v13","v11","a7"],["v16","v7","a8"]]);
1611 A := PathAlgebra(Rationals,Q);
1612 I := Ideal(A, [ A.a1*A.a4 - A.a2*A.a6 ]);
1613 gb := GBNPGroebnerBasis(I);
1614 GroebnerBasis(I,gb);
1615 B := A/I;
1616 B.a1*B.a4 - B.a2*B.a6;
1617 P := RightProjectiveModule(B, [B.v16]);
1618 """
1619 Q = self._quiver
1620 A = gap.PathAlgebra(QQ, Q)
1621 gap_generators = []
1622 z = gap.Zero(A)
1623 for element in generators:
1624 for (path, coeff) in element:
1625 z += coeff * gap('*'.join('%s.%s' %
1626 (A.name(),str(self.to_arrow(arrow)).replace('"',''))
1627 for arrow in path))
1628 gap_generators.append(z.name())
1629 I = gap('Ideal(%s, [%s])' % (A.name(), ','.join(gap_generators)))
1630 gb = gap.GBNPGroebnerBasis(I)
1631 gap.GroebnerBasis(I,gb)
1632 B = gap('%s/%s' % (A.name(), I.name()))
1633 v = self.to_vertex(vertex)
1634 #print "RightProjectiveModule(%s,[%s.v%s])" % (B.name(),B.name(),v)
1635 return gap("RightProjectiveModule(%s,[%s.v%s])" % (B.name(),B.name(),v))
1636
1637 def grobner_basis_of_ideal(self, generators):
1638 r"""
1639 TESTS::
1640
1641 sage: time Q, I = go(n=4)
1642 sage: q = Q.to_gap_quiver()
1643 sage: q.ideal(I)
1644 sage: q.grobner_basis_of_ideal(I)
1645 """
1646 gap.RequirePackage('"GBNP"')
1647 A = self.path_algebra()
1648 elems = map(self.path_algebra_element, generators)
1649 gb = gap.GBNPGroebnerBasis(elems, A)
1650 return GroebnerBasis(I, gb)
1651
1652 # TODO: INCOMPLETE
1653 def representation(self, matrices):
1654 r"""
1655 gap> Q := Quiver(2, [[1, 2, "a"], [2, 1, "b"],[1, 1, "c"]]);
1656 <quiver with 2 vertices and 3 arrows>
1657 gap> P := PathAlgebra(Rationals, Q);
1658 <algebra-with-one over Rationals, with 5 generators>
1659 gap> matrices := [["a", [[1,0,0],[0,1,0]]], ["b", [[0,1],[1,0],[0,1]]],
1660 > ["c", [[0,0],[1,0]]]];
1661 [ [ "a", [ [ 1, 0, 0 ], [ 0, 1, 0 ] ] ],
1662 [ "b", [ [ 0, 1 ], [ 1, 0 ], [ 0, 1 ] ] ],
1663 [ "c", [ [ 0, 0 ], [ 1, 0 ] ] ] ]
1664 gap> M := RightModuleOverPathAlgebra(P,matrices);
1665
1666 EXAMPLES::
1667
1668 sage: Q = Quiver({1:[1,2],2:[1]})
1669 sage: matrices = [["a", [[1,0,0],[0,1,0]]],
1670 ... ["b", [[0,1],[1,0],[0,1]]], ["c", [[0,0],[1,0]]]]
1671 sage: q = Q.to_gap_quiver()
1672
1673 """
1674 rep = []
1675 for arrow in self.arrows():
1676 m = matrices[self.from_arrow(arrow)]
1677 if m.nrows() == 0 or m.ncols() == 0:
1678 m = [m.nrows(), m.ncols()]
1679 rep.append( ['"%s"'%arrow, m] )
1680 Q = self._quiver
1681 A = gap.PathAlgebra(QQ, Q)
1682 print gap(rep)
1683 return gap.RightModuleOverPathAlgebra(A, rep)
Attached Files
To refer to attachments on a page, use attachment:filename, as shown below in the list of files. Do NOT use the URL of the [get] link, since this is subject to change and can break easily.You are not allowed to attach a file to this page.