Commits

Volker Braun  committed 47cd41a

added toric morphism factorization

  • Participants
  • Parent commits 073e9eb

Comments (0)

Files changed (11)

File 14291_reviewer.patch

+# HG changeset patch
+# User Dmitrii Pasechnik <dimpase@gmail.com>
+# Date 1363712673 -28800
+# Node ID c88f77f5b975d7eb044a979c1feaaf8091821131
+# Parent  7bf0ce3fbbc7422dd5c98b3abc4067186469aac8
+reviewer patch, adding moar actions
+
+diff --git a/sage/groups/perm_gps/permgroup.py b/sage/groups/perm_gps/permgroup.py
+--- a/sage/groups/perm_gps/permgroup.py
++++ b/sage/groups/perm_gps/permgroup.py
+@@ -96,6 +96,8 @@
+ 
+ - Javier Lopez Pena (2013): Added conjugacy classes.
+ 
++- Nathann Cohen, Dmitrii Pasechnik (2013): Added non-default actions.
++
+ REFERENCES:
+ 
+ - Cameron, P., Permutation Groups. New York: Cambridge University
+@@ -1039,7 +1041,7 @@
+     def orbits(self):
+         """
+         Returns the orbits of the elements of the domain under the
+-        group action.
++        default group action.
+         
+         EXAMPLES::
+         
+@@ -1066,21 +1068,26 @@
+         return [[self._domain_from_gap[x] for x in orbit] for orbit in
+                 self._gap_().Orbits(self._domain_gap()).sage()]
+ 
++    supported_actions = ["OnPoints", "OnTuples", "OnSets", "OnPairs", "OnSetsSets", 
++                "OnSetsDisjointSets", "OnSetsTuples", "OnTuplesSets", "OnTuplesTuples"]
++
+     @cached_method
+     def orbit(self, point, action = "OnPoints"):
+         """
+-        Return the orbit of a point (or set, or tuple) under the group action.
++        Return the orbit of a point under the group action in the list
++        `self.supported_actions`. 
++        These are taken from `http://www.gap-system.org/Manuals/doc/ref/chap41.html`_. 
+ 
+         INPUT:
+ 
+-        - ``point`` -- can be a point or a tuple of points, depending on the
+-          action to be considered.
+-
+-        - ``action`` (string) -- when ``point`` is a tuple of points, this
+-          variable defines whether the group is to be considered as acting on
+-          tuples (``action="ontuples"``) or acting on sets
+-          (``action="onsets"``). It is set to ``"onpoints"`` by default. See
+-          below for examples.
++        - ``point`` -- can be a point or any of the list above, depending on the
++          action to be considered. Note that sets should be "canonical", i.e. their
++          members must be sorted w.r.t. to the default order on them.
++
++        - ``action`` (string) -- if ``point`` is a tuple (of tuples) of points, this
++          variable describes how the group is acting. The list of possibilites is 
++          is given by  `self.supported_actions`.
++          It is set to ``"OnPoints"`` by default. See below for examples.
+ 
+         EXAMPLES::
+ 
+@@ -1104,6 +1111,13 @@
+ 
+             sage: S3.orbit((1,2), action = "OnTuples")
+             [[1, 2], [2, 3], [2, 1], [3, 1], [1, 3], [3, 2]]
++        
++        Action of `S_4` on sets of disjoint sets::
++
++            sage: S4 = groups.permutation.Symmetric(4)
++            sage: S4.orbit(((1,2),(3,4)), action = "OnSetsDisjointSets")
++            [[[1, 2], [3, 4]], [[1, 4], [2, 3]], [[1, 3], [2, 4]]]
++
+         """
+         if action == "OnPoints":
+             try:
+@@ -1115,12 +1129,55 @@
+                                  "argument explicitly.")
+             return [self._domain_from_gap[x] for x in self._gap_().Orbit(point).sage()]
+ 
+-        elif action in ["OnTuples", "OnSets"]:
+-            points = [self._domain_to_gap[x] for x in point]
+-            orbits = self._gap_().Orbit(points, action).sage()
+-            return [[self._domain_from_gap[x] for x in o] for o in orbits]
++        elif action in self.supported_actions:
++            if action in ['OnTuples', 'OnSets', 'OnPairs']:
++                points = [self._domain_to_gap[x] for x in point]
++                orbits = self._gap_().Orbit(points, action).sage()
++                return [[self._domain_from_gap[x] for x in o] for o in orbits]
++            else:
++                points = [[self._domain_to_gap[x] for x in p] for p in point]
++                orbits = self._gap_().Orbit(points, action).sage()
++                return [[[self._domain_from_gap[x] for x in p] for p in o] 
++                        for o in orbits]
++
+         else:
+-            raise ValueError("'action' can only take values among 'OnPoints', 'OnTuples' or 'OnSets'.")
++            raise ValueError("'action' can only take values among "+
++                             self.supported_actions)
++
++    def action(self, domain, action = "OnPoints"):
++        """
++        Return the permutation group induced by self acting on domain.
++        
++        INPUT:
++
++        - ``domain`` -- the list of things for which GAP knows how to compute
++          the action of the permutation group. For instance it can be obtained by
++          calling :meth:`orbit`. 
++
++        - ``action`` (string) -- the action on domain. Need not be limited to 
++          `self.supported_actions`.
++          It is set to ``"OnPoints"`` by default. See below for examples.
++
++        EXAMPLES::
++
++            Action of `S_5` on 2-subsets::
++
++            sage: S5 = groups.permutation.Symmetric(5)
++            sage: o10 = S5.orbit((1,2), action = "OnSets")
++            sage: S5_10 = S5.action(o10, action = "OnSets"); S5_10
++            Permutation Group with generators [(2,4)(6,9)(7,10), (1,2,3,5,7)(4,6,8,9,10)]
++            
++            Non-faithful action of `S_4` on sets of disjoint sets::
++
++            sage: S4 = groups.permutation.Symmetric(4)
++            sage: o3 = S4.orbit(((1,2),(3,4)), action = "OnSetsDisjointSets")
++            sage: S3 = S4.action(o3,  "OnSetsDisjointSets"); S3
++            Permutation Group with generators [(2,3), (1,2)]
++            sage: S3.order()
++            6
++
++        """
++        return PermutationGroup(gap_group = self._gap_().Action(domain, action))
+ 
+     def transversals(self, point):
+         """
+trac_14291.patch
+14291_reviewer.patch
+trac_14291-rev2.patch
+trac_14319.patch
+trac_14319_fix_fan_isomorphism.patch
+trac_13183_index_of_codomain_cone.patch
+trac_13183_untwist_lattice_splitting.patch
+trac_13194_polytope_fan_construct.patch
 trac_12892_orbit_closure_morphism.patch
-trac_fan_cone_intersection.patch
+trac_14353_fan_cone_intersection.patch
+trac_14353_factor_fan_morphism.patch
 trac_12892_toric_morphism_fibers.patch
 trac_12892_toric_morphism_divisors.patch
 trac_12900_Demazure_roots.patch
-trac_13194_polytope_fan_construct.patch
 trac_xxxx_fiber_divisor_graph.patch
 trac_13249_vb.patch
 trac_13249_volume.patch

File trac_13183_index_of_codomain_cone.patch

+# HG changeset patch
+# User Andrey Novoseltsev <novoselt@gmail.com>
+# Date 1359588744 25200
+# Node ID 6798c3edf6125b94e4ac8a925149333a06725d9c
+# Parent  e52aaa1873d77cda3faf2f36bb69d70ff54a5a84
+Implement index(cone) for fan morphisms and make some related improvements.
+
+diff --git a/sage/geometry/cone.py b/sage/geometry/cone.py
+--- a/sage/geometry/cone.py
++++ b/sage/geometry/cone.py
+@@ -210,7 +210,7 @@
+     is_ToricLatticeQuotient
+ from sage.geometry.toric_plotter import ToricPlotter, label_list
+ from sage.graphs.digraph import DiGraph
+-from sage.matrix.all import matrix, identity_matrix
++from sage.matrix.all import column_matrix, matrix, identity_matrix
+ from sage.misc.all import cached_method, flatten, latex, prod
+ from sage.misc.superseded import deprecation
+ from sage.modules.all import span, vector
+@@ -490,20 +490,25 @@
+     rays = []
+     lines = []
+     for g in cone.minimized_generators():
+-        ray = lattice(g.coefficients())
+-        ray.set_immutable()
+         if g.is_ray():
+-            rays.append(ray)
++            rays.append(g)
+         if g.is_line():
+-            lines.append(ray)
+-            negative_ray = -ray
+-            negative_ray.set_immutable()
+-            lines.append(negative_ray)
++            lines.append(g)
+     if (original_rays is not None and not lines and
+         len(rays) == len(original_rays)):
+         return ConvexRationalPolyhedralCone(original_rays, lattice, PPL=cone)
+     else:
+-        return ConvexRationalPolyhedralCone(rays + lines, lattice, PPL=cone)
++        rays = [ray.coefficients() for ray in rays]
++        for line in lines:
++            rays.append(line.coefficients())
++            rays.append(-vector(ZZ, rays[-1]))
++        try:
++            for i, ray in enumerate(rays):
++                rays[i] = lattice(ray)
++                rays[i].set_immutable()
++        except TypeError:
++            rays = normalize_rays(rays, lattice)
++        return ConvexRationalPolyhedralCone(rays, lattice, PPL=cone)
+ 
+ 
+ def normalize_rays(rays, lattice):
+@@ -559,13 +564,26 @@
+             ray_parent = parent(rays[0])
+             lattice = (ray_parent if is_ToricLattice(ray_parent)
+                                   else ToricLattice(len(rays[0])))
++        if lattice.base_ring() is not ZZ:
++            raise TypeError("lattice must be a free module over ZZ")
+         # Are we dealing with a quotient lattice?
+         try:
+             if not lattice.is_torsion_free():
+                 raise ValueError("cannot normalize rays of torsion quotients!")
+         except AttributeError:
+             pass
+-        V = lattice.base_extend(QQ)
++        V = None
++        try:
++            if lattice.is_ambient():
++                # Handle the most common case efficiently.
++                V = lattice.base_extend(QQ)
++                length = lambda ray: integral_length(ray)
++        except AttributeError:
++            pass
++        if V is None:
++            # Use a more general, but slower way.
++            V = lattice.vector_space_span_of_basis(lattice.basis())
++            length = lambda ray: integral_length(V.coordinate_vector(ray))
+         for n, ray in enumerate(rays):
+             try:
+                 if isinstance(ray, (list, tuple, V._element_class)):
+@@ -577,7 +595,7 @@
+             if ray.is_zero():
+                 ray = lattice(0)
+             else:
+-                ray = lattice(ray / integral_length(ray))
++                ray = lattice(ray / length(ray))
+             ray.set_immutable()
+             rays[n] = ray
+     return rays
+@@ -3165,7 +3183,7 @@
+     def _split_ambient_lattice(self):
+         r"""
+         Compute a decomposition of the ``N``-lattice into `N_\sigma`
+-        and its complement `N(\sigma)`.
++        and its complement isomorphic to `N(\sigma)`.
+ 
+         You should not call this function directly, but call
+         :meth:`sublattice` and :meth:`sublattice_complement` instead.
+@@ -3178,15 +3196,6 @@
+             Sublattice <N(1, 2)>
+             sage: c._sublattice_complement
+             Sublattice <N(0, 1)>
+-            sage: c._orthogonal_sublattice
+-            Sublattice <M(-2, 1)>
+-            sage: c._orthogonal_sublattice_complement
+-            Sublattice <M(1, 0)>
+-            sage: N = c.lattice()
+-            sage: n = N(27,31)
+-            sage: (N(0) + c._sublattice.gen(0) * (c._orthogonal_sublattice_complement.gen(0)*n)
+-            ...         + c._sublattice_complement.gen(0) * (c._orthogonal_sublattice.gen(0)*n))
+-            N(27, 31)
+ 
+         Degenerate cases::
+ 
+@@ -3194,8 +3203,6 @@
+             sage: C2_Z2._split_ambient_lattice()
+             sage: C2_Z2._sublattice
+             Sublattice <N(1, 0), N(0, 1)>
+-            sage: C2_Z2._orthogonal_sublattice
+-            Sublattice <>
+ 
+         Trivial cone::
+            
+@@ -3205,32 +3212,18 @@
+             Sublattice <>
+             sage: trivial_cone._sublattice_complement
+             Sublattice <N(1, 0, 0), N(0, 1, 0), N(0, 0, 1)>
+-            sage: trivial_cone._orthogonal_sublattice
+-            Sublattice <M(1, 0, 0), M(0, 1, 0), M(0, 0, 1)>
+-            sage: trivial_cone._orthogonal_sublattice_complement
+-            Sublattice <>
+         """
+-        Nsigma = self.rays().basis().matrix().transpose()
+-        r = Nsigma.ncols()
++        N = self.lattice()
++        n = N.dimension()
++        basis = self.rays().basis()
++        r = len(basis)
++        Nsigma = column_matrix(ZZ, r, n, [N.coordinates(v) for v in basis])
+         D, U, V = Nsigma.smith_form()  # D = U*N*V <=> N = Uinv*D*Vinv
+-        Uinv = U.inverse()
+-        n = Uinv.ncols()
+-        
+-        N = self.lattice()
+-        # basis for the spanned lattice
+-        basis = [ Uinv.column(i) for i in range(0,r) ]
+-        self._sublattice = N.submodule_with_basis(basis)
+-        # basis for a complement to the spanned lattice
+-        basis = [ Uinv.column(i) for i in range(r,n) ]
+-        self._sublattice_complement = N.submodule_with_basis(basis)
+-        
+-        M = self.dual_lattice()
+-        # basis for the dual spanned lattice
+-        basis = [U.row(i) for i in range(r, n)]
+-        self._orthogonal_sublattice = M.submodule_with_basis(basis)
+-        # basis for a complement to the dual spanned lattice
+-        basis = [U.row(i) for i in range(r)]
+-        self._orthogonal_sublattice_complement = M.submodule_with_basis(basis)
++        basis = (N.basis_matrix().transpose() * U.inverse()).columns()
++        # spanned lattice N_sigma
++        self._sublattice = N.submodule_with_basis(basis[:r])
++        # complement to the spanned lattice, isomorphic to N(sigma)
++        self._sublattice_complement = N.submodule_with_basis(basis[r:])
+ 
+     def sublattice(self, *args, **kwds):
+         r""" 
+@@ -3443,10 +3436,15 @@
+             sage: c12.sublattice()
+             Sublattice <N(1, 1, 1), N(0, 1, 0)>
+             sage: c12.orthogonal_sublattice()
+-            Sublattice <M(-1, 0, 1)>
++            Sublattice <M(1, 0, -1)>
+         """
+         if "_orthogonal_sublattice" not in self.__dict__:
+-            self._split_ambient_lattice()
++            try:
++                self._orthogonal_sublattice = self.sublattice_quotient().dual()
++            except AttributeError:
++                # Non-toric quotient? Just make ZZ^n then.
++                self._orthogonal_sublattice = ZZ**(self.lattice().dimension() -
++                                                  self.sublattice().dimension())
+         if args or kwds:
+             return self._orthogonal_sublattice(*args, **kwds)
+         else:
+@@ -3593,12 +3591,12 @@
+             Sublattice <M(0, 0, 3, -1)>
+             sage: sigma = rho.facets()[2]
+             sage: sigma.orthogonal_sublattice()
+-            Sublattice <M(0, 1, 1, 0), M(0, 3, 0, 1)>
++            Sublattice <M(0, 1, 1, 0), M(0, 0, 3, -1)>
+             sage: sigma.is_face_of(rho)
+             True
+             sage: Q = sigma.relative_orthogonal_quotient(rho); Q
+             1-d lattice, quotient
+-            of Sublattice <M(0, 1, 1, 0), M(0, 3, 0, 1)>
++            of Sublattice <M(0, 1, 1, 0), M(0, 0, 3, -1)>
+             by Sublattice <M(0, 0, 3, -1)>
+             sage: Q.gens()
+             (M[0, 1, 1, 0],)
+@@ -3608,11 +3606,11 @@
+             sage: rho = Cone([[1,-1,1,3],[-1,-1,1,3]])
+             sage: sigma = rho.facets()[0]
+             sage: sigma.orthogonal_sublattice()
+-            Sublattice <M(0, 1, 1, 0), M(1, 1, 0, 0), M(0, 3, 0, 1)>
++            Sublattice <M(1, 0, 2, -1), M(0, 1, 1, 0), M(0, 0, 3, -1)>
+             sage: rho.orthogonal_sublattice()
+-            Sublattice <M(0, 1, 1, 0), M(0, 3, 0, 1)>
++            Sublattice <M(0, 1, 1, 0), M(0, 0, 3, -1)>
+             sage: sigma.relative_orthogonal_quotient(rho).gens()
+-            (M[-1, -1, 0, 0],)
++            (M[-1, 0, -2, 1],)
+ 
+         Sign choice in the codimension one case::
+           
+diff --git a/sage/geometry/fan_morphism.py b/sage/geometry/fan_morphism.py
+--- a/sage/geometry/fan_morphism.py
++++ b/sage/geometry/fan_morphism.py
+@@ -82,10 +82,10 @@
+ from sage.geometry.cone import Cone
+ from sage.geometry.fan import Fan, is_Fan, discard_faces
+ from sage.matrix.all import matrix, is_Matrix
+-from sage.misc.all import cached_method, latex, walltime
++from sage.misc.all import cached_method, latex, prod, walltime
+ from sage.modules.free_module_morphism import (FreeModuleMorphism,
+                                                is_FreeModuleMorphism)
+-from sage.rings.all import ZZ, is_Infinite
++from sage.rings.all import Infinity, ZZ, is_Infinite
+ 
+ 
+ class FanMorphism(FreeModuleMorphism):
+@@ -943,13 +943,32 @@
+         return self._image_cone[cone]
+         
+     @cached_method
+-    def index(self):
++    def index(self, cone=None):
+         r"""
+         Return the index of ``self`` as a map between lattices.
+         
++        INPUT:
++        
++        - ``cone`` -- (default: ``None``) a :class:`cone
++          <sage.geometry.cone.ConvexRationalPolyhedralCone>` of the
++          :meth:`codomain_fan` of ``self``.
++        
+         OUTPUT:
+         
+-        - an integer or infinity.
++        - an integer, infinity, or ``None``.
++        
++        If no cone was specified, this function computes the index of the
++        image of ``self`` in the codomain. If a cone `\sigma` was given, the
++        index of ``self`` over `\sigma` is computed in the sense of
++        Definition 2.1.7 of [HLY]: if `\sigma'` is any cone of the
++        :meth:`domain_fan` of ``self`` whose relative interior is mapped to the
++        relative interior of `\sigma`, it is the index of the image of
++        `N'(\sigma')` in `N(\sigma)`, where `N'` and `N` are domain and codomain
++        lattices respectively. While that definition was formulated for the case
++        of the finite index only, we extend it to the infinite one as well and
++        return ``None`` if there is no `\sigma'` at all. See examples below for
++        situations when such things happen. Note also that the index of ``self``
++        is the same as index over the trivial cone.
+         
+         EXAMPLES::
+         
+@@ -964,8 +983,71 @@
+             sage: xi = FanMorphism(matrix([[1, 0]]), Sigma_p, Sigma)
+             sage: xi.index()
+             +Infinity
++            
++        Infinite index in the last example indicates that the image has positive
++        codimension in the codomain. Let's look at the rays of our fans::
++        
++            sage: Sigma_p.rays()
++            N( 1),
++            N(-1)
++            in 1-d lattice N
++            sage: Sigma.rays()
++            N( 1,  1),
++            N( 0,  1),
++            N(-1, -1),
++            N( 1,  0)
++            in 2-d lattice N
++            sage: xi.restrict_to_image().codomain_fan().rays()
++            N( 1, 0),
++            N(-1, 0)
++            in Sublattice <N(1, 0)>
++
++        We see that one of the rays of the fan of ``P1`` is mapped to a ray,
++        while the other one to the interior of some 2-d cone. Both rays
++        correspond to single points on ``P1``, yet one is mapped to the
++        distinguished point of a torus invariant curve of ``dP8`` (with the
++        rest of this curve being uncovered) and the other to a fixed point
++        of ``dP8`` (thus completely covering this torus orbit in ``dP8``).
++        
++        We should therefore expect the following behaviour: all indices over
++        1-d cones are ``None``, except for one which is infinite, and all
++        indices over 2-d cones are ``None``, except for one which is 1::
++            
++            sage: [xi.index(cone) for cone in Sigma(1)]
++            [None, None, None, +Infinity]
++            sage: [xi.index(cone) for cone in Sigma(2)]
++            [None, 1, None, None]
++            
++        TESTS::
++        
++            sage: Sigma = toric_varieties.dP8().fan()
++            sage: Sigma_p = toric_varieties.Cube_nonpolyhedral().fan()
++            sage: m = matrix([[2,6,10], [7,11,13]])
++            sage: zeta = FanMorphism(m, Sigma, Sigma_p, subdivide=True)
++            sage: [zeta.index(cone) for cone in flatten(Sigma_p.cones())]
++            [+Infinity, None, None, None, None, None, None, None, None, None,
++             4, 4, None, 4, None, None, 2, None, 4, None, 4, 1, 1, 1, 1, 1, 1]
++            sage: zeta = zeta.restrict_to_image()
++            sage: Sigma_p = zeta.codomain_fan()
++            sage: [zeta.index(cone) for cone in flatten(Sigma_p.cones())]
++            [4, 4, 1, 4, 4, 4, 4, 1, 1, 1, 1, 1, 1]
++            sage: zeta.index() == zeta.index(Sigma_p(0)[0])
++            True
+         """
+-        return self.matrix().image().index_in(self.codomain())
++        if cone is None:
++            try:
++                return self.matrix().image().index_in(self.codomain())
++            except ArithmeticError:
++                cone = Cone([], lattice=self.codomain())
++        cone = self._codomain_fan.embed(cone)
++        PPCs = self.primitive_preimage_cones(cone)
++        if not PPCs:
++            return None
++        Q = cone.sublattice_quotient()
++        S = Q.submodule([self(g)
++                         for g in PPCs[0].sublattice_complement().gens()])
++        i = prod((Q/S).invariants())
++        return i if i > 0 else Infinity
+ 
+     @cached_method
+     def is_bundle(self):
+diff --git a/sage/geometry/toric_lattice.py b/sage/geometry/toric_lattice.py
+--- a/sage/geometry/toric_lattice.py
++++ b/sage/geometry/toric_lattice.py
+@@ -1106,7 +1106,7 @@
+                 raise ValueError("only dual lattices of saturated sublattices "
+                                  "can be constructed! Got %s." % self)
+             self._dual = (self.ambient_module().dual() /
+-                          self.basis_matrix().right_kernel())
++                          self.basis_matrix().transpose().integer_kernel())
+             self._dual._dual = self
+         return self._dual
+ 
+@@ -1606,6 +1606,28 @@
+             True
+         """
+         return sum(self.invariants()) == 0
++        
++    def dual(self):
++        r"""
++        Return the lattice dual to ``self``.
++
++        OUTPUT:
++
++        - a :class:`toric lattice quotient <ToricLattice_quotient>`.
++
++        EXAMPLES::
++
++            sage: N = ToricLattice(3)
++            sage: Ns = N.submodule([(1, -1, -1)])
++            sage: Q = N / Ns
++            sage: Q.dual()
++            Sublattice <M(1, 0, 1), M(0, 1, -1)>
++        """
++        if "_dual" not in self.__dict__:
++            self._dual = self.V().dual().submodule(
++                    self.W().basis_matrix().transpose().integer_kernel().gens())
++            self._dual._dual = self
++        return self._dual
+ 
+     def rank(self):
+         r"""
+@@ -1632,6 +1654,8 @@
+             2
+         """
+         return self.V().rank() - self.W().rank()
++        
++    dimension = rank
+     
+     def coordinate_vector(self, x, reduce=False):
+         """
+@@ -1666,6 +1690,3 @@
+             return -coordinates
+         else:
+             return coordinates
+-            
+-        
+-

File trac_13183_untwist_lattice_splitting.patch

+# HG changeset patch
+# User Andrey Novoseltsev <novoselt@gmail.com>
+# Date 1342670694 21600
+# Node ID 42f795cf006e75b78adc0447eda4c01d0d2ee5bd
+# Parent  92d2af1de769911650b6970c45b9c4b98b848a98
+Get rid of extraneous transpositions in cone sublattice computation.
+
+diff --git a/sage/geometry/cone.py b/sage/geometry/cone.py
+--- a/sage/geometry/cone.py
++++ b/sage/geometry/cone.py
+@@ -209,7 +209,7 @@
+     is_ToricLatticeQuotient
+ from sage.geometry.toric_plotter import ToricPlotter, label_list
+ from sage.graphs.digraph import DiGraph
+-from sage.matrix.all import column_matrix, matrix, identity_matrix
++from sage.matrix.all import matrix, identity_matrix
+ from sage.misc.all import cached_method, flatten, latex, prod
+ from sage.misc.superseded import deprecation
+ from sage.modules.all import span, vector
+@@ -3106,7 +3106,7 @@
+             sage: C2_Z2 = Cone([(1,0),(1,2)])
+             sage: C2_Z2._split_ambient_lattice()
+             sage: C2_Z2._sublattice
+-            Sublattice <N(1, 0), N(0, 1)>
++            Sublattice <N(1, 2), N(0, -1)>
+ 
+         Trivial cone::
+            
+@@ -3121,9 +3121,9 @@
+         n = N.dimension()
+         basis = self.rays().basis()
+         r = len(basis)
+-        Nsigma = column_matrix(ZZ, r, n, [N.coordinates(v) for v in basis])
++        Nsigma = matrix(ZZ, r, n, [N.coordinates(v) for v in basis])
+         D, U, V = Nsigma.smith_form()  # D = U*N*V <=> N = Uinv*D*Vinv
+-        basis = (N.basis_matrix().transpose() * U.inverse()).columns()
++        basis = (V.inverse() * N.basis_matrix()).rows()
+         # spanned lattice N_sigma
+         self._sublattice = N.submodule_with_basis(basis[:r])
+         # complement to the spanned lattice, isomorphic to N(sigma)
+@@ -3177,9 +3177,9 @@
+             sage: cone.rays().basis().matrix().det()
+             -4
+             sage: cone.sublattice()
+-            Sublattice <N(1, 1, 1), N(0, 1, 0), N(1, 0, 0)>
++            Sublattice <N(-1, -1, 1), N(1, 0, 0), N(1, 1, 0)>
+             sage: matrix( cone.sublattice().gens() ).det()
+-            -1
++            1
+             
+         Another example::
+             
+@@ -3191,7 +3191,7 @@
+             N(4, -5, 1)
+             in 3-d lattice N
+             sage: c.sublattice()
+-            Sublattice <N(1, 2, 3), N(0, 13, 11)>
++            Sublattice <N(1, 2, 3), N(4, -5, 1)>
+             sage: c.sublattice(5, -3, 4)
+             N(5, -3, 4)
+             sage: c.sublattice(1, 0, 0)            
+@@ -3287,14 +3287,14 @@
+ 
+             sage: c = Cone([(1,2,3), (4,-5,1)])
+             sage: c.sublattice()
+-            Sublattice <N(1, 2, 3), N(0, 13, 11)>
++            Sublattice <N(1, 2, 3), N(4, -5, 1)>
+             sage: c.sublattice_complement()
+-            Sublattice <N(-7, -8, -16)>
++            Sublattice <N(0, -6, -5)>
+             sage: m = matrix( c.sublattice().gens() + c.sublattice_complement().gens() )
+             sage: m
+-            [  1   2   3]
+-            [  0  13  11]
+-            [ -7  -8 -16]
++            [ 1  2  3]
++            [ 4 -5  1]
++            [ 0 -6 -5]
+             sage: m.det()
+             -1
+             """
+@@ -3338,7 +3338,7 @@
+             Sublattice <>
+             sage: c12 = Cone([(1,1,1), (1,-1,1)])
+             sage: c12.sublattice()
+-            Sublattice <N(1, 1, 1), N(0, 1, 0)>
++            Sublattice <N(1, -1, 1), N(0, 1, 0)>
+             sage: c12.orthogonal_sublattice()
+             Sublattice <M(1, 0, -1)>
+         """
+@@ -3388,15 +3388,15 @@
+             sage: sigma = Cone([(1,1,1,3),(1,-1,1,3),(-1,-1,1,3),(-1,1,1,3)])
+             sage: rho   = Cone([(-1, -1, 1, 3), (-1, 1, 1, 3)])
+             sage: sigma.sublattice()
+-            Sublattice <N(1, 1, 1, 3), N(1, 0, 0, 0), N(0, 1, 0, 0)>
++            Sublattice <N(-1, -1, 1, 3), N(1, 0, 0, 0), N(1, 1, 0, 0)>
+             sage: rho.sublattice()
+-            Sublattice <N(-1, 1, 1, 3), N(0, 1, 0, 0)>
++            Sublattice <N(-1, 1, 1, 3), N(0, -1, 0, 0)>
+             sage: sigma.relative_quotient(rho)
+             1-d lattice, quotient
+-            of Sublattice <N(1, 1, 1, 3), N(1, 0, 0, 0), N(0, 1, 0, 0)>
++            of Sublattice <N(-1, -1, 1, 3), N(1, 0, 0, 0), N(1, 1, 0, 0)>
+             by Sublattice <N(1, 0, -1, -3), N(0, 1, 0, 0)>
+             sage: sigma.relative_quotient(rho).gens()
+-            (N[1, 0, 0, 0],)
++            (N[1, 1, 0, 0],)
+ 
+         More complicated example::
+   
+@@ -3404,12 +3404,12 @@
+             sage: sigma = Cone([(1, 2, 3), (1, -1, 1), (-1, 1, 1), (-1, -1, 1)])
+             sage: N_sigma = sigma.sublattice()
+             sage: N_sigma
+-            Sublattice <N(3, 0, 1), N(2, 1, 0), N(1, 0, 0)>
++            Sublattice <N(-1, 1, 1), N(1, 2, 3), N(0, 1, 1)>
+             sage: N_rho = rho.sublattice()
+             sage: N_rho
+-            Sublattice <N(1, -1, 1), N(0, 3, 2)>
++            Sublattice <N(1, -1, 1), N(1, 2, 3)>
+             sage: sigma.relative_quotient(rho).gens()
+-            (N[0, -2, -1],)
++            (N[0, 1, 1],)
+             sage: N = rho.lattice()
+             sage: N_sigma == N.span(N_rho.gens() + tuple(q.lift()
+             ...              for q in sigma.relative_quotient(rho).gens()))
+@@ -3421,15 +3421,15 @@
+             sage: sigma2 = Cone([(1, 1, -1), (1, 2, 3), (1, -1, 1), (1, -1, -1)])  # 3d
+             sage: rho = sigma1.intersection(sigma2)
+             sage: rho.sublattice()
+-            Sublattice <N(1, -1, 1), N(0, 3, 2)>
++            Sublattice <N(1, -1, 1), N(1, 2, 3)>
+             sage: sigma1.relative_quotient(rho)
+             1-d lattice, quotient
+-            of Sublattice <N(3, 0, 1), N(2, 1, 0), N(1, 0, 0)>
++            of Sublattice <N(-1, 1, 1), N(1, 2, 3), N(0, 1, 1)>
+             by Sublattice <N(1, 2, 3), N(0, 3, 2)>
+             sage: sigma1.relative_quotient(rho).gens()
+-            (N[0, -2, -1],)
++            (N[0, 1, 1],)
+             sage: sigma2.relative_quotient(rho).gens()
+-            (N[0, -1, -1],)
++            (N[-1, 0, -2],)
+         """
+         try: 
+             cached_values = self._relative_quotient

File trac_14291-rev2.patch

+# HG changeset patch
+# User Nathann Cohen <nathann.cohen@gmail.com>
+# Date 1363731554 -3600
+# Node ID c3b2b152c65064ab245e4ad7d9d108b66161e427
+# Parent  2e980ea8d962d06b92cb2170a5965cd65d6fefcf
+Orbits of tuples and sets -- documentation
+
+diff --git a/sage/groups/perm_gps/permgroup.py b/sage/groups/perm_gps/permgroup.py
+--- a/sage/groups/perm_gps/permgroup.py
++++ b/sage/groups/perm_gps/permgroup.py
+@@ -1068,15 +1068,17 @@
+         return [[self._domain_from_gap[x] for x in orbit] for orbit in
+                 self._gap_().Orbits(self._domain_gap()).sage()]
+ 
+-    supported_actions = ["OnPoints", "OnTuples", "OnSets", "OnPairs", "OnSetsSets", 
++    supported_actions = ["OnPoints", "OnTuples", "OnSets", "OnPairs", "OnSetsSets",
+                 "OnSetsDisjointSets", "OnSetsTuples", "OnTuplesSets", "OnTuplesTuples"]
+ 
+     @cached_method
+     def orbit(self, point, action = "OnPoints"):
+         """
+-        Return the orbit of a point under the group action in the list
+-        `self.supported_actions`. 
+-        These are taken from `http://www.gap-system.org/Manuals/doc/ref/chap41.html`_. 
++        Return the orbit of a point under a group action.
++
++        All actions available through this method can be obtained from
++        `self.supported_actions`. They are taken from GAP's list
++        `http://www.gap-system.org/Manuals/doc/ref/chap41.html`_.
+ 
+         INPUT:
+ 
+@@ -1085,7 +1087,7 @@
+           members must be sorted w.r.t. to the default order on them.
+ 
+         - ``action`` (string) -- if ``point`` is a tuple (of tuples) of points, this
+-          variable describes how the group is acting. The list of possibilites is 
++          variable describes how the group is acting. The list of possibilites is
+           is given by  `self.supported_actions`.
+           It is set to ``"OnPoints"`` by default. See below for examples.
+ 
+@@ -1111,7 +1113,7 @@
+ 
+             sage: S3.orbit((1,2), action = "OnTuples")
+             [[1, 2], [2, 3], [2, 1], [3, 1], [1, 3], [3, 2]]
+-        
++
+         Action of `S_4` on sets of disjoint sets::
+ 
+             sage: S4 = groups.permutation.Symmetric(4)
+@@ -1137,7 +1139,7 @@
+             else:
+                 points = [[self._domain_to_gap[x] for x in p] for p in point]
+                 orbits = self._gap_().Orbit(points, action).sage()
+-                return [[[self._domain_from_gap[x] for x in p] for p in o] 
++                return [[[self._domain_from_gap[x] for x in p] for p in o]
+                         for o in orbits]
+ 
+         else:
+@@ -1147,27 +1149,31 @@
+     def action(self, domain, action = "OnPoints"):
+         """
+         Return the permutation group induced by self acting on domain.
+-        
++
++        All actions available through this method can be obtained from
++        `self.supported_actions`. They are taken from GAP's list
++        `http://www.gap-system.org/Manuals/doc/ref/chap41.html`_.
++
+         INPUT:
+ 
+         - ``domain`` -- the list of things for which GAP knows how to compute
+           the action of the permutation group. For instance it can be obtained by
+-          calling :meth:`orbit`. 
+-
+-        - ``action`` (string) -- the action on domain. Need not be limited to 
++          calling :meth:`orbit`.
++
++        - ``action`` (string) -- the action on domain. Need not be limited to
+           `self.supported_actions`.
+           It is set to ``"OnPoints"`` by default. See below for examples.
+ 
+-        EXAMPLES::
+-
+-            Action of `S_5` on 2-subsets::
++        EXAMPLES:
++
++        Action of `S_5` on 2-subsets::
+ 
+             sage: S5 = groups.permutation.Symmetric(5)
+             sage: o10 = S5.orbit((1,2), action = "OnSets")
+             sage: S5_10 = S5.action(o10, action = "OnSets"); S5_10
+             Permutation Group with generators [(2,4)(6,9)(7,10), (1,2,3,5,7)(4,6,8,9,10)]
+-            
+-            Non-faithful action of `S_4` on sets of disjoint sets::
++
++        Non-faithful action of `S_4` on sets of disjoint sets::
+ 
+             sage: S4 = groups.permutation.Symmetric(4)
+             sage: o3 = S4.orbit(((1,2),(3,4)), action = "OnSetsDisjointSets")

File trac_14291.patch

+# HG changeset patch
+# User Nathann Cohen <nathann.cohen@gmail.com>
+# Date 1363519490 -3600
+# Node ID 884c704285a3d36daabcf5a4bfb64b3270defe46
+# Parent  a706b13de29b1153214c78d11f94b2c30090c88d
+Orbits of tuples and sets
+
+diff --git a/sage/groups/perm_gps/permgroup.py b/sage/groups/perm_gps/permgroup.py
+--- a/sage/groups/perm_gps/permgroup.py
++++ b/sage/groups/perm_gps/permgroup.py
+@@ -1067,9 +1067,20 @@
+                 self._gap_().Orbits(self._domain_gap()).sage()]
+ 
+     @cached_method
+-    def orbit(self, point):
++    def orbit(self, point, action = "OnPoints"):
+         """
+-        Return the orbit of the given point under the group action.
++        Return the orbit of a point (or set, or tuple) under the group action.
++
++        INPUT:
++
++        - ``point`` -- can be a point or a tuple of points, depending on the
++          action to be considered.
++
++        - ``action`` (string) -- when ``point`` is a tuple of points, this
++          variable defines whether the group is to be considered as acting on
++          tuples (``action="ontuples"``) or acting on sets
++          (``action="onsets"``). It is set to ``"onpoints"`` by default. See
++          below for examples.
+ 
+         EXAMPLES::
+ 
+@@ -1077,37 +1088,61 @@
+             sage: G.orbit(3)
+             [3, 4, 1]
+             sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]])
+-            sage: G.orbit(3)                                                 
++            sage: G.orbit(3)
+             [3, 4, 10, 1, 2]
+-
+             sage: G = PermutationGroup([ [('c','d')], [('a','c')] ])
+             sage: G.orbit('a')
+             ['a', 'c', 'd']
+-        """ 
+-        point = self._domain_to_gap[point]
+-        return [self._domain_from_gap[x] for x in self._gap_().Orbit(point).sage()]
+-    
++
++        Action of `S_3` on sets::
++
++            sage: S3 = groups.permutation.Symmetric(3)
++            sage: S3.orbit((1,2), action = "OnSets")
++            [[1, 2], [2, 3], [1, 3]]
++
++        On tuples::
++
++            sage: S3.orbit((1,2), action = "OnTuples")
++            [[1, 2], [2, 3], [2, 1], [3, 1], [1, 3], [3, 2]]
++        """
++        if action == "OnPoints":
++            try:
++                point = self._domain_to_gap[point]
++            except KeyError:
++                raise ValueError("The point given as argument does not seem to "+
++                                 "exist. If you want to compute an action on sets "+
++                                 "of tuples you *must* define the 'action' "+
++                                 "argument explicitly.")
++            return [self._domain_from_gap[x] for x in self._gap_().Orbit(point).sage()]
++
++        elif action in ["OnTuples", "OnSets"]:
++            points = [self._domain_to_gap[x] for x in point]
++            orbits = self._gap_().Orbit(points, action).sage()
++            return [[self._domain_from_gap[x] for x in o] for o in orbits]
++        else:
++            raise ValueError("'action' can only take values among 'OnPoints', 'OnTuples' or 'OnSets'.")
++
+     def transversals(self, point):
+         """
+-        If G is a permutation group acting on the set `X = \{1, 2, ...., n\}` 
+-        and H is the stabilizer subgroup of <integer>, a right 
+-        (respectively left) transversal is a set containing exactly 
+-        one element from each right (respectively left) coset of H. This 
+-        method returns a right transversal of ``self`` by the stabilizer 
++        If G is a permutation group acting on the set `X = \{1, 2, ...., n\}`
++        and H is the stabilizer subgroup of <integer>, a right
++        (respectively left) transversal is a set containing exactly
++        one element from each right (respectively left) coset of H. This
++        method returns a right transversal of ``self`` by the stabilizer
+         of ``self`` on <integer> position.
+ 
+         EXAMPLES::
+ 
+-            sage: G = PermutationGroup([ [(3,4)], [(1,3)] ])           
++            sage: G = PermutationGroup([ [(3,4)], [(1,3)] ])
+             sage: G.transversals(1)
+             [(), (1,3,4), (1,4,3)]
+             sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]])
+-            sage: G.transversals(1)                                    
++            sage: G.transversals(1)
+             [(), (1,2)(3,4), (1,3,2,10,4), (1,4,2,10,3), (1,10,4,3,2)]
+ 
+             sage: G = PermutationGroup([ [('c','d')], [('a','c')] ])
+             sage: G.transversals('a')
+-            [(), ('a','c','d'), ('a','d','c')]            
++            [(), ('a','c','d'), ('a','d','c')]
+         """
+         G = self._gap_()
+         return [self(G.RepresentativeAction(self._domain_to_gap[point], self._domain_to_gap[i]))
+@@ -1128,7 +1163,7 @@
+             sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]])
+             sage: G.stabilizer(10)
+             Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4,10)]) generated by [(2,3,4), (1,2)(3,4)]
+-            sage: G.stabilizer(1) 
++            sage: G.stabilizer(1)
+             Subgroup of (Permutation Group with generators [(1,2)(3,4), (1,2,3,4,10)]) generated by [(2,3)(4,10), (2,10,4)]
+             sage: G = PermutationGroup([[(2,3,4)],[(6,7)]])
+             sage: G.stabilizer(1)

File trac_14319.patch

+# HG changeset patch
+# User Nathann Cohen <nathann.cohen@gmail.com>
+# Date 1363778759 -3600
+# Node ID 8da8ff917556464499eecade3c96c492a1697e0b
+# Parent  5ed65b2c5b5f06692f6b1c9d0e3df2014b740263
+Graph Automorphism group with labeled vertices
+
+diff --git a/sage/geometry/fan_isomorphism.py b/sage/geometry/fan_isomorphism.py
+--- a/sage/geometry/fan_isomorphism.py
++++ b/sage/geometry/fan_isomorphism.py
+@@ -122,7 +122,9 @@
+         for cone in fan2.generating_cones() )
+ 
+     # iterate over all graph isomorphisms graph1 -> graph2
+-    for perm in graph2.automorphism_group(edge_labels=True):
++    g2 = graph2.relabel({v:(i if i!=0 else graph2.order()) for i,v in enumerate(graph2.vertices())}, inplace = False)
++
++    for perm in g2.automorphism_group(edge_labels=True):
+         # find a candidate m that maps max_cone to the graph image cone
+         image_ray_indices = [ perm(graph_iso[r]+1)-1 for r in fan1_pivot_rays ]
+         fan2_basis = fan2.rays(image_ray_indices) + fan2.virtual_rays()
+diff --git a/sage/geometry/polyhedron/base.py b/sage/geometry/polyhedron/base.py
+--- a/sage/geometry/polyhedron/base.py
++++ b/sage/geometry/polyhedron/base.py
+@@ -3815,16 +3815,9 @@
+         for edge in self.vertex_graph().edges():
+             i = edge[0]
+             j = edge[1]
+-            G.add_edge(i, j, (self.Vrepresentation(i).type(), self.Vrepresentation(j).type()) )
+-
+-        group, node_dict = G.automorphism_group(edge_labels=True, translation=True)
+-
+-        # Relabel the permutation group
+-        perm_to_vertex = dict( (i,v+1) for v,i in node_dict.items() )
+-        group = PermutationGroup([ [ tuple([ perm_to_vertex[i] for i in cycle ])
+-                                     for cycle in generator.cycle_tuples() ]
+-                                   for generator in group.gens() ])
+-
++            G.add_edge(i+1, j+1, (self.Vrepresentation(i).type(), self.Vrepresentation(j).type()) )
++
++        group = G.automorphism_group(edge_labels=True)
+         self._combinatorial_automorphism_group = group
+         return group
+ 
+@@ -4075,16 +4068,9 @@
+                 v_i = v_list[i]
+                 v_j = v_list[j]
+                 c_ij = rational_approximation( v_i * Qinv * v_j )
+-                G.add_edge(i,j, edge_label(i,j,c_ij))
+-
+-        group, node_dict = G.automorphism_group(edge_labels=True, translation=True)
+-
+-        # Relabel the permutation group
+-        perm_to_vertex = dict( (i,v+1) for v,i in node_dict.items() )
+-        group = PermutationGroup([ [ tuple([ perm_to_vertex[i] for i in cycle ])
+-                                     for cycle in generator.cycle_tuples() ]
+-                                   for generator in group.gens() ])
+-
++                G.add_edge(i+1,j+1, edge_label(i,j,c_ij))
++
++        group = G.automorphism_group(edge_labels=True)
+         self._restricted_automorphism_group = group
+         return group
+ 
+diff --git a/sage/geometry/triangulation/point_configuration.py b/sage/geometry/triangulation/point_configuration.py
+--- a/sage/geometry/triangulation/point_configuration.py
++++ b/sage/geometry/triangulation/point_configuration.py
+@@ -1149,16 +1149,9 @@
+             for j in range(i+1,len(v_list)):
+                 v_i = v_list[i]
+                 v_j = v_list[j]
+-                G.add_edge(i,j, v_i * Qinv * v_j)
++                G.add_edge(i+1,j+1, v_i * Qinv * v_j)
+ 
+-        group, node_dict = G.automorphism_group(edge_labels=True, translation=True)
+-
+-        # Relabel the permutation group
+-        perm_to_vertex = dict( (i,v+1) for v,i in node_dict.items() )
+-        group = PermutationGroup([ [ tuple([ perm_to_vertex[i] for i in cycle ])
+-                                     for cycle in generator.cycle_tuples() ]
+-                                   for generator in group.gens() ])
+-
++        group = G.automorphism_group(edge_labels=True)
+         self._restricted_automorphism_group = group
+         return group
+ 
+diff --git a/sage/graphs/generic_graph.py b/sage/graphs/generic_graph.py
+--- a/sage/graphs/generic_graph.py
++++ b/sage/graphs/generic_graph.py
+@@ -16181,62 +16181,60 @@
+         result = coarsest_equitable_refinement(CG, partition, G._directed)
+         return [[perm_from[b] for b in cell] for cell in result]
+ 
+-    def automorphism_group(self, partition=None, translation=False,
+-                           verbosity=0, edge_labels=False, order=False,
++    def automorphism_group(self, partition=None, verbosity=0,
++                           edge_labels=False, order=False,
+                            return_group=True, orbits=False):
+         """
+         Returns the largest subgroup of the automorphism group of the
+         (di)graph whose orbit partition is finer than the partition given.
+         If no partition is given, the unit partition is used and the entire
+         automorphism group is given.
+-        
+-        INPUT:
+-        
+-        
+-        -  ``translation`` - if True, then output includes a
+-           dictionary translating from keys == vertices to entries == elements
+-           of 1,2,...,n (since permutation groups can currently only act on
+-           positive integers).
+-        
++
++        INPUT:
++
+         -  ``partition`` - default is the unit partition,
+            otherwise computes the subgroup of the full automorphism group
+            respecting the partition.
+-        
++
+         -  ``edge_labels`` - default False, otherwise allows
+            only permutations respecting edge labels.
+-        
++
+         -  ``order`` - (default False) if True, compute the
+            order of the automorphism group
+-        
++
+         -  ``return_group`` - default True
+-        
++
+         -  ``orbits`` - returns the orbits of the group acting
+            on the vertices of the graph
+-        
+-        
+-        OUTPUT: The order of the output is group, translation, order,
+-        orbits. However, there are options to turn each of these on or
+-        off.
+-        
++
++        .. WARNING::
++
++            Since :trac:`14319` the domain of the automorphism group is equal to
++            the graph's vertex set, and the ``translation`` argument has become
++            useless.
++
++        OUTPUT: The order of the output is group, order, orbits. However, there
++        are options to turn each of these on or off.
++
+         EXAMPLES: Graphs::
+-        
++
+             sage: graphs_query = GraphQuery(display_cols=['graph6'],num_vertices=4)
+             sage: L = graphs_query.get_graphs_list()
+             sage: graphs_list.show_graphs(L)
+             sage: for g in L:
+             ...    G = g.automorphism_group()
+             ...    G.order(), G.gens()
+-            (24, [(2,3), (1,2), (1,4)])
+-            (4, [(2,3), (1,4)])
++            (24, [(2,3), (1,2), (0,1)])
++            (4, [(2,3), (0,1)])
+             (2, [(1,2)])
+-            (8, [(1,2), (1,4)(2,3)])
+-            (6, [(1,2), (1,4)])
++            (8, [(1,2), (0,1)(2,3)])
++            (6, [(1,2), (0,1)])
+             (6, [(2,3), (1,2)])
+-            (2, [(1,4)(2,3)])
++            (2, [(0,1)(2,3)])
+             (2, [(1,2)])
+-            (8, [(2,3), (1,3)(2,4), (1,4)])
+-            (4, [(2,3), (1,4)])
+-            (24, [(2,3), (1,2), (1,4)])
++            (8, [(2,3), (0,1), (0,2)(1,3)])
++            (4, [(2,3), (0,1)])
++            (24, [(2,3), (1,2), (0,1)])
+             sage: C = graphs.CubeGraph(4)
+             sage: G = C.automorphism_group()
+             sage: M = G.character_table() # random order of rows, thus abs() below
+@@ -16244,9 +16242,9 @@
+             712483534798848
+             sage: G.order()
+             384
+-        
+-        ::
+-        
++
++        ::
++
+             sage: D = graphs.DodecahedralGraph()
+             sage: G = D.automorphism_group()
+             sage: A5 = AlternatingGroup(5)
+@@ -16254,58 +16252,56 @@
+             sage: H = A5.direct_product(Z2)[0] #see documentation for direct_product to explain the [0]
+             sage: G.is_isomorphic(H)
+             True
+-        
++
+         Multigraphs::
+-        
++
+             sage: G = Graph(multiedges=True,sparse=True)
+             sage: G.add_edge(('a', 'b'))
+             sage: G.add_edge(('a', 'b'))
+             sage: G.add_edge(('a', 'b'))
+             sage: G.automorphism_group()
+-            Permutation Group with generators [(1,2)]
+-        
++            Permutation Group with generators [('a','b')]
++
+         Digraphs::
+-        
++
+             sage: D = DiGraph( { 0:[1], 1:[2], 2:[3], 3:[4], 4:[0] } )
+             sage: D.automorphism_group()
+-            Permutation Group with generators [(1,2,3,4,5)]
+-        
++            Permutation Group with generators [(0,1,2,3,4)]
++
+         Edge labeled graphs::
+-        
++
+             sage: G = Graph(sparse=True)
+             sage: G.add_edges( [(0,1,'a'),(1,2,'b'),(2,3,'c'),(3,4,'b'),(4,0,'a')] )
+             sage: G.automorphism_group(edge_labels=True)
+             Permutation Group with generators [(1,4)(2,3)]
+-        
+-        ::
+-        
++
++        ::
++
+             sage: G = Graph({0 : {1 : 7}})
+-            sage: G.automorphism_group(translation=True, edge_labels=True)
+-            (Permutation Group with generators [(1,2)], {0: 2, 1: 1})
++            sage: G.automorphism_group(edge_labels=True)
++            Permutation Group with generators [(0,1)]
+ 
+             sage: foo = Graph(sparse=True)
+             sage: bar = Graph(implementation='c_graph',sparse=True)
+             sage: foo.add_edges([(0,1,1),(1,2,2), (2,3,3)])
+             sage: bar.add_edges([(0,1,1),(1,2,2), (2,3,3)])
+-            sage: foo.automorphism_group(translation=True, edge_labels=True)
+-            (Permutation Group with generators [()], {0: 4, 1: 1, 2: 2, 3: 3})
+-            sage: foo.automorphism_group(translation=True)
+-            (Permutation Group with generators [(1,2)(3,4)], {0: 4, 1: 1, 2: 2, 3: 3})
+-            sage: bar.automorphism_group(translation=True, edge_labels=True)
+-            (Permutation Group with generators [()], {0: 4, 1: 1, 2: 2, 3: 3})
+-            sage: bar.automorphism_group(translation=True)
+-            (Permutation Group with generators [(1,2)(3,4)], {0: 4, 1: 1, 2: 2, 3: 3})
++            sage: foo.automorphism_group(edge_labels=True)
++            Permutation Group with generators [()]
++            sage: foo.automorphism_group()
++            Permutation Group with generators [(0,3)(1,2)]
++            sage: bar.automorphism_group(edge_labels=True)
++            Permutation Group with generators [()]
+ 
+         You can also ask for just the order of the group::
+-        
++
+             sage: G = graphs.PetersenGraph()
+             sage: G.automorphism_group(return_group=False, order=True)
+             120
+-        
++
+         Or, just the orbits (note that each graph here is vertex transitive)
+-        
+-        ::
+-        
++
++        ::
++
+             sage: G = graphs.PetersenGraph()
+             sage: G.automorphism_group(return_group=False, orbits=True)
+             [[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]]
+@@ -16326,8 +16322,25 @@
+             ...
+             KeyError: 6
+ 
+-        """
+-        from sage.groups.perm_gps.partn_ref.refinement_graphs import perm_group_elt, search_tree
++        Labeled automorphism group::
++
++            sage: digraphs.DeBruijn(3,2).automorphism_group()
++            Permutation Group with generators [('01','02')('10','20')('11','22')('12','21'), ('00','11')('01','10')('02','12')('20','21')]
++            sage: d = digraphs.DeBruijn(3,2)
++            sage: d.allow_multiple_edges(True)
++            sage: d.add_edge(d.edges()[0])
++            sage: d.automorphism_group()
++            Permutation Group with generators [('01','02')('10','20')('11','22')('12','21')]
++
++        The labeling is correct::
++
++            sage: g = graphs.PetersenGraph()
++            sage: ag = g.automorphism_group()
++            sage: for u,v in g.edges(labels = False):
++            ...       if len(ag.orbit((u,v),action="OnPairs")) != 30:
++            ...           print "ARggggggggggggg !!!"
++        """
++        from sage.groups.perm_gps.partn_ref.refinement_graphs import search_tree
+         from sage.groups.perm_gps.permgroup import PermutationGroup
+         dig = (self._directed or self.has_loops())
+         if partition is None:
+@@ -16394,7 +16407,8 @@
+                 HB.add_edge(u,v,None,self._directed)
+             GC = HB._cg
+             partition = [[G_to[v] for v in cell] for cell in partition]
+-            if translation:
++
++            if return_group:
+                 A = search_tree(GC, partition, dict_rep=True, lab=False, dig=dig, verbosity=verbosity, order=order)
+                 if order:
+                     a,b,c = A
+@@ -16408,14 +16422,22 @@
+                 a = search_tree(GC, partition, dict_rep=False, lab=False, dig=dig, verbosity=verbosity, order=order)
+                 if order:
+                     a,c = a
++
+         output = []
+         if return_group:
+             if len(a) != 0:
+-                output.append(PermutationGroup([perm_group_elt(aa) for aa in a]))
++                # We translate the integer permutations into a collection of
++                # cycles.
++                from sage.combinat.permutation import Permutation
++                gens = [Permutation([x+1 for x in aa]).to_cycles() for aa in a]
++
++                # We relabel the cycles using the vertices' names instead of integers
++                n = self.order()
++                int_to_vertex = {((i+1) if i != n else 1):v for v,i in b.iteritems()}
++                gens = [ [ tuple([int_to_vertex[i] for i in cycle]) for cycle in gen] for gen in gens]
++                output.append(PermutationGroup(gens = gens, domain = int_to_vertex.values()))
+             else:
+                 output.append(PermutationGroup([[]]))
+-        if translation:
+-            output.append(b)
+         if order:
+             output.append(c)
+         if orbits:
+diff --git a/sage/graphs/graph.py b/sage/graphs/graph.py
+--- a/sage/graphs/graph.py
++++ b/sage/graphs/graph.py
+@@ -2436,9 +2436,10 @@
+         if self.size() == 0:
+             return True
+ 
+-        A,T = self.automorphism_group(translation=True)
++        A = self.automorphism_group()
+         e = self.edge_iterator(labels=False).next()
+-        e = [T[e[0]], T[e[1]]]
++        e = [A._domain_to_gap[e[0]], A._domain_to_gap[e[1]]]
++
+         return gap("OrbitLength("+str(A._gap_())+",Set(" + str(e) + "),OnSets);") == self.size()
+ 
+     def is_arc_transitive(self):
+@@ -2477,9 +2478,10 @@
+         if self.size() == 0:
+             return True
+ 
+-        A,T = self.automorphism_group(translation=True)
++        A = self.automorphism_group()
+         e = self.edge_iterator(labels=False).next()
+-        e = [T[e[0]], T[e[1]]]
++        e = [A._domain_to_gap[e[0]], A._domain_to_gap[e[1]]]
++
+         return gap("OrbitLength("+str(A._gap_())+",Set(" + str(e) + "),OnTuples);") == 2*self.size()
+ 
+     def is_half_transitive(self):
+diff --git a/sage/groups/perm_gps/partn_ref/refinement_graphs.pyx b/sage/groups/perm_gps/partn_ref/refinement_graphs.pyx
+--- a/sage/groups/perm_gps/partn_ref/refinement_graphs.pyx
++++ b/sage/groups/perm_gps/partn_ref/refinement_graphs.pyx
+@@ -912,35 +912,6 @@
+                     i[j] = 0
+         return l
+ 
+-def perm_group_elt(lperm):
+-    """
+-    Given a list permutation of the set 0, 1, ..., n-1, returns the
+-    corresponding PermutationGroupElement where we take 0 = n.
+-    
+-    EXAMPLE::
+-    
+-        sage: from sage.groups.perm_gps.partn_ref.refinement_graphs import perm_group_elt
+-        sage: perm_group_elt([0,2,1])
+-        (1,2)
+-        sage: perm_group_elt([1,2,0])
+-        (1,2,3)
+-    """
+-    from sage.groups.perm_gps.permgroup_named import SymmetricGroup
+-    n = len(lperm)
+-    S = SymmetricGroup(n)
+-    Part = orbit_partition(lperm, list_perm=True)
+-    gens = []
+-    for z in Part:
+-        if len(z) > 1:
+-            if 0 in z:
+-                zed = z.index(0)
+-                generator = z[:zed] + [n] + z[zed+1:]
+-                gens.append(tuple(generator))
+-            else:
+-                gens.append(tuple(z))
+-    E = S(gens)
+-    return E
+-
+ def coarsest_equitable_refinement(CGraph G, list partition, bint directed):
+     """
+     Returns the coarsest equitable refinement of ``partition`` for ``G``.
+diff --git a/sage/groups/perm_gps/permgroup.py b/sage/groups/perm_gps/permgroup.py
+--- a/sage/groups/perm_gps/permgroup.py
++++ b/sage/groups/perm_gps/permgroup.py
+@@ -2696,7 +2696,8 @@
+         Now the full blocks::
+ 
+             sage: ag.blocks_all(representatives = False)
+-            [[[1, 16], [8, 17], [14, 19], [2, 12], [7, 18], [5, 10], [15, 20], [4, 9], [3, 13], [6, 11]]]
++            [[[1, 16], [2, 17], [15, 20], [9, 18], [6, 11], [3, 13], [8, 19], [4, 14], [5, 10], [7, 12]]]
++
+         """
+         ag = self._gap_()
+         if representatives:
+diff --git a/sage/groups/perm_gps/permgroup_element.pyx b/sage/groups/perm_gps/permgroup_element.pyx
+--- a/sage/groups/perm_gps/permgroup_element.pyx
++++ b/sage/groups/perm_gps/permgroup_element.pyx
+@@ -104,8 +104,8 @@
+     ``domain`` of the permutation group.
+ 
+     This is function is used when unpickling permutation groups and
+-    their elements.  
+-    
++    their elements.
++
+     EXAMPLES::
+ 
+         sage: from sage.groups.perm_gps.permgroup_element import make_permgroup_element_v2
+@@ -996,17 +996,11 @@
+ 
+     def dict(self):
+         """
+-        Returns list of the images of the integers from 1 to n under this
+-        permutation as a list of Python ints.
+-        
+-        .. note::
++        Returns a dictionary associating each element of the domain with its
++        image.
+ 
+-           :meth:`.list` returns a zero-indexed list. :meth:`.dict`
+-           return the actual mapping of the permutation, which will be
+-           indexed starting with 1.
+-        
+         EXAMPLES::
+-        
++
+             sage: G = SymmetricGroup(4)
+             sage: g = G((1,2,3,4)); g
+             (1,2,3,4)
+@@ -1020,12 +1014,10 @@
+             {1: 2, 2: 1, 3: 3, 4: 4}
+         """
+         from_gap = self._parent._domain_from_gap
++        to_gap = self._parent._domain_to_gap
+         cdef int i
+-        u = {}
+-        for i from 0 <= i < self.n:
+-            u[i+1] = from_gap[self.perm[i]+1]
+-        return u
+-            
++        return {e:from_gap[self.perm[i-1]+1] for e,i in to_gap.iteritems()}
++
+     def order(self):
+         """
+         Return the order of this group element, which is the smallest
+diff --git a/sage/homology/simplicial_complex.py b/sage/homology/simplicial_complex.py
+--- a/sage/homology/simplicial_complex.py
++++ b/sage/homology/simplicial_complex.py
+@@ -3103,7 +3103,7 @@
+ 
+         return isisom,tr
+ 
+-    def automorphism_group(self,translation=False):
++    def automorphism_group(self):
+         r"""
+         Returns the automorphism group of the simplicial complex
+ 
+@@ -3111,22 +3111,11 @@
+         vertices and facets of the simplicial complex, and computing
+         its automorphism group.
+ 
+-        INPUT:
+-
+-        - ``translation`` (boolean, default: ``False``) whether to return
+-          a dictionary associating the vertices of the simplicial
+-          complex to elements of the set on which the group acts
+-
+-        OUTPUT:
+-
+-        - a permutation group if ``translation`` is ``False``
+-        - a permutation group and a dictionary if ``translation`` is ``True``
+-
+-        .. NOTE::
+-
+-            The group is returned as a permutation group acting on
+-            integers from ``1`` to the number of vertices. The bijection
+-            with vertices is provided if ``translation`` is ``True``.
++        .. WARNING::
++
++            Since :trac:`14319` the domain of the automorphism group is equal to
++            the graph's vertex set, and the ``translation`` argument has become
++            useless.
+ 
+         EXAMPLES::
+ 
+@@ -3141,29 +3130,25 @@
+             sage: Z = SimplicialComplex([[1,2],[2,3,'a']])
+             sage: Z.automorphism_group().is_isomorphic(CyclicPermutationGroup(2))
+             True
+-            sage: group, dict = Z.automorphism_group(translation=True)
+-            sage: Set([dict[s] for s in Z.vertices()])
+-            {1, 2, 3, 4}
++            sage: group = Z.automorphism_group()
++            sage: group.domain()
++            {1, 2, 3, 'a'}
+         """
+         from sage.groups.perm_gps.permgroup import PermutationGroup
+-        from sage.combinat.permutation import Permutation
++
+         G = Graph()
+         G.add_vertices(self.vertices())
+         G.add_edges((f.tuple(),v) for f in self.facets() for v in f)
+-        groupe, simpl_to_gap = G.automorphism_group(translation=True,
+-                                           partition=[list(self.vertices()),
+-                                                      [f.tuple() for f in self.facets()]])
+-        gap_to_simpl = {x_gap:x for x,x_gap in simpl_to_gap.iteritems()} # reverse dictionary
+-        gap_to_range = {simpl_to_gap[x]:(i+1) for i,x in enumerate(self.vertices())}
+-        permgroup = PermutationGroup([
+-                    Permutation([tuple([gap_to_range[x] for x in c])
+-                                 for c in g.cycle_tuples()
+-                                 if not isinstance(gap_to_simpl[c[0]],tuple)])
+-                    for g in groupe.gens()])
+-        if translation:
+-            return permgroup, {f:gap_to_range[simpl_to_gap[f]] for f in self.vertices()}
+-        else:
+-            return permgroup
++        groupe = G.automorphism_group(partition=[list(self.vertices()),
++                                                 [f.tuple() for f in self.facets()]])
++
++
++        gens = [ [tuple(c) for c in g.cycle_tuples() if not isinstance(c[0],tuple)]
++                 for g in groupe.gens()]
++
++        permgroup = PermutationGroup(gens = gens, domain = self.vertices())
++
++        return permgroup
+ 
+     def _Hom_(self, other, category=None):
+         """

File trac_14319_fix_fan_isomorphism.patch

+# HG changeset patch
+# Parent 9ad78e8eedf80ad30c83f5942f07a600b7468c77
+
+Fix bug in fan isomorphism check and improve doctesting
+
+diff --git a/sage/geometry/fan.py b/sage/geometry/fan.py
+--- a/sage/geometry/fan.py
++++ b/sage/geometry/fan.py
+@@ -2554,7 +2554,7 @@
+ 
+         EXAMPLES::
+ 
+-            sage: rays = ((1, 1), (0, 1), (-1, -1), (1, 0))
++            sage: rays = ((1, 1), (0, 1), (-1, -1), (3, 1))
+             sage: cones = [(0,1), (1,2), (2,3), (3,0)]
+             sage: fan1 = Fan(cones, rays)
+             sage: m = matrix([[-2,3],[1,-1]])
+diff --git a/sage/geometry/fan_isomorphism.py b/sage/geometry/fan_isomorphism.py
+--- a/sage/geometry/fan_isomorphism.py
++++ b/sage/geometry/fan_isomorphism.py
+@@ -16,6 +16,7 @@
+ 
+ from sage.rings.all import ZZ
+ from sage.matrix.constructor import column_matrix, matrix
++from sage.geometry.cone import Cone
+ 
+ 
+ 
+@@ -76,7 +77,8 @@
+ 
+     OUTPUT:
+ 
+-    Yields the fan isomorphisms as matrices.
++    Yields the fan isomorphisms as matrices acting from the right on
++    rays.
+ 
+     EXAMPLES::
+ 
+@@ -84,8 +86,8 @@
+         sage: from sage.geometry.fan_isomorphism import fan_isomorphism_generator
+         sage: tuple( fan_isomorphism_generator(fan, fan) )
+         (
+-        [1 0]  [ 1  0]  [0 1]  [ 0  1]  [-1 -1]  [-1 -1]
+-        [0 1], [-1 -1], [1 0], [-1 -1], [ 1  0], [ 0  1]
++        [1 0]  [0 1]  [ 1  0]  [-1 -1]  [ 0  1]  [-1 -1]
++        [0 1], [1 0], [-1 -1], [ 1  0], [-1 -1], [ 0  1]
+         )
+ 
+         sage: m1 = matrix([(1, 0), (0, -5), (-3, 4)])
+@@ -100,6 +102,41 @@
+         [18  1 -5]
+         [ 4  0 -1]
+         [ 5  0 -1]
++
++        sage: m0 = identity_matrix(ZZ, 2)
++        sage: m1 = matrix([(1, 0), (0, -5), (-3, 4)])
++        sage: m2 = matrix([(3, 0), (1, 0), (-2, 1)])
++        sage: m1.elementary_divisors() == m2.elementary_divisors() == [1,1,0]
++        True
++        sage: fan0 = Fan([Cone([m0*vector([1,0]), m0*vector([1,1])]),
++        ...               Cone([m0*vector([1,1]), m0*vector([0,1])])])
++        sage: fan1 = Fan([Cone([m1*vector([1,0]), m1*vector([1,1])]),
++        ...               Cone([m1*vector([1,1]), m1*vector([0,1])])])
++        sage: fan2 = Fan([Cone([m2*vector([1,0]), m2*vector([1,1])]),
++        ...               Cone([m2*vector([1,1]), m2*vector([0,1])])])
++        sage: tuple(fan_isomorphism_generator(fan0, fan0))
++        (
++        [1 0]  [0 1]
++        [0 1], [1 0]
++        )
++        sage: tuple(fan_isomorphism_generator(fan1, fan1))
++        (
++        [1 0 0]  [ -3 -20  28]
++        [0 1 0]  [ -1  -4   7]
++        [0 0 1], [ -1  -5   8]
++        )
++        sage: tuple(fan_isomorphism_generator(fan1, fan2))
++        (
++        [18  1 -5]  [ 6 -3  7]
++        [ 4  0 -1]  [ 1 -1  2]
++        [ 5  0 -1], [ 2 -1  2]
++        )
++        sage: tuple(fan_isomorphism_generator(fan2, fan1))                  
++        (
++        [ 0 -1  1]  [ 0 -1  1]
++        [ 1 -7  2]  [ 2 -2 -5]
++        [ 0 -5  4], [ 1  0 -3]
++        )
+     """
+     if not fan_isomorphic_necessary_conditions(fan1, fan2):
+         return
+@@ -109,36 +146,35 @@
+     graph_iso = graph1.is_isomorphic(graph2, edge_labels=True, certify=True)
+     if not graph_iso[0]:
+         return
+-    graph_iso = dict( (k.ray(0), v.ambient_ray_indices()[0])
+-                      for k,v in graph_iso[1].iteritems() )
++    graph_iso = graph_iso[1]
+ 
++    # Pick a basis of rays in fan1
+     max_cone = fan1(fan1.dim())[0]
+     fan1_pivot_rays = max_cone.rays()
+     fan1_basis = fan1_pivot_rays + fan1.virtual_rays()   # A QQ-basis for N_1
++    fan1_pivot_cones = [ fan1.embed(Cone([r])) for r in fan1_pivot_rays ]
+ 
+-    # The fan2 cones as set(set(integers))
++    # The fan2 cones as set(set(ray indices))
+     fan2_cones = frozenset(
+         frozenset(cone.ambient_ray_indices())
+         for cone in fan2.generating_cones() )
+ 
+     # iterate over all graph isomorphisms graph1 -> graph2
+-    g2 = graph2.relabel({v:(i if i!=0 else graph2.order()) for i,v in enumerate(graph2.vertices())}, inplace = False)
+-
+-    for perm in g2.automorphism_group(edge_labels=True):
+-        # find a candidate m that maps max_cone to the graph image cone
+-        image_ray_indices = [ perm(graph_iso[r]+1)-1 for r in fan1_pivot_rays ]
+-        fan2_basis = fan2.rays(image_ray_indices) + fan2.virtual_rays()
++    for perm in graph2.automorphism_group(edge_labels=True):
++        # find a candidate m that maps fan1_basis to the image rays under the graph isomorphism
++        fan2_pivot_cones = [ perm(graph_iso[c]) for c in fan1_pivot_cones ]
++        fan2_pivot_rays = fan2.rays([ c.ambient_ray_indices()[0] for c in fan2_pivot_cones  ])
++        fan2_basis = fan2_pivot_rays + fan2.virtual_rays()
+         try:
+-            m = matrix(fan1_basis).solve_right(matrix(fan2_basis))
++            m = matrix(ZZ, fan1_basis).solve_right(matrix(ZZ, fan2_basis))
+             m = m.change_ring(ZZ)
+         except (ValueError, TypeError):
+             continue # no solution
+ 
+         # check that the candidate m lifts the vertex graph homomorphism
+-        graph_image_ray_indices = [ perm(graph_iso[r]+1)-1 for r in fan1.rays() ]
++        graph_image_ray_indices = [ perm(graph_iso[c]).ambient_ray_indices()[0] for c in fan1(1) ]
+         try:
+-            matrix_image_ray_indices = [ fan2.rays().index(fan1.ray(i)*m)
+-                                         for i in range(fan1.nrays()) ]
++            matrix_image_ray_indices = [ fan2.rays().index(r*m) for r in fan1.rays() ]
+         except ValueError:
+             continue
+         if graph_image_ray_indices != matrix_image_ray_indices:
+@@ -150,6 +186,7 @@
+                       for i in cone.ambient_ray_indices())
+             for cone in fan1.generating_cones() )
+         if image_cones == fan2_cones:
++            m.set_immutable()
+             yield m
+ 
+ 
+@@ -172,7 +209,7 @@
+ 
+     EXAMPLE::
+ 
+-        sage: rays = ((1, 1), (0, 1), (-1, -1), (1, 0))
++        sage: rays = ((1, 1), (0, 1), (-1, -1), (3, 1))
+         sage: cones = [(0,1), (1,2), (2,3), (3,0)]
+         sage: fan1 = Fan(cones, rays)
+ 

File trac_14353_factor_fan_morphism.patch

+# HG changeset patch
+# Parent 70f82cece4ff30ffc08838b736bc733a4ae420b8
+
+Factor a toric morphism into a surjective and generically injective morphism
+
+diff --git a/sage/geometry/fan_morphism.py b/sage/geometry/fan_morphism.py
+--- a/sage/geometry/fan_morphism.py
++++ b/sage/geometry/fan_morphism.py
+@@ -1686,3 +1686,95 @@
+                                         for cone in self.codomain_fan()),
+                     lattice=L, check=False)
+         return FanMorphism(m, self.domain_fan(), Sigma)
++
++    def factor(self):
++        r"""
++        Factor the fan morphism into a surjection and a generically
++        injective map.
++
++        OUTPUT:
++
++        Starting with a fan morphism $f$, this method returns a pair
++        $(f_1, f_2)$ of fan morphisms such that
++
++        * $f = f_1 \circ f_2$,
++
++        * $f_2$ is surjective, and
++
++        * $f_1$ is injective at a generic point of the domain (in
++          particular, on the maximal torus).
++
++        The intermediate fan (that is, the codomain fan of $f_1$) is
++        the image of the support of the domain fan (which is a cone)
++        intersected with the codomain fan of $f$, see
++        :meth:`~sage.geometry.fan.RationalPolyhedralFan.intersection`. The
++        map $f_2$ is the embedding of this intersection in the whole
++        codomain fan of $f$.
++
++        EXAMPLES::
++
++            sage: N = ToricLattice(3)
++            sage: n1 = N( 1,1,1)
++            sage: n2 = N( 0,1,1)
++            sage: n3 = N(-1,1,1)
++            sage: domain_fan = Fan([Cone([n1,n2]), Cone([n2,n3])])
++            sage: m = matrix([[0,1,3], [0,1,3]]).transpose()
++            sage: image_fan = Fan([Cone([(1,0), (0,1)])])
++            sage: fm = FanMorphism(m, domain_fan, image_fan)
++            sage: fm1, fm2 = fm.factor()
++
++            sage: fm2.is_surjective()
++            True
++            sage: fm1.is_injective()
++            True
++            sage: fm1 * fm2 == fm
++            True
++            sage: fm2.matrix() * fm1.matrix() == m
++            True
++
++            sage: fm.domain_fan() is fm2.domain_fan()
++            True
++            sage: fm.codomain_fan() is fm1.codomain_fan()                  
++            True
++            sage: fm2.codomain_fan() is fm1.domain_fan()
++            True
++
++        The second map need not be injective everywhere, for example
++        here ``fm1`` is injective on the maximal torus but not on the
++        divisor $z_1=0$ ::
++
++            sage: BlC2_patch = ToricVariety(Fan([Cone([(1,0),(1,1)])]))
++            sage: C2 = toric_varieties.A2()
++            sage: f = BlC2_patch.hom(identity_matrix(2), C2)
++            sage: fm1, fm2 = f.fan_morphism().factor()
++            sage: fm2.is_surjective()
++            True
++            sage: fm1.is_injective()
++            False
++            sage: f.as_polynomial_map()
++            Scheme morphism:
++              From: 2-d affine toric variety
++              To:   2-d affine toric variety
++              Defn: Defined on coordinates by sending [z0 : z1] to
++                    [z0*z1 : z1]
++        """
++        fan1 = self.domain_fan()
++        fan2 = self.codomain_fan()
++        # self.domain_fan() --fm1--> fan ---fm2--> self.codomain_fan()
++        D, U, V = self.matrix().smith_form()
++        Vinv = V.inverse().change_ring(ZZ)
++        rk = D.rank()
++        # m1 and m2 are the matrices defining m1 and m2
++        # self.matrix() == m1 * m2
++        m1 = (self.matrix()*V).submatrix(col=0, ncols=rk)
++        m2 = Vinv.submatrix(row=0, nrows=rk)
++        m2_inv = V.submatrix(col=0, ncols=rk)  # right inverse of m2
++        # construct the intermediate fan
++        support_img = Cone([self(r) for r in fan1.support().rays()])
++        fan_img = fan2.intersection(support_img)
++        fan = Fan([Cone([r*m2_inv for r in c.rays()])
++                   for c in fan_img.generating_cones()])
++        # construct the two fan morphisms
++        fm1 = FanMorphism(m1, fan1, fan)
++        fm2 = FanMorphism(m2, fan, fan2)
++        return fm2, fm1
+diff --git a/sage/schemes/toric/homset.py b/sage/schemes/toric/homset.py
+--- a/sage/schemes/toric/homset.py
++++ b/sage/schemes/toric/homset.py
+@@ -231,6 +231,28 @@
+         raise TypeError, "x must be a fan morphism or a list/tuple of polynomials"
+ 
+ 
++    def _an_element_(self):
++        """
++        Construct a sample morphism.
++
++        OUTPUT:
++
++        An element of the homset.
++
++        EXAMPLES::
++
++            sage: P2 = toric_varieties.P2()
++            sage: homset = P2.Hom(P2)
++            sage: homset.an_element()   # indirect doctest
++            Scheme endomorphism of 2-d CPR-Fano toric variety covered by 3 affine patches
++              Defn: Defined by sending Rational polyhedral fan in 2-d lattice N to
++                    Rational polyhedral fan in 2-d lattice N.
++        """
++        from sage.matrix.constructor import zero_matrix
++        zero = zero_matrix(self.domain().dimension_relative(), 
++                           self.codomain().dimension_relative())
++        return self(zero)
++
+ class SchemeHomset_points_toric_field(SchemeHomset_points):
+     """
+     Set of rational points of a toric variety.
+diff --git a/sage/schemes/toric/morphism.py b/sage/schemes/toric/morphism.py
+--- a/sage/schemes/toric/morphism.py
++++ b/sage/schemes/toric/morphism.py
+@@ -710,3 +710,114 @@
+                 polys[i] *= x**d
+         return SchemeMorphism_polynomial_toric_variety(self.parent(), polys)
+ 
++    def is_injective(self):
++        r"""
++        Check if ``self`` is injective.
++        
++        See
++        :meth:`~sage.geometry.fan_morphism.FanMorphism.is_injective`
++        for a description of the toric algorithm.
++               
++        OUTPUT:
++        
++        Boolean. Whether ``self`` is injective.
++
++        EXAMPLES::
++        
++            sage: X = toric_varieties.A(2)
++            sage: m = identity_matrix(2)
++            sage: f = X.hom(m, X)
++            sage: f.is_injective()
++            True
++            
++            sage: Y = ToricVariety(Fan([Cone([(1,0), (1,1)])]))
++            sage: f = Y.hom(m, X)
++            sage: f.is_injective()
++            False
++        """        
++        return self.fan_morphism().is_injective()
++        
++    def is_surjective(self):
++        r"""
++        Check if ``self`` is surjective.
++        
++        See
++        :meth:`~sage.geometry.fan_morphism.FanMorphism.is_surjective`
++        for a description of the toric algorithm.
++               
++        OUTPUT:
++        
++        Boolean. Whether ``self`` is surjective.
++
++        EXAMPLES::
++        
++            sage: X = toric_varieties.A(2)
++            sage: m = identity_matrix(2)
++            sage: f = X.hom(m, X)
++            sage: f.is_surjective()
++            True
++            
++            sage: Y = ToricVariety(Fan([Cone([(1,0), (1,1)])]))
++            sage: f = Y.hom(m, X)
++            sage: f.is_surjective()
++            False
++        """        
++        return self.fan_morphism().is_surjective()
++
++    def factor(self):
++        r"""
++        Factor into a surjection and a generically injective map.
++
++        See
++        :meth:`~sage.geometry.fan_morphism.FanMorphism.factor`
++        for a description of the toric algorithm.
++
++        OUTPUT:
++
++        Starting with a toric morphism $f$, this method returns a pair
++        $(f_1, f_2)$ of toric morphisms such that
++
++        * $f = f_1 \circ f_2$,
++
++        * $f_2$ is surjective, and
++
++        * $f_1$ is injective at a generic point of the domain (in
++          particular, on the maximal torus).
++
++        EXAMPLES::
++
++            sage: N = ToricLattice(3)
++            sage: n1 = N( 1,1,1)
++            sage: n2 = N( 0,1,1)
++            sage: n3 = N(-1,1,1)
++            sage: domain = ToricVariety(Fan([Cone([n1,n2]), Cone([n2,n3])]))
++            sage: m = matrix([[0,1,3], [0,1,3]]).transpose()
++            sage: codomain = ToricVariety(Fan([Cone([(1,0), (0,1)])]))
++            sage: f = domain.hom(m, codomain)
++            sage: f1, f2 = f.factor()
++            sage: f2
++            Scheme morphism:
++              From: 3-d toric variety covered by 2 affine patches
++              To:   1-d affine toric variety
++              Defn: Defined by sending Rational polyhedral fan in 3-d lattice N
++                    to Rational polyhedral fan in 1-d lattice N.
++            sage: f1
++            Scheme morphism:
++              From: 1-d affine toric variety
++              To:   2-d affine toric variety
++              Defn: Defined by sending Rational polyhedral fan in 1-d lattice N
++                    to Rational polyhedral fan in 2-d lattice N.
++            
++            sage: f2.is_surjective()
++            True
++            sage: f1.is_injective()
++            True
++            sage: f1.fan_morphism() * f2.fan_morphism() == f.fan_morphism()
++            True
++        """
++        fm1, fm2 = self.fan_morphism().factor()
++        from sage.schemes.toric.all import ToricVariety
++        X = self.domain()
++        Y = ToricVariety(fm2.codomain_fan())
++        Z = self.codomain()
++        return Y.hom(fm1, Z), X.hom(fm2, Y)

File trac_14353_fan_cone_intersection.patch

+# HG changeset patch
+# Parent bdacde3b4f598e31100c8d083a4ca8c77f47de15
+
+Implement support of a fan and intersection of fan with cone
+
+diff --git a/sage/geometry/fan.py b/sage/geometry/fan.py
+--- a/sage/geometry/fan.py
++++ b/sage/geometry/fan.py
+@@ -1455,13 +1455,51 @@
+                               stacklevel=3)
+             return False
+ 
++    def support(self):
++        """
++        Return the support of the fan.
++
++        The support of a fan is the union of all cones of the fan,
++        which is a (usually not strictly) convex polyhedral cone.
++
++        OUTPUT:
++
++        A rational polyhedral cone.
++
++        EXAMPLES:
++
++            sage: cone = Cone([(0,-1), (1,0)])
++            sage: fan = Fan([cone])
++            sage: fan.support()
++            2-d cone in 2-d lattice N
++            sage: fan.support().rays()
++            N(0, -1),
++            N(1,  0)
++            in 2-d lattice N
++            sage: fan.support() == cone
++            True
++
++            sage: cone2 = Cone([(1,0), (0,1)])
++            sage: fan = Fan([cone, cone2])
++            sage: fan.support()
++            2-d cone in 2-d lattice N
++            sage: fan.support().rays()
++            N(1,  0),
++            N(0,  1),
++            N(0, -1)
++            in 2-d lattice N
++            sage: fan.support().is_strictly_convex()
++            False
++        """
++        return Cone(self.rays())
++        
+     def support_contains(self, *args):
+         r"""
+         Check if a point is contained in the support of the fan.
+         
+-        The support of a fan is the union of all cones of the fan. If
+-        you want to know whether the fan contains a given cone, you
+-        should use :meth:`contains` instead.
++        The support of a fan is the union of all cones of the fan, see
++        :meth:`support`. If you want to know whether the fan contains
++        a given cone, you should use :meth:`contains` instead.
+ 
+         INPUT:
+ 
+@@ -1566,6 +1604,33 @@
+         except AttributeError: # The result is either incomplete or unknown.
+             return RationalPolyhedralFan(new_cones, rc.rays(), rc.lattice())
+ 
++    def intersection(self, cone):
++        """
++        Return the intersection with the given cone.
++
++        OUTPUT:
++
++        The intersection of the fan with the given cone as a new
++        fan. This is the fan generated by the intersections of the
++        cones of the fan with the specified ``cone``.
++
++        EXAMPLES::
++
++             sage: fan = toric_varieties.P2().fan()
++             sage: fan.intersection(fan.generating_cone(0)).cones()
++             ((0-d cone of Rational polyhedral fan in 2-d lattice N,),
++              (1-d cone of Rational polyhedral fan in 2-d lattice N,
++               1-d cone of Rational polyhedral fan in 2-d lattice N),
++              (2-d cone of Rational polyhedral fan in 2-d lattice N,))
++             sage: fan.intersection(Cone([(1,2)])).cones()
++             ((0-d cone of Rational polyhedral fan in 2-d lattice N,),
++              (1-d cone of Rational polyhedral fan in 2-d lattice N,))
++             sage: fan.intersection(fan.support()).is_equivalent(fan)
++             True
++        """
++        cones = [cone.intersection(c) for c in self.generating_cones()]
++        return Fan(cones, discard_faces=True)
++
+     def _latex_(self):
+         r"""
+         Return a LaTeX representation of ``self``.

File trac_fan_cone_intersection.patch

-# HG changeset patch
-# Parent bad55404883844d7a70194ebaf011bc015930e9c
-
-diff --git a/sage/geometry/fan.py b/sage/geometry/fan.py
---- a/sage/geometry/fan.py
-+++ b/sage/geometry/fan.py
-@@ -1393,13 +1393,51 @@
-                               stacklevel=3)
-             return False
- 
-+    def support(self):
-+        """
-+        Return the support of the fan.
-+
-+        The support of a fan is the union of all cones of the fan,
-+        which is a (usually not strictly) convex polyhedral cone.
-+
-+        OUTPUT:
-+
-+        A rational polyhedral cone.
-+
-+        EXAMPLES:
-+
-+            sage: cone = Cone([(0,-1), (1,0)])
-+            sage: fan = Fan([cone])
-+            sage: fan.support()
-+            2-d cone in 2-d lattice N
-+            sage: fan.support().rays()
-+            N(0, -1),
-+            N(1,  0)
-+            in 2-d lattice N
-+            sage: fan.support() == cone
-+