def __init__(self, t=None, index_set=None, odd_isotropic_roots=[],
                 **options):
        """
        Initialize ``self``.

        EXAMPLES::

            sage: d = DynkinDiagram(["A", 3])
            sage: TestSuite(d).run()
        """
        if isinstance(t, DiGraph):
            if isinstance(t, DynkinDiagram_class):
                self._cartan_type = t._cartan_type
                self._odd_isotropic_roots = tuple(odd_isotropic_roots)
            else:
                self._cartan_type = None
                self._odd_isotropic_roots = ()
            DiGraph.__init__(self, data=t, **options)
            return

        DiGraph.__init__(self, **options)
        self._cartan_type = t
        self._odd_isotropic_roots = tuple(odd_isotropic_roots)
        if index_set is not None:
            self.add_vertices(index_set)
        elif t is not None:
            self.add_vertices(t.index_set())

    def inclusion_digraph(self):
        r"""
        Returns the class inclusion digraph

        Upon the first call, this loads the database from the local
        XML file. Subsequent calls are cached.

        EXAMPLES::

            sage: g = graph_classes.inclusion_digraph(); g
            Digraph on ... vertices
        """
        classes    = self.classes()
        inclusions = self.inclusions()

        from sage.graphs.digraph import DiGraph
        inclusion_digraph = DiGraph()
        inclusion_digraph.add_vertices(classes.keys())

        for edge in inclusions:
            if edge.get("confidence","") == "unpublished":
                continue
            inclusion_digraph.add_edge(edge['super'], edge['sub'])

        return inclusion_digraph

    def RandomDirectedGNP(self, n, p):
        r"""
        Returns a random digraph on `n` nodes. Each edge is
        inserted independently with probability `p`.
        
        REFERENCES:

        - [1] P. Erdos and A. Renyi, On Random Graphs, Publ.  Math. 6,
          290 (1959).

        - [2] E. N. Gilbert, Random Graphs, Ann. Math.  Stat., 30,
          1141 (1959).
        
        PLOTTING: When plotting, this graph will use the default
        spring-layout algorithm, unless a position dictionary is
        specified.
        
        EXAMPLE::
        
            sage: D = digraphs.RandomDirectedGNP(10, .2)
            sage: D.num_verts()
            10
            sage: D.edges(labels=False)
            [(0, 1), (0, 3), (0, 6), (0, 8), (1, 4), (3, 7), (4, 1), (4, 8), (5, 2), (5, 6), (5, 8), (6, 4), (7, 6), (8, 4), (8, 5), (8, 7), (8, 9), (9, 3), (9, 4), (9, 6)]
        """
        from sage.misc.prandom import random
        D = DiGraph(n)
        for i in xrange(n):
            for j in xrange(i):
                if random() < p:
                    D.add_edge(i,j)
            for j in xrange(i+1,n):
                if random() < p:
                    D.add_edge(i,j)
        return D

    def basis_of_simple_closed_curves(self):
        from sage.graphs.digraph import DiGraph
        from sage.all import randint

        n = self._origami.nb_squares()
        C = self.chain_space()
        G = DiGraph(multiedges=True,loops=True,implementation='c_graph')

        for i in xrange(2*n):
            G.add_edge(self._starts[i], self._ends[i], i)

        waiting = [0]
        gens = []
        reps = [None] * G.num_verts()
        reps[0] = C.zero()

        while waiting:
            x = waiting.pop(randint(0,len(waiting)-1))
            for v0,v1,e in G.outgoing_edges(x):
                if reps[v1] is not None:
                    gens.append(reps[v0] + C.gen(e) - reps[v1])
                else:
                    reps[v1] = reps[v0] + C.gen(e)
                    waiting.append(v1)

        return gens

    def Tournament(self,n):
        r"""
        Returns a tournament on `n` vertices.

        In this tournament there is an edge from `i` to `j` if `i<j`.

        INPUT:

        - ``n`` (integer) -- number of vertices in the tournament.

        EXAMPLES::

            sage: g = digraphs.Tournament(5)
            sage: g.vertices()
            [0, 1, 2, 3, 4]
            sage: g.size()
            10
            sage: g.automorphism_group().cardinality()
            1
        """
        if n<0:
            raise ValueError("The number of vertices must be a positive integer.")

        g = DiGraph()
        g.name("Tournament on "+str(n)+" vertices")

        for i in range(n-1):
            for j in range(i+1, n):
                g.add_edge(i,j)

        if n:
            from sage.graphs.graph_plot import _circle_embedding
            _circle_embedding(g, range(n))

        return g

    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([1,2,3,4], [3,4,1,2])
            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 tree(self):
        r"""
        Returns the Huffman tree corresponding to the current encoding.

        INPUT:

        - None.

        OUTPUT:

        - The binary tree representing a Huffman code.

        EXAMPLES::

            sage: from sage.coding.source_coding.huffman import Huffman
            sage: str = "Sage is my most favorite general purpose computer algebra system"
            sage: h = Huffman(str)
            sage: T = h.tree(); T
            Digraph on 39 vertices
            sage: T.show(figsize=[20,20])
            <BLANKLINE>
        """
        from sage.graphs.digraph import DiGraph
        g = DiGraph()
        g.add_edges(self._generate_edges(self._tree))
        return g

    def as_digraph(self):
        """
        Returns a directed graph version of ``self``.

        .. WARNING::

            At this time, the output makes sense only if ``self`` is a
            labelled binary tree with no repeated labels and no ``None``
            labels.

        EXAMPLES::

           sage: LT = LabelledOrderedTrees()
           sage: t1 = LT([LT([],label=6),LT([],label=1)],label=9)
           sage: t1.as_digraph()
           Digraph on 3 vertices

           sage: t = BinaryTree([[None, None],[[],None]]);
           sage: lt = t.canonical_labelling()
           sage: lt.as_digraph()
           Digraph on 4 vertices
        """
        from sage.graphs.digraph import DiGraph
        resu = dict([[self.label(),
                    [t.label() for t in self if not t.is_empty()]]])
        resu = DiGraph(resu)
        for t in self:
            if not t.is_empty():
                resu = resu.union(t.as_digraph())
        return resu

    def relabel(self, relabelling, inplace=False, **kwds):
        """
        Return the relabelling Dynkin diagram of ``self``.

        EXAMPLES::

            sage: D = DynkinDiagram(['C',3])
            sage: D.relabel({1:0, 2:4, 3:1})
            O---O=<=O
            0   4   1
            C3 relabelled by {1: 0, 2: 4, 3: 1}
            sage: D
            O---O=<=O
            1   2   3
            C3
        """
        if inplace:
            DiGraph.relabel(self, relabelling, inplace, **kwds)
            G = self
        else:
            # We must make a copy of ourselves first because of DiGraph's
            #   relabel default behavior is to do so in place, and if not
            #   then it recurses on itself with no argument for inplace
            G = self.copy().relabel(relabelling, inplace=True, **kwds)
        if self._cartan_type is not None:
            G._cartan_type = self._cartan_type.relabel(relabelling)
        return G

        def bhz_poset(self):
            r"""
            Return the Bergeron-Hohlweg-Zabrocki partial order on the Coxeter
            group.

            This is a partial order on the elements of a finite
            Coxeter group `W`, which is distinct from the Bruhat
            order, the weak order and the shard intersection order. It
            was defined in [BHZ05]_.

            This partial order is not a lattice, as there is no unique
            maximal element. It can be succintly defined as follows.

            Let `u` and `v` be two elements of the Coxeter group `W`. Let
            `S(u)` be the support of `u`. Then `u \leq v` if and only
            if `v_{S(u)} = u` (here `v = v^I v_I` denotes the usual
            parabolic decomposition with respect to the standard parabolic
            subgroup `W_I`).

            .. SEEALSO::

                :meth:`bruhat_poset`, :meth:`shard_poset`, :meth:`weak_poset`

            EXAMPLES::

                sage: W = CoxeterGroup(['A',3], base_ring=ZZ)
                sage: P = W.bhz_poset(); P
                Finite poset containing 24 elements
                sage: P.relations_number()
                103
                sage: P.chain_polynomial()
                34*q^4 + 90*q^3 + 79*q^2 + 24*q + 1
                sage: len(P.maximal_elements())
                13

            REFERENCE:

            .. [BHZ05] \N. Bergeron, C. Hohlweg, and M. Zabrocki, *Posets
               related to the Connectivity Set of Coxeter Groups*.
               :arxiv:`math/0509271v3`
            """
            from sage.graphs.digraph import DiGraph
            from sage.combinat.posets.posets import Poset

            def covered_by(ux, vy):
                u, iu, Su = ux
                v, iv, Sv = vy
                if len(Sv) != len(Su) + 1:
                    return False
                if not all(u in Sv for u in Su):
                    return False
                return all((v * iu).has_descent(x, positive=True) for x in Su)

            vertices = [(u, u.inverse(),
                         tuple(set(u.reduced_word_reverse_iterator())))
                        for u in self]
            dg = DiGraph([vertices, covered_by])
            dg.relabel(lambda x: x[0])
            return Poset(dg, cover_relations=True)

    def Circulant(self,n,integers):
        r"""
        Returns a circulant digraph on `n` vertices from a set of integers.

        INPUT:

        - ``n`` (integer) -- number of vertices.

        - ``integers`` -- the list of integers such that there is an edge from
          `i` to `j` if and only if ``(j-i)%n in integers``.

        EXAMPLE::

            sage: digraphs.Circulant(13,[3,5,7])
            Circulant graph ([3, 5, 7]): Digraph on 13 vertices

        TESTS::

            sage: digraphs.Circulant(13,[3,5,7,"hey"])
            Traceback (most recent call last):
            ...
            ValueError: The list must contain only relative integers.
            sage: digraphs.Circulant(-2,[3,5,7,3])
            Traceback (most recent call last):
            ...
            ValueError: n must be a positive integer
            sage: digraphs.Circulant(3,[3,5,7,3.4])
            Traceback (most recent call last):
            ...
            ValueError: The list must contain only relative integers.
        """
        from sage.graphs.graph_plot import _circle_embedding
        from sage.rings.integer_ring import ZZ

        # Bad input and loops
        loops = False
        if not n in ZZ or n <= 0:
            raise ValueError("n must be a positive integer")

        for i in integers:
            if not i in ZZ:
                raise ValueError("The list must contain only relative integers.")
            if (i%n) == 0:
                loops = True

        G=DiGraph(n, name="Circulant graph ("+str(integers)+")", loops=loops)

        _circle_embedding(G, range(n))
        for v in range(n):
            G.add_edges([(v,(v+j)%n) for j in integers])

        return G

    def as_graph(self):
        r"""
        Return the graph associated to self
        """
        from sage.graphs.digraph import DiGraph

        G = DiGraph(multiedges=True,loops=True)
        d = self.degree()
        g = [self.g_tuple(i) for i in xrange(4)]
        for i in xrange(d):
            for j in xrange(4):
                G.add_edge(i,g[j][i],j)
        return G

 def __init__(self, data = None, arcs = None, edges = None,
              multiedges = True, loops = True, **kargs):
     init = True
     if data is None:
         if edges is None:
             edges = []
         if arcs is None:
             arcs = []
     else:
         if isinstance(data, MixedGraph):
             if edges is not None or arcs is not None:
                 raise ValueError("Edges or arcs should not be specified with a MixedGraph")
             self._edges = data._edges
             self._arcs = data._arcs
             init = False
         elif isinstance(data, Graph):
             if edges is not None:
                 raise ValueError("Edges should not be specified with a Graph")
             edges = data.edges(labels=False)
             if arcs is None:
                 arcs = []
         elif isinstance(data, DiGraph):
             if arcs is not None:
                 raise ValueError("Arcs should not be specified with a DiGraph")
             arcs = data.edges(labels=False)
             if edges is None:
                 edges = []
         elif arcs is not None and edges is None:
             edges = data
             data = None
         else:
             if edges is not None or arcs is not None:
                 raise ValueError("Edges or arcs should not be specified with other data")
             self._edges = []
             self._arcs = []
             for i, e in enumerate(data):
                 u, v = e
                 if isinstance(e, (set, frozenset, Set_generic)):
                     self._edges.append((u, v, i))
                 else:
                     self._arcs.append((u, v, i))
             init = False
     if init:
         n = len(edges)
         self._edges = [(u, v, i) for i, (u, v) in enumerate(edges)]
         self._arcs = [(u, v, i+n) for i, (u, v) in enumerate(arcs)]
     DiGraph.__init__(self, self._edges + self._arcs,
                      multiedges = multiedges, loops = loops, **kargs)
     if isinstance(data, GenericGraph) and data._pos is not None and \
         kargs.setdefault('pos', None) is None and len(data) == len(self):
             self._pos = data._pos

    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 YoungsLatticePrincipalOrderIdeal(lam):
        """
        Return the principal order ideal of the
        partition `lam` in Young's Lattice.

        INPUT:

        - ``lam`` -- a partition

        EXAMPLES::

            sage: P = Posets.YoungsLatticePrincipalOrderIdeal(Partition([2,2]))
            sage: P
            Finite lattice containing 6 elements
            sage: P.cover_relations()
            [[[], [1]],
             [[1], [1, 1]],
             [[1], [2]],
             [[1, 1], [2, 1]],
             [[2], [2, 1]],
             [[2, 1], [2, 2]]]
        """
        from sage.misc.flatten import flatten
        from sage.combinat.partition import Partition

        def lower_covers(l):
            """
            Nested function returning those partitions obtained
            from the partition `l` by removing
            a single cell.
            """
            return [l.remove_cell(c[0], c[1]) for c in l.removable_cells()]

        def contained_partitions(l):
            """
            Nested function returning those partitions contained in
            the partition `l`
            """
            if l == Partition([]):
                return l
            return flatten([l, [contained_partitions(m)
                                for m in lower_covers(l)]])

        ideal = list(set(contained_partitions(lam)))
        H = DiGraph(dict([[p, lower_covers(p)] for p in ideal]))
        return LatticePoset(H.reverse())

    def Path(self,n):
        r"""
        Returns a directed path on `n` vertices.

        INPUT:

        - ``n`` (integer) -- number of vertices in the path.

        EXAMPLES::

            sage: g = digraphs.Path(5)
            sage: g.vertices()
            [0, 1, 2, 3, 4]
            sage: g.size()
            4
            sage: g.automorphism_group().cardinality()
            1
        """
        if n<0:
            raise ValueError("The number of vertices must be a positive integer.")

        g = DiGraph()
        g.name("Path on "+str(n)+" vertices")

        if n:
            g.add_path(range(n))

        g.set_pos({i:(i,0) for i in range(n)})
        return g

    def Path(self,n):
        r"""
        Returns a directed path on `n` vertices.

        INPUT:

        - ``n`` (integer) -- number of vertices in the path.

        EXAMPLES::

            sage: g = digraphs.Path(5)
            sage: g.vertices()
            [0, 1, 2, 3, 4]
            sage: g.size()
            4
            sage: g.automorphism_group().cardinality()
            1
        """
        g = DiGraph(n)
        g.name("Path")

        if n:
            g.add_path(range(n))

        g.set_pos({i:(i,0) for i in range(n)})
        return g

 def quiver_v2(self):
     #if hasattr(self, "_quiver_cache"):
     #    return self._quiver_cache
     from sage.combinat.subset import Subsets
     from sage.graphs.digraph import DiGraph
     Q = DiGraph(multiedges=True)
     Q.add_vertices(self.j_transversal())
     g = self.associated_graph()
     for U in Subsets(g.vertices()):
         for W in Subsets(U):
             h = g.subgraph(U.difference(W))
             n = h.connected_components_number() - 1
             if n > 0:
                 u = self.j_class_representative(self.j_class_index(self(''.join(U))))
                 w = self.j_class_representative(self.j_class_index(self(''.join(W))))
                 for i in range(n):
                     Q.add_edge(w, u, i)
     return Q

    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())