def coxeter_graph(self):
        """
        Return the Coxeter graph of ``self``.

        EXAMPLES::

            sage: C = CoxeterMatrix(['A',3])
            sage: C.coxeter_graph()
            Graph on 3 vertices

            sage: C = CoxeterMatrix([['A',3],['A',1]])
            sage: C.coxeter_graph()
            Graph on 4 vertices
        """
        n = self.rank()
        I = self.index_set()
        val = lambda x: infinity if x == -1 else x
        G = Graph(
            [
                (I[i], I[j], val((self._matrix)[i, j]))
                for i in range(n)
                for j in range(i)
                if self._matrix[i, j] not in [1, 2]
            ]
        )
        G.add_vertices(I)
        return G.copy(immutable=True)

    def coxeter_diagram(self):
        """
        Returns a Coxeter diagram for type H.

        EXAMPLES::

             sage: ct = CartanType(['H',3])
             sage: ct.coxeter_diagram()
             Graph on 3 vertices
             sage: sorted(ct.coxeter_diagram().edges())
             [(1, 2, 3), (2, 3, 5)]
             sage: ct.coxeter_matrix()
             [1 3 2]
             [3 1 5]
             [2 5 1]

             sage: ct = CartanType(['H',4])
             sage: ct.coxeter_diagram()
             Graph on 4 vertices
             sage: sorted(ct.coxeter_diagram().edges())
             [(1, 2, 3), (2, 3, 3), (3, 4, 5)]
             sage: ct.coxeter_matrix()
             [1 3 2 2]
             [3 1 3 2]
             [2 3 1 5]
             [2 2 5 1]
        """
        from sage.graphs.graph import Graph
        n = self.n
        g = Graph(multiedges=False)
        for i in range(1, n):
            g.add_edge(i, i+1, 3)
        g.set_edge_label(n-1, n, 5)
        return g

        def irreducible_component_index_sets(self):
            r"""
            Return a list containing the index sets of the irreducible components of
            ``self`` as finite reflection groups.

            EXAMPLES::

                sage: W = ReflectionGroup([1,1,3], [3,1,3], 4); W       # optional - gap3
                Reducible complex reflection group of rank 7 and type A2 x G(3,1,3) x ST4
                sage: sorted(W.irreducible_component_index_sets())      # optional - gap3
                [[1, 2], [3, 4, 5], [6, 7]]

            ALGORITHM:

                Take the connected components of the graph on the
                index set with edges (i,j) where s[i] and s[j] don't
                commute.
            """
            I = self.index_set()
            s = self.simple_reflections()
            from sage.graphs.graph import Graph
            G = Graph([I,
                       [[i,j]
                        for i,j in itertools.combinations(I,2)
                        if s[i]*s[j] != s[j]*s[i] ]],
                      format="vertices_and_edges")
            return G.connected_components()

    def coxeter_diagram(self):
        """
        Return the Coxeter diagram for ``self``.

        EXAMPLES::

            sage: cd = CartanType("A2xB2xF4").coxeter_diagram()
            sage: cd
            Graph on 8 vertices
            sage: cd.edges()
            [(1, 2, 3), (3, 4, 4), (5, 6, 3), (6, 7, 4), (7, 8, 3)]

            sage: CartanType("F4xA2").coxeter_diagram().edges()
            [(1, 2, 3), (2, 3, 4), (3, 4, 3), (5, 6, 3)]

            sage: cd = CartanType("A1xH3").coxeter_diagram(); cd
            Graph on 4 vertices
            sage: cd.edges()
            [(2, 3, 3), (3, 4, 5)]
        """
        from sage.graphs.graph import Graph
        relabelling = self._index_relabelling
        g = Graph(multiedges=False)
        g.add_vertices(self.index_set())
        for i,t in enumerate(self._types):
            for [e1, e2, l] in t.coxeter_diagram().edges():
                g.add_edge(relabelling[i,e1], relabelling[i,e2], label=l)
        return g

    def edge_coloring(self):
        r"""
        Compute a proper edge-coloring.

        A proper edge-coloring is an assignment of colors to the sets of the
        hypergraph such that two sets with non-empty intersection receive
        different colors. The coloring returned minimizes the number of colors.

        OUTPUT:

        A partition of the sets into color classes.

        EXAMPLES::

            sage: H = Hypergraph([{1,2,3},{2,3,4},{3,4,5},{4,5,6}]); H
            Hypergraph on 6 vertices containing 4 sets
            sage: C = H.edge_coloring()
            sage: C # random
            [[{3, 4, 5}], [{4, 5, 6}, {1, 2, 3}], [{2, 3, 4}]]
            sage: Set(sum(C,[])) == Set(H._sets)
            True
        """
        from sage.graphs.graph import Graph
        g = Graph([self._sets,lambda x,y : len(x&y)],loops = False)
        return g.coloring(algorithm="MILP")

    def edge_coloring(self):
        r"""
        Compute a proper edge-coloring.

        A proper edge-coloring is an assignment of colors to the sets of the
        incidence structure such that two sets with non-empty intersection
        receive different colors. The coloring returned minimizes the number of
        colors.

        OUTPUT:

        A partition of the sets into color classes.

        EXAMPLES::

            sage: H = Hypergraph([{1,2,3},{2,3,4},{3,4,5},{4,5,6}]); H
            Incidence structure with 6 points and 4 blocks
            sage: C = H.edge_coloring()
            sage: C # random
            [[[3, 4, 5]], [[2, 3, 4]], [[4, 5, 6], [1, 2, 3]]]
            sage: Set(map(Set,sum(C,[]))) == Set(map(Set,H.blocks()))
            True
        """
        from sage.graphs.graph import Graph
        blocks = self.blocks()
        blocks_sets = map(frozenset,blocks)
        g = Graph([range(self.num_blocks()),lambda x,y : len(blocks_sets[x]&blocks_sets[y])],loops = False)
        return [[blocks[i] for i in C] for C in g.coloring(algorithm="MILP")]

    def to_bipartite_graph(self, with_partition=False):
        r"""
        Returns the associated bipartite graph

        INPUT:

        - with_partition -- boolean (default: False)

        OUTPUT:

        - a graph or a pair (graph, partition)

        EXAMPLES::

            sage: H = designs.steiner_triple_system(7).blocks()
            sage: H = Hypergraph(H)
            sage: g = H.to_bipartite_graph(); g
            Graph on 14 vertices
            sage: g.is_regular()
            True
        """
        from sage.graphs.graph import Graph

        G = Graph()
        domain = list(self.domain())
        G.add_vertices(domain)
        for s in self._sets:
            for i in s:
                G.add_edge(s, i)
        if with_partition:
            return (G, [domain, list(self._sets)])
        else:
            return G

def CompleteMultipartiteGraph(l):
    r"""
    Returns a complete multipartite graph.

    INPUT:

    - ``l`` -- a list of integers : the respective sizes
      of the components.

    EXAMPLE:

    A complete tripartite graph with sets of sizes
    `5, 6, 8`::

        sage: g = graphs.CompleteMultipartiteGraph([5, 6, 8]); g
        Multipartite Graph with set sizes [5, 6, 8]: Graph on 19 vertices

    It clearly has a chromatic number of 3::

        sage: g.chromatic_number()
        3
    """
    g = Graph()
    for i in l:
        g = g + CompleteGraph(i)

    g = g.complement()
    g.name("Multipartite Graph with set sizes "+str(l))

    return g

    def cluster_in_box(self, m, pt=None):
        r"""
        Return the cluster (as a list) in the primal box [-m,m]^d
        containing the point pt.

        INPUT:

        - ``m`` - integer
        - ``pt`` - tuple, point in Z^d. If None, pt=zero is considered.

        EXAMPLES::

            sage: from slabbe import BondPercolationSample
            sage: S = BondPercolationSample(0.3,2)
            sage: S.cluster_in_box(2)         # random
            [(-2, -2), (-2, -1), (-1, -2), (-1, -1), (-1, 0), (0, 0)]
        """
        G = Graph()
        G.add_edges(self.edges_in_box(m))
        if pt is None:
            pt = self.zero()
        if pt in G:
            return G.connected_component_containing_vertex(pt)
        else:
            return []

    def __classcall_private__(cls, G):
        """
        Normalize input to ensure a unique representation.

        TESTS::

            sage: G1 = RightAngledArtinGroup(graphs.CycleGraph(5))
            sage: Gamma = Graph([(0,1),(1,2),(2,3),(3,4),(4,0)])
            sage: G2 = RightAngledArtinGroup(Gamma)
            sage: G3 = RightAngledArtinGroup([(0,1),(1,2),(2,3),(3,4),(4,0)])
            sage: G1 is G2 and G2 is G3
            True

        Handle the empty graph::

            sage: RightAngledArtinGroup(Graph())
            Traceback (most recent call last):
            ...
            ValueError: the graph must not be empty
        """
        if not isinstance(G, Graph):
            G = Graph(G, immutable=True)
        else:
            G = G.copy(immutable=True)
        if G.num_verts() == 0:
            raise ValueError("the graph must not be empty")
        return super(RightAngledArtinGroup, cls).__classcall__(cls, G)

 def hamiltonian_cycle(self, algorithm = "tsp", *largs, **kargs):
     store = lookup(kargs, "store", default = discretezoo.WRITE_TO_DB,
                    destroy = True)
     cur = lookup(kargs, "cur", default = None, destroy = True)
     default = len(largs) + len(kargs) == 0 and \
         algorithm in ["tsp", "backtrack"]
     if default:
         if algorithm == "tsp":
             try:
                 out = Graph.hamiltonian_cycle(self, algorithm, *largs,
                                               **kargs)
                 h = True
             except EmptySetError as out:
                 h = False
         elif algorithm == "backtrack":
             out = Graph.hamiltonian_cycle(self, algorithm, *largs, **kargs)
             h = out[0]
         try:
             lookup(self._graphprops, "is_hamiltonian")
         except KeyError:
             if store:
                 self._update_rows(ZooGraph, {"is_hamiltonian": h},
                                   {self._spec["primary_key"]: self._zooid},
                                   cur = cur)
             update(self._graphprops, "is_hamiltonian", h)
         if isinstance(out, BaseException):
             raise out
         else:
             return out
     else:
         return Graph.hamiltonian_cycle(self, algorithm, *largs, **kargs)

def import_graphs(file, cl = ZooGraph, db = None, format = "sparse6",
                  index = "index", verbose = False):
    r"""
    Import graphs from ``file`` into the database.

    This function is used to import new censuses of graphs and is not meant
    to be used by users of DiscreteZOO.

    To properly import the graphs, all graphs of the same order must be
    together in the file, and no graph of this order must be present in the
    database.

    INPUT:

    - ``file`` - the filename containing a graph in each line.

    - ``cl`` - the class to be used for imported graphs
      (default: ``ZooGraph``).

    - ``db`` - the database to import into. The default value of ``None`` means
      that the default database should be used.

    - ``format`` - the format the graphs are given in. If ``format`` is
      ``'graph6'`` or ``'sparse6'`` (default), then the graphs are read as
      strings, otherwised they are evaluated as Python expressions before
      being passed to Sage's ``Graph``.

    - ``index``: the name of the parameter of the constructor of ``cl``
      to which the serial number of the graph of a given order is passed.

    - ``verbose``: whether to print information about the progress of importing
      (default: ``False``).
    """
    info = ZooInfo(cl)
    if db is None:
        db = info.getdb()
    info.initdb(db = db, commit = False)
    previous = 0
    i = 0
    cur = db.cursor()
    with open(file) as f:
        for line in f:
            data = line.strip()
            if format not in ["graph6", "sparse6"]:
                data = eval(data)
            g = Graph(data)
            n = g.order()
            if n > previous:
                if verbose and previous > 0:
                    print "Imported %d graphs of order %d" % (i, previous)
                previous = n
                i = 0
            i += 1
            cl(graph = g, order = n, cur = cur, db = db, **{index: i})
        if verbose:
            print "Imported %d graphs of order %d" % (i, n)
        f.close()
    cur.close()
    db.commit()

    def to_undirected_graph(self):
        r"""
        Return the undirected graph obtained from the tree nodes and edges.

        The graph is endowed with an embedding, so that it will be displayed
        correctly.

        EXAMPLES::

            sage: t = OrderedTree([])
            sage: t.to_undirected_graph()
            Graph on 1 vertex
            sage: t = OrderedTree([[[]],[],[]])
            sage: t.to_undirected_graph()
            Graph on 5 vertices

        If the tree is labelled, we use its labelling to label the graph. This
        will fail if the labels are not all distinct.
        Otherwise, we use the graph canonical labelling which means that
        two different trees can have the same graph.

        EXAMPLES::

            sage: t = OrderedTree([[[]],[],[]])
            sage: t.canonical_labelling().to_undirected_graph()
            Graph on 5 vertices

        TESTS::

            sage: t.canonical_labelling().to_undirected_graph() == t.to_undirected_graph()
            False
            sage: OrderedTree([[],[]]).to_undirected_graph() == OrderedTree([[[]]]).to_undirected_graph()
            True
            sage: OrderedTree([[],[],[]]).to_undirected_graph() == OrderedTree([[[[]]]]).to_undirected_graph()
            False
        """
        from sage.graphs.graph import Graph
        g = Graph()
        if self in LabelledOrderedTrees():
            relabel = False
        else:
            self = self.canonical_labelling()
            relabel = True
        roots = [self]
        g.add_vertex(name=self.label())
        emb = {self.label(): []}
        while roots:
            node = roots.pop()
            children = reversed([child.label() for child in node])
            emb[node.label()].extend(children)
            for child in node:
                g.add_vertex(name=child.label())
                emb[child.label()] = [node.label()]
                g.add_edge(child.label(), node.label())
                roots.append(child)
        g.set_embedding(emb)
        if relabel:
            g = g.canonical_label()
        return g

 def create_graph_from_model(self, solver, model):
     """
     Given a model from the SAT solver, construct the graph.
     """
     g = Graph()
     on_vertices = solver.get_objects_in_model(model, self, self.internal_graph.vertices())
     on_edges = solver.get_objects_in_model(model, self, self.internal_graph.edges(labels=False))
     g.add_vertices(on_vertices)
     g.add_edges(on_edges)
     return g

    def coxeter_graph(self):
        """
        Return the Coxeter graph of ``self``.

        EXAMPLES::

            sage: W = CoxeterGroup(['H',3], implementation="reflection")
            sage: G = W.coxeter_graph(); G
            Graph on 3 vertices
            sage: G.edges()
            [(1, 2, None), (2, 3, 5)]
            sage: CoxeterGroup(G) is W
            True
            sage: G = Graph([(0, 1, 3), (1, 2, oo)])
            sage: W = CoxeterGroup(G)
            sage: W.coxeter_graph() == G
            True
            sage: CoxeterGroup(W.coxeter_graph()) is W
            True
        """
        G = Graph()
        G.add_vertices(self.index_set())
        for i, row in enumerate(self._matrix.rows()):
            for j, val in enumerate(row[i + 1 :]):
                if val == 3:
                    G.add_edge(self._index_set[i], self._index_set[i + 1 + j])
                elif val > 3:
                    G.add_edge(self._index_set[i], self._index_set[i + 1 + j], val)
                elif val == -1:  # FIXME: Hack because there is no ZZ\cup\{\infty\}
                    G.add_edge(self._index_set[i], self._index_set[i + 1 + j], infinity)
        return G

def CircularLadderGraph(n):
    """
    Returns a circular ladder graph with 2\*n nodes.

    A Circular ladder graph is a ladder graph that is connected at the
    ends, i.e.: a ladder bent around so that top meets bottom. Thus it
    can be described as two parallel cycle graphs connected at each
    corresponding node pair.

    This constructor depends on NetworkX numeric labels.

    PLOTTING: Upon construction, the position dictionary is filled to
    override the spring-layout algorithm. By convention, the circular
    ladder graph is displayed as an inner and outer cycle pair, with
    the first n nodes drawn on the inner circle. The first (0) node is
    drawn at the top of the inner-circle, moving clockwise after that.
    The outer circle is drawn with the (n+1)th node at the top, then
    counterclockwise as well.

    EXAMPLES: Construct and show a circular ladder graph with 26 nodes

    ::

        sage: g = graphs.CircularLadderGraph(13)
        sage: g.show() # long time

    Create several circular ladder graphs in a Sage graphics array

    ::

        sage: g = []
        sage: j = []
        sage: for i in range(9):
        ....:    k = graphs.CircularLadderGraph(i+3)
        ....:    g.append(k)
        sage: for i in range(3):
        ....:    n = []
        ....:    for m in range(3):
        ....:        n.append(g[3*i + m].plot(vertex_size=50, vertex_labels=False))
        ....:    j.append(n)
        sage: G = sage.plot.graphics.GraphicsArray(j)
        sage: G.show() # long time
    """
    pos_dict = {}
    for i in range(n):
        x = float(cos((pi/2) + ((2*pi)/n)*i))
        y = float(sin((pi/2) + ((2*pi)/n)*i))
        pos_dict[i] = [x,y]
    for i in range(n,2*n):
        x = float(2*(cos((pi/2) + ((2*pi)/n)*(i-n))))
        y = float(2*(sin((pi/2) + ((2*pi)/n)*(i-n))))
        pos_dict[i] = (x,y)

    G = Graph(pos=pos_dict, name="Circular Ladder graph")
    G.add_vertices( range(2*n) )
    G.add_cycle( range(n) )
    G.add_cycle( range(n,2*n) )
    G.add_edges( (i,i+n) for i in range(n) )
    return G

    def __init__(
        self, data=None, zooid=None, props=None, graph=None, vertex_labels=None, name=None, cur=None, db=None, **kargs
    ):
        ZooObject.__init__(self, db)
        kargs["immutable"] = True
        kargs["data_structure"] = "static_sparse"
        if isinteger(data):
            zooid = Integer(data)
            data = None
        elif isinstance(data, GenericGraph):
            graph = data
            data = None
        elif isinstance(data, dict):
            props = data
            data = None
        if props is not None:
            if "id" in props:
                zooid = props["id"]
            if "data" in props:
                data = props["data"]
            props = {k: v for k, v in props.items() if k not in ["id", "data"]}

        if graph is not None:
            if not isinstance(graph, GenericGraph):
                raise TypeError("not a graph")
            data = graph
            if name is None:
                name = graph.name()
            if isinstance(graph, ZooGraph):
                zooid = graph._zooid
                self._props = graph._props
            if cur is not None:
                if self._props is None:
                    self._props = {}
                self._props["diameter"] = graph.diameter()
                self._props["girth"] = graph.girth()
                self._props["order"] = graph.order()
            elif zooid is None:
                raise IndexError("graph id not given")
        else:
            cur = None
            if props is not None:
                self._props = self._todict(props, skip=ZooGraph._spec["skip"], fields=ZooGraph._spec["fields"])

        self._zooid = zooid
        if data is None:
            data = self._db_read()["data"]
        if vertex_labels is not None:
            data = Graph(data).relabel(vertex_labels, inplace=False)
        Graph.__init__(self, data=data, name=name, **kargs)
        if cur is not None:
            self._db_write(cur)

def _polar_graph(m, q, g, intersection_size=None):
    r"""
    The helper function to build graphs `(D)U(m,q)` and `(D)Sp(m,q)`

    Building a graph on an orbit of a group `g` of `m\times m` matrices over `GF(q)` on
    the points (or subspaces of dimension ``m//2``) isotropic w.r.t. the form `F`
    left invariant by the group `g`.

    The only constraint is that the first ``m//2`` elements of the standard
    basis must generate a totally isotropic w.r.t. `F` subspace; this is the case with
    these groups coming from GAP; namely, `F` has the anti-diagonal all-1 matrix.

    INPUT:

    - ``m`` -- the dimension of the underlying vector space

    - ``q`` -- the size of the field

    - ``g`` -- the group acting

    - ``intersection_size`` -- if ``None``, build the graph on the isotropic points, with
      adjacency being orthogonality w.r.t. `F`. Otherwise, build the graph on the maximal
      totally isotropic subspaces, with adjacency specified by ``intersection_size`` being
      as given.

    TESTS::

        sage: from sage.graphs.generators.classical_geometries import _polar_graph
        sage: _polar_graph(4, 4, libgap.GeneralUnitaryGroup(4, 2))
        Graph on 45 vertices
        sage: _polar_graph(4, 4, libgap.GeneralUnitaryGroup(4, 2), intersection_size=1)
        Graph on 27 vertices
    """
    from sage.libs.gap.libgap import libgap
    from itertools import combinations
    W=libgap.FullRowSpace(libgap.GF(q), m)  # F_q^m
    B=libgap.Elements(libgap.Basis(W))      # the standard basis of W
    V = libgap.Orbit(g,B[0],libgap.OnLines) # orbit on isotropic points
    gp = libgap.Action(g,V,libgap.OnLines)  # make a permutation group
    s = libgap.Subspace(W,[B[i] for i in range(m//2)]) # a totally isotropic subspace
    # and the points there
    sp = [libgap.Elements(libgap.Basis(x))[0] for x in libgap.Elements(s.Subspaces(1))]
    h = libgap.Set(map(lambda x: libgap.Position(V, x), sp)) # indices of the points in s
    L = libgap.Orbit(gp, h, libgap.OnSets) # orbit on these subspaces
    if intersection_size == None:
        G = Graph()
        for x in L: # every pair of points in the subspace is adjacent to each other in G
            G.add_edges(combinations(x, 2))
        return G
    else:
        return Graph([L, lambda i,j: libgap.Size(libgap.Intersection(i,j))==intersection_size],
                        loops=False)

def CayleyGraph(vspace, gens, directed=False):
  """
  Generate a Cayley Graph over given vector space with edges
  generated by given generators. The graph is optionally directed.
  Try e.g. CayleyGraph(VectorSpace(GF(2), 3), [(1,0,0), (0,1,0), (0,0,1)])
  """
  G = Graph()
  for v in vspace:
    G.add_vertex(tuple(v))
    for g in gens:
      g2 = vspace(g)
      G.add_edge(tuple(v), tuple(v + g2))
  return G

def graph6_to_plot(graph6):
    """
    Constructs a graph from a graph6 string and returns a Graphics
    object with arguments preset for show function.

    EXAMPLE::

        sage: from sage.graphs.graph_database import graph6_to_plot
        sage: type(graph6_to_plot('D??'))
        <class 'sage.plot.graphics.Graphics'>
    """
    g = Graph(str(graph6))
    return g.plot(layout='circular',vertex_size=30,vertex_labels=False,graph_border=False)