## 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.
• [get | view] (2012-02-08 10:13:40, 189.3 KB) [[attachment:Basic Combinatorics intro.sws]]
• [get | view] (2012-02-09 10:11:00, 616.2 KB) [[attachment:Cluster Package demo (1).sws]]
• [get | view] (2012-02-09 10:10:36, 47.8 KB) [[attachment:Cluster complexes and generalized associahedra (1).sws]]
• [get | view] (2012-02-08 09:25:38, 55.5 KB) [[attachment:Notebook intro.sws]]
• [get | view] (2012-02-09 10:10:49, 2715.7 KB) [[attachment:Sage-Combinat demo (1).sws]]
• [get | view] (2012-02-09 10:11:09, 666.7 KB) [[attachment:The Compendium (1).sws]]
• [get | view] (2012-02-09 14:18:20, 63.0 KB) [[attachment:quiver.py]]
• [get | view] (2012-02-10 12:49:55, 77.4 KB) [[attachment:reflection_functors.sws]]

You are not allowed to attach a file to this page.