# HG changeset patch
# User alpar
# Date 1111664665 0
# Node ID 609fe893df8c6c7c877f24e6bfe3e26c2db6a4cf
# Parent  4fee8e9d901470cad8939069d4d08249bdc9ac48
- simple makefile added
- _FixId class added (more clarification needed)
- LinExpr class added
- some higher level interfaces added to LpSolverBase
- minor corrections

diff -r 4fee8e9d9014 -r 609fe893df8c src/work/athos/lp/Makefile
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/athos/lp/Makefile	Thu Mar 24 11:44:25 2005 +0000
@@ -0,0 +1,3 @@
+lp_base.o: lp_base.cc lp_base.h lin_expr.h
+
+	g++ -Wall -ggdb --no-inline -I../../.. -c $<
\ No newline at end of file
diff -r 4fee8e9d9014 -r 609fe893df8c src/work/athos/lp/lin_expr.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/athos/lp/lin_expr.h	Thu Mar 24 11:44:25 2005 +0000
@@ -0,0 +1,71 @@
+/* -*- C++ -*-
+ * src/lemon/lin_expr.h - Part of LEMON, a generic C++ optimization library
+ *
+ * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Combinatorial Optimization Research Group, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#ifndef LEMON_LIN_EXPR_H
+#define LEMON_LIN_EXPR_H
+
+#include<vector>
+
+
+#include<map>
+
+///\file
+///\brief Classes to handle linear expressions
+namespace lemon {
+  
+  /// Class to handle sparse linear expressions
+  template <class _V,class _C>
+  class SparseLinExpr : public std::map<_V, _C>
+  {
+  public:
+    typedef _V Var; 
+    typedef _C Coeff;
+    
+  protected:
+    typedef typename std::map<_V, _C> Base;
+
+    Coeff const_comp;
+  public:
+    SparseLinExpr() { }
+    SparseLinExpr(const Var &v) : const_comp(v) {
+      Base::insert(std::make_pair(v, 1));
+    }
+    SparseLinExpr(const Coeff &v) : const_comp(v) {}
+    
+    void set(const Var &v,const Coeff &c) {
+      return Base::insert(std::make_pair(v, c));
+    }
+//     Coeff &operator[](const Var &v) { return data[v]; }
+//     const Coeff &operator[](const Var &v) const { return data[v]; }
+
+    Coeff &constComp() { return const_comp; }
+    const Coeff &constComp() const { return const_comp; }
+
+    ///Removes the components with zero coefficient.
+    void simplify() {
+      for (typename Base::iterator i=Base::begin(); i!=Base::end();) {
+	typename Base::iterator j=i;
+	++j;
+	if ((*i).second==0) Base::erase(i);
+	j=i;
+      }
+    }
+   
+  };
+
+} //namespace lemon
+
+#endif //LEMON_LIN_EXPR_H
diff -r 4fee8e9d9014 -r 609fe893df8c src/work/athos/lp/lp_base.cc
--- a/src/work/athos/lp/lp_base.cc	Wed Mar 23 16:59:13 2005 +0000
+++ b/src/work/athos/lp/lp_base.cc	Thu Mar 24 11:44:25 2005 +0000
@@ -1,5 +1,5 @@
 /* -*- C++ -*-
- * src/lemon/maps.h - Part of LEMON, a generic C++ optimization library
+ * src/lib/lp_base.cc - Part of LEMON, a generic C++ optimization library
  *
  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Combinatorial Optimization Research Group, EGRES).
@@ -14,15 +14,12 @@
  *
  */
 
-#ifndef LEMON_LP_BASE_CC
-#define LEMON_LP_BASE_CC
-
 ///\file
 ///\brief The implementation of the LP solver interface.
 
 #include "lp_base.h"
 namespace lemon {
 
+
+
 } //namespace lemon
-
-#endif //LEMON_LP_BASE_CC
diff -r 4fee8e9d9014 -r 609fe893df8c src/work/athos/lp/lp_base.h
--- a/src/work/athos/lp/lp_base.h	Wed Mar 23 16:59:13 2005 +0000
+++ b/src/work/athos/lp/lp_base.h	Thu Mar 24 11:44:25 2005 +0000
@@ -1,5 +1,5 @@
 /* -*- C++ -*-
- * src/lemon/maps.h - Part of LEMON, a generic C++ optimization library
+ * src/lemon/lp_base.h - Part of LEMON, a generic C++ optimization library
  *
  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
  * (Egervary Combinatorial Optimization Research Group, EGRES).
@@ -17,19 +17,100 @@
 #ifndef LEMON_LP_BASE_H
 #define LEMON_LP_BASE_H
 
+#include<vector>
+
+#include<lemon/error.h>
+
+#include"lin_expr.h"
 ///\file
 ///\brief The interface of the LP solver interface.
 namespace lemon {
+  
+  ///Internal data structure to convert floating id's to fix one's
+    
+  ///\todo This might by implemented to be usable in other places.
+  class _FixId 
+  {
+    std::vector<int> index;
+    std::vector<int> cross;
+    int first_free;
+  public:
+    _FixId() : first_free(-1) {};
+    ///Convert a floating id to a fix one
+
+    ///\param n is a floating id
+    ///\return the corresponding fix id
+    int fixId(int n) {return cross[n];}
+    ///Convert a fix id to a floating one
+
+    ///\param n is a fix id
+    ///\return the corresponding floating id
+    int floatingId(int n) { return index[n];}
+    ///Add a new floating id.
+
+    ///\param n is a floating id
+    ///\return the fix id of the new value
+    ///\todo Multiple additions should also be handled.
+    int insert(int n)
+    {
+      if(n>=int(cross.size())) {
+	cross.resize(n+1);
+	if(first_free==-1) {
+	  cross[n]=index.size();
+	  index.push_back(n);
+	}
+	else {
+	  cross[n]=first_free;
+	  int next=index[first_free];
+	  index[first_free]=n;
+	  first_free=next;
+	}
+      }
+      else throw LogicError(); //floatingId-s must form a continuous range;
+    }
+    ///Remove a fix id.
+
+    ///\param n is a fix id
+    ///
+    void erase(int n) 
+    {
+      int fl=index[n];
+      index[n]=first_free;
+      first_free=n;
+      for(int i=fl+1;i<int(cross.size());++i) {
+	cross[i-1]=cross[i];
+	index[cross[i]]--;
+      }
+      cross.pop_back();
+    }
+    ///An upper bound on the largest fix id.
+
+    ///\todo Do we need this?
+    ///
+    std::size_t maxFixId() { return cross.size()-1; }
+  
+  };
+    
+  ///Common base class for LP solvers
   class LpSolverBase {
+    
   public:
 
-    //UNCATEGORIZED
-
     /// \e
     typedef double Value;
     /// \e 
     static const Value INF;
-   protected:
+    
+    ///\e
+    class Col { protected: int id; friend class LpSolverBase; };
+    ///\e
+    class Row { protected: int id; friend class LpSolverBase; };
+
+    typedef SparseLinExpr<Col, Value> Expr;
+
+  protected:
+    _FixId rows;
+    _FixId cols;
 
     //MATRIX MANIPULATING FUNCTIONS
 
@@ -38,34 +119,42 @@
     /// \e
     virtual int _addRow() = 0;
     /// \e
+
     /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
+    ///
     virtual void _setRowCoeffs(int i, 
 			       int length,
                                int  const * indices, 
                                Value  const * values ) = 0;
     /// \e
+
     /// \warning Arrays are indexed from 1 (datum at index 0 is ignored)
+    ///
     virtual void _setColCoeffs(int i, 
 			       int length,
                                int  const * indices, 
                                Value  const * values ) = 0;
     
     /// \e
+
     /// The lower bound of a variable (column) have to be given by an 
     /// extended number of type Value, i.e. a finite number of type 
     /// Value or -INF.
     virtual void _setColLowerBound(int i, Value value) = 0;
     /// \e
+
     /// The upper bound of a variable (column) have to be given by an 
     /// extended number of type Value, i.e. a finite number of type 
     /// Value or INF.
     virtual void _setColUpperBound(int i, Value value) = 0;
     /// \e
+
     /// The lower bound of a linear expression (row) have to be given by an 
     /// extended number of type Value, i.e. a finite number of type 
     /// Value or -INF.
     virtual void _setRowLowerBound(int i, Value value) = 0;
     /// \e
+
     /// The upper bound of a linear expression (row) have to be given by an 
     /// extended number of type Value, i.e. a finite number of type 
     /// Value or INF.
@@ -73,6 +162,90 @@
 
     /// \e
     virtual void _setObjCoeff(int i, Value obj_coef) = 0;
+
+    ///\e
+
+    ///\bug unimplemented!!!!
+    void clearObj() {}
+  public:
+
+
+    ///\e
+    virtual ~LpSolverBase() {}
+
+    ///Add a new empty column (i.e a new variable) to the LP
+    Col addCol() { Col c; c.id=cols.insert(_addCol()); return c;}
+    ///Add a new empty row (i.e a new constaint) to the LP
+    Row addRow() { Row r; r.id=rows.insert(_addRow()); return r;}
+
+    ///Add a new row (i.e a new constaint) to the LP
+
+    ///\param l lower bound (-INF means no bound)
+    ///\param e a linear expression (see \ref Expr)
+    ///\param u upper bound (INF means no bound)
+    ///\bug This is a temportary function. The interface will change to
+    ///a better one.
+    Row addRow(Value l,Expr e, Value u) {
+      Row r=addRow();
+      std::vector<int> indices;
+      std::vector<Value> values;
+      indices.push_back(0);
+      values.push_back(0);
+      for(Expr::iterator i=e.begin(); i!=e.end(); ++i) {
+	indices.push_back(cols.floatingId((*i).first.id));
+	values.push_back((*i).second);
+      }
+      _setRowCoeffs(rows.floatingId(r.id),indices.size()-1,
+		    &indices[0],&values[0]);
+      _setRowLowerBound(rows.floatingId(r.id),l);
+      _setRowUpperBound(rows.floatingId(r.id),l);
+      return r;
+    }
+
+    /// Set the lower bound of a column (i.e a variable)
+
+    /// The upper bound of a variable (column) have to be given by an 
+    /// extended number of type Value, i.e. a finite number of type 
+    /// Value or -INF.
+    virtual void setColLowerBound(Col c, Value value) {
+      _setColLowerBound(cols.floatingId(c.id),value);
+    }
+    /// Set the upper bound of a column (i.e a variable)
+
+    /// The upper bound of a variable (column) have to be given by an 
+    /// extended number of type Value, i.e. a finite number of type 
+    /// Value or INF.
+    virtual void setColUpperBound(Col c, Value value) {
+      _setColUpperBound(cols.floatingId(c.id),value);
+    };
+    /// Set the lower bound of a row (i.e a constraint)
+
+    /// The lower bound of a linear expression (row) have to be given by an 
+    /// extended number of type Value, i.e. a finite number of type 
+    /// Value or -INF.
+    virtual void setRowLowerBound(Row r, Value value) {
+      _setRowLowerBound(rows.floatingId(r.id),value);
+    };
+    /// Set the upper bound of a row (i.e a constraint)
+
+    /// The upper bound of a linear expression (row) have to be given by an 
+    /// extended number of type Value, i.e. a finite number of type 
+    /// Value or INF.
+    virtual void setRowUpperBound(Row r, Value value) {
+      _setRowUpperBound(rows.floatingId(r.id),value);
+    };
+    ///Set an element of the objective function
+    void setObjCoeff(Col c, Value v) {_setObjCoeff(cols.floatingId(c.id),v); };
+    ///Set the objective function
+    
+    ///\param e is a linear expression of type \ref Expr.
+    ///\todo What to do with the constant component?
+    void setObj(Expr e) {
+      clearObj();
+      for (Expr::iterator i=e.begin(); i!=e.end(); ++i)
+	setObjCoeff((*i).first,(*i).second);
+    }
+    
   };  
 
 } //namespace lemon