CoCalc -- alcove

GitHub Repository: sagemath/sagelib
Path: blob/master/sage/combinat/crystals/alcove_path.py
⁴⁰⁹⁶ views
1
r"""
2
Crystals of alcove paths
3
"""
4

5
#*****************************************************************************
6
#       Copyright (C) 2008 Brant Jones <brant at math.ucdavis.edu>
7
#
8
#  Distributed under the terms of the GNU General Public License (GPL)
9
#                  http://www.gnu.org/licenses/
10
#****************************************************************************
11

12
from sage.structure.unique_representation import UniqueRepresentation
13
from sage.structure.parent import Parent
14
from sage.categories.classical_crystals import ClassicalCrystals
15
from sage.combinat.crystals.letters import Letter
16
from sage.combinat.root_system.cartan_type import CartanType
17
from sage.rings.integer import Integer
18
from sage.misc.misc import math,ellipsis_range
19
from sage.combinat.partition import Partitions
20
from sage.combinat.crystals.all import CrystalOfTableaux
21
from sage.combinat.root_system.root_system import RootSystem
22
from sage.graphs.graph import DiGraph
23
import copy
24

25
#####################################################################
26
#  Crystal (parent) class.
27
#####################################################################
28

29
class ClassicalCrystalOfAlcovePaths(UniqueRepresentation, Parent):
30
    r"""
31
    Implementation of crystal of alcove paths of the given classical type with
32
    given highest weight, based on the Lenart--Postnikov model [LP2008].
33

34
    These are highest weight crystals for classical types `A_n`, `B_n`, `C_n`,
35
    `D_n` and the exceptional types `F_4`, `G_2`, `E_6`, `E_7`, `E_8`.
36

37
    INPUT:
38

39
        - ``cartan_type`` is the Cartan type of a classical Dynkin diagram
40
        - ``highest_weight`` is a dominant weight as a list of coefficients of
41
          the fundamental weights `Lambda_i`
42

43
    In this model, a chain of roots is associated to the given highest_weight,
44
    and then the elements of the crystal are indexed by "admissible subsets"
45
    which indicate "folding positions" along the chain of roots.  See [LP2008]
46
    for details.
47

48
    TODO:
49

50
    - Resolve speed issues;  `E_6(\Lambda_1)` takes just under 4 minutes to list().
51
      To construct the highest-weight node takes 15 sec for `E_6(\Lambda_4)`.
52
      The initial chain has 42 roots.
53

54
    TESTS:
55

56
    The following example appears in Figure 2 of [LP2008]::
57

58
        sage: C = ClassicalCrystalOfAlcovePaths(['G',2],[0,1]);
59
        sage: G = C.digraph()
60
        sage: GG= DiGraph({
61
        ...       ()        : {(0)         : 2 },
62
        ...       (0)       : {(0,8)       : 1 },
63
        ...       (0,1)     : {(0,1,7)     : 2 },
64
        ...       (0,1,2)   : {(0,1,2,9)   : 1 },
65
        ...       (0,1,2,3) : {(0,1,2,3,4) : 2 },
66
        ...       (0,1,2,6) : {(0,1,2,3)   : 1 },
67
        ...       (0,1,2,9) : {(0,1,2,6)   : 1 },
68
        ...       (0,1,7)   : {(0,1,2)     : 2 },
69
        ...       (0,1,7,9) : {(0,1,2,9)   : 2 },
70
        ...       (0,5)     : {(0,1)       : 1, (0,5,7) : 2 },
71
        ...       (0,5,7)   : {(0,5,7,9)   : 1 },
72
        ...       (0,5,7,9) : {(0,1,7,9)   : 1 },
73
        ...       (0,8)     : {(0,5)       : 1 },
74
        ...       })
75
        sage: G.is_isomorphic(GG)
76
        True
77

78
        sage: for edge in sorted([(u.value, v.value, i) for (u,v,i) in G.edges()]):
79
        ...       print edge
80
        ([], [0], 2)
81
        ([0], [0, 8], 1)
82
        ([0, 1], [0, 1, 7], 2)
83
        ([0, 1, 2], [0, 1, 2, 9], 1)
84
        ([0, 1, 2, 3], [0, 1, 2, 3, 4], 2)
85
        ([0, 1, 2, 6], [0, 1, 2, 3], 1)
86
        ([0, 1, 2, 9], [0, 1, 2, 6], 1)
87
        ([0, 1, 7], [0, 1, 2], 2)
88
        ([0, 1, 7, 9], [0, 1, 2, 9], 2)
89
        ([0, 5], [0, 1], 1)
90
        ([0, 5], [0, 5, 7], 2)
91
        ([0, 5, 7], [0, 5, 7, 9], 1)
92
        ([0, 5, 7, 9], [0, 1, 7, 9], 1)
93
        ([0, 8], [0, 5], 1)
94

95
    REFERENCES:
96

97
        .. [LP2008]  C. Lenart and A. Postnikov. A combinatorial model for crystals of Kac-Moody algebras. Trans. Amer. Math. Soc.  360  (2008), 4349-4381. 
98
    """
99

100
    @staticmethod
101
    def __classcall__(cls, cartan_type, highest_weight):
102
        """
103
        cartan_type and heighest_weight are lists, which are mutable, this
104
        causes a problem for class UniqueRepresentation, the following code
105
        fixes this problem.
106

107
        EXAMPLES::
108
            sage: ClassicalCrystalOfAlcovePaths.__classcall__(ClassicalCrystalOfAlcovePaths,['A',3],[0,1,0])
109
            <class 'sage.combinat.crystals.alcove_path.ClassicalCrystalOfAlcovePaths_with_category'>
110
        """
111
        cartan_type = CartanType(cartan_type)
112
        highest_weight = tuple(highest_weight)
113
        return super(ClassicalCrystalOfAlcovePaths, cls).__classcall__(cls, cartan_type, highest_weight)
114

115
    def __init__(self, cartan_type, highest_weight):
116
        """
117
        EXAMPLES::
118

119
            sage: C = ClassicalCrystalOfAlcovePaths(['A',3],[1,0,0])
120
            sage: C.list()
121
            [[], [0], [0, 1], [0, 1, 2]]
122
            sage: TestSuite(C).run()
123
        """
124
        Parent.__init__(self, category = ClassicalCrystals())
125
        self._cartan_type = CartanType(cartan_type)
126
        self._name = "The crystal of alcove paths for type %s"%cartan_type
127
        self.chain_cache = {}
128
        self.endweight_cache = {}
129

130
        self.R = RootSystem(cartan_type)
131
        alpha = self.R.root_space().simple_roots()
132
        Lambda = self.R.weight_space().basis()
133

134
        self.positive_roots = sorted(self.R.root_space().positive_roots());
135

136
        self.weight = Lambda[Integer(1)] - Lambda[Integer(1)]
137
        offset = self.R.index_set()[Integer(0)]
138
        for j in self.R.index_set():
139
            self.weight = self.weight + highest_weight[j-offset]*Lambda[j]
140

141
        self.initial_element = self([])
142

143
        self.initial_element.chain = self.get_initial_chain(self.weight)
144
        rho = (Integer(1)/Integer(2))*sum(self.positive_roots)
145
        self.initial_element.endweight = rho
146

147
        self.chain_cache[ str([]) ] = self.initial_element.chain
148
        self.endweight_cache[ str([]) ] = self.initial_element.endweight
149

150
        self.module_generators = [self.initial_element]
151

152
        self._list = super(ClassicalCrystalOfAlcovePaths, self).list()
153
        self._digraph = super(ClassicalCrystalOfAlcovePaths, self).digraph()
154
        self._digraph_closure = self.digraph().transitive_closure()
155

156
    def get_initial_chain(self, highest_weight):
157
        """
158
        Called internally by __init__() to construct the chain of roots
159
        associated to the highest weight element.
160

161
        EXAMPLES::
162
            sage: C = ClassicalCrystalOfAlcovePaths(['A',3],[0,1,0])
163
            sage: C.get_initial_chain(RootSystem(['A',3]).weight_space().basis()[1])
164
            [[alpha[1], alpha[1]], [alpha[1] + alpha[2], alpha[1] + alpha[2]], [alpha[1] + alpha[2] + alpha[3], alpha[1] + alpha[2] + alpha[3]]]
165
        """
166
        pos_roots = self.positive_roots
167
        tis = self.R.index_set()
168
        tis.reverse()
169
        cv_to_pos_root = {}
170
        to_sort = []
171
        for r in pos_roots:
172
            j = highest_weight.scalar( r.associated_coroot() )
173
            if (int(math.floor(j)) - j == Integer(0)):
174
                j = j - Integer(1)
175
            j = int(math.floor(j))
176
            for k in (ellipsis_range(Integer(0),Ellipsis,j)):
177
                cv = []
178
                cv.append((Integer(1)/highest_weight.scalar(r.associated_coroot()))*k)
179
                for i in tis:
180
                    cv.append((Integer(1)/highest_weight.scalar(r.associated_coroot()))*r.associated_coroot().coefficient(i))
181
                cv_to_pos_root[ str(cv) ] = r
182
                to_sort.append( cv )
183

184
        to_sort.sort() # Note:  Python sorts nested lists lexicographically by default.
185
        lambda_chain = []
186
        for t in to_sort:
187
            lambda_chain.append( [ cv_to_pos_root[str(t)], cv_to_pos_root[str(t)] ] )
188
        return lambda_chain
189

190
    def _element_constructor_(self, value):
191
        """
192
        Coerces value into self.
193

194
        EXAMPLES::
195

196
            sage: C = ClassicalCrystalOfAlcovePaths(['A',3],[1,0,0])
197
            sage: C.module_generators
198
            [[]]
199
            sage: C([]).e(1)
200
            sage: C([]).f(1)
201
            [0]
202
        """
203
        return self.element_class(self, value)
204

205
    def list(self):
206
        """
207
        Returns a list of the elements of self.
208

209
        .. warning::
210

211
           This can be slow!
212

213
        EXAMPLES::
214

215
            sage: C = ClassicalCrystalOfAlcovePaths(['A',3],[0,1,0])
216
            sage: C.list()
217
            [[], [0], [0, 1], [0, 2], [0, 1, 2], [0, 1, 2, 3]]
218
        """
219
        return self._list
220

221
    def digraph(self):
222
        """
223
        Returns the directed graph associated to self.
224

225
        EXAMPLES::
226

227
            sage: C = ClassicalCrystalOfAlcovePaths(['A',3],[0,1,0])
228
            sage: C.digraph().vertices()
229
            [[], [0], [0, 1], [0, 2], [0, 1, 2], [0, 1, 2, 3]]
230
            sage: C.digraph().edges()
231
            [([], [0], 2), ([0], [0, 1], 1), ([0], [0, 2], 3), ([0, 1], [0, 1, 2], 3), ([0, 2], [0, 1, 2], 1), ([0, 1, 2], [0, 1, 2, 3], 2)]
232
        """
233
        return self._digraph
234

235
    def lt_elements(self, x, y):
236
        r"""
237
        Returns True if and only if there is a path
238
        from x to y in the crystal graph.
239

240
        Because the crystal graph is classical, it is a directed
241
        acyclic graph which can be interpreted as a poset. This
242
        function implements the comparison function of this poset.
243

244
        EXAMPLES::
245

246
            sage: C = ClassicalCrystalOfAlcovePaths(['A',3],[0,1,0])
247
            sage: x = C([])
248
            sage: y = C([0,2])
249
            sage: C.lt_elements(x,y)
250
            True
251
            sage: C.lt_elements(y,x)
252
            False
253
            sage: C.lt_elements(x,x)
254
            False
255
        """
256
        assert x.parent() == self and y.parent() == self
257
        if self._digraph_closure.has_edge(x,y):
258
            return True
259
        return False
260

261
#####################################################################
262
#  Element class.
263
#####################################################################
264

265
class ClassicalCrystalOfAlcovePathsElement(Letter):
266
    r"""
267
    Crystal of alcove paths element
268

269
    These elements are indexed by "admissible subsets" which indicate "folding positions"
270
    along the chain of roots.  Not every subset corresponds to an element.
271

272
    TESTS::
273

274
        sage: C = ClassicalCrystalOfAlcovePaths(['A',3],[0,1,0])
275
        sage: C.list()
276
        [[], [0], [0, 1], [0, 2], [0, 1, 2], [0, 1, 2, 3]]
277
        sage: [ [ x < y for y in C ] for x in C ]
278
        [[False, True, True, True, True, True], [False, False, True, True, True, True], [False, False, False, False, True, True], [False, False, False, False, True, True], [False, False, False, False, False, True], [False, False, False, False, False, False]]
279
        sage: C([]).parent()
280
        <class 'sage.combinat.crystals.alcove_path.ClassicalCrystalOfAlcovePaths_with_category'>
281
        sage: C([])
282
        []
283
        sage: C([]) == C([0])
284
        False
285
        sage: C([]) == C([])
286
        True
287
        sage: C([]) < C([0])
288
        True
289
        sage: C([0,1]) < C([0,2])
290
        False
291
        sage: C([0,1]) < C([0,1,2,3])
292
        True
293
        sage: TestSuite(C).run()
294
    """
295

296
    def __init__(self, parent, value):
297
        """
298
        INPUT:
299

300
        - ``value`` is an admissible subset, stored as a list.
301

302
        chain is a chain of roots.  This is computed from value, using
303
        get_chain_from_subset().  We do this lazily because it can be
304
        expensive.
305

306
        endweight is the weight that lies at the end of the chain of roots.
307

308
        chain and endweight are cached (in the parent), and they are only
309
        computed when required by E(), F() or weight().
310

311
        The weight of the element can be theoretically be computed from
312
        endweight, although this is not yet implemented.
313

314
        EXAMPLES::
315

316
            sage: C = ClassicalCrystalOfAlcovePaths(['A',3],[0,1,0])
317
            sage: C.list()
318
            [[], [0], [0, 1], [0, 2], [0, 1, 2], [0, 1, 2, 3]]
319
            sage: c = C([0,1])
320
            sage: TestSuite(c).run()
321
        """
322
        Letter.__init__(self, parent, value)
323
        if (str(value) in parent.chain_cache.keys()):
324
            self.chain = parent.chain_cache[ str(value) ]
325
            self.endweight = parent.endweight_cache[ str(value) ]
326
        else:
327
            self.chain = None
328
            self.endweight = None
329

330
    def get_chain_from_subset(self, verbose = False):
331
        r"""
332
        Returns a list of pairs of roots, from an admissible subset of
333
        an initial chain of pairs of roots.  Called internally by
334
        __init__().
335

336
        EXAMPLES::
337

338
            sage: C = ClassicalCrystalOfAlcovePaths(['A',3],[0,1,0])
339
            sage: C([]).get_chain_from_subset()
340
            ([[alpha[2], alpha[2]], [alpha[1] + alpha[2], alpha[1] + alpha[2]], [alpha[2] + alpha[3], alpha[2] + alpha[3]], [alpha[1] + alpha[2] + alpha[3], alpha[1] + alpha[2] + alpha[3]]], 3/2*alpha[1] + 2*alpha[2] + 3/2*alpha[3])
341
        """
342
        rchain = []
343
        # NT: Is a deep copy required?
344
        rchain = copy.deepcopy(self.parent().initial_element.chain)
345
        rend = copy.deepcopy(self.parent().initial_element.endweight)
346
        J = sorted(copy.deepcopy(self.value))
347
        J.reverse()
348

349
        if verbose == True:
350
            print "**** get_chain_from_subset():  initial weight at infinity ", rend
351
        for i in J:
352
            (rchain, rend) = self.fold(i, rchain, rend)
353
            if verbose == True:
354
                print "**** get_chain_from_subset() after fold ", i, ":  weight at infinity ", rend
355
        return (rchain, rend)
356

357
    def fold(self, i, chain, endweight):
358
        r"""
359
        Returns a new chain that results from folding at position i.
360
        Called internally by __init__().
361

362
        TESTS::
363

364
            sage: C = ClassicalCrystalOfAlcovePaths(['A',3],[0,1,0])
365
            sage: C([0]).get_chain_from_subset()
366
            ([[alpha[2], -alpha[2]], [alpha[1], alpha[1]], [alpha[3], alpha[3]], [alpha[1] + alpha[2] + alpha[3], alpha[1] + alpha[2] + alpha[3]]], 3/2*alpha[1] + alpha[2] + 3/2*alpha[3])
367
        """
368
        s = self.parent().R.root_space().reflection(chain[i][Integer(0)])
369
        chain[i][Integer(1)] = s(chain[i][Integer(1)])
370
        for j in (ellipsis_range((i+Integer(1)),Ellipsis,len(chain)-Integer(1))):
371
            pair = chain[j]
372
            pair[Integer(0)] = s(pair[Integer(0)])
373
            pair[Integer(1)] = s(pair[Integer(1)])
374
        return (chain, s(endweight))
375

376
    def __hash__(self):
377
        """
378
        Return hash value.
379

380
        EXAMPLES::
381

382
            sage: C = ClassicalCrystalOfAlcovePaths(['A',3],[0,1,0])
383
            sage: C([0]).__hash__() == C([]).f(2).__hash__()
384
            True
385
        """
386
        return hash(tuple(self.value))
387

388
    def e(self, i, verbose=False):
389
        r"""
390
        Returns the action of `e_i` on self.
391

392
        EXAMPLES::
393

394
            sage: C = ClassicalCrystalOfAlcovePaths(['E',6],[1,0,0,0,0,0])  # long time (20s on sage.math, 2011)
395
            sage: C.module_generators  # long time
396
            [[]]
397
            sage: C([]).f(1)  # long time
398
            [0]
399
            sage: C([]).f(1).e(1)  # long time
400
            []
401
        """
402
        assert i in self.index_set()
403

404
        # Construct the chain associated to the subset self.value
405
        if self.chain is None:
406
            if (str(self.value) in self.parent().chain_cache.keys()):
407
                self.chain = self.parent().chain_cache[ str(self.value) ]
408
                self.endweight = self.parent().endweight_cache[ str(self.value) ]
409
            else:
410
                (self.chain, self.endweight) = self.get_chain_from_subset()
411
                self.parent().chain_cache[str(self.value)] = copy.deepcopy(self.chain)
412
                self.parent().endweight_cache[str(self.value)] = copy.deepcopy(self.endweight)
413

414
        ai = self.parent().R.root_space().simple_root(i)
415

416
        if verbose == True:
417
            print "( self.value, i = ", self.value, i, " ) "
418
            print "( chain = ", self.chain, " ) "
419
        IJp = filter( lambda j: self.chain[j][Integer(0)] == ai or self.chain[j][Integer(0)] == (-Integer(1))*ai, (ellipsis_range(Integer(0) ,Ellipsis, len(self.chain)-Integer(1))) )
420
        if verbose == True:
421
            print "( IJp = ", IJp, ") "
422
        SJp = []
423
        for j in IJp:
424
            pair = self.chain[j]
425
            if ( pair[Integer(0)].coefficients()[Integer(0)] < Integer(0) ):
426
                SJp.append( -Integer(1) )
427
            else:
428
                SJp.append( Integer(1) )
429
            if ( pair[Integer(1)].coefficients()[Integer(0)] < Integer(0) ):
430
                SJp.append( -Integer(1) )
431
            else:
432
                SJp.append( Integer(1) )
433

434
        if (self.endweight.scalar( ai.associated_coroot() ) < Integer(0)):
435
            SJp.append( -Integer(1) )
436
        else:
437
            SJp.append( Integer(1) )
438

439
        if verbose == True:
440
            print "( SJp = ", SJp, ") "
441

442
        LJp = []
443
        t = Integer(0)-(Integer(1)/Integer(2))
444
        for j in (ellipsis_range(Integer(0),Ellipsis,len(SJp)-Integer(1))):
445
            if SJp[j] == Integer(1):
446
                t = t+(Integer(1)/Integer(2))
447
            elif SJp[j] == -Integer(1):
448
                t = t-(Integer(1)/Integer(2))
449
            if ((j % Integer(2)) == Integer(0)):
450
                LJp.append(t)
451

452
        if verbose == True:
453
            print "( LJp = ", LJp, " ) "
454

455
        MJp = max(LJp)
456
        if verbose == True:
457
            print "( MJp = ", MJp, " ) "
458

459
        if (MJp <= LJp[ len(LJp)-1 ]):
460
            return None
461

462
        rLJp = copy.deepcopy(LJp)
463
        rLJp.reverse()
464
        k = rLJp.index(MJp)
465
        k = (len(LJp)-1) - k
466
        m = k + 1
467

468
        rsubseq = []
469
        rsubseq.extend(self.value)
470
        rsubseq.remove(IJp[k])
471
        if (m < len(IJp)):
472
            rsubseq.append(IJp[m])
473
        rsubseq.sort()
474

475
        return self.parent()(rsubseq)
476

477
    def f(self, i, verbose=False):
478
        r"""
479
        Returns the action of `f_i` on self.
480

481
        EXAMPLES::
482

483
            sage: C = ClassicalCrystalOfAlcovePaths(['E',6],[1,0,0,0,0,0])  # long time (21s on sage.math, 2011)
484
            sage: C.module_generators  # long time
485
            [[]]
486
            sage: C([]).f(1)  # long time
487
            [0]
488
            sage: C([]).f(1).f(3)  # long time
489
            [0, 1]
490
            sage: C([]).f(1).f(3).f(4)  # long time
491
            [0, 1, 2]
492
            sage: C([]).f(1).f(3).f(4).f(5)  # long time
493
            [0, 1, 2, 4]
494
            sage: C([]).f(1).f(3).f(4).f(2)  # long time
495
            [0, 1, 2, 3]
496
        """
497
        assert i in self.index_set()
498

499
        # Construct the chain associated to the subset self.value
500
        if self.chain is None:
501
            if (str(self.value) in self.parent().chain_cache.keys()):
502
                self.chain = self.parent().chain_cache[ str(self.value) ]
503
                self.endweight = self.parent().endweight_cache[ str(self.value) ]
504
            else:
505
                (self.chain, self.endweight) = self.get_chain_from_subset()
506
                self.parent().chain_cache[str(self.value)] = copy.deepcopy(self.chain)
507
                self.parent().endweight_cache[str(self.value)] = copy.deepcopy(self.endweight)
508

509
        ai = self.parent().R.root_space().simple_root(i)
510

511
        if verbose == True:
512
            print "( self.value, i = ", self.value, i, " ) "
513
            print "( chain = ", self.chain, " ) "
514
        IJp = filter( lambda j: self.chain[j][Integer(0)] == ai or self.chain[j][Integer(0)] == (-Integer(1))*ai, (ellipsis_range(Integer(0) ,Ellipsis, len(self.chain)-Integer(1))) )
515
        if verbose == True:
516
            print "( IJp = ", IJp, ") "
517
        SJp = []
518
        for j in IJp:
519
            pair = self.chain[j]
520
            if ( pair[Integer(0)].coefficients()[Integer(0)] < Integer(0) ):
521
                SJp.append( -Integer(1) )
522
            else:
523
                SJp.append( Integer(1) )
524
            if ( pair[Integer(1)].coefficients()[Integer(0)] < Integer(0) ):
525
                SJp.append( -Integer(1) )
526
            else:
527
                SJp.append( Integer(1) )
528

529
        # Incidentally, the vector at infinity in LJp is <mu(J), a_p^check>.
530
        # This gives an alternative way to calculate the last SJp/LJp entries.
531
        if (self.endweight.scalar( ai.associated_coroot() ) < Integer(0)):
532
            SJp.append( -Integer(1) )
533
        else:
534
            SJp.append( Integer(1) )
535

536
        if verbose == True:
537
            print "( SJp = ", SJp, ") "
538

539
        LJp = []
540
        t = Integer(0)-(Integer(1)/Integer(2))
541
        for j in (ellipsis_range(Integer(0),Ellipsis,len(SJp)-Integer(1))):
542
            if SJp[j] == Integer(1):
543
                t = t+(Integer(1)/Integer(2))
544
            elif SJp[j] == -Integer(1):
545
                t = t-(Integer(1)/Integer(2))
546
            if ((j % Integer(2)) == Integer(0)):
547
                LJp.append(t)
548

549
        if verbose == True:
550
            print "( LJp = ", LJp, " ) "
551

552
        MJp = max(LJp)
553
        if verbose == True:
554
            print "( MJp = ", MJp, " ) "
555

556
        if (MJp <= Integer(0)):
557
            return None
558

559
        m = LJp.index(MJp)
560
        k = m - Integer(1)
561

562
        rsubseq = []
563
        rsubseq.extend(self.value)
564
        if (m < len(IJp)):
565
            rsubseq.remove(IJp[m])
566
        rsubseq.append(IJp[k])
567
        rsubseq.sort()
568

569
        return self.parent()(rsubseq)
570

571
ClassicalCrystalOfAlcovePaths.Element = ClassicalCrystalOfAlcovePathsElement
572

573
#####################################################################
574
#  Code to test by comparing with existing crystal implementations.
575
#####################################################################
576

577
def compare_graphs(g1, g2, node1, node2):
578
    r"""
579
    Returns two edge-labeled DiGraphs obtained from Crystal.digraph(), starting
580
    from the root nodes of each graph.
581

582
    EXAMPLES:
583
        sage: G1 = sage.combinat.crystals.all.CrystalOfTableaux(['A',3], shape = [1,1]).digraph()
584
        sage: G2 = ClassicalCrystalOfAlcovePaths(['A',3],[0,1,0]).digraph()
585
        sage: sage.combinat.crystals.alcove_path.compare_graphs(G1, G2, G1.vertices()[0], G2.vertices()[0])
586
        True
587
    """
588
    for out_edge in g1.outgoing_edges( node1 ):
589
        matched = False
590
        for o2 in g2.outgoing_edges( node2 ):
591
            if o2[2] == out_edge[2]:
592
                if matched == True:
593
                    print "ERROR:  Two edges with the same label for ", out_edge, " exist."
594
                    return False
595
                matched = True
596
                result = compare_graphs(g1, g2, out_edge[1], o2[1])
597
                if result == False:
598
                    return False
599
        if matched == False:
600
            print "ERROR:  No matching edge for ", out_edge, "."
601
            return False
602
    return True
603

604
def test_against_tableaux(R, N, k):
605
    r"""
606
    Tests our ClassicalCrystalOfAlcovePaths against all of the tableaux crystals
607
    of type R in rank N with highest weight given by a partition of k.
608

609
    EXAMPLES::
610

611
        sage: sage.combinat.crystals.alcove_path.test_against_tableaux(['A',3], 3, 2)
612
        ** Shape  [2]
613
          T has  10  nodes.
614
          C weight  [2, 0, 0]
615
          C has  10  nodes.
616
          Compare graphs:  True
617
        ** Shape  [1, 1]
618
          T has  6  nodes.
619
          C weight  [0, 1, 0]
620
          C has  6  nodes.
621
          Compare graphs:  True
622
    """
623
    shapes = Partitions(k).list()
624
    for shape in shapes:
625
        print "** Shape ", shape
626
        T = CrystalOfTableaux(R, shape = shape)
627
        ct = len(T.list())
628
        print "  T has ", ct, " nodes."
629
        #T.digraph().show(edge_labels=True)
630
        H = T.digraph()
631
        weight = T.module_generators[0].weight()
632
        w = [ weight.scalar(RootSystem(R).ambient_space().simple_coroot(i)) for i in range(1,N+1) ]
633
        print "  C weight ", w
634

635
        C = ClassicalCrystalOfAlcovePaths(R , w)
636

637
        cc = len(C.list())
638
        #C.digraph().show(edge_labels=True)
639
        G = C.digraph()
640
        print "  C has ", cc, " nodes."
641
        if cc != ct:
642
            print "FAIL: number of nodes differ.", cc, ct
643
            return
644
        print "  Compare graphs: ", compare_graphs(G, H, G.vertices()[0], H.vertices()[0])
645

646

647

648
def test_some_specific_examples():
649
    r"""
650
    Tests our ClassicalCrystalOfAlcovePaths against some specific examples.
651

652
    EXAMPLES::
653

654
        sage: sage.combinat.crystals.alcove_path.test_some_specific_examples()  # long time (12s on sage.math, 2011)
655
        G2 example passed.
656
        C3 example passed.
657
        B3 example 1 passed.
658
        B3 example 2 passed.
659
        True
660
    """
661

662
    # This appears in Lenart.
663
    C = ClassicalCrystalOfAlcovePaths(['G',2],[0,1]);
664
    G = C.digraph();
665
    
666
    GT = DiGraph({
667
        ()        : {(0)         : 2 },
668
        (0)       : {(0,8)       : 1 },
669
        (0,1)     : {(0,1,7)     : 2 },
670
        (0,1,2)   : {(0,1,2,9)   : 1 },
671
        (0,1,2,3) : {(0,1,2,3,4) : 2 },
672
        (0,1,2,6) : {(0,1,2,3)   : 1 },
673
        (0,1,2,9) : {(0,1,2,6)   : 1 },
674
        (0,1,7)   : {(0,1,2)     : 2 },
675
        (0,1,7,9) : {(0,1,2,9)   : 2 },
676
        (0,5)     : {(0,1)       : 1, (0,5,7) : 2 },
677
        (0,5,7)   : {(0,5,7,9)   : 1 },
678
        (0,5,7,9) : {(0,1,7,9)   : 1 },
679
        (0,8)     : {(0,5)       : 1 }
680
        })
681

682

683
    if (G.is_isomorphic(GT) != True):
684
        return False;
685
    else:
686
        print "G2 example passed."
687

688
    # Some examples from Hong--Kang:
689

690
    # type C, ex. 8.3.5, pg. 189
691
    C = ClassicalCrystalOfAlcovePaths(['C',3],[0,0,1]);
692
    G = C.digraph();
693
    GT = DiGraph({
694
        ():{ (0): 3},
695
        (0):{ (0, 6): 2},
696
        (0, 1):{ (0, 1, 3): 3, (0, 1, 7): 1},
697
        (0, 1, 2):{ (0, 1, 2, 3): 3},
698
        (0, 1, 2, 3):{ (0, 1, 2, 3, 8): 2},
699
        (0, 1, 2, 3, 4):{ (0, 1, 2, 3, 4, 5): 3},
700
        (0, 1, 2, 3, 8):{ (0, 1, 2, 3, 4): 2},
701
        (0, 1, 3):{ (0, 1, 3, 7): 1},
702
        (0, 1, 3, 7):{ (0, 1, 2, 3): 1, (0, 1, 3, 7, 8): 2},
703
        (0, 1, 3, 7, 8):{ (0, 1, 2, 3, 8): 1},
704
        (0, 1, 7):{ (0, 1, 2): 1, (0, 1, 3, 7): 3},
705
        (0, 6):{ (0, 1): 2, (0, 6, 7): 1},
706
        (0, 6, 7):{ (0, 1, 7): 2}
707
        })
708

709
    if (G.is_isomorphic(GT) != True):
710
        return False;
711
    else:
712
        print "C3 example passed."
713

714
    # type B, fig. 8.1 pg. 172
715
    C = ClassicalCrystalOfAlcovePaths(['B',3],[2,0,0]);
716
    G = C.digraph();
717

718
    GT = DiGraph({
719
        ():{ (6): 1},
720
        (0):{ (0, 7): 2},
721
        (0, 1):{ (0, 1, 11): 3},
722
        (0, 1, 2):{ (0, 1, 2, 9): 2},
723
        (0, 1, 2, 3):{ (0, 1, 2, 3, 10): 1},
724
        (0, 1, 2, 3, 10):{ (0, 1, 2, 3, 4): 1},
725
        (0, 1, 2, 9):{ (0, 1, 2, 3): 2, (0, 1, 2, 9, 10): 1},
726
        (0, 1, 2, 9, 10):{ (0, 1, 2, 3, 10): 2},
727
        (0, 1, 5):{ (0, 1, 2): 3, (0, 1, 5, 9): 2},
728
        (0, 1, 5, 9):{ (0, 1, 2, 9): 3, (0, 1, 5, 9, 10): 1},
729
        (0, 1, 5, 9, 10):{ (0, 1, 2, 9, 10): 3},
730
        (0, 1, 8):{ (0, 1, 5): 3},
731
        (0, 1, 8, 9):{ (0, 1, 5, 9): 3, (0, 1, 8, 9, 10): 1},
732
        (0, 1, 8, 9, 10):{ (0, 1, 5, 9, 10): 3},
733
        (0, 1, 11):{ (0, 1, 8): 3},
734
        (0, 7):{ (0, 1): 2, (0, 7, 11): 3},
735
        (0, 7, 8):{ (0, 7, 8, 9): 2},
736
        (0, 7, 8, 9):{ (0, 1, 8, 9): 2},
737
        (0, 7, 8, 9, 10):{ (0, 1, 8, 9, 10): 2},
738
        (0, 7, 11):{ (0, 1, 11): 2, (0, 7, 8): 3},
739
        (6):{ (0): 1, (6, 7): 2},
740
        (6, 7):{ (0, 7): 1, (6, 7, 11): 3},
741
        (6, 7, 8):{ (0, 7, 8): 1, (6, 7, 8, 9): 2},
742
        (6, 7, 8, 9):{ (6, 7, 8, 9, 10): 1},
743
        (6, 7, 8, 9, 10):{ (0, 7, 8, 9, 10): 1},
744
        (6, 7, 11):{ (0, 7, 11): 1, (6, 7, 8): 3}
745
        })
746

747
    if (G.is_isomorphic(GT) != True):
748
        return False;
749
    else:
750
        print "B3 example 1 passed."
751

752
    C = ClassicalCrystalOfAlcovePaths(['B',3],[0,1,0]);
753
    G = C.digraph();
754

755
    GT = DiGraph({
756
        ():{ (0): 2},
757
        (0):{ (0, 1): 1, (0, 7): 3},
758
        (0, 1):{ (0, 1, 7): 3},
759
        (0, 1, 2):{ (0, 1, 2, 8): 2},
760
        (0, 1, 2, 3):{ (0, 1, 2, 3, 5): 1, (0, 1, 2, 3, 9): 3},
761
        (0, 1, 2, 3, 4):{ (0, 1, 2, 3, 4, 5): 1},
762
        (0, 1, 2, 3, 4, 5):{ (0, 1, 2, 3, 4, 5, 6): 2},
763
        (0, 1, 2, 3, 5):{ (0, 1, 2, 3, 5, 9): 3},
764
        (0, 1, 2, 3, 5, 9):{ (0, 1, 2, 3, 4, 5): 3},
765
        (0, 1, 2, 3, 9):{ (0, 1, 2, 3, 4): 3, (0, 1, 2, 3, 5, 9): 1},
766
        (0, 1, 2, 5):{ (0, 1, 2, 3, 5): 2},
767
        (0, 1, 2, 8):{ (0, 1, 2, 3): 2},
768
        (0, 1, 2, 8, 9):{ (0, 1, 2, 3, 9): 2},
769
        (0, 1, 7):{ (0, 1, 2): 3, (0, 1, 7, 8): 2},
770
        (0, 1, 7, 8):{ (0, 1, 7, 8, 9): 3},
771
        (0, 1, 7, 8, 9):{ (0, 1, 2, 8, 9): 3},
772
        (0, 2):{ (0, 1, 2): 1, (0, 2, 5): 2},
773
        (0, 2, 5):{ (0, 2, 5, 8): 1},
774
        (0, 2, 5, 8):{ (0, 1, 2, 5): 1},
775
        (0, 7):{ (0, 1, 7): 1, (0, 2): 3}
776
        })
777

778
    if (G.is_isomorphic(GT) != True):
779
        return False;
780
    else:
781
        print "B3 example 2 passed."
782

783
    # type B, fig. 8.3 pg. 174
784

785
    return True;
786

787

788
Product

Resources

Company
