sparsity.cc

Go to the documentation of this file.

// Sparsity structure computation -*- C++ -*-

// $Id: sparsity.cc 554 2008-04-10 20:35:22Z herman $
// Copyright (C) 2001-2008 Hermann Schichl, Mihaly Csaba Markot
//
// This file is a COCONUT inference engine.  This library
// is free software; you can redistribute it and/or modify it under the
// terms of the Library GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// Library GNU General Public License for more details.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the Library GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the Library GNU General Public License.

#include <coconut_config.h>
#include <dag.h>
#include <model.h>
#include <vector>
#include <algorithm>
#include <g_algo.h>
#include <cmath>
#include <set>
#include <api_exception.h>
#include <array_vector.h>
#include <sparsity.h>

#define SP_DBG 0

namespace coco {


typedef std::pair<unsigned int, unsigned int> ipair;

typedef std::set<ipair> splist;


class sparsity_visitor : public preorder_visitor<expression_node,
                                                 const variable_indicator&,
                                                 const variable_indicator&>
{
  splist& sp_list;
  variable_indicator v;
  unsigned int numvars;
  unsigned int n;
  int base;

private:
  void make_clique()
  {
#if SP_DBG
    std::cout << "in make_clique" << std::endl;
#endif
    for(unsigned int i=0; i<numvars; i++)
    {
      if(!v.test(i)) continue;
      sp_list.insert(std::make_pair(i+base,i+base));
      for(unsigned int j=i+1; j<numvars; j++)
        if(v.test(j))
          sp_list.insert(std::make_pair(i+base,j+base));
    }
  }

  void make_bipartite(const variable_indicator& __vn)
  {
#if SP_DBG
    std::cout << "in make_bipartite" << std::endl;
#endif
    for(unsigned int i=0; i<numvars; i++)
    {
      if(!v.test(i)) continue;
      for(unsigned int j=0; j<numvars; j++)
        if(__vn.test(j))
          sp_list.insert(std::make_pair(std::min(i,j)+base,std::max(i,j)+base));
    }
  }

public:
  sparsity_visitor(splist &__o, int __n, bool __b = false) : sp_list(__o),
                                        numvars(__n), base(__b ? 1 : 0)
    { }

  sparsity_visitor(const sparsity_visitor& __c) : sp_list(__c.sp_list),
                                                v(__c.v), numvars(__c.numvars),
                                                base(__c.base)
    { }


  bool preorder(const expression_node &r)
  {
#if SP_DBG
    std::cout << "in preorder: " << r.operator_type << std::endl;
#endif
    bool rval = false;
    n = 0;

    v = r.v_i;

#if SP_DBG
    std::cout << "v - after v=r.v_i: " << std::endl;
    for(unsigned int i=0; i<numvars; i++)
      if(v.test(i)) std::cout << i << " ";
    std::cout << std::endl;
#endif

    if(r.operator_type < 0)
    {
      switch(r.operator_type)
      {
        case EXPRINFO_CONSTANT:
        case EXPRINFO_VARIABLE:
        case EXPRINFO_LIN:
          break;
        case EXPRINFO_SUM:
        case EXPRINFO_MEAN:
          rval = true;
          break;
        case EXPRINFO_PROD:
        case EXPRINFO_SCPROD:
          rval = true;
          v.clear();
          break;
        case EXPRINFO_MONOME:
          throw nyi_exception("sparsity_evaluator: MONOME!");
          break;
        case EXPRINFO_INTPOWER:
          if(r.params.nn() == 1)
            rval = true;
          else
            make_clique();
          break;
        case EXPRINFO_POLY:
          if(r.params.d().size() <= 2)
            rval = true;
          else
            make_clique();
          break;
        case EXPRINFO_POW:
        case EXPRINFO_INVERT:
        case EXPRINFO_DIV:
        case EXPRINFO_MAX:
        case EXPRINFO_MIN:
        case EXPRINFO_SQUARE:
        case EXPRINFO_SQROOT:
        case EXPRINFO_EXP:
        case EXPRINFO_LOG:
        case EXPRINFO_SIN:
        case EXPRINFO_COS:
        case EXPRINFO_ATAN2:
        case EXPRINFO_GAUSS:
        case EXPRINFO_ABS:
        case EXPRINFO_NORM:
        case EXPRINFO_LOOKUP:
        case EXPRINFO_PWLIN:
        case EXPRINFO_SPLINE:
        case EXPRINFO_PWCONSTLC:
        case EXPRINFO_PWCONSTRC:
        case EXPRINFO_IN:
        case EXPRINFO_IF:
        case EXPRINFO_AND:
        case EXPRINFO_OR:
        case EXPRINFO_NOT:
        case EXPRINFO_IMPLIES:
        case EXPRINFO_COUNT:
        case EXPRINFO_ALLDIFF:
        case EXPRINFO_HISTOGRAM:
        case EXPRINFO_LEVEL:
        case EXPRINFO_NEIGHBOR:
        case EXPRINFO_NOGOOD:
        case EXPRINFO_EXPECTATION:
        case EXPRINFO_INTEGRAL:
        case EXPRINFO_DET:
        case EXPRINFO_COND:
        case EXPRINFO_PSD:
        case EXPRINFO_MPROD:
        case EXPRINFO_FEM:
        case EXPRINFO_CMPROD:
        case EXPRINFO_CGFEM:
          make_clique();
          break;
        case EXPRINFO_QUAD:
          for(linalg::matrix<double>::iterator __r = r.params.m().begin();
              __r != r.params.m().end(); ++__r)
            for(linalg::matrix<double>::OneD::iterator __c = (*__r).begin();
                __c != (*__r).end(); ++__c)
              if(__c.column() >= __c.row())
                sp_list.insert(std::make_pair(__c.row()+base,
                                              __c.column()+base));
          break;
        default:
          throw api_exception(apiee_internal,
              std::string("sparsity_evaluator: unknown operator type ")+
              convert_to_str(r.operator_type));
          break;
      }
    }
    else if(r.operator_type > 0)
    {
      make_clique();
    }
    else
      throw api_exception(apiee_internal,
              std::string("sparsity_evaluator: cannot handle GHOST nodes!"));
    return rval;
  }
  
  const variable_indicator& vvalue() { return v; }
  const variable_indicator& value() { return v; }

  void collect(const expression_node &r, const variable_indicator& __v)
  { 
#if SP_DBG
    std::cout << "in collect: " << r.operator_type << std::endl;
#endif

    if(r.operator_type < 0)
    {
      switch(r.operator_type)
      {
        case EXPRINFO_PROD:
#if SP_DBG
          std::cout << "__v - before make_bipartite: " << std::endl;
          for(unsigned int i=0; i<numvars; i++)
            if(__v.test(i)) std::cout << i << " ";
          std::cout << std::endl;
          std::cout << "v - before make_bipartite: " << std::endl;
          for(unsigned int i=0; i<numvars; i++)
            if(v.test(i)) std::cout << i << " ";
          std::cout << std::endl;

          std::cout << "splist - before make_bipartite: " << std::endl;
          for(splist::const_iterator b=sp_list.begin(); b!=sp_list.end(); ++b)
            std::cout << b->first << "  " << b->second << std::endl;
          std::cout << "end splist " << std::endl;
#endif

          make_bipartite(__v);

#if SP_DBG
          std::cout << "splist - after make_bipartite: " << std::endl;
          for(splist::const_iterator b=sp_list.begin(); b!=sp_list.end(); ++b)
            std::cout << b->first << "  " << b->second << std::endl;
          std::cout << "end splist " << std::endl;
#endif

          v.set_all(__v);

#if SP_DBG
          std::cout << "v - after set_all: " << std::endl;
          for(unsigned int i=0; i<numvars; i++)
            if(v.test(i)) std::cout << i << " ";
          std::cout << std::endl;
#endif

          break;
        case EXPRINFO_CONSTANT:
        case EXPRINFO_VARIABLE:
        case EXPRINFO_INVERT:
        case EXPRINFO_SUM:
        case EXPRINFO_MAX:
        case EXPRINFO_MIN:
        case EXPRINFO_DIV:
        case EXPRINFO_INTPOWER:
        case EXPRINFO_SQUARE:
        case EXPRINFO_POW:
        case EXPRINFO_SQROOT:
        case EXPRINFO_EXP:
        case EXPRINFO_LOG:
        case EXPRINFO_SIN:
        case EXPRINFO_COS:
        case EXPRINFO_ATAN2:
        case EXPRINFO_GAUSS:
        case EXPRINFO_LIN:
        case EXPRINFO_QUAD:
        case EXPRINFO_ABS:
        case EXPRINFO_NORM:
        case EXPRINFO_LOOKUP:
        case EXPRINFO_PWLIN:
        case EXPRINFO_SPLINE:
        case EXPRINFO_PWCONSTLC:
        case EXPRINFO_PWCONSTRC:
        case EXPRINFO_IN:
        case EXPRINFO_IF:
        case EXPRINFO_AND:
        case EXPRINFO_OR:
        case EXPRINFO_NOT:
        case EXPRINFO_IMPLIES:
        case EXPRINFO_COUNT:
        case EXPRINFO_ALLDIFF:
        case EXPRINFO_HISTOGRAM:
        case EXPRINFO_LEVEL:
        case EXPRINFO_NEIGHBOR:
        case EXPRINFO_NOGOOD:
        case EXPRINFO_EXPECTATION:
        case EXPRINFO_INTEGRAL:
        case EXPRINFO_DET:
        case EXPRINFO_COND:
        case EXPRINFO_PSD:
        case EXPRINFO_MPROD:
        case EXPRINFO_FEM:
        case EXPRINFO_CMPROD:
        case EXPRINFO_CGFEM:
          break;
        case EXPRINFO_SCPROD:
          if((n&1) == 0)
            v = __v;
          else
          {
#if SP_DBG
            std::cout << "in collect - SCPROD" << std::endl;
#endif
            make_bipartite(__v);
          }
          if(n == r.n_children)
            v = r.v_i;
          break;
        case EXPRINFO_MONOME:
          throw nyi_exception("sparsity_evaluator: MONOME!");
          break;
        default:
          throw api_exception(apiee_internal,
              std::string("sparsity_evaluator: unknown operator type ")+
              convert_to_str(r.operator_type));
          break;
      }
    }
    else if(r.operator_type > 0)
    {
      ;
    }
    n++;
  }
};


static void row2column_wise(std::vector<unsigned int>& ridx,
                            std::vector<unsigned int>& cidx,
                            const bool row_one_based,
                            const bool col_one_based)
{
  if (!ridx.empty())
  {
    unsigned int i,j;

    unsigned int roffset = row_one_based ? 1 : 0;
    unsigned int coffset = col_one_based ? 1 : 0;

    // determine maximal column index - these may occur in the last elements
    // of each block in cidx
    unsigned int maxcol = col_one_based ? 1 : 0;
    for (i=1; i<ridx.size(); ++i) // always 1
      if (cidx[ridx[i]-1-roffset] > maxcol) // always 1
        maxcol = cidx[ridx[i]-1-roffset]; // always 1
    if (cidx.back() > maxcol)
      maxcol = cidx.back();

    // create buffer for the column indices    
    std::vector<std::vector<unsigned int> > buf(maxcol+1-coffset);

    // fill buffer
    for (i=0; i<ridx.size()-1; ++i) // always 0, and 1
    {
      for (j=ridx[i]-roffset; j<ridx[i+1]-roffset; ++j)
        buf[cidx[j]-coffset].push_back(i+roffset);
    }
    for (j=ridx.back()-roffset; j<cidx.size(); ++j)
      buf[cidx[j]-coffset].push_back(i+roffset);
    
    // clear original data
    ridx.clear();
    cidx.clear();

    // fill ridx and cidx from buf
    unsigned int last = coffset;
    for (std::vector<std::vector<unsigned int> >::const_iterator c=buf.begin();
          c!=buf.end(); ++c)
    {
      ridx.insert(ridx.end(),c->begin(),c->end());
      cidx.push_back(last);
      last += c->size();
    }
  }
  else  // if ridx is empty, then so does cidx => we need not do anything
  {
    ;
  }
}



static void _sparsity(const model& DAG, std::vector<unsigned int>& H_ridx,
              std::vector<unsigned int>& H_cidx,
              std::vector<unsigned int>& J_funidx,
              std::vector<unsigned int>& J_varidx,
              bool J_with_obj, bool J_obj_is_first, bool org_only,
              bool H_upper_only, bool with_H, bool with_J, sp_indexing indexing,
              bool fun_one_based, bool var_one_based)
{
  unsigned int i=0;

  if(with_H)
  {
    splist sparse_matrix;
    sparsity_visitor s(sparse_matrix, DAG.number_of_variables(), var_one_based);

    if(!DAG.objective.is_ground())
      recursive_preorder_walk_if(DAG.objective, s);

#if SP_DBG
    std::cout << "splist - after preorder walk on objective : " << std::endl;
    for(splist::const_iterator b=sparse_matrix.begin(); b!=sparse_matrix.end(); ++b)
      std::cout << b->first << "  " << b->second << std::endl;
    std::cout << "end splist " << std::endl;
#endif

    for(std::vector<expression_walker>::const_iterator b =
        DAG.constraints.begin(); b != DAG.constraints.end(); ++b)
    {
#if SP_DBG
      std::cout << "constraint properties: " << (*b)->is(ex_bound)
      << "  " << org_only << "  " << (*b)->is(ex_kj) << std::endl;
#endif
      if(!((*b)->is(ex_bound) || (org_only && (*b)->is(ex_kj))))
#if SP_DBG
      {
        std::cout << "call recursive_preorder_walk_if" << std::endl;
#endif
        recursive_preorder_walk_if(*b, s);
#if SP_DBG
      }
#endif
    }

#if SP_DBG
    std::cout << "splist - after preorder walks on constraints: " << std::endl;
    for(splist::const_iterator b=sparse_matrix.begin(); b!=sparse_matrix.end(); ++b)
      std::cout << b->first << "  " << b->second << std::endl;
    std::cout << "end splist " << std::endl;
#endif

    if(indexing == full_indexing)
    {
      // producing the Hessian row index vector of the objective
      for(splist::iterator b=sparse_matrix.begin(); b!=sparse_matrix.end(); ++b)
      {
        H_ridx.push_back((*b).first);
        if(!H_upper_only && (*b).first != (*b).second)
          H_ridx.push_back((*b).second);
      }
      // producing the Hessian column index vector of the objective
      for(splist::iterator b=sparse_matrix.begin(); b!=sparse_matrix.end(); ++b)
      {
        H_cidx.push_back((*b).second);
        if(!H_upper_only && (*b).first != (*b).second)
          H_cidx.push_back((*b).first);
      }
    }
    else // row or column-wise indexing - we do it row-wise and transpose when
         // necessary
    {
      if(!H_upper_only)
      {
        splist _H;
        for(splist::iterator b=sparse_matrix.begin(); b!=sparse_matrix.end();
            ++b)
          if((*b).first != (*b).second)
            _H.insert(std::make_pair((*b).second, (*b).first));
        sparse_matrix.insert(_H.begin(), _H.end());
      }
      i = var_one_based ? 1 : 0;
      unsigned int last = i-1;
      for(splist::iterator b=sparse_matrix.begin(); b!=sparse_matrix.end(); ++b)
      {
        if(last != (*b).first)
        {
          for(++last; last != (*b).first; ++last)
            H_ridx.push_back(i);
          H_ridx.push_back(i);
        }
        H_cidx.push_back((*b).second);
        ++i;
      }
        // transpose the structure for column_wise indexing      
      if (indexing == column_wise_indexing)
        row2column_wise(H_ridx,H_cidx,var_one_based,var_one_based);
    }
  }

  if(with_J)
  {
    int base = var_one_based ? 1 : 0;
    i = fun_one_based ? 1 : 0;
    if(J_with_obj && J_obj_is_first)
    {
      if(indexing == full_indexing)
      {
        J_funidx.insert(J_funidx.end(),
            DAG.objective.is_ground() ? 0 : DAG.objective->sem.dim, i);
        ++i;
      }
      else // row or column-wise indexing - we do everything row-wise and
           // transpose at the end when necessary
      {
        J_funidx.push_back(i);
        if(!DAG.objective.is_ground())
          i += DAG.objective->sem.dim;
      }
      for(unsigned int j=0; j<DAG.number_of_variables(); j++)
      {
        if(!DAG.objective.is_ground() && DAG.objective->v_i.test(j))
          J_varidx.push_back(j+base);
      }
    }
    // compute the row and column index vectors of the Jacobian
    for(std::vector<expression_walker>::const_iterator
        b = DAG.constraints.begin(); b != DAG.constraints.end(); ++b)
    {
      if((*b)->is(ex_bound) || (org_only && (*b)->is(ex_kj))) continue;
      if(indexing == full_indexing)
      {
        J_funidx.insert(J_funidx.end(), (*b)->sem.dim, i);
        ++i;
      }
      else
      {
        J_funidx.push_back(i);
        i += (*b)->sem.dim;
      }
      for(unsigned int j=0; j<DAG.number_of_variables(); j++)
      {
        if((*b)->v_i.test(j))
          J_varidx.push_back(j+base);
      }
    }
    if(J_with_obj && !J_obj_is_first)
    {
      if(indexing == full_indexing)
        J_funidx.insert(J_funidx.end(), 
            DAG.objective.is_ground() ? 0 : DAG.objective->sem.dim, i);
      else
        J_funidx.push_back(i);
      for(unsigned int j=0; j<DAG.number_of_variables(); j++)
      {
        if(!DAG.objective.is_ground() && DAG.objective->v_i.test(j))
          J_varidx.push_back(j+base);
      }
    }
    
      // transpose the structure for column_wise indexing      
    if (indexing == column_wise_indexing)
      row2column_wise(J_funidx,J_varidx,fun_one_based,var_one_based);
    
  } // if with_J
}

void sparsity(const model& DAG, std::vector<unsigned int>& H_ridx,
              std::vector<unsigned int>& H_cidx,
              std::vector<unsigned int>& J_funidx,
              std::vector<unsigned int>& J_varidx,
              bool J_with_obj, bool J_obj_is_first, bool org_only,
              bool H_upper_only, sp_indexing indexing, bool fun_one_based,
              bool var_one_based)
{
  _sparsity(DAG, H_ridx, H_cidx, J_funidx, J_varidx, J_with_obj, J_obj_is_first,
            org_only, H_upper_only, true, true, indexing, fun_one_based,
            var_one_based);
}

void sparsity(const model& DAG, std::vector<unsigned int>& H_ridx,
              std::vector<unsigned int>& H_cidx,
              bool org_only, bool H_upper_only,
              sp_indexing indexing, bool var_one_based)
{
  std::vector<unsigned int> _dummy;
  _sparsity(DAG, H_ridx, H_cidx, _dummy, _dummy, false, false, org_only,
            H_upper_only, true, false, indexing, false, var_one_based);
}

void sparsity(const model& DAG, std::vector<unsigned int>& J_funidx,
              std::vector<unsigned int>& J_varidx,
              bool J_with_obj, bool J_obj_is_first, bool org_only,
              sp_indexing indexing, bool fun_one_based, bool var_one_based)
{
  std::vector<unsigned int> _dummy;
  _sparsity(DAG, _dummy, _dummy, J_funidx, J_varidx, J_with_obj, J_obj_is_first,
            org_only, false, false, true, indexing, fun_one_based,
            var_one_based);
}

void sparsity(const model& DAG, unsigned int &nnz_H, unsigned int *&H_ridx,
              unsigned int *&H_cidx, unsigned int &nnz_J,
              unsigned int *&J_funidx, unsigned int *&J_varidx,
              bool J_with_obj, bool J_obj_is_first, bool org_only,
              bool H_upper_only, sp_indexing indexing, bool fun_one_based,
              bool var_one_based)
{
  std::vector<unsigned int> _Hr;
  std::vector<unsigned int> _Hc;
  std::vector<unsigned int> _Jf;
  std::vector<unsigned int> _Jv;
  array_vector<unsigned int> __h;

  _sparsity(DAG, _Hr, _Hc, _Jf, _Jv, J_with_obj, J_obj_is_first, org_only,
            H_upper_only, true, true, indexing, fun_one_based, var_one_based);
  nnz_H = _Hc.size();
  H_ridx = new unsigned int [_Hr.size()];
  H_cidx = new unsigned int [nnz_H];
  nnz_J = _Jv.size();
  J_funidx = new unsigned int [_Jf.size()];
  J_varidx = new unsigned int [nnz_J];

  __h.assignvector(H_ridx, _Hr.size());
  __h.copy_into(_Hr);
  __h.assignvector(H_cidx, nnz_H);
  __h.copy_into(_Hc);
  __h.assignvector(J_funidx, _Jf.size());
  __h.copy_into(_Jf);
  __h.assignvector(J_varidx, nnz_J);
  __h.copy_into(_Jv);
}

void sparsity(const model& DAG, int &nnz_H, int *&H_ridx, int *&H_cidx,
              int &nnz_J, int *&J_funidx, int *&J_varidx,
              bool J_with_obj, bool J_obj_is_first, bool org_only,
              bool H_upper_only, sp_indexing indexing, bool fun_one_based,
              bool var_one_based)
{
  sparsity(DAG, *(unsigned int *)&nnz_H, (unsigned int *&)H_ridx,
           (unsigned int *&)H_cidx, *(unsigned int *)&nnz_J,
           (unsigned int *&)J_funidx, (unsigned int *&)J_varidx, J_with_obj,
           J_obj_is_first, org_only, H_upper_only, indexing,
           fun_one_based, var_one_based);
}

void sparsity(const model& DAG, unsigned int &nnz_H,
              unsigned int *&H_ridx, unsigned int *&H_cidx, bool org_only,
              bool H_upper_only, sp_indexing indexing, bool fun_one_based,
              bool var_one_based)
{
  std::vector<unsigned int> _Hr;
  std::vector<unsigned int> _Hc;
  std::vector<unsigned int> _dummy;
  array_vector<unsigned int> __h;

  _sparsity(DAG, _Hr, _Hc, _dummy, _dummy, false, false, org_only, H_upper_only,
            true, false, indexing, fun_one_based, var_one_based);
  nnz_H = _Hc.size();
  H_ridx = new unsigned int [_Hr.size()];
  H_cidx = new unsigned int [nnz_H];

  __h.assignvector(H_ridx, _Hr.size());
  __h.copy_into(_Hr);
  __h.assignvector(H_cidx, nnz_H);
  __h.copy_into(_Hc);
}

void sparsity(const model& DAG, int &nnz_H, int *&H_ridx, int *&H_cidx,
              bool org_only, bool H_upper_only, sp_indexing indexing,
              bool var_one_based)
{
  sparsity(DAG, *(unsigned int*)&nnz_H, (unsigned int *&)H_ridx,
     (unsigned int *&)H_cidx, org_only, H_upper_only, indexing,
     false, var_one_based);
}

void sparsity(const model& DAG, unsigned int &nnz_J, unsigned int *&J_funidx,
              unsigned int *&J_varidx, bool J_with_obj, bool J_obj_is_first,
              bool org_only, sp_indexing indexing, bool fun_one_based,
              bool var_one_based)
{
  std::vector<unsigned int> _dummy;
  std::vector<unsigned int> _Jf;
  std::vector<unsigned int> _Jv;
  array_vector<unsigned int> __h;

  _sparsity(DAG, _dummy, _dummy, _Jf, _Jv, J_with_obj, J_obj_is_first,
            org_only, false, false, true, indexing, fun_one_based,
            var_one_based);
  nnz_J = _Jv.size();
  J_funidx = new unsigned int [_Jf.size()];
  J_varidx = new unsigned int [nnz_J];

  __h.assignvector(J_funidx, _Jf.size());
  __h.copy_into(_Jf);
  __h.assignvector(J_varidx, nnz_J);
  __h.copy_into(_Jv);
}


void sparsity(const model& DAG, int &nnz_J, int *&J_funidx, int *&J_varidx,
              bool J_with_obj, bool J_obj_is_first, bool org_only,
              sp_indexing indexing, bool fun_one_based, bool var_one_based)
{
  sparsity(DAG, *(unsigned int *)&nnz_J, (unsigned int *&)J_funidx,
           (unsigned int *&)J_varidx, J_with_obj, J_obj_is_first, org_only,
           indexing, fun_one_based, var_one_based);
}


} // namespace coco

---