def _matrix_to_digraph( M ):
    """
    Returns the digraph obtained from the matrix ``M``.
    In order to generate a quiver, we assume that ``M`` is skew-symmetrizable.

    EXAMPLES::

        sage: from sage.combinat.cluster_algebra_quiver.mutation_class import _matrix_to_digraph
        sage: _matrix_to_digraph(matrix(3,[0,1,0,-1,0,-1,0,1,0]))
        Digraph on 3 vertices
    """
    n = M.ncols()

    dg = DiGraph(sparse=True)
    for i,j in M.nonzero_positions():
        if i >= n: a,b = M[i,j],-M[i,j]
        else: a,b = M[i,j],M[j,i]
        if a > 0:
            dg._backend.add_edge(i,j,(a,b),True)
        elif i >= n:
            dg._backend.add_edge(j,i,(-a,-b),True)
    if dg.order() < M.nrows():
        for i in [ index for index in xrange(M.nrows()) if index not in dg ]:
            dg.add_vertex(i)
    return dg

def _dig6_to_digraph( dig6 ):
    """
    Returns the digraph obtained from the dig6 and edge data.

    INPUT:

    - ``dig6`` -- a pair ``(dig6, edges)`` where ``dig6`` is a string encoding a digraph and ``edges`` is a dict or tuple encoding edges

    EXAMPLES::

        sage: from sage.combinat.cluster_algebra_quiver.mutation_class import _digraph_to_dig6
        sage: from sage.combinat.cluster_algebra_quiver.mutation_class import _dig6_to_digraph
        sage: dg = ClusterQuiver(['A',4]).digraph()
        sage: data = _digraph_to_dig6(dg)
        sage: _dig6_to_digraph(data)
        Digraph on 4 vertices
        sage: _dig6_to_digraph(data).edges()
        [(0, 1, (1, -1)), (2, 1, (1, -1)), (2, 3, (1, -1))]
    """
    dig6, edges = dig6
    dg = DiGraph( dig6 )
    if not type(edges) == dict:
        edges = dict( edges )
    for edge in dg._backend.iterator_in_edges(dg,False):
        if edge in edges:
            dg.set_edge_label( edge[0],edge[1],edges[edge] )
        else:
            dg.set_edge_label( edge[0],edge[1], (1,-1) )
    return dg

def _digraph_mutate( dg, k, n, m ):
    """
    Returns a digraph obtained from dg with n+m vertices by mutating at vertex k.

    INPUT:

    - ``dg`` -- a digraph with integral edge labels with ``n+m`` vertices
    - ``k`` -- the vertex at which ``dg`` is mutated

    EXAMPLES::

        sage: from sage.combinat.cluster_algebra_quiver.mutation_class import _digraph_mutate
        sage: dg = ClusterQuiver(['A',4]).digraph()
        sage: dg.edges()
        [(0, 1, (1, -1)), (2, 1, (1, -1)), (2, 3, (1, -1))]
        sage: _digraph_mutate(dg,2,4,0).edges()
        [(0, 1, (1, -1)), (1, 2, (1, -1)), (3, 2, (1, -1))]
    """
    edges = dict( ((v1,v2),label) for v1,v2,label in dg._backend.iterator_in_edges(dg,True) )
    in_edges = [ (v1,v2,edges[(v1,v2)]) for (v1,v2) in edges if v2 == k ]
    out_edges = [ (v1,v2,edges[(v1,v2)]) for (v1,v2) in edges if v1 == k ]
    in_edges_new = [ (v2,v1,(-label[1],-label[0])) for (v1,v2,label) in in_edges ]
    out_edges_new = [ (v2,v1,(-label[1],-label[0])) for (v1,v2,label) in out_edges ]
    diag_edges_new = []
    diag_edges_del = []

    for (v1,v2,label1) in in_edges:
        for (w1,w2,label2) in out_edges:
            l11,l12 = label1
            l21,l22 = label2
            if (v1,w2) in edges:
                diag_edges_del.append( (v1,w2,edges[(v1,w2)]) )
                a,b = edges[(v1,w2)]
                a,b = a+l11*l21, b-l12*l22
                diag_edges_new.append( (v1,w2,(a,b)) )
            elif (w2,v1) in edges:
                diag_edges_del.append( (w2,v1,edges[(w2,v1)]) )
                a,b = edges[(w2,v1)]
                a,b = b+l11*l21, a-l12*l22
                if a<0:
                    diag_edges_new.append( (w2,v1,(b,a)) )
                elif a>0:
                    diag_edges_new.append( (v1,w2,(a,b)) )
            else:
                a,b = l11*l21,-l12*l22
                diag_edges_new.append( (v1,w2,(a,b)) )

    del_edges = in_edges + out_edges + diag_edges_del
    new_edges = in_edges_new + out_edges_new + diag_edges_new
    new_edges += [ (v1,v2,edges[(v1,v2)]) for (v1,v2) in edges if not (v1,v2,edges[(v1,v2)]) in del_edges ]

    dg_new = DiGraph()
    for v1,v2,label in new_edges:
        dg_new._backend.add_edge(v1,v2,label,True)
    if dg_new.order() < n+m:
        dg_new_vertices = [ v for v in dg_new ]
        for i in [ v for v in dg if v not in dg_new_vertices ]:
            dg_new.add_vertex(i)

    return dg_new

    def plot(self, label_elements=True, element_labels=None,
            label_font_size=12,label_font_color='black', layout = "acyclic", **kwds):
        """
        Returns a Graphics object corresponding to the Hasse diagram.
        
        EXAMPLES::
        
            sage: uc = [[2,3], [], [1], [1], [1], [3,4]]
            sage: elm_lbls = Permutations(3).list()
            sage: P = Poset(uc,elm_lbls)
            sage: H = P._hasse_diagram
            sage: levels = H.level_sets()
            sage: heights = dict([[i, levels[i]] for i in range(len(levels))])
            sage: type(H.plot(label_elements=True))
            <class 'sage.plot.graphics.Graphics'>
        
        ::
        
            sage: P = Posets.SymmetricGroupBruhatIntervalPoset([0,1,2,3], [2,3,0,1])
            sage: P._hasse_diagram.plot()
        """
        # Set element_labels to default to the vertex set.
        if element_labels is None:
            element_labels = range(self.num_verts())

        # Create the underlying graph.
        graph = DiGraph(self)
        graph.relabel(element_labels)

        return graph.plot(layout = layout, **kwds)

 def add_edge(self, i, j, label=1):
     """
     EXAMPLES::
     
         sage: from sage.combinat.root_system.dynkin_diagram import DynkinDiagram_class
         sage: d = DynkinDiagram_class(CartanType(['A',3]))
         sage: list(sorted(d.edges()))
         []
         sage: d.add_edge(2, 3)
         sage: list(sorted(d.edges()))
         [(2, 3, 1), (3, 2, 1)]
     """
     DiGraph.add_edge(self, i, j, label)
     if not self.has_edge(j, i):
         self.add_edge(j, i, 1)

 def __getitem__(self, i):
     r"""
     With a tuple (i,j) as argument, returns the scalar product
     `\langle
             \alpha^\vee_i, \alpha_j\rangle`.
     
     Otherwise, behaves as the usual DiGraph.__getitem__
     
     EXAMPLES: We use the `C_4` dynkin diagram as a cartan
     matrix::
     
         sage: g = DynkinDiagram(['C',4])
         sage: matrix([[g[i,j] for j in range(1,5)] for i in range(1,5)])
         [ 2 -1  0  0]
         [-1  2 -1  0]
         [ 0 -1  2 -2]
         [ 0  0 -1  2]
     
     The neighbors of a node can still be obtained in the usual way::
     
         sage: [g[i] for i in range(1,5)]
         [[2], [1, 3], [2, 4], [3]]
     """
     if not isinstance(i, tuple):
         return DiGraph.__getitem__(self, i)
     [i, j] = i
     if i == j:
         return 2
     elif self.has_edge(j, i):
         return -self.edge_label(j, i)
     else:
         return 0

        def digraph(self):
            """
            Returns the DiGraph associated to self.

            EXAMPLES::

                sage: C = Crystals().example(5)
                sage: C.digraph()
                Digraph on 6 vertices

            The edges of the crystal graph are by default colored using blue for edge 1, red for edge 2,
            and green for edge 3::

                sage: C = Crystals().example(3)
                sage: G = C.digraph()
                sage: view(G, pdflatex=True, tightpage=True)  #optional - dot2tex graphviz

            One may also overwrite the colors::

                sage: C = Crystals().example(3)
                sage: G = C.digraph()
                sage: G.set_latex_options(color_by_label = {1:"red", 2:"purple", 3:"blue"})
                sage: view(G, pdflatex=True, tightpage=True)  #optional - dot2tex graphviz

            Or one may add colors to yet unspecified edges::

                sage: C = Crystals().example(4)
                sage: G = C.digraph()
                sage: C.cartan_type()._index_set_coloring[4]="purple"
                sage: view(G, pdflatex=True, tightpage=True)  #optional - dot2tex graphviz

            TODO: add more tests
            """
            from sage.graphs.all import DiGraph
            d = {}
            for x in self:
                d[x] = {}
                for i in self.index_set():
                    child = x.f(i)
                    if child is None:
                        continue
                    d[x][child]=i
            G = DiGraph(d)
            if have_dot2tex():
                G.set_latex_options(format="dot2tex", edge_labels = True, color_by_label = self.cartan_type()._index_set_coloring,
                                    edge_options = lambda (u,v,label): ({"backward":label ==0}))
            return G

    def __init__(self, t=None):
        """
        INPUT:

         - ``t`` - a Cartan type or None

        EXAMPLES::
        
            sage: d = DynkinDiagram(["A", 3])
            sage: d == loads(dumps(d))
            True

        Implementation note: if a Cartan type is given, then the nodes
        are initialized from the index set of this Cartan type.
        """
        DiGraph.__init__(self)
        self._cartan_type = t
        if t is not None:
            self.add_vertices(t.index_set())

    def IntegerPartitions(n):
        """
        Returns the poset of integer partitions on the integer ``n``.

        A partition of a positive integer `n` is a non-increasing list
        of positive integers that sum to `n`. If `p` and `q` are
        integer partitions of `n`, then `p` covers `q` if and only
        if `q` is obtained from `p` by joining two parts of `p`
        (and sorting, if necessary).

        EXAMPLES::
        
            sage: P = Posets.IntegerPartitions(7); P
            Finite poset containing 15 elements
            sage: len(P.cover_relations())
            28
        """
        def lower_covers(partition):
            r"""
            Nested function for computing the lower covers
            of elements in the poset of integer partitions.
            """
            lc = []
            for i in range(0,len(partition)-1):
                for j in range(i+1,len(partition)):
                    new_partition = partition[:]
                    del new_partition[j]
                    del new_partition[i]
                    new_partition.append(partition[i]+partition[j])
                    new_partition.sort(reverse=True)
                    tup = tuple(new_partition)
                    if tup not in lc: 
                        lc.append(tup)
            return lc
        from sage.combinat.partition import partitions_list
        H = DiGraph(dict([[tuple(p),lower_covers(p)] for p in
            partitions_list(n)]))
        return Poset(H.reverse())

    def __init__(self):
        """
        EXAMPLES::

            sage: C = sage.categories.examples.crystals.NaiveCrystal()
            sage: C == Crystals().example(choice='naive')
            True
        """
        Parent.__init__(self, category = ClassicalCrystals())
        self.n = 2
        self._cartan_type = CartanType(['A',2])
        self.G = DiGraph(5)
        self.G.add_edges([ [0,1,1], [1,2,1], [2,3,1], [3,5,1],  [0,4,2], [4,5,2] ])
        self.module_generators = [ self(0) ]

    def _digraph(self):
        r"""
        Constructs the underlying digraph and stores the result as an
        attribute.

        EXAMPLES::
        
            sage: from sage.combinat.yang_baxter_graph import SwapIncreasingOperator
            sage: ops = [SwapIncreasingOperator(i) for i in range(2)]
            sage: Y = YangBaxterGraph(root=(1,2,3), operators=ops)
            sage: Y._digraph
            Digraph on 6 vertices
        """
        digraph = DiGraph()
        digraph.add_vertex(self._root)
        queue = [self._root]
        while queue:
            u = queue.pop()
            for (v, l) in self._succesors(u):
                if v not in digraph:
                    queue.append(v)
                digraph.add_edge(u, v, l)
        return digraph

    def RestrictedIntegerPartitions(n):
        """
        Returns the poset of integer partitions on the integer `n`
        ordered by restricted refinement. That is, if `p` and `q`
        are integer partitions of `n`, then `p` covers `q` if and
        only if `q` is obtained from `p` by joining two distinct
        parts of `p` (and sorting, if necessary).

        EXAMPLES::
        
            sage: P = Posets.RestrictedIntegerPartitions(7); P
            Finite poset containing 15 elements
            sage: len(P.cover_relations())
            17
        """
        def lower_covers(partition):
            r"""
            Nested function for computing the lower covers of elements in the
            restricted poset of integer partitions.
            """
            lc = []
            for i in range(0,len(partition)-1):
                for j in range(i+1,len(partition)):
                    if partition[i] != partition[j]:
                        new_partition = partition[:]
                        del new_partition[j]
                        del new_partition[i]
                        new_partition.append(partition[i]+partition[j])
                        new_partition.sort(reverse=True)
                        tup = tuple(new_partition)
                        if tup not in lc: 
                            lc.append(tup)
            return lc
        from sage.combinat.partition import Partitions
        H = DiGraph(dict([[tuple(p),lower_covers(p)] for p in
            Partitions(n)]))
        return Poset(H.reverse())

    def to_dag(self):
        """
        Returns a directed acyclic graph corresponding to the skew
        partition.
        
        EXAMPLES::
        
            sage: dag = SkewPartition([[3, 2, 1], [1, 1]]).to_dag()
            sage: dag.edges()
            [('0,1', '0,2', None), ('0,1', '1,1', None)]
            sage: dag.vertices()
            ['0,1', '0,2', '1,1', '2,0']
        """
        i = 0

        #Make the skew tableau from the shape
        skew = [[1]*row_length for row_length in self.outer()]
        inner = self.inner()
        for i in range(len(inner)):
            for j in range(inner[i]):
                skew[i][j] = None

        G = DiGraph()
        for row in range(len(skew)):
            for column in range(len(skew[row])):
                if skew[row][column] is not None:
                    string = "%d,%d" % (row, column)
                    G.add_vertex(string)
                    #Check to see if there is a node to the right
                    if column != len(skew[row]) - 1:
                        newstring = "%d,%d" % (row, column+1)
                        G.add_edge(string, newstring)

                    #Check to see if there is anything below
                    if row != len(skew) - 1:
                        if len(skew[row+1]) > column:
                            if skew[row+1][column] is not None:
                                newstring = "%d,%d" % (row+1, column)
                                G.add_edge(string, newstring)
        return G

def _is_valid_digraph_edge_set( edges, frozen=0 ):
    """
    Returns True if the input data is the edge set of a digraph for a quiver (no loops, no 2-cycles, edge-labels of the specified format), and returns False otherwise.

    INPUT:

    - ``frozen`` -- (integer; default:0) The number of frozen vertices.

    EXAMPLES::

        sage: from sage.combinat.cluster_algebra_quiver.mutation_class import _is_valid_digraph_edge_set
        sage: _is_valid_digraph_edge_set( [[0,1,'a'],[2,3,(1,-1)]] )
        The given digraph has edge labels which are not integral or integral 2-tuples.
        False
        sage: _is_valid_digraph_edge_set( [[0,1],[2,3,(1,-1)]] )
        True
        sage: _is_valid_digraph_edge_set( [[0,1,'a'],[2,3,(1,-1)],[3,2,(1,-1)]] )
        The given digraph or edge list contains oriented 2-cycles.
        False
    """
    try:
        dg = DiGraph()
        dg.allow_multiple_edges(True)
        dg.add_edges( edges )

        # checks if the digraph contains loops
        if dg.has_loops():
            print "The given digraph or edge list contains loops."
            return False

        # checks if the digraph contains oriented 2-cycles
        if _has_two_cycles( dg ):
            print "The given digraph or edge list contains oriented 2-cycles."
            return False

        # checks if all edge labels are 'None', positive integers or tuples of positive integers
        if not all( i == None or ( i in ZZ and i > 0 ) or ( type(i) == tuple and len(i) == 2 and i[0] in ZZ and i[1] in ZZ ) for i in dg.edge_labels() ):
            print "The given digraph has edge labels which are not integral or integral 2-tuples."
            return False

        # checks if all edge labels for multiple edges are 'None' or positive integers
        if dg.has_multiple_edges():
            for e in set( dg.multiple_edges(labels=False) ):
                if not all( i == None or ( i in ZZ and i > 0 ) for i in dg.edge_label( e[0], e[1] ) ):
                    print "The given digraph or edge list contains multiple edges with non-integral labels."
                    return False

        n = dg.order() - frozen
        if n < 0:
            print "The number of frozen variables is larger than the number of vertices."
            return False

        if [ e for e in dg.edges(labels=False) if e[0] >= n] <> []:
            print "The given digraph or edge list contains edges within the frozen vertices."
            return False

        return True
    except StandardError:
        print "Could not even build a digraph from the input data."
        return False

    def RandomPoset(n,p):
        r"""
        Generate a random poset on ``n`` vertices according to a
        probability ``p``.

        INPUT:

        - ``n`` - number of vertices, a non-negative integer

        - ``p`` - a probability, a real number between 0 and 1 (inclusive)

        OUTPUT:

        A poset on ``n`` vertices.  The construction decides to make an
        ordered pair of vertices comparable in the poset with probability
        ``p``, however a pair is not made comparable if it would violate
        the defining properties of a poset, such as transitivity.

        So in practice, once the probability exceeds a small number the
        generated posets may be very similar to a chain.  So to create
        interesting examples, keep the probability small, perhaps on the
        order of `1/n`.

        EXAMPLES::

            sage: Posets.RandomPoset(17,.15)
            Finite poset containing 17 elements

        TESTS::

            sage: Posets.RandomPoset('junk', 0.5)
            Traceback (most recent call last):
            ...
            TypeError: number of elements must be an integer, not junk

            sage: Posets.RandomPoset(-6, 0.5)
            Traceback (most recent call last):
            ...
            ValueError: number of elements must be non-negative, not -6

            sage: Posets.RandomPoset(6, 'garbage')
            Traceback (most recent call last):
            ...
            TypeError: probability must be a real number, not garbage

            sage: Posets.RandomPoset(6, -0.5)
            Traceback (most recent call last):
            ...
            ValueError: probability must be between 0 and 1, not -0.5
        """
        try:
            n = Integer(n)
        except:
            raise TypeError("number of elements must be an integer, not {0}".format(n))
        if n < 0:
            raise ValueError("number of elements must be non-negative, not {0}".format(n))
        try:
            p = float(p)
        except:
            raise TypeError("probability must be a real number, not {0}".format(p))
        if p < 0 or p> 1:
            raise ValueError("probability must be between 0 and 1, not {0}".format(p))
        
        D = DiGraph(loops=False,multiedges=False)
        D.add_vertices(range(n))
        for i in range(n):
            for j in range(n):
                if random.random() < p:
                    D.add_edge(i,j)
                    if not D.is_directed_acyclic():
                        D.delete_edge(i,j)
        return Poset(D,cover_relations=False)

#.........这里部分代码省略.........

            INPUT:

            - ``X`` -- (optional) the vertex set `X` (default:
              the whole set of vertices of ``self`` of weight `0`)
            - ``index_set`` -- (optional) the index set `I`
              (default: the whole index set of ``self``); this has
              to be a subset of the index set of ``self`` (as a list
              or tuple)
            - ``directed`` -- (default: ``True``) whether to have the
              dual equivalence graph be directed, where the head of
              an edge `b - b'` is `b` and the tail is
              `b' = f_{i-1} f_i e_{i-1} e_i b`)

            .. SEEALSO::

                :meth:`sage.combinat.partition.Partition.dual_equivalence_graph`

            REFERENCES:

            .. [Assaf08] Sami Assaf. *A combinatorial realization of Schur-Weyl
               duality via crystal graphs and dual equivalence graphs*.
               FPSAC 2008, 141-152, Discrete Math. Theor. Comput. Sci. Proc.,
               AJ, Assoc. Discrete Math. Theor. Comput. Sci., (2008).
               :arxiv:`0804.1587v1`

            EXAMPLES::

                sage: T = crystals.Tableaux(['A',3], shape=[2,2])
                sage: G = T.dual_equivalence_graph()
                sage: sorted(G.edges())
                [([[1, 3], [2, 4]], [[1, 2], [3, 4]], 2),
                 ([[1, 2], [3, 4]], [[1, 3], [2, 4]], 3)]
                sage: T = crystals.Tableaux(['A',4], shape=[3,2])
                sage: G = T.dual_equivalence_graph()
                sage: sorted(G.edges())
                [([[1, 3, 5], [2, 4]], [[1, 3, 4], [2, 5]], 4),
                 ([[1, 3, 5], [2, 4]], [[1, 2, 5], [3, 4]], 2),
                 ([[1, 3, 4], [2, 5]], [[1, 2, 4], [3, 5]], 2),
                 ([[1, 2, 5], [3, 4]], [[1, 3, 5], [2, 4]], 3),
                 ([[1, 2, 4], [3, 5]], [[1, 2, 3], [4, 5]], 3),
                 ([[1, 2, 3], [4, 5]], [[1, 2, 4], [3, 5]], 4)]

                sage: T = crystals.Tableaux(['A',4], shape=[3,1])
                sage: G = T.dual_equivalence_graph(index_set=[1,2,3])
                sage: G.vertices()
                [[[1, 3, 4], [2]], [[1, 2, 4], [3]], [[1, 2, 3], [4]]]
                sage: G.edges()
                [([[1, 3, 4], [2]], [[1, 2, 4], [3]], 2),
                 ([[1, 2, 4], [3]], [[1, 2, 3], [4]], 3)]

            TESTS::

                sage: T = crystals.Tableaux(['A',4], shape=[3,1])
                sage: G = T.dual_equivalence_graph(index_set=[2,3])
                sage: sorted(G.edges())
                [([[1, 2, 4], [3]], [[1, 2, 3], [4]], 3),
                 ([[2, 4, 5], [3]], [[2, 3, 5], [4]], 3)]
                sage: sorted(G.vertices())
                [[[1, 3, 4], [2]],
                 [[1, 2, 4], [3]],
                 [[2, 4, 5], [3]],
                 [[1, 2, 3], [4]],
                 [[2, 3, 5], [4]],
                 [[1, 1, 1], [5]],
                 [[1, 1, 5], [5]],
                 [[1, 5, 5], [5]],
                 [[2, 3, 4], [5]]]
            """
            if index_set is None:
                index_set = self.index_set()

            def wt_zero(x):
                for i in index_set:
                    if x.epsilon(i) != x.phi(i):
                        return False
                return True

            if X is None:
                X = [x for x in self if wt_zero(x)]
                checker = lambda x: True
            elif any(not wt_zero(x) for x in X):
                raise ValueError("the elements are not all weight 0")
            else:
                checker = lambda x: x in X

            edges = []
            for x in X:
                for k, i in enumerate(index_set[1:]):
                    im = index_set[k]
                    if x.epsilon(i) == 1 and x.epsilon(im) == 0:
                        y = x.e(i).e(im).f(i).f(im)
                        if checker(y):
                            edges.append([x, y, i])
            from sage.graphs.all import DiGraph
            G = DiGraph([X, edges], format="vertices_and_edges", immutable=True)
            if have_dot2tex():
                G.set_latex_options(format="dot2tex", edge_labels=True,
                                    color_by_label=self.cartan_type()._index_set_coloring)
            return G

    def uncompactify(self):
        r"""
        Returns the tree obtained from self by splitting edges so that they
        are labelled by exactly one letter. The resulting tree is
        isomorphic to the suffix trie.

        EXAMPLES::

            sage: from sage.combinat.words.suffix_trees import ImplicitSuffixTree, SuffixTrie
            sage: abbab = Words("ab")("abbab")
            sage: s = SuffixTrie(abbab)
            sage: t = ImplicitSuffixTree(abbab)
            sage: t.uncompactify().is_isomorphic(s.to_digraph())
            True
        """
        tree = self.to_digraph(word_labels=True)
        newtree = DiGraph()
        newtree.add_vertices(range(tree.order()))
        new_node = tree.order() + 1
        for (u,v,label) in tree.edge_iterator():
            if len(label) == 1:
                newtree.add_edge(u,v)
            else:
                newtree.add_edge(u,new_node,label[0]);
                for w in label[1:-1]:
                    newtree.add_edge(new_node,new_node+1,w)
                    new_node += 1
                newtree.add_edge(new_node,v,label[-1])
                new_node += 1
        return newtree

    def markov_chain_digraph(self, action = 'promotion', labeling = 'identity'):
        r"""
        Returns the digraph of the action of generalized promotion or tau on ``self``

        INPUT:

        - ``action`` -- 'promotion' or 'tau' (default: 'promotion')
        - ``labeling`` -- 'identity' or 'source' (default: 'identity')

        .. todo::

            - generalize this feature by accepting a family of operators as input
            - move up in some appropriate category

        This method creates a graph with vertices being the linear extensions of a given finite
        poset and an edge from `\pi` to `\pi'` if `\pi' = \pi \partial_i` where `\partial_i` is
        the promotion operator (see :meth:`promotion`) if ``action`` is set to ``promotion``
        and `\tau_i` (see :meth:`tau`) if ``action`` is set to ``tau``. The label of the edge
        is `i` (resp. `\pi_i`) if ``labeling`` is set to ``identity`` (resp. ``source``).

        EXAMPLES::

            sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]), linear_extension = True)
            sage: L = P.linear_extensions()
            sage: G = L.markov_chain_digraph(); G
            Looped multi-digraph on 5 vertices
            sage: sorted(G.vertices(), key = repr)
            [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3]]
            sage: sorted(G.edges(), key = repr)
            [([1, 2, 3, 4], [1, 2, 3, 4], 4), ([1, 2, 3, 4], [1, 2, 4, 3], 2), ([1, 2, 3, 4], [1, 2, 4, 3], 3),
            ([1, 2, 3, 4], [2, 1, 4, 3], 1), ([1, 2, 4, 3], [1, 2, 3, 4], 3), ([1, 2, 4, 3], [1, 2, 4, 3], 4),
            ([1, 2, 4, 3], [1, 4, 2, 3], 2), ([1, 2, 4, 3], [2, 1, 3, 4], 1), ([1, 4, 2, 3], [1, 2, 3, 4], 1),
            ([1, 4, 2, 3], [1, 2, 3, 4], 2), ([1, 4, 2, 3], [1, 4, 2, 3], 3), ([1, 4, 2, 3], [1, 4, 2, 3], 4),
            ([2, 1, 3, 4], [1, 2, 4, 3], 1), ([2, 1, 3, 4], [2, 1, 3, 4], 4), ([2, 1, 3, 4], [2, 1, 4, 3], 2),
            ([2, 1, 3, 4], [2, 1, 4, 3], 3), ([2, 1, 4, 3], [1, 4, 2, 3], 1), ([2, 1, 4, 3], [2, 1, 3, 4], 2),
            ([2, 1, 4, 3], [2, 1, 3, 4], 3), ([2, 1, 4, 3], [2, 1, 4, 3], 4)]

            sage: G = L.markov_chain_digraph(labeling = 'source')
            sage: sorted(G.vertices(), key = repr)
            [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3]]
            sage: sorted(G.edges(), key = repr)
            [([1, 2, 3, 4], [1, 2, 3, 4], 4), ([1, 2, 3, 4], [1, 2, 4, 3], 2), ([1, 2, 3, 4], [1, 2, 4, 3], 3),
            ([1, 2, 3, 4], [2, 1, 4, 3], 1), ([1, 2, 4, 3], [1, 2, 3, 4], 4), ([1, 2, 4, 3], [1, 2, 4, 3], 3),
            ([1, 2, 4, 3], [1, 4, 2, 3], 2), ([1, 2, 4, 3], [2, 1, 3, 4], 1), ([1, 4, 2, 3], [1, 2, 3, 4], 1),
            ([1, 4, 2, 3], [1, 2, 3, 4], 4), ([1, 4, 2, 3], [1, 4, 2, 3], 2), ([1, 4, 2, 3], [1, 4, 2, 3], 3),
            ([2, 1, 3, 4], [1, 2, 4, 3], 2), ([2, 1, 3, 4], [2, 1, 3, 4], 4), ([2, 1, 3, 4], [2, 1, 4, 3], 1),
            ([2, 1, 3, 4], [2, 1, 4, 3], 3), ([2, 1, 4, 3], [1, 4, 2, 3], 2), ([2, 1, 4, 3], [2, 1, 3, 4], 1),
            ([2, 1, 4, 3], [2, 1, 3, 4], 4), ([2, 1, 4, 3], [2, 1, 4, 3], 3)]

        The edges of the graph are by default colored using blue for
        edge 1, red for edge 2, green for edge 3, and yellow for edge 4::

            sage: view(G) #optional - dot2tex graphviz

        Alternatively, one may get the graph of the action of the ``tau`` operator::

            sage: G = L.markov_chain_digraph(action='tau'); G
            Looped multi-digraph on 5 vertices
            sage: sorted(G.vertices(), key = repr)
            [[1, 2, 3, 4], [1, 2, 4, 3], [1, 4, 2, 3], [2, 1, 3, 4], [2, 1, 4, 3]]
            sage: sorted(G.edges(), key = repr)
            [([1, 2, 3, 4], [1, 2, 3, 4], 2), ([1, 2, 3, 4], [1, 2, 4, 3], 3), ([1, 2, 3, 4], [2, 1, 3, 4], 1),
            ([1, 2, 4, 3], [1, 2, 3, 4], 3), ([1, 2, 4, 3], [1, 4, 2, 3], 2), ([1, 2, 4, 3], [2, 1, 4, 3], 1),
            ([1, 4, 2, 3], [1, 2, 4, 3], 2), ([1, 4, 2, 3], [1, 4, 2, 3], 1), ([1, 4, 2, 3], [1, 4, 2, 3], 3),
            ([2, 1, 3, 4], [1, 2, 3, 4], 1), ([2, 1, 3, 4], [2, 1, 3, 4], 2), ([2, 1, 3, 4], [2, 1, 4, 3], 3),
            ([2, 1, 4, 3], [1, 2, 4, 3], 1), ([2, 1, 4, 3], [2, 1, 3, 4], 3), ([2, 1, 4, 3], [2, 1, 4, 3], 2)]
            sage: view(G) #optional - dot2tex graphviz

        .. seealso:: :meth:`markov_chain_transition_matrix`, :meth:`promotion`, :meth:`tau`

        TESTS::

            sage: P = Poset(([1,2,3,4], [[1,3],[1,4],[2,3]]), linear_extension = True, facade = True)
            sage: L = P.linear_extensions()
            sage: G = L.markov_chain_digraph(labeling = 'source'); G
            Looped multi-digraph on 5 vertices
        """
        d = dict([x,dict([y,[]] for y in self)] for x in self)
        if action == 'promotion':
            R = range(self.poset().cardinality())
        else:
            R = range(self.poset().cardinality()-1)
        if labeling == 'source':
            for x in self:
                for i in R:
                    child = getattr(x, action)(i+1)
                    d[x][child]+=[self.poset().unwrap(x[i])]
        else:
            for x in self:
                for i in R:
                    child = getattr(x, action)(i+1)
                    d[x][child]+=[i+1]
        G = DiGraph(d)
        if have_dot2tex():
            G.set_latex_options(format="dot2tex", edge_labels = True, color_by_label = {1:"blue", 2:"red", 3:"green", 4:"yellow"})
            #G.set_latex_options(format="dot2tex", edge_labels = True, color_by_label = {1:"green", 2:"blue", 3:"brown", 4:"red"})
        return G

def _digraph_mutate(dg, k, frozen=None):
    """
    Return a digraph obtained from ``dg`` by mutating at vertex ``k``.

    Vertices can be labelled by anything, and frozen vertices must
    be explicitly given.

    INPUT:

    - ``dg`` -- a digraph with integral edge labels with ``n+m`` vertices
    - ``k`` -- the vertex at which ``dg`` is mutated
    - ``frozen`` -- the list of frozen vertices (default is the empty list)

    EXAMPLES::

        sage: from sage.combinat.cluster_algebra_quiver.mutation_class import _digraph_mutate
        sage: from sage.combinat.cluster_algebra_quiver.quiver import ClusterQuiver
        sage: dg = ClusterQuiver(['A',4]).digraph()
        sage: dg.edges()
        [(0, 1, (1, -1)), (2, 1, (1, -1)), (2, 3, (1, -1))]
        sage: _digraph_mutate(dg,2).edges()
        [(0, 1, (1, -1)), (1, 2, (1, -1)), (3, 2, (1, -1))]

    TESTS::

       sage: dg = DiGraph([('a','b',(1,-1)),('c','a',(1,-1))])
       sage: _digraph_mutate(dg,'a').edges()
       [('a', 'c', (1, -1)), ('b', 'a', (1, -1)), ('c', 'b', (1, -1))]
       sage: _digraph_mutate(dg,'a',frozen=['b','c']).edges()
       [('a', 'c', (1, -1)), ('b', 'a', (1, -1))]

       sage: dg = DiGraph([('a','b',(2,-2)),('c','a',(2,-2)),('b','c',(2,-2))])
       sage: _digraph_mutate(dg,'a').edges()
       [('a', 'c', (2, -2)), ('b', 'a', (2, -2)), ('c', 'b', (2, -2))]
    """
    # assert sorted(list(dg)) == list(range(n + m))
    # this is not assumed anymore
    if frozen is None:
        frozen = []

    edge_it = dg.incoming_edge_iterator(dg, True)
    edges = {(v1, v2): label for v1, v2, label in edge_it}
    edge_it = dg.incoming_edge_iterator([k], True)
    in_edges = [(v1, v2, label) for v1, v2, label in edge_it]
    edge_it = dg.outgoing_edge_iterator([k], True)
    out_edges = [(v1, v2, label) for v1, v2, label in edge_it]

    in_edges_new = [(v2, v1, (-label[1], -label[0]))
                    for (v1, v2, label) in in_edges]
    out_edges_new = [(v2, v1, (-label[1], -label[0]))
                     for (v1, v2, label) in out_edges]
    diag_edges_new = []
    diag_edges_del = []

    for (v1, v2, label1) in in_edges:
        l11, l12 = label1
        for (w1, w2, label2) in out_edges:
            if v1 in frozen and w2 in frozen:
                continue
            l21, l22 = label2
            if (v1, w2) in edges:
                diag_edges_del.append((v1, w2))
                a, b = edges[(v1, w2)]
                a, b = a + l11 * l21, b - l12 * l22
                diag_edges_new.append((v1, w2, (a, b)))
            elif (w2, v1) in edges:
                diag_edges_del.append((w2, v1))
                a, b = edges[(w2, v1)]
                a, b = b + l11 * l21, a - l12 * l22
                if a < 0:
                    diag_edges_new.append((w2, v1, (b, a)))
                elif a > 0:
                    diag_edges_new.append((v1, w2, (a, b)))
            else:
                a, b = l11 * l21, -l12 * l22
                diag_edges_new.append((v1, w2, (a, b)))

    del_edges = [tuple(ed[:2]) for ed in in_edges + out_edges]
    del_edges += diag_edges_del
    new_edges = in_edges_new + out_edges_new
    new_edges += diag_edges_new
    new_edges += [(v1, v2, edges[(v1, v2)]) for (v1, v2) in edges
                  if (v1, v2) not in del_edges]

    dg_new = DiGraph()
    dg_new.add_vertices(list(dg))
    for v1, v2, label in new_edges:
        dg_new.add_edge(v1, v2, label)

    return dg_new

class NaiveCrystal(UniqueRepresentation, Parent):
    r"""
    This is an example of a "crystal" which does not come from any kind of
    representation, designed primarily to test the Stembridge local rules with.
    The crystal has vertices labeled 0 through 5, with 0 the highest weight.

    The code here could also possibly be generalized to create a class that
    automatically builds a crystal from an edge-colored digraph, if someone
    feels adventurous.

    Currently, only the methods :meth:`highest_weight_vector`, :meth:`e`, and :meth:`f` are
    guaranteed to work.

    EXAMPLES::

        sage: C = Crystals().example(choice='naive')
        sage: C.highest_weight_vector()
        0
    """
    def __init__(self):
        """
        EXAMPLES::

            sage: C = sage.categories.examples.crystals.NaiveCrystal()
            sage: C == Crystals().example