Commits

Volker Braun  committed 9f76bed

rearranging patches again

  • Participants
  • Parent commits 82eb372

Comments (0)

Files changed (20)

-trac_13653_exception_fix.patch
-trac_13646_fix_mip.patch
-trac_12533_arbitrary_precision_LP_solver_backend_for_5.3_vb.patch
-trac_13650_base_ring.patch
-trac_13650_normalize_coefficients.patch
-trac_12091_constraints_parents.patch
 trac_13211_fix_gap_doctests.patch
 trac_13211_pool_size.patch
 trac_13211_itanium_fix.patch
 trac_13687_assertions.patch
 trac_12407_primitive_permutation_groups.patch
 trac_12407_review.patch
+trac_12407_fix_testcases.patch
 trac_12339_fpgroups_vb.patch
 trac_12339_braids.patch
 trac_12339_braid_groups_4.patch
-trac_11395_update_gfan.patch
-trac11395-fix_tutorial.patch
-trac_11395_doctest_fix.patch
+trac_12339_braid_groups_review.patch
+trac_12339_pickling.patch
+trac_13740_final_fixes.patch
+trac_7557-maxima_complex_number_conversion.patch
 trac_4411_and_10607_phc_fixes_5.0.patch
 trac_10508_doctest.patch
 trac_10508_update_atlas_docs.patch
 trac_xxxx_ssh.patch #+cluster
 trac_xxxx_cluster_tools.patch #+cluster
-trac_13638_ray_adjacency_fix.patch
 trac_11763-polyhedra_coercion_folded.2.patch
 trac_11763_fix_associahedron.patch
 trac_11763_lazy_import.patch
+trac_13638_ray_adjacency_fix.patch
 trac_13312_polyhedral_neg_polar.patch
 trac_9880_revert_marking_random_from_trac_10187.patch #+pynac
 trac_11667_use_groebner_basis_with_degree_bound.patch  #+todo
 trac_12900_Demazure_roots.patch
 trac_13194_polytope_fan_construct.patch
 trac_xxxx_fiber_divisor_graph.patch
+trac_13691.patch
+trac_13691_Sum.patch
+trac_13756_documentation.patch
 trac_xxxx_fan_refinement.patch
 trac_xxxx_startup_module_path.patch
 trac_zzzz_Chow_ring.patch

File trac11395-fix_tutorial.patch

-# HG changeset patch
-# User Francois Bissey <francois.bissey@canterbury.ac.nz>
-# Date 1341802674 -43200
-# Node ID d882d4f4a770b24dc453d52157f02b8fcf19a740
-# Parent  9dcde86c7cff22bca54e9c9b589f6ff41cd655fd
-trac 11395: upgrade to gfan 0.5. Fix tutorials.
-
-diff --git a/doc/de/tutorial/tour_advanced.rst b/doc/de/tutorial/tour_advanced.rst
---- a/doc/de/tutorial/tour_advanced.rst
-+++ b/doc/de/tutorial/tour_advanced.rst
-@@ -66,13 +66,13 @@
-     in a, b, c, d over Rational Field
-     sage: F.reduced_groebner_bases ()
-     [[-c^2 + b*d, -b*c + a*d, -b^2 + a*c],
-+     [-c^2 + b*d, b^2 - a*c, -b*c + a*d],
-+     [-c^2 + b*d, b*c - a*d, b^2 - a*c, -c^3 + a*d^2],
-+     [c^3 - a*d^2, -c^2 + b*d, b*c - a*d, b^2 - a*c],
-      [c^2 - b*d, -b*c + a*d, -b^2 + a*c],
-      [c^2 - b*d, b*c - a*d, -b^2 + a*c, -b^3 + a^2*d],
-      [c^2 - b*d, b*c - a*d, b^3 - a^2*d, -b^2 + a*c],
--     [c^2 - b*d, b*c - a*d, b^2 - a*c],
--     [-c^2 + b*d, b^2 - a*c, -b*c + a*d],
--     [-c^2 + b*d, b*c - a*d, b^2 - a*c, -c^3 + a*d^2],
--     [c^3 - a*d^2, -c^2 + b*d, b*c - a*d, b^2 - a*c]]
-+     [c^2 - b*d, b*c - a*d, b^2 - a*c]]
-     sage: F.polyhedralfan()
-     Polyhedral fan in 4 dimensions of dimension 4
- 
-diff --git a/doc/en/tutorial/tour_advanced.rst b/doc/en/tutorial/tour_advanced.rst
---- a/doc/en/tutorial/tour_advanced.rst
-+++ b/doc/en/tutorial/tour_advanced.rst
-@@ -65,13 +65,13 @@
-     in a, b, c, d over Rational Field
-     sage: F.reduced_groebner_bases ()
-     [[-c^2 + b*d, -b*c + a*d, -b^2 + a*c],
-+     [-c^2 + b*d, b^2 - a*c, -b*c + a*d],
-+     [-c^2 + b*d, b*c - a*d, b^2 - a*c, -c^3 + a*d^2],
-+     [c^3 - a*d^2, -c^2 + b*d, b*c - a*d, b^2 - a*c],
-      [c^2 - b*d, -b*c + a*d, -b^2 + a*c],
-      [c^2 - b*d, b*c - a*d, -b^2 + a*c, -b^3 + a^2*d],
-      [c^2 - b*d, b*c - a*d, b^3 - a^2*d, -b^2 + a*c],
--     [c^2 - b*d, b*c - a*d, b^2 - a*c],
--     [-c^2 + b*d, b^2 - a*c, -b*c + a*d],
--     [-c^2 + b*d, b*c - a*d, b^2 - a*c, -c^3 + a*d^2],
--     [c^3 - a*d^2, -c^2 + b*d, b*c - a*d, b^2 - a*c]]
-+     [c^2 - b*d, b*c - a*d, b^2 - a*c]]
-     sage: F.polyhedralfan()
-     Polyhedral fan in 4 dimensions of dimension 4
- 
-diff --git a/doc/fr/tutorial/tour_advanced.rst b/doc/fr/tutorial/tour_advanced.rst
---- a/doc/fr/tutorial/tour_advanced.rst
-+++ b/doc/fr/tutorial/tour_advanced.rst
-@@ -67,13 +67,13 @@
-     in a, b, c, d over Rational Field
-     sage: F.reduced_groebner_bases ()
-     [[-c^2 + b*d, -b*c + a*d, -b^2 + a*c],
-+     [-c^2 + b*d, b^2 - a*c, -b*c + a*d],
-+     [-c^2 + b*d, b*c - a*d, b^2 - a*c, -c^3 + a*d^2],
-+     [c^3 - a*d^2, -c^2 + b*d, b*c - a*d, b^2 - a*c],
-      [c^2 - b*d, -b*c + a*d, -b^2 + a*c],
-      [c^2 - b*d, b*c - a*d, -b^2 + a*c, -b^3 + a^2*d],
-      [c^2 - b*d, b*c - a*d, b^3 - a^2*d, -b^2 + a*c],
--     [c^2 - b*d, b*c - a*d, b^2 - a*c],
--     [-c^2 + b*d, b^2 - a*c, -b*c + a*d],
--     [-c^2 + b*d, b*c - a*d, b^2 - a*c, -c^3 + a*d^2],
--     [c^3 - a*d^2, -c^2 + b*d, b*c - a*d, b^2 - a*c]]
-+     [c^2 - b*d, b*c - a*d, b^2 - a*c]]
-     sage: F.polyhedralfan()
-     Polyhedral fan in 4 dimensions of dimension 4
- 
-diff --git a/doc/ru/tutorial/tour_advanced.rst b/doc/ru/tutorial/tour_advanced.rst
---- a/doc/ru/tutorial/tour_advanced.rst
-+++ b/doc/ru/tutorial/tour_advanced.rst
-@@ -61,13 +61,13 @@
-     in a, b, c, d over Rational Field
-     sage: F.reduced_groebner_bases ()
-     [[-c^2 + b*d, -b*c + a*d, -b^2 + a*c],
-+     [-c^2 + b*d, b^2 - a*c, -b*c + a*d],
-+     [-c^2 + b*d, b*c - a*d, b^2 - a*c, -c^3 + a*d^2],
-+     [c^3 - a*d^2, -c^2 + b*d, b*c - a*d, b^2 - a*c],
-      [c^2 - b*d, -b*c + a*d, -b^2 + a*c],
-      [c^2 - b*d, b*c - a*d, -b^2 + a*c, -b^3 + a^2*d],
-      [c^2 - b*d, b*c - a*d, b^3 - a^2*d, -b^2 + a*c],
--     [c^2 - b*d, b*c - a*d, b^2 - a*c],
--     [-c^2 + b*d, b^2 - a*c, -b*c + a*d],
--     [-c^2 + b*d, b*c - a*d, b^2 - a*c, -c^3 + a*d^2],
--     [c^3 - a*d^2, -c^2 + b*d, b*c - a*d, b^2 - a*c]]
-+     [c^2 - b*d, b*c - a*d, b^2 - a*c]]
-     sage: F.polyhedralfan()
-     Polyhedral fan in 4 dimensions of dimension 4
- 

File trac_11395_doctest_fix.patch

-# HG changeset patch
-# Parent 064ba9d34dc911d27e738ad2a3c72bca5149b9cc
-
-Trivial doctest fix
-
-diff --git a/sage/rings/polynomial/groebner_fan.py b/sage/rings/polynomial/groebner_fan.py
---- a/sage/rings/polynomial/groebner_fan.py
-+++ b/sage/rings/polynomial/groebner_fan.py
-@@ -501,7 +501,7 @@
-             sage: GF = I.groebner_fan()
-             sage: PF = GF.tropical_intersection()
-             sage: fan = PF.to_RationalPolyhedralFan()
--            sage: [q.facet_normals() for q in fan]
-+            sage: [tuple(q.facet_normals()) for q in fan]
-             [(M(0, -1, 0), M(-1, 0, 0)), (M(0, 0, -1), M(-1, 0, 0)), (M(0, 0, 1), M(-1, 0, 0)), (M(0, 1, 0), M(-1, 0, 0)), (M(0, 0, -1), M(0, -1, 0)), (M(0, 0, 1), M(0, -1, 0)), (M(0, 1, 0), M(0, 0, -1)), (M(0, 1, 0), M(0, 0, 1)), (M(1, 0, 0), M(0, -1, 0)), (M(1, 0, 0), M(0, 0, -1)), (M(1, 0, 0), M(0, 0, 1)), (M(1, 0, 0), M(0, 1, 0))]
- 
-         Here we use the RationalPolyhedralFan's Gale_transform method on a tropical

File trac_11395_update_gfan.patch

-# HG changeset patch
-# User Marshall Hampton <hamptonio@gmail.com>
-# Date 1342132172 18000
-# Node ID 49b07e1dd3e18c955d0a36c0ce7fffa401263b7c
-# Parent  7a2a36b9da0fc4bfc82fbd11ca7d48f741f74bf7
-[mq]: trac_11395_update_gfan.patch
-
-diff --git a/sage/rings/polynomial/groebner_fan.py b/sage/rings/polynomial/groebner_fan.py
---- a/sage/rings/polynomial/groebner_fan.py
-+++ b/sage/rings/polynomial/groebner_fan.py
-@@ -76,6 +76,9 @@
- from sage.plot.all import line, Graphics, polygon
- from sage.plot.plot3d.shapes2 import line3d
- from sage.geometry.polyhedron.constructor import Polyhedron
-+from sage.geometry.fan import Fan
-+from sage.matrix.constructor import matrix
-+from sage.misc.misc_c import prod
- 
- def prefix_check(str_list):
-     """
-@@ -128,11 +131,11 @@
-     EXAMPLES::
-     
-         sage: R.<x,y,z,w> = PolynomialRing(QQ,4)
--        sage: ts = R.ideal([x^2+y^2+z^2-1,x^4-y^2-z-1,x+y+z,w+x+y])
--        sage: tsg = ts.groebner_fan()
--        sage: tstr = tsg.tropical_intersection()
-+        sage: I = R.ideal([x^2+y^2+z^2-1,x^4-y^2-z-1,x+y+z,w+x+y])
-+        sage: GF = I.groebner_fan()
-+        sage: TI = GF.tropical_intersection()
-         sage: from sage.rings.polynomial.groebner_fan import _cone_parse
--        sage: _cone_parse(tstr.fan_dict['CONES'])
-+        sage: _cone_parse(TI.fan_dict['CONES'])
-         {1: [[0], [1], [2], [3], [4]], 2: [[2, 3]]}
-     """
-     cone_dict = {}
-@@ -277,10 +280,9 @@
-         return self._relative_interior_point
-     
- class PolyhedralFan(SageObject):
--    def __init__(self, gfan_polyhedral_fan):
-+    def __init__(self, gfan_polyhedral_fan, parameter_indices = []):
-         """
-         Converts polymake/gfan data on a polyhedral fan into a sage class.
--        Currently (18-03-2008) needs a lot of work.
-         
-         INPUT:
-         
-@@ -300,7 +302,7 @@
-         """
-         fan_keys = ['AMBIENT_DIM','DIM','LINEALITY_DIM','RAYS','N_RAYS',
-                     'LINEALITY_SPACE','ORTH_LINEALITY_SPACE','F_VECTOR',
--                    'CONES','MAXIMAL_CONES','PURE']
-+                    'CONES','MAXIMAL_CONES','PURE','SIMPLICIAL','MULTIPLICITIES']
-         poly_lines = gfan_polyhedral_fan.split('\n')
-         self.fan_dict = {}
-         key_ind = 0
-@@ -319,8 +321,12 @@
-             temp_ray = ray.split('\t')[0]
-             temp_ray = temp_ray.split(' ')
-             temp_ray = [int(x) for x in temp_ray]
-+            if parameter_indices != []:
-+                for q in parameter_indices:
-+                    temp_ray = temp_ray[0:q] + [0] + temp_ray[q:]
-             self._rays.append(temp_ray)
-         self._cone_dict = _cone_parse(self.fan_dict['CONES'])
-+        self._maximal_cone_dict = _cone_parse(self.fan_dict['MAXIMAL_CONES'])
-         self._str = gfan_polyhedral_fan
- 
-     def _repr_(self):
-@@ -349,7 +355,7 @@
-             sage: gf = R3.ideal([x^8-y^4,y^4-z^2,z^2-2]).groebner_fan()
-             sage: pf = gf.polyhedralfan()
-             sage: pf._str_()
--            '_application PolyhedralFan\n_version 2.2\n_type PolyhedralFan\n\nAMBIENT_DIM\n3\n\nDIM\n3\n\nLINEALITY_DIM\n0\n\nRAYS\n0 0 1\t# 0\n0 1 0\t# 1\n1 0 0\t# 2\n\nN_RAYS\n3\n\nLINEALITY_SPACE\n\nORTH_LINEALITY_SPACE\n1 0 0\n0 1 0\n0 0 1\n\nF_VECTOR\n1 3 3 1\n\nMY_EULER\n0\n\nSIMPLICIAL\n1\n\nPURE\n1\n\nCONES\n{}\t# Dimension 0\n{0}\t# Dimension 1\n{1}\n{2}\n{0 1}\t# Dimension 2\n{0 2}\n{1 2}\n{0 1 2}\t# Dimension 3\n\nMAXIMAL_CONES\n{0 1 2}\t# Dimension 3\n'
-+            '_application fan\n_version 2.2\n_type SymmetricFan\n\nAMBIENT_DIM\n3\n\nDIM\n3\n\nLINEALITY_DIM\n0\n\nRAYS\n0 0 1\t# 0\n0 1 0\t# 1\n1 0 0\t# 2\n\nN_RAYS\n3\n\nLINEALITY_SPACE\n\nORTH_LINEALITY_SPACE\n1 0 0\n0 1 0\n0 0 1\n\nF_VECTOR\n1 3 3 1\n\nSIMPLICIAL\n1\n\nPURE\n1\n\nCONES\n{}\t# Dimension 0\n{0}\t# Dimension 1\n{1}\n{2}\n{0 1}\t# Dimension 2\n{0 2}\n{1 2}\n{0 1 2}\t# Dimension 3\n\nMAXIMAL_CONES\n{0 1 2}\t# Dimension 3\n'
-         """
-         return self._str
- 
-@@ -383,9 +389,8 @@
-     
-     def lineality_dim(self):
-         """
--        Returns the lineality dimension of the Groebner fan. This is 
--        just the difference between the ambient dimension and the dimension
--        of the cone.
-+        Returns the lineality dimension of the fan. This is the
-+        dimension of the largest subspace contained in the fan.
-         
-         EXAMPLES::
-         
-@@ -399,7 +404,7 @@
- 
-     def rays(self):
-         """
--        Returns a list of rays of the polyhedral fan.
-+        A list of rays of the polyhedral fan. 
-         
-         EXAMPLES::
-         
-@@ -411,12 +416,353 @@
-             [[-1, 0, 1], [-1, 1, 0], [1, -2, 1], [1, 1, -2], [2, -1, -1]]
-         """
-         return sorted(self._rays)
-+
-+    def cones(self):
-+        """
-+        A dictionary of cones in which the keys are the cone dimensions.
-+        For each dimension, the value is a list of the cones,
-+        where each element consists of a list of ray indices. 
-         
-+        EXAMPLES::
-+        
-+            sage: R.<x,y,z> = QQ[]
-+            sage: f = 1+x+y+x*y
-+            sage: I = R.ideal([f+z*f, 2*f+z*f, 3*f+z^2*f])
-+            sage: GF = I.groebner_fan()
-+            sage: PF = GF.tropical_intersection()
-+            sage: PF.cones()
-+            {1: [[0], [1], [2], [3], [4], [5]], 2: [[0, 1], [0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [2, 4], [3, 4], [1, 5], [2, 5], [3, 5], [4, 5]]}
-+        """
-+        return self._cone_dict
-+
-+    def maximal_cones(self):
-+        """
-+        A dictionary of the maximal cones in which the keys are the
-+        cone dimensions.  For each dimension, the value is a list of
-+        the maximal cones, where each element consists of a list of ray indices.  
-+        
-+        EXAMPLES::
-+        
-+            sage: R.<x,y,z> = QQ[]
-+            sage: f = 1+x+y+x*y
-+            sage: I = R.ideal([f+z*f, 2*f+z*f, 3*f+z^2*f])
-+            sage: GF = I.groebner_fan()
-+            sage: PF = GF.tropical_intersection()
-+            sage: PF.maximal_cones()
-+            {2: [[0, 1], [0, 2], [0, 3], [0, 4], [1, 2], [1, 3], [2, 4], [3, 4], [1, 5], [2, 5], [3, 5], [4, 5]]}
-+        """
-+        return self._maximal_cone_dict
-+
-+    def f_vector(self):
-+        """
-+        The f-vector of the fan.
-+        
-+        EXAMPLES::
-+        
-+            sage: R.<x,y,z> = QQ[]
-+            sage: f = 1+x+y+x*y
-+            sage: I = R.ideal([f+z*f, 2*f+z*f, 3*f+z^2*f])
-+            sage: GF = I.groebner_fan()
-+            sage: PF = GF.tropical_intersection()
-+            sage: PF.f_vector()
-+            [1, 6, 12]
-+        """
-+        str_data = self.fan_dict['F_VECTOR'][0]
-+        fv = [Integer(x) for x in str_data.split(' ')]
-+        return fv
-+
-+    def is_simplicial(self):
-+        """
-+        Whether the fan is simplicial or not.
-+
-+        EXAMPLES::
-+        
-+            sage: R.<x,y,z> = QQ[]
-+            sage: f = 1+x+y+x*y
-+            sage: I = R.ideal([f+z*f, 2*f+z*f, 3*f+z^2*f])
-+            sage: GF = I.groebner_fan()
-+            sage: PF = GF.tropical_intersection()
-+            sage: PF.is_simplicial()
-+            True
-+        """
-+        return bool(int(self.fan_dict['SIMPLICIAL'][0]))
-+
-+    def to_RationalPolyhedralFan(self):
-+        """
-+        Converts to the RationalPolyhedralFan class, which is more actively
-+        maintained.  While the information in each class is essentially the
-+        same, the methods and implementation are different.
-+
-+        EXAMPLES::
-+        
-+            sage: R.<x,y,z> = QQ[]
-+            sage: f = 1+x+y+x*y
-+            sage: I = R.ideal([f+z*f, 2*f+z*f, 3*f+z^2*f])
-+            sage: GF = I.groebner_fan()
-+            sage: PF = GF.tropical_intersection()
-+            sage: fan = PF.to_RationalPolyhedralFan()
-+            sage: [q.facet_normals() for q in fan]
-+            [(M(0, -1, 0), M(-1, 0, 0)), (M(0, 0, -1), M(-1, 0, 0)), (M(0, 0, 1), M(-1, 0, 0)), (M(0, 1, 0), M(-1, 0, 0)), (M(0, 0, -1), M(0, -1, 0)), (M(0, 0, 1), M(0, -1, 0)), (M(0, 1, 0), M(0, 0, -1)), (M(0, 1, 0), M(0, 0, 1)), (M(1, 0, 0), M(0, -1, 0)), (M(1, 0, 0), M(0, 0, -1)), (M(1, 0, 0), M(0, 0, 1)), (M(1, 0, 0), M(0, 1, 0))]
-+
-+        Here we use the RationalPolyhedralFan's Gale_transform method on a tropical
-+        prevariety.
-+        
-+        .. link
-+
-+        ::
-+        
-+            sage: fan.Gale_transform()
-+            [ 1  0  0  0  0  1 -2]
-+            [ 0  1  0  0  1  0 -2]
-+            [ 0  0  1  1  0  0 -2]
-+
-+        """
-+        try:
-+            return self._fan
-+        except:
-+            cdnt = []
-+            cones = self.cones()
-+            for x in cones:
-+                if x > 1:
-+                    cdnt = cdnt + cones[x]
-+            fan = Fan(cones=cdnt, rays = self.rays(), discard_faces=True)
-+            self._fan = fan
-+            return self._fan
-+
-+class InitialForm(SageObject):
-+    def __init__(self, cone, rays, initial_forms):
-+        """
-+        A system of initial forms from a polynomial system.
-+        To each form is associated a cone and a list of
-+        polynomials (the initial form system itself).
-+
-+        This class is intended for internal use inside of the
-+        TropicalPrevariety class.
-+
-+        EXAMPLES::
-+        
-+            sage: from sage.rings.polynomial.groebner_fan import InitialForm
-+            sage: R.<x,y> = QQ[]
-+            sage: inform = InitialForm([0], [[-1, 0]], [y^2 - 1, y^2 - 2, y^2 - 3])
-+            sage: inform._cone
-+            [0]
-+        """
-+        self._cone = cone
-+        self._rays = rays
-+        self._initial_forms = initial_forms
-+
-+
-+    def cone(self):
-+        """
-+        The cone associated with the initial form system.
-+        
-+        EXAMPLES::
-+        
-+            sage: R.<x,y> = QQ[]
-+            sage: I = R.ideal([(x+y)^2-1,(x+y)^2-2,(x+y)^2-3])
-+            sage: GF = I.groebner_fan()
-+            sage: PF = GF.tropical_intersection()
-+            sage: pfi0 = PF.initial_form_systems()[0]
-+            sage: pfi0.cone()
-+            [0]
-+        """
-+        return self._cone
-+
-+    def rays(self):
-+        """
-+        The rays of the cone associated with the initial form system.
-+
-+        EXAMPLES::
-+        
-+            sage: R.<x,y> = QQ[]
-+            sage: I = R.ideal([(x+y)^2-1,(x+y)^2-2,(x+y)^2-3])
-+            sage: GF = I.groebner_fan()
-+            sage: PF = GF.tropical_intersection()
-+            sage: pfi0 = PF.initial_form_systems()[0]
-+            sage: pfi0.rays()
-+            [[-1, 0]]
-+        """
-+        return self._rays
-+
-+    def internal_ray(self):
-+        """
-+        A ray internal to the cone associated with the initial form
-+        system.
-+
-+        EXAMPLES::
-+        
-+            sage: R.<x,y> = QQ[]
-+            sage: I = R.ideal([(x+y)^2-1,(x+y)^2-2,(x+y)^2-3])
-+            sage: GF = I.groebner_fan()
-+            sage: PF = GF.tropical_intersection()
-+            sage: pfi0 = PF.initial_form_systems()[0]
-+            sage: pfi0.internal_ray()
-+            (-1, 0)
-+        """
-+        return sum([vector(q) for q in self.rays()])
-+
-+    def initial_forms(self):
-+        """
-+        The initial forms (polynomials).
-+
-+        EXAMPLES::
-+        
-+            sage: R.<x,y> = QQ[]
-+            sage: I = R.ideal([(x+y)^2-1,(x+y)^2-2,(x+y)^2-3])
-+            sage: GF = I.groebner_fan()
-+            sage: PF = GF.tropical_intersection()
-+            sage: pfi0 = PF.initial_form_systems()[0]
-+            sage: pfi0.initial_forms()
-+            [y^2 - 1, y^2 - 2, y^2 - 3]
-+        """
-+        return self._initial_forms
-+
-+def verts_for_normal(normal, poly):
-+    """
-+    Returns the exponents of the vertices of a newton polytope
-+    that make up the supporting hyperplane for the given outward
-+    normal.
-+
-+    EXAMPLES::
-+
-+        sage: from sage.rings.polynomial.groebner_fan import verts_for_normal
-+        sage: R.<x,y,z> = PolynomialRing(QQ,3)
-+        sage: f1 = x*y*z - 1
-+        sage: f2 = f1*(x^2 + y^2 + 1)
-+        sage: verts_for_normal([1,1,1],f2)
-+        [(3, 1, 1), (1, 3, 1)]
-+    """
-+    exps = [tuple(x) for x in poly.exponents()]
-+    expmat = matrix(exps)
-+    vals = expmat*vector(QQ,normal)
-+    maxval = max(vals)
-+    outverts = []
-+    for i in range(len(exps)):
-+        if vals[i] == maxval:
-+            outverts.append(exps[i])
-+    return outverts
-+
-+class TropicalPrevariety(PolyhedralFan):
-+    
-+    def __init__(self, gfan_polyhedral_fan, polynomial_system, poly_ring, parameters = []):
-+        """
-+        This class is a subclass of the PolyhedralFan class,
-+        with some additional methods for tropical prevarieties.
-+        
-+        INPUT:
-+        
-+        
-+        -  ``gfan_polyhedral_fan`` - output from gfan of a
-+           polyhedral fan.
-+        -  ``polynomial_system`` - a list of polynomials
-+        -  ``poly_ring`` - the polynomial ring of the list of polynomials
-+        -  ``parameters`` (optional) - a list of variables to be considered as parameters 
-+        
-+        EXAMPLES::
-+        
-+            sage: R.<x,y,z> = QQ[]
-+            sage: I = R.ideal([(x+y+z)^2-1,(x+y+z)-x,(x+y+z)-3])
-+            sage: GF = I.groebner_fan()
-+            sage: TI = GF.tropical_intersection()
-+            sage: TI._polynomial_system
-+            [x^2 + 2*x*y + y^2 + 2*x*z + 2*y*z + z^2 - 1, y + z, x + y + z - 3]
-+        """
-+        parameter_indices = []
-+        if parameters != []:
-+            allvars = poly_ring.gens()
-+            parameter_indices = [allvars.index(q) for q in parameters]
-+        PolyhedralFan.__init__(self, gfan_polyhedral_fan, parameter_indices = parameter_indices)
-+        self._polynomial_system = polynomial_system
-+        self._parameters = parameters
-+        
-+    def initial_form_systems(self):
-+        """
-+        Returns a list of systems of initial forms for each cone
-+        in the tropical prevariety.
-+
-+        EXAMPLES::
-+
-+            sage: R.<x,y> = QQ[]
-+            sage: I = R.ideal([(x+y)^2-1,(x+y)^2-2,(x+y)^2-3])
-+            sage: GF = I.groebner_fan()
-+            sage: PF = GF.tropical_intersection()
-+            sage: pfi = PF.initial_form_systems()
-+            sage: for q in pfi:
-+            ...     print q.initial_forms()
-+            [y^2 - 1, y^2 - 2, y^2 - 3]
-+            [x^2 - 1, x^2 - 2, x^2 - 3]
-+            [x^2 + 2*x*y + y^2, x^2 + 2*x*y + y^2, x^2 + 2*x*y + y^2]
-+        """
-+        try:
-+            return self._initial_form_systems
-+        except AttributeError:
-+            initial_form_systems = []
-+            pvars = self._polynomial_system[0].parent().gens()
-+            nvars = len(pvars)
-+            for dcone in self.cones():
-+                for acone in self.cones()[dcone]:
-+                    rays = [self.rays()[i] for i in acone]
-+                    repray = sum([vector(q) for q in rays])
-+                    iforms = []
-+                    for poly in self._polynomial_system:
-+                        verts = verts_for_normal(repray, poly)
-+                        nform = 0
-+                        for x in verts:    
-+                            factorlist = [pvars[i]**x[i] for i in range(nvars)]
-+                            temp_monomial = prod(factorlist)
-+                            nform += poly.monomial_coefficient(temp_monomial)*temp_monomial
-+                        iforms.append(nform)
-+                    initial_form_systems.append(InitialForm(acone, rays, iforms))
-+            self._initial_form_systems = initial_form_systems
-+            return self._initial_form_systems
-+
-+def ring_to_gfan_format(input_ring):
-+    """
-+    Converts a ring to gfan's format.
-+
-+    EXAMPLES::
-+
-+        sage: R.<w,x,y,z> = QQ[]
-+        sage: from sage.rings.polynomial.groebner_fan import ring_to_gfan_format
-+        sage: ring_to_gfan_format(R)
-+        'Q[w, x, y, z]'
-+        sage: R2.<x,y> = GF(2)[]
-+        sage: ring_to_gfan_format(R2)
-+        'Z/2Z[x, y]'
-+    """
-+    if input_ring.base_ring() == QQ:
-+        ring_str = 'Q' + str(input_ring.gens()).replace('(','[').replace(')',']')
-+    elif input_ring.base_ring() == ZZ:
-+        ring_str = 'Z' + str(input_ring.gens()).replace('(','[').replace(')',']')
-+    else:
-+        ring_str = 'Z/' + str(input_ring.characteristic()) + 'Z'+ str(input_ring.gens()).replace('(','[').replace(')',']')
-+    return ring_str
-+
-+def ideal_to_gfan_format(input_ring, polys):
-+    """
-+    Return the ideal in gfan's notation.
-+        
-+        EXAMPLES::
-+        
-+            sage: R.<x,y,z> = PolynomialRing(QQ,3)
-+            sage: polys = [x^2*y - z, y^2*z - x, z^2*x - y]
-+            sage: from sage.rings.polynomial.groebner_fan import ideal_to_gfan_format
-+            sage: ideal_to_gfan_format(R, polys)
-+            'Q[x, y, z]{x^2*y-z,y^2*z-x,x*z^2-y}'
-+    """
-+    ideal_gen_str = '{' + (str(polys).replace(' ', '').replace("'",""))[1:-1] + '}'
-+    ring_str = ring_to_gfan_format(input_ring)
-+    output = ring_str + ideal_gen_str
-+    return output
- 
- class GroebnerFan(SageObject):
-     
-     def __init__(self, I, is_groebner_basis=False, symmetry=None, verbose=False):
-         """
-+        This class is used to access capabilities of the program Gfan.  In
-+        addition to computing Groebner fans, Gfan can compute other things in
-+        tropical geometry such as tropical prevarieties.
-+        
-         INPUT:
-         
-         
-@@ -435,11 +781,25 @@
-         
-         EXAMPLES::
-         
--            sage: R.<x,y,z> = PolynomialRing(QQ, 3, order='lex')
-+            sage: R.<x,y,z> = QQ[]
-             sage: I = R.ideal([x^2*y - z, y^2*z - x, z^2*x - y])
-             sage: G = I.groebner_fan(); G
-             Groebner fan of the ideal:
--            Ideal (x^2*y - z, -x + y^2*z, x*z^2 - y) of Multivariate Polynomial Ring in x, y, z over Rational Field
-+            Ideal (x^2*y - z, y^2*z - x, x*z^2 - y) of Multivariate Polynomial Ring in x, y, z over Rational Field
-+            
-+        Here is an example of the use of the tropical_intersection command, and then using the RationalPolyhedralFan
-+        class to compute the Stanley-Reisner ideal of the tropical prevariety::
-+
-+            sage: R.<x,y,z> = QQ[]
-+            sage: I = R.ideal([(x+y+z)^3-1,(x+y+z)^3-x,(x+y+z)-3])
-+            sage: GF = I.groebner_fan()
-+            sage: PF = GF.tropical_intersection()
-+            sage: PF.rays()
-+            [[-1, 0, 0], [0, -1, 0], [0, 0, -1], [1, 1, 1]]
-+            sage: RPF = PF.to_RationalPolyhedralFan()
-+            sage: RPF.Stanley_Reisner_ideal(PolynomialRing(QQ,4,'A, B, C, D'))
-+            Ideal (A*B, A*C, B*C*D) of Multivariate Polynomial Ring in A, B, C, D over Rational Field
-+
-         """
-         self.__is_groebner_basis = is_groebner_basis
-         self.__symmetry = symmetry
-@@ -452,6 +812,7 @@
-             raise RuntimeError, "Ring variables cannot contain each other as prefixes"
-         S = I.ring()
-         R = S.base_ring()
-+        # todo: add support for ZZ, which only works for bases computation, not tropical intersections
-         if not R.is_field():
-             raise NotImplementedError, "Groebner fan computation only implemented over fields"
-         if not (R is QQ or (R.is_finite() and R.is_prime_field() and R.order() <= 32749)):
-@@ -566,11 +927,7 @@
-             sage: G._gfan_ring()
-             'Q[x, y, z]'
-         """
--        if self.__ideal.base_ring() == QQ:
--            ring_str = 'Q' + str(self.__ideal.ring().gens()).replace('(','[').replace(')',']')
--        else:
--            ring_str = 'Z/' + str(self.__ideal.base_ring().characteristic()) + 'Z'+ str(self.__ideal.ring().gens()).replace('(','[').replace(')',']')
--        return ring_str
-+        return ring_to_gfan_format(self.ring())
-     
-     def _gfan_ideal(self):
-         """
-@@ -586,9 +943,7 @@
-         try:
-             return self.__gfan_ideal
-         except AttributeError:
--            ideal_gen_str = '{' + (str(self.__ideal.gens()).replace(' ', '').replace("'",""))[1:-1] + '}'
--            ring_str = self._gfan_ring()
--            self.__gfan_ideal = ring_str + ideal_gen_str
-+            self.__gfan_ideal = ideal_to_gfan_format(self.ring(),self.__ideal.gens())
-             return self.__gfan_ideal
- 
-     def weight_vectors(self):
-@@ -601,7 +956,7 @@
-             sage: r3.<x,y,z> = PolynomialRing(QQ,3)
-             sage: g = r3.ideal([x^3+y,y^3-z,z^2-x]).groebner_fan()
-             sage: g.weight_vectors()
--            [(3, 7, 1), (5, 1, 2), (7, 1, 4), (1, 1, 4), (1, 1, 1), (1, 4, 1), (1, 4, 10)]
-+            [(3, 7, 1), (5, 1, 2), (7, 1, 4), (5, 1, 4), (1, 1, 1), (1, 4, 8), (1, 4, 10)]
-             sage: r4.<x,y,z,w> = PolynomialRing(QQ,4)
-             sage: g4 = r4.ideal([x^3+y,y^3-z,z^2-x,z^3 - w]).groebner_fan()
-             sage: len(g4.weight_vectors())
-@@ -641,7 +996,7 @@
-         try:
-             return self.__gfan_reduced_groebner_bases
-         except AttributeError:
--            B = self.gfan()
-+            B = self.gfan(cmd='bases')
-             B = B.replace('\n','')
-             self.__gfan_reduced_groebner_bases = B
-             return B
-@@ -718,11 +1073,11 @@
-             return self.__gfan_mod
-         except AttributeError:
-             mod = ''
--            p = self.characteristic()
--            if p != 0:
--                mod += ' --mod %s'%p
--            else:
--                mod += ''
-+            #p = self.characteristic()
-+            #if p != 0:
-+            #    mod += ' --mod %s'%p
-+            #else:
-+            #    mod += ''
- 
-             if self.__is_groebner_basis:
-                 mod += ' -g'
-@@ -733,7 +1088,7 @@
-             self.__gfan_mod = mod
-             return self.__gfan_mod
- 
--    def gfan(self, cmd='', I=None, format=True):
-+    def gfan(self, cmd='bases', I=None, format=True):
-         r"""
-         Returns the gfan output as a string given an input cmd; the default
-         is to produce the list of reduced Groebner bases in gfan format.
-@@ -1128,11 +1483,7 @@
-             sage: R.<x,y> = PolynomialRing(QQ)
-             sage: G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
-             sage: G._gfan_stats()
--            {'Number of reduced Groebner bases': 3,
--             'Maximal total degree of a Groebner basis': 4,
--             'Dimension of homogeneity space': 0,
--             'Number of variables': 2,
--             'Minimal total degree of a Groebner basis': 2}
-+            {'Number of reduced Groebner bases': 3, 'Number of variables': 2, 'Maximal number of terms in Groebner basis': 6, 'Minimal total degree of a Groebner basis': 2, 'Maximal total degree of a Groebner basis': 4, 'Maximal number of polynomials in Groebner basis': 3, 'Dimension of homogeneity space': 0}
-         """
-         try:
-             return self.__stats
-@@ -1280,29 +1631,104 @@
-         """
-         self[0].interactive(*args, **kwds)
- 
--    def tropical_intersection(self, ideal_arg = False, *args, **kwds):
-+    def tropical_intersection(self, parameters = [], symmetry_generators = [], *args, **kwds):
-         """
-         Returns information about the tropical intersection of the
--        polynomials defining the ideal.
-+        polynomials defining the ideal.  This is the common refinement
-+        of the outward-pointing normal fans of the Newton polytopes of
-+        the generators of the ideal. Note that some people use the
-+        inward-pointing normal fans.
-+
-+        INPUT:
-+
-+        - ``parameters`` (optional) - a list of variables to be considered as parameters
-+        - ``symmetry_generators`` (optional) - generators of the symmetry group
-+
-+        OUTPUT: a TropicalPrevariety object
-         
-         EXAMPLES::
-         
-             sage: R.<x,y,z> = PolynomialRing(QQ,3)
--            sage: i1 = ideal(x*z + 6*y*z - z^2, x*y + 6*x*z + y*z - z^2, y^2 + x*z + y*z)
--            sage: gf = i1.groebner_fan()
-+            sage: I = R.ideal(x*z + 6*y*z - z^2, x*y + 6*x*z + y*z - z^2, y^2 + x*z + y*z)
-+            sage: gf = I.groebner_fan()
-             sage: pf = gf.tropical_intersection()
-             sage: pf.rays()
-             [[-2, 1, 1]]
-+
-+            sage: R.<x,y,z> = PolynomialRing(QQ,3)
-+            sage: f1 = x*y*z - 1
-+            sage: f2 = f1*(x^2 + y^2 + z^2)
-+            sage: f3 = f2*(x + y + z - 1)
-+            sage: I = R.ideal([f1,f2,f3])
-+            sage: gf = I.groebner_fan()
-+            sage: pf = gf.tropical_intersection(symmetry_generators = '(1,2,0),(1,0,2)')
-+            sage: pf.rays()
-+            [[-2, 1, 1], [1, -2, 1], [1, 1, -2]]
-+
-+            sage: R.<x,y,z> = QQ[]
-+            sage: I = R.ideal([(x+y+z)^2-1,(x+y+z)-x,(x+y+z)-3])
-+            sage: GF = I.groebner_fan()
-+            sage: TI = GF.tropical_intersection()
-+            sage: TI.rays()
-+            [[-1, 0, 0], [0, -1, -1], [1, 1, 1]]
-+            sage: GF = I.groebner_fan()
-+            sage: TI = GF.tropical_intersection(parameters=[y])
-+            sage: TI.rays()
-+            [[-1, 0, 0]]
-         """
-         try:
-             return self.__tropical_intersection
-         except AttributeError:
--            f = self.gfan(cmd='tropicalintersection', I = self._gfan_ideal())
--            pf = PolyhedralFan(f)
-+            cmd = 'tropicalintersection'
-+            id_str = self._gfan_ideal()
-+            if parameters != []:
-+                allvars = self.ring().gens()
-+                truevars = [q for q in allvars if not q in parameters]
-+                base_ring = self.ring().base_ring()
-+                new_ring = PolynomialRing(base_ring, len(truevars), string.join([str(q) for q in truevars], sep=','))
-+                old_polys = self.ideal().gens()
-+                new_polys = []
-+                sub = dict([[v,1] for v in parameters])
-+                for apoly in old_polys:
-+                    mons = apoly.monomials()
-+                    mons = [m.subs(sub) for m in mons]
-+                    new_polys.append(sum(mons))
-+                id_str = ideal_to_gfan_format(new_ring, new_polys)
-+            if symmetry_generators != []:
-+                cmd = cmd + ' --symmetryExploit'
-+                id_str = id_str + '{' + symmetry_generators + '}'
-+            f = self.gfan(cmd=cmd, I = id_str)
-+            pf = TropicalPrevariety(f,self.ideal().gens(), self.ring(), parameters = parameters)
-+            pf._gfan_output = f
-             self.__tropical_intersection = pf
-             return pf
-         
-+
-+    def mixed_volume(self):
-+        """
-+        Returns the mixed volume of the generators of this ideal (i.e. this is
-+        not really an ideal property, it can depend on the generators used).
-+        The generators must give a square system (as many polynomials as variables).
-+
-+        EXAMPLES::
-         
-+            sage: R.<x,y,z> = QQ[]
-+            sage: example_ideal = R.ideal([x^2-y-1,y^2-z-1,z^2-x-1])
-+            sage: gf = example_ideal.groebner_fan()
-+            sage: mv = gf.mixed_volume()
-+            sage: mv
-+            8
-+    
-+            sage: R2.<x,y> = QQ[]
-+            sage: g1 = 1 - x + x^7*y^3 + 2*x^8*y^4
-+            sage: g2 = 2 + y + 3*x^7*y^3 + x^8*y^4
-+            sage: example2 = R2.ideal([g1,g2])
-+            sage: example2.groebner_fan().mixed_volume()
-+            15
-+        """ 
-+        if len(self.ring().variable_names()) != self.ideal().ngens():
-+            raise UserWarning, 'not a square system'
-+        return Integer(self.gfan(cmd='mixedvolume'))
- 
- class ReducedGroebnerBasis(SageObject, list):
-     def __init__(self, groebner_fan, gens, gfan_gens):

File trac_12091_constraints_parents.patch

-# HG changeset patch
-# Parent 11be0924d40f1d23ddc48ed1b8e72dbaef1bcc25
-
-Implement parents for constraints, fix chained inequalities
-
-diff --git a/doc/en/reference/numerical.rst b/doc/en/reference/numerical.rst
---- a/doc/en/reference/numerical.rst
-+++ b/doc/en/reference/numerical.rst
-@@ -6,6 +6,7 @@
- 
-    sage/numerical/knapsack
-    sage/numerical/mip
-+   sage/numerical/linear_functions
-    sage/numerical/optimize
- 
- LP Solver backends
-diff --git a/module_list.py b/module_list.py
---- a/module_list.py
-+++ b/module_list.py
-@@ -1254,6 +1254,11 @@
-               include_dirs=[SAGE_INC],
-               libraries=["csage","stdc++"]),
- 
-+    Extension("sage.numerical.linear_functions",
-+              ["sage/numerical/linear_functions.pyx"],
-+              include_dirs=[SAGE_INC],
-+              libraries=["csage","stdc++"]),
-+
-     Extension("sage.numerical.backends.generic_backend",
-               ["sage/numerical/backends/generic_backend.pyx"],
-               include_dirs = [SAGE_INC, "sage/c_lib/include/"],
-diff --git a/sage/numerical/linear_functions.pxd b/sage/numerical/linear_functions.pxd
-new file mode 100644
---- /dev/null
-+++ b/sage/numerical/linear_functions.pxd
-@@ -0,0 +1,38 @@
-+from sage.structure.parent cimport Parent
-+from sage.structure.element cimport ModuleElement, RingElement, Element
-+
-+
-+cdef class LinearFunctionsParent_class(Parent):
-+    cpdef _element_constructor_(self, x)
-+    cpdef _coerce_map_from_(self, R)
-+    cdef object _multiplication_symbol
-+    cpdef object _get_multiplication_symbol(self)
-+
-+cdef class LinearFunction(ModuleElement):
-+    cdef dict _f
-+    cpdef iteritems(self)
-+    cpdef ModuleElement _add_(self, ModuleElement b)
-+    cpdef ModuleElement _sub_(self, ModuleElement b)
-+    cpdef ModuleElement _lmul_(self, RingElement b)
-+    cpdef ModuleElement _rmul_(self, RingElement b)
-+    cpdef ModuleElement _neg_(self)
-+    cpdef _acted_upon_(self, x, bint self_on_left)
-+    cdef _richcmp(left, right, int op)
-+    cpdef is_zero(self)
-+    cpdef equals(LinearFunction left, LinearFunction right)
-+
-+cdef class LinearConstraintsParent_class(Parent):
-+    cdef LinearFunctionsParent_class _LF
-+    cpdef _element_constructor_(self, left, right=?, equality=?)
-+    cpdef _coerce_map_from_(self, R)
-+
-+cdef class LinearConstraint(Element):
-+    cdef bint equality
-+    cdef list constraints
-+    cdef _richcmp(left, right, int op)
-+    cdef LinearConstraint _chained_comparator_hack_part1(LinearConstraint left, LinearConstraint right)
-+    cdef _chained_comparator_hack_part2(self)
-+    cpdef equals(LinearConstraint left, LinearConstraint right)
-+
-+cdef LinearConstraint _chained_comparator_hack_search
-+cdef LinearConstraint _chained_comparator_hack_replace
-diff --git a/sage/numerical/linear_functions.pyx b/sage/numerical/linear_functions.pyx
-new file mode 100644
---- /dev/null
-+++ b/sage/numerical/linear_functions.pyx
-@@ -0,0 +1,1393 @@
-+"""
-+Linear Functions and Constraints
-+
-+This module implements linear functions (see :class:`LinearFunction`)
-+in formal variables and chained (in)equalities between them (see
-+:class:`LinearConstraint`). By convention, these are always written as
-+either equalities or less-or-equal. For example::
-+
-+    sage: p = MixedIntegerLinearProgram()
-+    sage: x = p.new_variable()
-+    sage: f = 1 + x[1] + 2*x[2];  f     #  a linear function
-+    1 + x_0 + 2*x_1
-+    sage: type(f)
-+    <type 'sage.numerical.linear_functions.LinearFunction'>
-+    
-+    sage: c = (0 <= f);  c    # a constraint
-+    0 <= 1 + x_0 + 2*x_1
-+    sage: type(c)
-+    <type 'sage.numerical.linear_functions.LinearConstraint'>
-+    
-+Note that you can use this module without any reference to linear
-+programming, it only implements linear functions over a base ring and
-+constraints. However, for ease of demonstration we will always
-+construct them out of linear programs (see
-+:mod:`~sage.numerical.mip`).
-+
-+Constraints can be equations or (non-strict) inequalities. They can be
-+chained::
-+
-+    sage: p = MixedIntegerLinearProgram()
-+    sage: x = p.new_variable()
-+    sage: x[0] == x[1] == x[2] == x[3]
-+    x_0 == x_1 == x_2 == x_3
-+
-+    sage: ieq_01234 = x[0] <= x[1] <= x[2] <= x[3] <= x[4]
-+    sage: ieq_01234
-+    x_0 <= x_1 <= x_2 <= x_3 <= x_4
-+
-+If necessary, the direction of inequality is flipped to always write
-+inqualities as less or equal::
-+
-+    sage: x[5] >= ieq_01234
-+    x_0 <= x_1 <= x_2 <= x_3 <= x_4 <= x_5
-+
-+    sage: (x[5]<=x[6]) >= ieq_01234
-+    x_0 <= x_1 <= x_2 <= x_3 <= x_4 <= x_5 <= x_6
-+    sage: (x[5]<=x[6]) <= ieq_01234
-+    x_5 <= x_6 <= x_0 <= x_1 <= x_2 <= x_3 <= x_4
-+
-+TESTS:
-+
-+See :trac:`12091` ::
-+
-+    sage: p = MixedIntegerLinearProgram()
-+    sage: b = p.new_variable()
-+    sage: b[0] <= b[1] <= 2
-+    x_0 <= x_1 <= 2
-+    sage: list(b[0] <= b[1] <= 2)
-+    [x_0, x_1, 2]
-+    sage: 1 >= b[1] >= 2*b[0]
-+    2*x_0 <= x_1 <= 1
-+    sage: b[2] >= b[1] >= 2*b[0]
-+    2*x_0 <= x_1 <= x_2
-+"""
-+
-+
-+#*****************************************************************************
-+#       Copyright (C) 2012 Nathann Cohen <nathann.cohen@gmail.com>
-+#       Copyright (C) 2012 Volker Braun <vbraun.name@gmail.com>
-+#
-+#  Distributed under the terms of the GNU General Public License (GPL)
-+#  as published by the Free Software Foundation; either version 2 of
-+#  the License, or (at your option) any later version.
-+#                  http://www.gnu.org/licenses/
-+#*****************************************************************************
-+
-+include "../ext/stdsage.pxi"
-+include "../ext/interrupt.pxi"
-+include "../ext/cdefs.pxi"
-+
-+from sage.structure.parent cimport Parent
-+from sage.structure.element cimport ModuleElement, Element
-+from sage.misc.cachefunc import cached_function
-+
-+
-+
-+#*****************************************************************************
-+#
-+# Utility functions to test that something is a linear function / constraint
-+#
-+#*****************************************************************************
-+
-+def is_LinearFunction(x):
-+    """
-+    Test whether ``x`` is a linear function
-+    
-+    INPUT:
-+
-+    - ``x`` -- anything.
-+
-+    OUTPUT:
-+
-+    Boolean.
-+    
-+    EXAMPLES::
-+    
-+        sage: p = MixedIntegerLinearProgram()
-+        sage: x = p.new_variable()
-+        sage: from sage.numerical.linear_functions import is_LinearFunction
-+        sage: is_LinearFunction(x[0] - 2*x[2])
-+        True
-+        sage: is_LinearFunction('a string')
-+        False
-+    """
-+    return isinstance(x, LinearFunction)
-+
-+def is_LinearConstraint(x):
-+    """
-+    Test whether ``x`` is a linear constraint
-+    
-+    INPUT:
-+
-+    - ``x`` -- anything.
-+
-+    OUTPUT:
-+
-+    Boolean.
-+    
-+    EXAMPLES::
-+    
-+        sage: p = MixedIntegerLinearProgram()
-+        sage: x = p.new_variable()
-+        sage: ieq = (x[0] <= x[1])
-+        sage: from sage.numerical.linear_functions import is_LinearConstraint
-+        sage: is_LinearConstraint(ieq)
-+        True
-+        sage: is_LinearConstraint('a string')
-+        False
-+    """
-+    return isinstance(x, LinearConstraint)
-+
-+
-+#*****************************************************************************
-+#
-+# Factory functions for the parents to ensure uniqueness
-+#
-+#*****************************************************************************
-+
-+@cached_function
-+def LinearFunctionsParent(base_ring):
-+    """
-+    Return the parent for linear functions over ``base_ring``.
-+
-+    The output is cached, so only a single parent is ever constructed
-+    for a given base ring.
-+
-+    INPUT:
-+
-+    - ``base_ring`` -- a ring. The coefficient ring for the linear
-+      funcitons.
-+
-+    OUTPUT:
-+
-+    The parent of the linear functions over ``base_ring``.
-+
-+    EXAMPLES::
-+
-+        sage: from sage.numerical.linear_functions import LinearFunctionsParent
-+        sage: LinearFunctionsParent(QQ)
-+        Linear functions over Rational Field
-+    """
-+    return LinearFunctionsParent_class(base_ring)
-+
-+@cached_function
-+def LinearConstraintsParent(linear_functions_parent):
-+   """
-+   Return the parent for linear functions over ``base_ring``.
-+
-+   The output is cached, so only a single parent is ever constructed
-+   for a given base ring.
-+
-+    INPUT:
-+
-+    - ``linear_functions_parent`` -- a
-+      :class:`LinearFunctionsParent_class`. The type of linear
-+      functions that the constraints are made out of.
-+
-+    OUTPUT:
-+
-+    The parent of the linear constraints with the given linear functions.
-+
-+    EXAMPLES::
-+
-+        sage: from sage.numerical.linear_functions import \
-+        ...       LinearFunctionsParent, LinearConstraintsParent
-+        sage: LF = LinearFunctionsParent(QQ)
-+        sage: LinearConstraintsParent(LF)
-+        Linear constraints over Rational Field
-+   """
-+   return LinearConstraintsParent_class(linear_functions_parent)
-+
-+
-+
-+#*****************************************************************************
-+#
-+# Parent of linear functions
-+#
-+#*****************************************************************************
-+
-+cdef class LinearFunctionsParent_class(Parent):
-+    r"""
-+    The parent for all linear functions over a fixed base ring.
-+
-+    .. warning::
-+    
-+        You should use :func:`LinearFunctionsParent` to construct
-+        instances of this class.
-+
-+    INPUT/OUTPUT:
-+
-+    See :func:`LinearFunctionsParent`
-+
-+    EXAMPLES::
-+
-+        sage: from sage.numerical.linear_functions import LinearFunctionsParent_class
-+        sage: LinearFunctionsParent_class
-+        <type 'sage.numerical.linear_functions.LinearFunctionsParent_class'>
-+    """
-+
-+    def __init__(self, base_ring):
-+        """
-+        The Python constructor
-+        
-+        TESTS::
-+
-+            sage: from sage.numerical.linear_functions import LinearFunctionsParent
-+            sage: LinearFunctionsParent(RDF)
-+            Linear functions over Real Double Field
-+        """
-+        from sage.categories.modules_with_basis import ModulesWithBasis
-+        Parent.__init__(self, base=base_ring, category=ModulesWithBasis(base_ring))
-+        self._multiplication_symbol = '*'
-+
-+    def set_multiplication_symbol(self, symbol='*'):
-+        """
-+        Set the multiplication symbol when pretty-printing linear functions.
-+
-+        INPUT:
-+
-+        - ``symbol`` -- string, default: ``'*'``. The multiplication
-+          symbol to be used.
-+
-+        EXAMPLES::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: x = p.new_variable()
-+            sage: f = -1-2*x[0]-3*x[1]
-+            sage: LF = f.parent()
-+            sage: LF._get_multiplication_symbol()
-+            '*'
-+            sage: f
-+            -1 - 2*x_0 - 3*x_1
-+            sage: LF.set_multiplication_symbol(' ')
-+            sage: f
-+            -1 - 2 x_0 - 3 x_1
-+            sage: LF.set_multiplication_symbol()
-+            sage: f
-+            -1 - 2*x_0 - 3*x_1
-+        """
-+        self._multiplication_symbol = symbol
-+
-+    cpdef _get_multiplication_symbol(self):
-+        """
-+        Return the multiplication symbol.
-+        
-+        OUTPUT:
-+        
-+        String. By default, this is ``'*'``.
-+        
-+        EXAMPLES::
-+        
-+            sage: LF = MixedIntegerLinearProgram().linear_functions_parent()
-+            sage: LF._get_multiplication_symbol()
-+            '*'
-+        """
-+        return self._multiplication_symbol
-+
-+    def _repr_(self):
-+        """
-+        Return as string representation
-+        
-+        EXAMPLES::
-+        
-+            sage: MixedIntegerLinearProgram().linear_functions_parent()
-+            Linear functions over Real Double Field
-+        """
-+        return 'Linear functions over '+str(self.base_ring())
-+
-+    cpdef _element_constructor_(self, x):
-+        """
-+        Construt a :class:`LinearFunction` from ``x``.
-+
-+        EXAMPLES::
-+        
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: LF = p.linear_functions_parent()
-+            sage: LF._element_constructor_(123)
-+            123
-+            sage: p(123)    # indirect doctest
-+            123
-+            sage: type(_)
-+            <type 'sage.numerical.linear_functions.LinearFunction'>
-+
-+            sage: p_QQ = MixedIntegerLinearProgram(solver='ppl')
-+            sage: LF_QQ = p_QQ.linear_functions_parent()
-+            sage: f = LF({-1:1/2, 2:3/4});  f
-+            0.5 + 0.75*x_2
-+            sage: LF(f) is f
-+            True
-+            sage: LF_QQ(f)
-+            1/2 + 3/4*x_2
-+            sage: LF_QQ(f) is f
-+            False
-+        """
-+        if is_LinearFunction(x):
-+            if x.parent() is self:
-+                return x
-+            else:
-+                return LinearFunction(self, (<LinearFunction>x)._f)
-+        return LinearFunction(self, x)
-+
-+    cpdef _coerce_map_from_(self, R):
-+        """
-+        Allow coercion of scalars into linear functions.
-+        
-+        INPUT:
-+        
-+        - ``R`` -- a ring.
-+        
-+        OUTPUT:
-+
-+        Boolean. Whether there is a coercion map.
-+
-+        EXAMPLES::
-+        
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: parent = p.linear_functions_parent()
-+            sage: parent.coerce(int(2))
-+            2
-+            sage: parent._coerce_map_from_(int)
-+            True
-+        """
-+        if R in [int, float, long, complex]:
-+            return True
-+        from sage.rings.real_mpfr import mpfr_prec_min
-+        from sage.rings.all import RealField
-+        if RealField(mpfr_prec_min()).has_coerce_map_from(R):
-+            return True
-+        return False
-+
-+    def _an_element_(self):
-+        """
-+        Returns an element
-+
-+        OUTPUT:
-+
-+        A linear function.
-+
-+        EXAMPLES::
-+
-+            sage: p = MixedIntegerLinearProgram().linear_functions_parent()
-+            sage: p._an_element_()
-+            5*x_2 + 7*x_5
-+            sage: p.an_element()   # indirect doctest
-+            5*x_2 + 7*x_5
-+        """
-+        return self._element_constructor_({2:5, 5:7})
-+
-+
-+#*****************************************************************************
-+#
-+# Elements of linear functions
-+#
-+#*****************************************************************************
-+
-+cdef class LinearFunction(ModuleElement):
-+    r"""
-+    An elementary algebra to represent symbolic linear functions.
-+
-+    .. warning::
-+    
-+        You should never instantiate :class:`LinearFunction`
-+        manually. Use the element constructor in the parent
-+        instead. For convenience, you can also call the
-+        :class:`MixedIntegerLinearProgram` instance directly.
-+
-+    EXAMPLES:
-+
-+    For example, do this::
-+
-+        sage: p = MixedIntegerLinearProgram()
-+        sage: p({0 : 1, 3 : -8})
-+        x_0 - 8*x_3
-+
-+    or this::
-+
-+        sage: parent = p.linear_functions_parent()
-+        sage: parent({0 : 1, 3 : -8})
-+        x_0 - 8*x_3
-+
-+    instead of this::
-+            
-+        sage: from sage.numerical.linear_functions import LinearFunction
-+        sage: LinearFunction(p.linear_functions_parent(), {0 : 1, 3 : -8})
-+        x_0 - 8*x_3
-+    """
-+
-+    def __init__(self, parent, f):
-+        r"""
-+        Constructor taking a dictionary or a numerical value as its argument.
-+
-+        A linear function is represented as a dictionary. The
-+        values are the coefficient of the variable represented
-+        by the keys ( which are integers ). The key ``-1``
-+        corresponds to the constant term.
-+
-+        EXAMPLES:
-+
-+        With a dictionary::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: p({0 : 1, 3 : -8})
-+            x_0 - 8*x_3
-+
-+        Using the constructor with a numerical value::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: p(25)
-+            25
-+        """
-+        ModuleElement.__init__(self, parent)
-+        R = self.base_ring()
-+        if isinstance(f, dict):
-+            self._f = dict( (int(key), R(value)) for key, value in f.iteritems() )
-+        else:
-+            self._f = {-1: R(f)}
-+
-+    cpdef iteritems(self):
-+        """
-+        Iterate over the index, coefficient pairs
-+
-+        OUTPUT:
-+
-+        An iterator over the ``(key, coefficient)`` pairs. The keys
-+        are integers indexing the variables. The key ``-1``
-+        corresponds to the constant term.
-+        
-+        EXAMPLES::
-+        
-+            sage: p = MixedIntegerLinearProgram(solver = 'ppl')
-+            sage: x = p.new_variable()
-+            sage: f = 0.5 + 3/2*x[1] + 0.6*x[3]
-+            sage: for id, coeff in f.iteritems():
-+            ...      print 'id =', id, '  coeff =', coeff
-+            id = 0   coeff = 3/2
-+            id = 1   coeff = 3/5
-+            id = -1   coeff = 1/2
-+        """
-+        return self._f.iteritems()
-+
-+    def dict(self):
-+        r"""
-+        Returns the dictionary corresponding to the Linear Function.
-+
-+        OUTPUT:
-+
-+        The linear function is represented as a dictionary. The value
-+        are the coefficient of the variable represented by the keys (
-+        which are integers ). The key ``-1`` corresponds to the
-+        constant term.
-+
-+        EXAMPLE::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: lf = p({0 : 1, 3 : -8})
-+            sage: lf.dict()
-+            {0: 1.0, 3: -8.0}
-+        """
-+        return dict(self._f)
-+
-+    cpdef ModuleElement _add_(self, ModuleElement b):
-+        r"""
-+        Defining the + operator
-+
-+        EXAMPLE::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: p({0 : 1, 3 : -8}) + p({2 : 5, 3 : 2}) - 16
-+            -16 + x_0 + 5*x_2 - 6*x_3
-+        """
-+        e = dict(self._f)
-+        for (id,coeff) in b.dict().iteritems():
-+            e[id] = self._f.get(id,0) + coeff
-+        P = self.parent()
-+        return P(e)
-+
-+    cpdef ModuleElement _neg_(self):
-+        r"""
-+        Defining the - operator (opposite).
-+
-+        EXAMPLE::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: - p({0 : 1, 3 : -8})
-+            -1*x_0 + 8*x_3
-+        """
-+        P = self.parent()
-+        return P(dict([(id,-coeff) for (id, coeff) in self._f.iteritems()]))
-+
-+    cpdef ModuleElement _sub_(self, ModuleElement b):
-+        r"""
-+        Defining the - operator (substraction).
-+
-+        EXAMPLE::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: p({2 : 5, 3 : 2}) - 3
-+            -3 + 5*x_2 + 2*x_3
-+            sage: p({0 : 1, 3 : -8}) - p({2 : 5, 3 : 2}) - 16
-+            -16 + x_0 - 5*x_2 - 10*x_3
-+        """
-+        e = dict(self._f)
-+        for (id,coeff) in b.dict().iteritems():
-+            e[id] = self._f.get(id,0) - coeff
-+        P = self.parent()
-+        return P(e)
-+
-+    cpdef ModuleElement _rmul_(self, RingElement b):
-+        r"""
-+        Left multiplication by scalars
-+
-+        EXAMPLE::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: p({2 : 5, 3 : 2}) * 3
-+            15*x_2 + 6*x_3
-+        """
-+        P = self.parent()
-+        return P(dict([(id,b*coeff) for (id, coeff) in self._f.iteritems()]))
-+
-+    cpdef ModuleElement _lmul_(self, RingElement b):
-+        r"""
-+        Right multiplication by scalars
-+
-+        EXAMPLE::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: 3 * p({2 : 5, 3 : 2})
-+            15*x_2 + 6*x_3
-+        """
-+        return self._rmul_(b)
-+
-+    cpdef _acted_upon_(self, x, bint self_on_left):
-+       """
-+       Act with scalars that do not have a natural coercion into
-+       ``self.base_ring()``
-+
-+       EXAMPLES:
-+
-+       Note that there is no coercion from ``RR`` to ``QQ``, but you
-+       can explicitly convert them::
-+
-+           sage: 1/2 * 0.6
-+           0.300000000000000
-+
-+       If there were a coercion, then 0.6 would have been coerced into
-+       6/10 and the result would have been rational. This is
-+       undesirable, which is why there cannot be a coercion on the
-+       level of the coefficient rings.
-+
-+       By declaring an action of ``RR`` on the linear functions over
-+       ``QQ`` we make the following possible::
-+
-+           sage: p = MixedIntegerLinearProgram(solver='ppl')
-+           sage: p.base_ring()
-+           Rational Field
-+           sage: x = p.new_variable()
-+           sage: x[0] * 0.6
-+           3/5*x_0
-+       """
-+       R = self.base_ring()
-+       try:
-+           x_R = R(x)
-+       except TypeError:
-+           return None
-+       return self._rmul_(x_R)
-+
-+    def _coeff_formatter(self, coeff, constant_term=False):
-+        """
-+        Pretty-print multiplicative coefficient ``x`` 
-+        
-+        OUTPUT:
-+
-+        String, including a trailing space if the coefficient is not
-+        one. Empty string otherwise.
-+
-+        EXAMPLES::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: f = p(1);  type(f)
-+            <type 'sage.numerical.linear_functions.LinearFunction'>
-+            sage: f._coeff_formatter(1)
-+            ''
-+            sage: f._coeff_formatter(1, constant_term=True)
-+            '1'
-+            sage: f._coeff_formatter(RDF(12.0))
-+            '12*'
-+            sage: f._coeff_formatter(RDF(12.3))
-+            '12.3*'
-+
-+            sage: q = MixedIntegerLinearProgram(solver='ppl')
-+            sage: f = p(1)
-+            sage: f._coeff_formatter(13/45)
-+            '13/45*'
-+        """
-+        R = self.base_ring()
-+        if coeff == R.one() and not constant_term:
-+            return ''
-+        try: 
-+            from sage.rings.all import ZZ
-+            coeff = ZZ(coeff)    # print as integer if possible
-+        except TypeError:
-+            pass
-+        if constant_term:
-+            return str(coeff)
-+        else:
-+            return str(coeff) + self.parent()._get_multiplication_symbol()
-+
-+    def _repr_(self):
-+        r"""
-+        Returns a string version of the linear function.
-+
-+        EXAMPLE::
-+
-+            sage: p = MixedIntegerLinearProgram(solver='GLPK')
-+            sage: p({-1: -15, 2 : -5.1, 3 : 2/3})
-+            -15 - 5.1*x_2 + 0.666666666667*x_3
-+            sage: p = MixedIntegerLinearProgram(solver='ppl')
-+            sage: p({-1: -15, 2 : -5.1, 3 : 2/3})
-+            -15 - 51/10*x_2 + 2/3*x_3
-+        """
-+        cdef dict d = dict(self._f)
-+        cdef bint first = True
-+        t = ""
-+
-+        if d.has_key(-1):
-+            coeff = d.pop(-1)
-+            if coeff!=0:
-+                t = self._coeff_formatter(coeff, constant_term=True)
-+                first = False
-+
-+        cdef list l = sorted(d.items())
-+        for id,coeff in l:
-+            sign = cmp(coeff,0)
-+            if sign == 0:
-+                continue
-+            if not first:
-+                if sign == -1:
-+                    t += ' - '
-+                if sign == +1:
-+                    t += ' + '
-+                t += self._coeff_formatter(abs(coeff)) + 'x_' + str(id)
-+            else:
-+                t += self._coeff_formatter(coeff) + 'x_' + str(id)
-+            first = False
-+        
-+        if first:
-+            return '0'
-+        else:
-+            return t
-+
-+    cpdef is_zero(self):
-+        """
-+        Test whether ``self`` is zero.
-+
-+        OUTPUT:
-+        
-+        Boolean.
-+
-+        EXAMPLES::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: x = p.new_variable()
-+            sage: (x[1] - x[1] + 0*x[2]).is_zero()
-+            True
-+        """
-+        for coeff in self._f.values():
-+            if not coeff.is_zero():
-+                return False
-+        return True
-+
-+    cpdef equals(LinearFunction left, LinearFunction right):
-+        """
-+        Logically compare ``left`` and ``right``.
-+
-+        OUTPUT:
-+
-+        Boolean.
-+
-+        EXAMPLES::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: x = p.new_variable()
-+            sage: (x[1] + 1).equals(3/3 + 1*x[1] + 0*x[2])
-+            True
-+        """
-+        return (left-right).is_zero()
-+
-+    def __richcmp__(left, right, int op):
-+        """
-+        Override the rich comparison.
-+        
-+        The Sage framework sometimes expects that rich comparison
-+        results in a boolean value, but we want to return
-+        :class:`~sage.numerical.linear_functions.LinearConstraint`
-+        objects.
-+
-+        EXAMPLES::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: x = p.new_variable()
-+            sage: x[0].__le__(x[1])    # indirect doctest
-+            x_0 <= x_1
-+        """
-+        return (<LinearFunction>left)._richcmp(right, op)
-+
-+    cdef _richcmp(left, right, int op):
-+        """
-+        Create a inequality or equality object.
-+
-+        EXAMPLE::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: from sage.numerical.linear_functions import LinearFunction
-+            sage: p({2 : 5, 3 : 2}) <= p({2 : 3, 9 : 2})
-+            5*x_2 + 2*x_3 <= 3*x_2 + 2*x_9
-+
-+            sage: p({2 : 5, 3 : 2}) >= p({2 : 3, 9 : 2})
-+            3*x_2 + 2*x_9 <= 5*x_2 + 2*x_3
-+
-+            sage: p({2 : 5, 3 : 2}) == p({2 : 3, 9 : 2})
-+            5*x_2 + 2*x_3 == 3*x_2 + 2*x_9
-+
-+            sage: p({2 : 5, 3 : 2}) < p({2 : 3, 9 : 2})
-+            Traceback (most recent call last):
-+            ...
-+            ValueError: strict < is not allowed, use <= instead.
-+
-+            sage: p({2 : 5, 3 : 2}) > p({2 : 3, 9 : 2})
-+            Traceback (most recent call last):
-+            ...
-+            ValueError: strict > is not allowed, use >= instead.
-+
-+        TESTS::
-+
-+            sage: cm = sage.structure.element.get_coercion_model()
-+            sage: cm.explain(10, p(1), operator.le)
-+            Coercion on left operand via
-+                Conversion map:
-+                  From: Integer Ring
-+                  To:   Linear functions over Real Double Field
-+            Arithmetic performed after coercions.
-+            Result lives in Linear functions over Real Double Field
-+            Linear functions over Real Double Field
-+
-+            sage: x = p.new_variable()
-+            sage: operator.le(10, x[0])
-+            10 <= x_0
-+            sage: x[0] <= 1
-+            x_0 <= 1
-+            sage: x[0] >= 1
-+            1 <= x_0
-+            sage: 1 <= x[0]
-+            1 <= x_0
-+            sage: 1 >= x[0]
-+            x_0 <= 1
-+       """
-+        LF = left.parent()
-+        LC = LinearConstraintsParent(LF)
-+        equality = (op == Py_EQ)
-+        cdef LinearConstraint  left_constraint = LC(left,  equality=equality)
-+        cdef LinearConstraint right_constraint = LC(right, equality=equality)
-+        if op == Py_LT:
-+            raise ValueError("strict < is not allowed, use <= instead.")
-+        elif op == Py_EQ:
-+            return left_constraint._richcmp(right_constraint, op)
-+        elif op == Py_GT:
-+            raise ValueError("strict > is not allowed, use >= instead.")
-+        elif op == Py_LE:
-+            return left_constraint._richcmp(right_constraint, op)
-+        elif op == Py_NE:
-+            raise ValueError("inequality != is not allowed, use one of <=, ==, >=.")
-+        elif op == Py_GE:
-+            return left_constraint._richcmp(right_constraint, op)
-+        else:
-+            assert(False)   # unreachable
-+
-+    def __hash__(self):
-+        r"""
-+        Defines a ``__hash__`` function
-+
-+        EXAMPLE::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: f = p({2 : 5, 3 : 2})
-+            sage: f.__hash__()   # random output
-+            103987752
-+            sage: d = {}
-+            sage: d[f] = 3
-+        """
-+        return id(self)
-+
-+
-+#*****************************************************************************
-+#
-+# Parent of linear constraints
-+#
-+#*****************************************************************************
-+
-+cdef class LinearConstraintsParent_class(Parent):
-+    """
-+    Parent for :class:`LinearConstraint`
-+
-+    .. warning::
-+
-+        This class has no reason to be instanciated by the user, and
-+        is meant to be used by instances of
-+        :class:`MixedIntegerLinearProgram`. Also, use the
-+        :func:`LinearConstraintsParent` factory function.
-+
-+    INPUT/OUTPUT: 
-+        
-+        See :func:`LinearFunctionsParent`
-+
-+    EXAMPLES::
-+
-+        sage: p = MixedIntegerLinearProgram()
-+        sage: LC = p.linear_constraints_parent();  LC
-+        Linear constraints over Real Double Field
-+        sage: from sage.numerical.linear_functions import LinearConstraintsParent
-+        sage: LinearConstraintsParent(p.linear_functions_parent()) is LC
-+        True
-+    """
-+
-+    def __init__(self, linear_functions_parent):
-+        """
-+        The Python constructor
-+        
-+        INPUT/OUTPUT: 
-+        
-+        See :func:`LinearFunctionsParent`
-+
-+        TESTS::
-+
-+            sage: from sage.numerical.linear_functions import LinearFunctionsParent
-+            sage: LF = LinearFunctionsParent(RDF)
-+            sage: from sage.numerical.linear_functions import LinearConstraintsParent
-+            sage: LinearConstraintsParent(LF)
-+            Linear constraints over Real Double Field
-+        """
-+        Parent.__init__(self)
-+        self._LF = linear_functions_parent
-+
-+    def linear_functions_parent(self):
-+        """
-+        Return the parent for the linear functions
-+
-+        EXAMPLES::
-+
-+            sage: LC = MixedIntegerLinearProgram().linear_constraints_parent()
-+            sage: LC.linear_functions_parent()
-+            Linear functions over Real Double Field
-+        """
-+        return self._LF
-+
-+    def _repr_(self):
-+        """
-+        Return a string representation
-+
-+        OUTPUT:
-+
-+        String.
-+        
-+        EXAMPLES::
-+        
-+            sage: MixedIntegerLinearProgram().linear_constraints_parent()
-+            Linear constraints over Real Double Field
-+        """
-+        return 'Linear constraints over '+str(self.linear_functions_parent().base_ring())
-+
-+    cpdef _element_constructor_(self, left, right=None, equality=False):
-+        """
-+        Construt a :class:`LinearConstraint`.
-+
-+        INPUT:
-+
-+        - ``left`` -- a :class:`LinearFunction`, or something that can
-+          be converted into one, a list/tuple of
-+          :class:`LinearFunction`, or an existing
-+          :class:`LinearConstraint`.
-+          
-+        - ``right`` -- a :class:`LinearFunction` or ``None``
-+          (default).
-+
-+        - ``equality`` -- boolean (default: ``True``). Whether to
-+          construct an equation or an inequality.
-+          
-+        OUTPUT:
-+
-+        The :class:`LinearConstraint` constructed from the input data.
-+
-+        EXAMPLES::
-+        
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: LC = p.linear_constraints_parent()
-+            sage: LC._element_constructor_(1, 2)
-+            1 <= 2
-+
-+            sage: x = p.new_variable()
-+            sage: LC([x[0], x[1], x[2]])
-+            x_0 <= x_1 <= x_2
-+
-+            sage: LC([x[0], x[1], x[2]], equality=True)
-+            x_0 == x_1 == x_2
-+            
-+            sage: type(_)
-+            <type 'sage.numerical.linear_functions.LinearConstraint'>
-+
-+        TESTS::
-+
-+            sage: inequality = LC([x[0], 1/2*x[1], 3/4*x[2]]); inequality
-+            x_0 <= 0.5*x_1 <= 0.75*x_2
-+            sage: LC(inequality) is inequality
-+            True
-+            sage: p_QQ = MixedIntegerLinearProgram(solver='ppl')
-+            sage: LC_QQ = p_QQ.linear_constraints_parent()
-+            sage: LC_QQ(inequality)
-+            x_0 <= 1/2*x_1 <= 3/4*x_2
-+            sage: LC_QQ(inequality) is inequality
-+            False
-+        """
-+        if right is None and is_LinearConstraint(left):
-+            if (left.parent() is self) and (left.is_equation() == equality):
-+                return left
-+            else:
-+                return LinearConstraint(self, (<LinearConstraint>left).constraints, 
-+                                        equality=equality)
-+        if right is None:
-+            if isinstance(left, (list,tuple)):
-+                return LinearConstraint(self, left, equality=equality)
-+            else:
-+                return LinearConstraint(self, [left], equality=equality)
-+        else:
-+            return LinearConstraint(self, [left, right], equality=equality)
-+
-+    cpdef _coerce_map_from_(self, R):
-+        """
-+        Allow coercion of scalars into linear functions.
-+
-+        EXAMPLES::
-+        
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: parent = p.linear_constraints_parent()
-+            sage: parent.coerce(int(2))
-+            trivial constraint starting with 2
-+            sage: parent._coerce_map_from_(int)
-+            True
-+        """
-+        return self.linear_functions_parent().has_coerce_map_from(R)
-+
-+    def _an_element_(self):
-+        """
-+        Returns an element
-+
-+        EXAMPLES::
-+
-+            sage: p = MixedIntegerLinearProgram().linear_functions_parent()
-+            sage: p._an_element_()
-+            5*x_2 + 7*x_5
-+            sage: p.an_element()   # indirect doctest
-+            5*x_2 + 7*x_5
-+        """
-+        LF = self.linear_functions_parent()
-+        return self(0) <= LF.an_element()
-+
-+
-+    
-+#*****************************************************************************
-+#
-+# Elements of linear constraints
-+#
-+#*****************************************************************************
-+
-+_chained_comparator_hack_search = None
-+_chained_comparator_hack_replace = None
-+
-+cdef class LinearConstraint(Element):
-+    """
-+    A class to represent formal Linear Constraints.
-+
-+    A Linear Constraint being an inequality between
-+    two linear functions, this class lets the user
-+    write ``LinearFunction1 <= LinearFunction2``
-+    to define the corresponding constraint, which
-+    can potentially involve several layers of such
-+    inequalities (``(A <= B <= C``), or even equalities
-+    like ``A == B``.
-+
-+    Trivial constraints (meaning that they have only one term and no
-+    relation) are also allowed. They are required for the coercion
-+    system to work.
-+    
-+    .. warning::
-+
-+        This class has no reason to be instanciated by the user, and
-+        is meant to be used by instances of
-+        :class:`MixedIntegerLinearProgram`.
-+
-+    INPUT:
-+
-+    - ``parent`` -- the parent, a :class:`LinearConstraintsParent_class`
-+
-+    - ``terms`` -- a list/tuple/iterable of two or more linear
-+      functions (or things that can be converted into linear
-+      functions).
-+
-+    - ``equality`` -- boolean (default: ``False``). Whether the terms
-+      are the entries of a chained less-or-equal (``<=``) inequality
-+      or a chained equality.
-+
-+    EXAMPLE::
-+
-+        sage: p = MixedIntegerLinearProgram()
-+        sage: b = p.new_variable()
-+        sage: b[2]+2*b[3] <= b[8]-5
-+        x_0 + 2*x_1 <= -5 + x_2
-+    """
-+
-+    def __init__(self, parent, terms, equality=False):
-+        r"""
-+        Constructor for ``LinearConstraint``
-+
-+        INPUT:
-+
-+        See :class:`LinearConstraint`.
-+
-+        EXAMPLE::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: b = p.new_variable()
-+            sage: b[2]+2*b[3] <= b[8]-5
-+            x_0 + 2*x_1 <= -5 + x_2
-+        """
-+        assert len(terms) > 0
-+        super(LinearConstraint, self).__init__(parent)
-+        self.equality = equality
-+        LF = parent.linear_functions_parent()
-+        self.constraints = [ LF(term) for term in terms ]
-+
-+    cpdef equals(LinearConstraint left, LinearConstraint right):
-+        """
-+        Compare ``left`` and ``right``.
-+
-+        OUTPUT:
-+
-+        Boolean. Whether all terms of ``left`` and ``right`` are
-+        equal. Note that this is stronger than mathematical
-+        equivalence of the relations.
-+
-+        EXAMPLES::
-+
-+            sage: p = MixedIntegerLinearProgram()
-+            sage: x = p.new_variable()
-+            sage: (x[1] + 1 >= 2).equals(3/3 + 1*x[1] + 0*x[2] >= 8/4)
-+            True
-+            sage: (x[1] + 1 >= 2).equals(x[1] + 1-1 >= 1-1)
-+            False
-+        """
-+        if len(left.constraints) != len(right.constraints):
-+            return False
-+        if left.equality != right.equality:
-+            return False
-+        cdef LinearFunction l, r
-+        for i in range(len(left.constraints)):
-+            l = <LinearFunction>(left.constraints[i])
-+            r = <LinearFunction>(right.constraints[i])