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.