sc_simplex_feasibility.h File Reference

This header provides functions to test whether a constraint system is feasible, using the simplex method. More...

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <strings.h>
#include <limits.h>
#include "boolean.h"
#include "assert.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"

Include dependency graph for sc_simplex_feasibility.h:

Go to the source code of this file.

Data Structures
struct	vec_s
	Type of vectors. More...
struct	constr_s
	Type of linear constraint. More...
struct	table_s
	Type of simplex tableau. More...
struct	vartbl_s
	Type of variable tables. More...

Macros
#define	DEBUG(code)   {}

Functions
static void *	safe_malloc (size_t size)
static bool	sc_get_feasibility (Psysteme sys, int ofl_ctrl)
	Main Function. More...

Variables
Each variable is represented by a non-negative, integer value.
#define	VAR_NULL   (-1)
	A special value used to represent the absence of variable. More...
#define	VAR_MAXNB   (1971)
	Maximum number of variables. More...
#define	var_fprint(stream, var)   (fprintf(stream, "x%d", var))
	Output var on stdio stream stream. More...
#define	var_print(var)   (var_fprint(stdout, var))
	Output var on stdout. More...
typedef int	var_t
	Type of variables. More...

Vectors
A vector is a structure to map each variable to a rational value.
#define	VEC_NULL   NULL
	The empty vector. More...
#define	vec_init(vec)   (vec = VEC_NULL)
	Set vec to be the empty vector. More...
#define	vec_print(vec)   (vec_fprint(stdout, vec))
	Output vec on stdout. More...
typedef struct vec_s	vec_s
	Type of vectors. More...
typedef struct vec_s *	vec_p
static void	vec_clear (vec_p *pvec)
	Free the space occupied by pvec. More...
static void	vec_set (vec_p *pvec, vec_p vec)
	Copy vec into pvec. More...
static void	vec_append_atfirst (vec_p *pvec, var_t var, qval_t coeff)
	Add the element (var, @coeff) to pvec, in first position. More...
static void	vec_append (vec_p *pvec, var_t var, qval_t coeff)
	Add the element (var, coeff) to pvec. More...
static void	vec_get_coeff (qval_t coeff, vec_p vec, var_t var)
	Get the value associated to var in vec, and store it into coeff. More...
static void	vec_iadd (vec_p *pvec, vec_p vec)
	Set pvec to pvec + vec. More...
static void	vec_imul (vec_p *pvec, qval_t coeff)
	Set pvec to coeff times pvec. More...
static void	vec_iaddmul (vec_p *pvec, qval_t coeff, vec_p vec)
	Set pvec to pvec + coeff times vec. More...
static void	vec_ineg (vec_p vec)
	Set vec to -vec. More...
static int NOWUNUSED	vec_fprint (FILE *stream, vec_p vec)
	Output vec on stdio stream stream. More...

Linear Constraints
A linear constraint is either a linear equality (a1 x1 + ... an xn = b) or a linear inequality (a1 x1 + ... + an xn <= b).
#define	constr_get_coeff(coeff, constr, var)    (vec_get_coeff(coeff, (constr)->vec, var))
	Get the coefficient of var in constr, and store it into coeff. More...
#define	constr_print(constr)   (constr_fprint(stdout, constr))
	Output constr on stdout. More...
enum	constrrel_t { CONSTR_EQ , CONSTR_LE }
	Type of linear constraint relations. More...
typedef struct constr_s	constr_s
	Type of linear constraint. More...
typedef struct constr_s *	constr_p
typedef constr_s	constr_t[1]
	Type of linear constraint. More...
static void	constr_init (constr_p constr)
	Initialize constr and set it to 0 = 0. More...
static void	constr_clear (constr_p constr)
	Free the space occupied by constr. More...
static void NOWUNUSED	constr_set (constr_p constr1, constr_p constr2)
	Copy constr2 into constr1. More...
static void	constr_iadd (constr_p constr1, constr_p constr2)
	Set constr1 to constr1 + constr2. More...
static void	constr_imul (constr_p constr, qval_t coeff)
	Set constr to coeff times constr. More...
static void	constr_iaddmul (constr_p constr1, qval_t coeff, constr_p constr2)
	Set constr1 to constr1 + coeff times constr2. More...
static void	constr_makepos (constr_p constr)
	Turn constr into an equivalent constraint whose constant term is non-negative. More...
static void	constr_apply_pivot (constr_p constr, var_t pivot_var, constr_p pivot_constr)
	Make pivot_var coefficient null in constr, using pivot_constr. More...
static int NOWUNUSED	constr_fprint (FILE *stream, constr_p constr)
	Output constr on stdio stream stream. More...

Simplex Tableau
A simplex tableau consists in a list of constraint, an objective function to minimize and its current value. Those data evolve when the simplex is running.
#define	table_get_nbvars(tbl)   ((tbl)->nbvars)
	Number of variables in tbl. More...
#define	table_get_nbconstrs(tbl)   ((tbl)->nbconstrs)
	Number of constraints in tbl. More...
#define	table_print(tbl)   (table_fprint(stdout, tbl))
	Output tbl on stdout. More...
typedef struct table_s	table_s
	Type of simplex tableau. More...
typedef struct table_s *	table_p
typedef table_s	table_t[1]
	Type of simplex tableau. More...
static void	table_init (table_p tbl, int nbconstrs)
	Initialize tbl, with room for nbconstrs constraints. More...
static void	table_clear (table_p tbl)
	Free the space occupied by tbl. More...
static void	table_makepos (table_p tbl)
	Turn constraints into tbl into equivalent ones, whose constant term is non-negative. More...
static void	table_addsignvars (table_p tbl)
	Ensure that all variables in tbl are non-negative. More...
static void	table_addofsvars (table_p tbl)
	Ensure that all constraints in tbl are equalities. More...
static int NOWUNUSED	table_fprint (FILE *stream, table_p tbl)
	Output tbl on stdio stream stream. More...
static void	table_canonicalize (table_p tbl)
	Canonicalize tbl: ensure that all variables are non-negative, and all constraints are equalities whose constant term is non-negative. More...
static void	table_set_obj (table_p tbl)
	Initialize the objective function and value from constraints in tbl. More...
static void	table_addobjvars (table_p tbl)
	Add objective variables to each constraint of @tbl whose constant term is not zero. More...
static void	table_prepare (table_p tbl)
	Canonicalize tbl, set the objective and add objective variables. More...
static var_t	table_get_pivotvar (table_p tbl)
	Get the next pivot variable in @tbl. More...
static var_t	table_get_assocvar (table_p tbl, int row)
	Retrieve the variable associated with the row (i.e. More...
static int	table_get_pivotrow (table_p tbl, var_t var)
static bool	table_get_pivot (table_p tbl, var_t *pvar, int *prow)
	Get the next pivot variable and row in @tbl, and store them in pvar and prow respectively. More...
static void	table_apply_pivot (table_p tbl, var_t var, int row)
	Apply pivot (var, row) in tbl. More...
static void	table_run_simplex (table_p tbl)
	Run simplex algorithm on @tbl. More...
static bool	table_get_feasibility (table_p tbl)
	Determine whether the constraint system described in tbl is feasible, using simplex method. More...

Datatype Conversion
Here are utility functions to convert Linear types (Variable, Vecteur, Contrainte, Systeme) to datatypes used in this files. In most of conversion functions, a variable table vartbl is passed, to help translating Linear named variables into indices.
#define	vartbl_clear(vartbl)
	Free the space occupied by vartbl. More...
typedef struct vartbl_s *	vartbl_p
typedef vartbl_s	vartbl_t[1]
	Type of variable tables. More...
static void	vartbl_init (vartbl_p vartbl)
	Initialize @vartbl to an empty table. More...
static var_t	vartbl_find (vartbl_p vartbl, Variable name)
	Get the variable index associated to name, creating a new one if necessary. More...
static void	vec_set_vecteur (vartbl_t vartbl, vec_p *pvec, Pvecteur vec)
	Copy vec into pvec. More...
static void	constr_set_contrainte (vartbl_t vartbl, constr_p constr1, Pcontrainte constr2, bool is_ineq)
	Copy constr2 into constr1. More...
static void	table_init_set_systeme (table_p tbl, Psysteme sys)
	Initialize tbl from sys. More...

Detailed Description

This header provides functions to test whether a constraint system is feasible, using the simplex method.

It can be used with any of the headers arith_fixprec.c or arith_mulprec.c, this in fixed- or multiple-precision.

Definition in file sc_simplex_feasibility.h.

Macro Definition Documentation

constr_get_coeff

#define constr_get_coeff	(		coeff,
			constr,
			var
	)		(vec_get_coeff(coeff, (constr)->vec, var))

Get the coefficient of var in constr, and store it into coeff.

Definition at line 415 of file sc_simplex_feasibility.h.

constr_print

#define constr_print

(

constr

)

(constr_fprint(stdout, constr))

Output constr on stdout.

Definition at line 504 of file sc_simplex_feasibility.h.

DEBUG

#define DEBUG

(

code

)

{}

Definition at line 50 of file sc_simplex_feasibility.h.

table_get_nbconstrs

#define table_get_nbconstrs

(

tbl

)

((tbl)->nbconstrs)

Number of constraints in tbl.

Definition at line 569 of file sc_simplex_feasibility.h.

table_get_nbvars

#define table_get_nbvars

(

tbl

)

((tbl)->nbvars)

Number of variables in tbl.

Definition at line 564 of file sc_simplex_feasibility.h.

table_print

#define table_print

(

tbl

)

(table_fprint(stdout, tbl))

Output tbl on stdout.

Definition at line 961 of file sc_simplex_feasibility.h.

var_fprint

#define var_fprint	(		stream,
			var
	)		(fprintf(stream, "x%d", var))

Output var on stdio stream stream.

Definition at line 90 of file sc_simplex_feasibility.h.

VAR_MAXNB

#define VAR_MAXNB   (1971)

Maximum number of variables.

Definition at line 85 of file sc_simplex_feasibility.h.

VAR_NULL

#define VAR_NULL   (-1)

A special value used to represent the absence of variable.

Definition at line 80 of file sc_simplex_feasibility.h.

var_print

#define var_print

(

var

)

(var_fprint(stdout, var))

Output var on stdout.

Definition at line 95 of file sc_simplex_feasibility.h.

vartbl_clear

#define vartbl_clear

(

vartbl

)

Free the space occupied by vartbl.

Definition at line 998 of file sc_simplex_feasibility.h.

vec_init

#define vec_init

(

vec

)

(vec = VEC_NULL)

Set vec to be the empty vector.

Definition at line 125 of file sc_simplex_feasibility.h.

VEC_NULL

#define VEC_NULL   NULL

The empty vector.

Definition at line 120 of file sc_simplex_feasibility.h.

vec_print

#define vec_print

(

vec

)

(vec_fprint(stdout, vec))

Output vec on stdout.

Definition at line 348 of file sc_simplex_feasibility.h.

Typedef Documentation

constr_p

typedef struct constr_s * constr_p

constr_s

typedef struct constr_s constr_s

Type of linear constraint.

constr_t

typedef constr_s constr_t[1]

Type of linear constraint.

Definition at line 381 of file sc_simplex_feasibility.h.

table_p

typedef struct table_s * table_p

table_s

typedef struct table_s table_s

Type of simplex tableau.

The objective function and the associated value are stored into a constraint obj, other constraints are in the constraint table constr.

table_t

typedef table_s table_t[1]

Type of simplex tableau.

Definition at line 531 of file sc_simplex_feasibility.h.

var_t

typedef int var_t

Type of variables.

Definition at line 75 of file sc_simplex_feasibility.h.

vartbl_p

typedef struct vartbl_s * vartbl_p

vartbl_t

typedef vartbl_s vartbl_t[1]

Type of variable tables.

Definition at line 985 of file sc_simplex_feasibility.h.

vec_p

typedef struct vec_s * vec_p

vec_s

typedef struct vec_s vec_s

Type of vectors.

Typically, most of values are equal to zero, so a sparse, linked-list structure is used. Internally, variables are ordered by decreasing order.

Enumeration Type Documentation

constrrel_t

enum constrrel_t

Type of linear constraint relations.

Enumerator
CONSTR_EQ	equality
CONSTR_LE	inequality

Definition at line 363 of file sc_simplex_feasibility.h.

{
        CONSTR_EQ, /**< equality */
        CONSTR_LE /**< inequality */
} constrrel_t;

Function Documentation

constr_apply_pivot()

static void constr_apply_pivot ( constr_p  constr, var_t  pivot_var, constr_p  pivot_constr  )

static

Make pivot_var coefficient null in constr, using pivot_constr.

pivot_constr must be an equality.

Definition at line 474 of file sc_simplex_feasibility.h.

{
        qval_t coeff;
        qval_init(coeff);
        constr_get_coeff(coeff, constr, pivot_var);
        qval_neg(coeff, coeff);
        constr_iaddmul(constr, coeff, pivot_constr);
        qval_clear(coeff);
}

References constr_get_coeff, constr_iaddmul(), qval_clear, qval_init, and qval_neg.

Referenced by table_apply_pivot().

Here is the call graph for this function:

Here is the caller graph for this function:

constr_clear()

static void constr_clear ( constr_p  constr )

static

Free the space occupied by constr.

Definition at line 396 of file sc_simplex_feasibility.h.

{
        vec_clear(&constr->vec);
        qval_clear(constr->cst);
}

References constr_s::cst, qval_clear, constr_s::vec, and vec_clear().

Referenced by table_clear().

Here is the call graph for this function:

Here is the caller graph for this function:

constr_fprint()

static int NOWUNUSED constr_fprint ( FILE *  stream, constr_p  constr  )

static

Output constr on stdio stream stream.

Definition at line 488 of file sc_simplex_feasibility.h.

{
        int c = vec_fprint(stream, constr->vec);
        if (constr->rel == CONSTR_EQ) {
                c += fprintf(stream, " == ");
        }
        else {
                c += fprintf(stream, " <= ");
        }
        c += qval_fprint(stream, constr->cst);
        return c;
}

References CONSTR_EQ, constr_s::cst, fprintf(), qval_fprint, constr_s::rel, constr_s::vec, and vec_fprint().

Referenced by table_fprint().

Here is the call graph for this function:

Here is the caller graph for this function:

constr_iadd()

static void constr_iadd ( constr_p  constr1, constr_p  constr2  )

static

Set constr1 to constr1 + constr2.

constr2 must be an equality.

Definition at line 422 of file sc_simplex_feasibility.h.

{
        // general case is not needed
        assert(constr2->rel == CONSTR_EQ);
        vec_iadd(&constr1->vec, constr2->vec);
        qval_add(constr1->cst, constr1->cst, constr2->cst);
}

References assert, CONSTR_EQ, constr_s::cst, qval_add, constr_s::rel, constr_s::vec, and vec_iadd().

Referenced by table_set_obj().

Here is the call graph for this function:

Here is the caller graph for this function:

constr_iaddmul()

static void constr_iaddmul ( constr_p  constr1, qval_t  coeff, constr_p  constr2  )

static

Set constr1 to constr1 + coeff times constr2.

constr2 must be an equality or coeff a non-negative value.

Definition at line 444 of file sc_simplex_feasibility.h.

{
        if (!qval_equal_i(coeff, 0, 1)) {
                vec_iaddmul(&constr1->vec, coeff, constr2->vec);
                qval_t tmp;
                qval_init(tmp);
                qval_mul(tmp, coeff, constr2->cst);
                qval_add(constr1->cst, constr1->cst, tmp);
                qval_clear(tmp);
        }
}

References constr_s::cst, qval_add, qval_clear, qval_equal_i, qval_init, qval_mul, constr_s::vec, and vec_iaddmul().

Referenced by constr_apply_pivot().

Here is the call graph for this function:

Here is the caller graph for this function:

constr_imul()

static void constr_imul ( constr_p  constr, qval_t  coeff  )

static

Set constr to coeff times constr.

constr must be an equality or coeff a non-negative value.

Definition at line 434 of file sc_simplex_feasibility.h.

{
        vec_imul(&constr->vec, coeff);
        qval_mul(constr->cst, constr->cst, coeff);
}

References constr_s::cst, qval_mul, constr_s::vec, and vec_imul().

Referenced by table_apply_pivot().

Here is the call graph for this function:

Here is the caller graph for this function:

constr_init()

static void constr_init ( constr_p  constr )

static

Initialize constr and set it to 0 = 0.

Definition at line 386 of file sc_simplex_feasibility.h.

{
        vec_init(constr->vec);
        constr->rel = CONSTR_EQ;
        qval_init(constr->cst);
}

References CONSTR_EQ, constr_s::cst, qval_init, constr_s::rel, constr_s::vec, and vec_init.

Referenced by table_init().

Here is the caller graph for this function:

constr_makepos()

static void constr_makepos ( constr_p  constr )

static

Turn constr into an equivalent constraint whose constant term is non-negative.

constr must be an equality.

Definition at line 461 of file sc_simplex_feasibility.h.

{
        assert(constr->rel == CONSTR_EQ);
        if (qval_cmp_i(constr->cst, 0, 1) < 0) {
                vec_ineg(constr->vec);
                qval_neg(constr->cst, constr->cst);
        }
}

References assert, CONSTR_EQ, constr_s::cst, qval_cmp_i, qval_neg, constr_s::rel, constr_s::vec, and vec_ineg().

Referenced by table_makepos().

Here is the call graph for this function:

Here is the caller graph for this function:

constr_set()

static void NOWUNUSED constr_set ( constr_p  constr1, constr_p  constr2  )

static

Copy constr2 into constr1.

Definition at line 405 of file sc_simplex_feasibility.h.

{
        vec_set(&constr1->vec, constr2->vec);
        constr1->rel = constr2->rel;
        qval_set(constr1->cst, constr2->cst);
}

References constr_s::cst, qval_set, constr_s::rel, constr_s::vec, and vec_set().

Here is the call graph for this function:

constr_set_contrainte()

static void constr_set_contrainte ( vartbl_t  vartbl, constr_p  constr1, Pcontrainte  constr2, bool  is_ineq  )

static

Copy constr2 into constr1.

Definition at line 1037 of file sc_simplex_feasibility.h.

{
        vec_set_vecteur(vartbl, &constr1->vec, constr2->vecteur);
        constr1->rel = is_ineq ? CONSTR_LE : CONSTR_EQ;
        Pvecteur vec;
        for (vec = constr2->vecteur; vec != NULL; vec = vec->succ) {
                if (vec->var == TCST) {
                        qval_set_i(constr1->cst, -vec->val, 1);
                        break;
                }
        }
}

References CONSTR_EQ, CONSTR_LE, constr_s::cst, qval_set_i, constr_s::rel, Svecteur::succ, TCST, Svecteur::val, Svecteur::var, constr_s::vec, vec_set_vecteur(), and Scontrainte::vecteur.

Referenced by table_init_set_systeme().

Here is the call graph for this function:

Here is the caller graph for this function:

safe_malloc()

static void* safe_malloc ( size_t  size )

static

Definition at line 56 of file sc_simplex_feasibility.h.

{
        void* m = malloc(size);
        if (m == NULL) {
                fprintf(stderr, "[" __FILE__ "] out of memory\n");
                abort();
        }
        return m;
}

References abort, fprintf(), and malloc().

Referenced by sc_get_feasibility(), table_init(), vec_append_atfirst(), vec_iadd(), vec_iaddmul(), and vec_set().

Here is the call graph for this function:

Here is the caller graph for this function:

sc_get_feasibility()

static bool sc_get_feasibility ( Psysteme  sys, int  ofl_ctrl  )

inlinestatic

Main Function.

Determine whether a system sys of equations and inequations is feasible. Parameter ofl_ctrl indicates whether an overflow control is performed (possible values: NO_OFL_CTRL, FWD_OFL_CTRL).

Definition at line 1085 of file sc_simplex_feasibility.h.

{
        if (ofl_ctrl != FWD_OFL_CTRL) {
                fprintf(stderr, "[sc_simplexe_feasibility] "
                        "should not (yet) be called with control %d...\n", ofl_ctrl);
        }
        volatile table_p tbl = safe_malloc(sizeof(table_t));
        table_init_set_systeme(tbl, sys);
        CATCH(simplex_arithmetic_error | timeout_error | overflow_error) {
                table_clear(tbl);
                free(tbl);
                if (ofl_ctrl == FWD_OFL_CTRL) {
                        RETHROW();
                }
                return true;
        }
        bool feasible = table_get_feasibility(tbl);
        table_clear(tbl);
        free(tbl);
        UNCATCH(simplex_arithmetic_error | timeout_error | overflow_error);
        return feasible;
}

References CATCH, fprintf(), free(), FWD_OFL_CTRL, overflow_error, RETHROW, safe_malloc(), simplex_arithmetic_error, table_clear(), table_get_feasibility(), table_init_set_systeme(), timeout_error, and UNCATCH.

Here is the call graph for this function:

table_addobjvars()

static void table_addobjvars ( table_p  tbl )

static

Add objective variables to each constraint of @tbl whose constant term is not zero.

Definition at line 728 of file sc_simplex_feasibility.h.

{
        qval_t one;
        qval_init(one); qval_set_i(one, 1, 1);
        int i;
        for (i = 0; i < tbl->nbconstrs; i++) {
                constr_p constr = tbl->constrs[i];
                assert(qval_cmp_i(constr->cst, 0, 1) >= 0);
                if (!qval_equal_i(constr->cst, 0, 1)) {
                        var_t var = tbl->nbvars;
                        vec_append_atfirst(&constr->vec, var, one);
                        tbl->nbvars++;
                }
        }
        qval_clear(one);
}

References assert, table_s::constrs, constr_s::cst, table_s::nbconstrs, table_s::nbvars, qval_clear, qval_cmp_i, qval_equal_i, qval_init, qval_set_i, constr_s::vec, and vec_append_atfirst().

Referenced by table_prepare().

Here is the call graph for this function:

Here is the caller graph for this function:

table_addofsvars()

static void table_addofsvars ( table_p  tbl )

static

Ensure that all constraints in tbl are equalities.

A new offset variable is introduced into inequalities to turn them in equalities. E.g., inequality a1 x1 + ... + an xn <= b becomes: a1 x1 + ... + an xn + y = b.

Definition at line 666 of file sc_simplex_feasibility.h.

{
        qval_t one;
        qval_init(one); qval_set_i(one, 1, 1);
        int i;
        for (i = 0; i < tbl->nbconstrs; i++) {
                constr_p constr = tbl->constrs[i];
                if (constr->rel == CONSTR_LE) {
                        vec_append_atfirst(&constr->vec, tbl->nbvars, one);
                        tbl->nbvars++;
                        constr->rel = CONSTR_EQ;
                }
        }
        qval_clear(one);
}

References CONSTR_EQ, CONSTR_LE, table_s::constrs, table_s::nbconstrs, table_s::nbvars, qval_clear, qval_init, qval_set_i, constr_s::rel, constr_s::vec, and vec_append_atfirst().

Referenced by table_canonicalize().

Here is the call graph for this function:

Here is the caller graph for this function:

table_addsignvars()

static void table_addsignvars ( table_p  tbl )

static

Ensure that all variables in tbl are non-negative.

Each occurrence of a unknown-sign variable a x is turned into a x+ - a x-, where @x+ and @x- are new, non-negative variables. Each occurrence of a negative variable a x is turned into -a x', where x' is a new, non-negative variable. We try to do this only when necessary, to limit the amount of newly created variables.

Definition at line 593 of file sc_simplex_feasibility.h.

{
        // first, we try to determine the sign of variables
        static int vars_info[VAR_MAXNB]; // -1 negative or null, +1 positive or null, 0 unknown
        int i;
        for (i = 0; i < VAR_MAXNB; i++) {
                vars_info[i] = 0;
        }
        for (i = 0; i < tbl->nbconstrs; i++) {
                constr_p constr = tbl->constrs[i];
                vec_p vec = constr->vec;
                if (vec != VEC_NULL && vec->succ == VEC_NULL) {
                        var_t var = vec->var;
                        int lsign = value_sign(qval_cmp_i(vec->coeff, 0, 1));
                        assert(lsign != 0);
                        int rsign = value_sign(qval_cmp_i(constr->cst, 0, 1));
                        int sign;
                        if (constr->rel == CONSTR_EQ) {
                                sign = rsign == 0 ? 1 : lsign * rsign;
                        }
                        else {
                                sign = rsign == 0 ? -lsign : (rsign == 1 ? 0 : lsign * rsign);
                        }
                        if (sign != 0 && vars_info[var] == 0) {
                                vars_info[var] = sign;
                        }
                }
        }
        // negative variables are inverted
        for (i = 0; i < tbl->nbconstrs; i++) {
                constr_p constr = tbl->constrs[i];
                vec_p vec;
                for (vec = constr->vec; vec != VEC_NULL; vec = vec->succ) {
                        var_t var = vec->var;
                        if (vars_info[var] < 0) {
                                qval_neg(vec->coeff, vec->coeff);
                        }
                }
        }
        // unknown sign variables are split
        var_t var;
        for (var = tbl->nbvars - 1; var >= 0; var--) {
                if (vars_info[var] == 0) {
                        vars_info[var] = tbl->nbvars;
                        tbl->nbvars++;
                }
                else {
                        vars_info[var] = VAR_NULL;
                }
        }
        // and then, injected into constraints
        qval_t coeff;
        qval_init(coeff);
        for (i = 0; i < tbl->nbconstrs; i++) {
                constr_p constr = tbl->constrs[i];
                vec_p vec;
                for (vec = constr->vec; vec != VEC_NULL; vec = vec->succ) {
                        var_t var = vec->var;
                        if (vars_info[var] != VAR_NULL) {
                                qval_neg(coeff, vec->coeff);
                                vec_append_atfirst(&constr->vec, vars_info[var], coeff);
                        }
                }
        }
        qval_clear(coeff);
}

References assert, vec_s::coeff, CONSTR_EQ, table_s::constrs, constr_s::cst, table_s::nbconstrs, table_s::nbvars, qval_clear, qval_cmp_i, qval_init, qval_neg, constr_s::rel, vec_s::succ, value_sign, vec_s::var, VAR_MAXNB, VAR_NULL, constr_s::vec, vec_append_atfirst(), and VEC_NULL.

Referenced by table_canonicalize().

Here is the call graph for this function:

Here is the caller graph for this function:

table_apply_pivot()

static void table_apply_pivot ( table_p  tbl, var_t  var, int  row  )

static

Apply pivot (var, row) in tbl.

Definition at line 865 of file sc_simplex_feasibility.h.

{
        constr_p constr = tbl->constrs[row];
        // pivot constraint is normalized s.t. its coefficient on var is 1
        qval_t coeff;
        qval_init(coeff);
        constr_get_coeff(coeff, constr, var);
        qval_inv(coeff, coeff);
        constr_imul(constr, coeff);
        qval_clear(coeff);
        // then is substracted from other constraints s.t. the coefficient on var is 0
        constr_apply_pivot(tbl->obj, var, constr);
        int i;
        for (i = 0; i < tbl->nbconstrs; i++) {
                if (i != row) {
                        constr_apply_pivot(tbl->constrs[i], var, constr);
                }
        }
}

References constr_apply_pivot(), constr_get_coeff, constr_imul(), table_s::constrs, table_s::nbconstrs, table_s::obj, qval_clear, qval_init, and qval_inv.

Referenced by table_run_simplex().

Here is the call graph for this function:

Here is the caller graph for this function:

table_canonicalize()

static void table_canonicalize ( table_p  tbl )

static

Canonicalize tbl: ensure that all variables are non-negative, and all constraints are equalities whose constant term is non-negative.

Definition at line 688 of file sc_simplex_feasibility.h.

{
        DEBUG(
                fprintf(stderr, "Initial system:\n");
                table_fprint(stderr, tbl);
        );
        table_addsignvars(tbl);
        DEBUG(
                fprintf(stderr, "\nWith signed variables:\n");
                table_fprint(stderr, tbl);
        );
        table_addofsvars(tbl);
        DEBUG(
                fprintf(stderr, "\nWith offset variables:\n");
                table_fprint(stderr, tbl);
        );
        table_makepos(tbl);
        DEBUG(
                fprintf(stderr, "\nWith positive constants:\n");
                table_fprint(stderr, tbl);
        );
}

References DEBUG, fprintf(), table_addofsvars(), table_addsignvars(), table_fprint(), and table_makepos().

Referenced by table_prepare().

Here is the call graph for this function:

Here is the caller graph for this function:

table_clear()

static void table_clear ( table_p  tbl )

static

Free the space occupied by tbl.

Definition at line 551 of file sc_simplex_feasibility.h.

{
        constr_clear(tbl->obj);
        int i;
        for (i = 0; i < tbl->nbconstrs; i++) {
                constr_clear(tbl->constrs[i]);
        }
        free(tbl->constrs);
}

References constr_clear(), table_s::constrs, free(), table_s::nbconstrs, and table_s::obj.

Referenced by sc_get_feasibility().

Here is the call graph for this function:

Here is the caller graph for this function:

table_fprint()

static int NOWUNUSED table_fprint ( FILE *  stream, table_p  tbl  )

static

Output tbl on stdio stream stream.

Definition at line 930 of file sc_simplex_feasibility.h.

{
        int c = constr_fprint(stream, tbl->obj);
        c += fprintf(stream, "\n");
        int i;
        for (i = 0; i < 40; i++) {
                c += fprintf(stream, "-");
        }
        c += fprintf(stream, "\n");
        if (tbl->nbconstrs == 0) {
                c += fprintf(stream, "true\n");
        }
        else {
                for (i = 0; i < tbl->nbconstrs; i++) {
                        c += fprintf(stream, "(%2d: ", i);
                        c += var_fprint(stream, table_get_assocvar(tbl, i));
                        c += fprintf(stream, ") ");
                        c += constr_fprint(stream, tbl->constrs[i]);
                        c += fprintf(stream, "\n");
                }
        }
        for (i = 0; i < 40; i++) {
                c += fprintf(stream, "-");
        }
        c += fprintf(stream, "\n");
        return c;
}

References constr_fprint(), table_s::constrs, fprintf(), table_s::nbconstrs, table_s::obj, table_get_assocvar(), and var_fprint.

Referenced by table_canonicalize(), table_prepare(), and table_run_simplex().

Here is the call graph for this function:

Here is the caller graph for this function:

table_get_assocvar()

static var_t table_get_assocvar ( table_p  tbl, int  row  )

static

Retrieve the variable associated with the row (i.e.

constraint) row in tbl.

Definition at line 781 of file sc_simplex_feasibility.h.

{
        if (row != -1) {
                qval_t tmp;
                qval_init(tmp);
                constr_p constr = tbl->constrs[row];
                vec_p vec;
                for (vec = constr->vec; vec != VEC_NULL; vec = vec->succ) {
                        if (qval_equal_i(vec->coeff, 1, 1)) {
                                var_t var = vec->var;
                                bool unitcol = true;
                                int i;
                                for (i = 0; i < tbl->nbconstrs; i++) {
                                        if (i != row) {
                                                constr_get_coeff(tmp, tbl->constrs[i], var);
                                                if (!qval_equal_i(tmp, 0, 1)) {
                                                        unitcol = false;
                                                        break;
                                                }
                                        }
                                }
                                if (unitcol) {
                                        return var;
                                }
                        }
                }
                qval_clear(tmp);
        }
        return VAR_NULL;
}

References vec_s::coeff, constr_get_coeff, table_s::constrs, table_s::nbconstrs, qval_clear, qval_equal_i, qval_init, vec_s::succ, vec_s::var, VAR_NULL, constr_s::vec, and VEC_NULL.

Referenced by table_fprint(), and table_get_pivotrow().

Here is the caller graph for this function:

table_get_feasibility()

static bool table_get_feasibility ( table_p  tbl )

static

Determine whether the constraint system described in tbl is feasible, using simplex method.

Definition at line 920 of file sc_simplex_feasibility.h.

{
        table_prepare(tbl);
        table_run_simplex(tbl);
        return qval_equal_i(tbl->obj->cst, 0, 1);
}

References table_s::obj, qval_equal_i, table_prepare(), and table_run_simplex().

Referenced by sc_get_feasibility().

Here is the call graph for this function:

Here is the caller graph for this function:

table_get_pivot()

static bool table_get_pivot ( table_p  tbl, var_t *  pvar, int *  prow  )

static

Get the next pivot variable and row in @tbl, and store them in pvar and prow respectively.

Definition at line 855 of file sc_simplex_feasibility.h.

{
        *pvar = table_get_pivotvar(tbl);
        *prow = table_get_pivotrow(tbl, *pvar);
        return *prow != -1;
}

References table_get_pivotrow(), and table_get_pivotvar().

Referenced by table_run_simplex().

Here is the call graph for this function:

Here is the caller graph for this function:

table_get_pivotrow()

static int table_get_pivotrow ( table_p  tbl, var_t  var  )

static

Definition at line 818 of file sc_simplex_feasibility.h.

{
        int pivot_row = -1;
        if (var != VAR_NULL) {
                var_t pivot_assoc = VAR_NULL;
                qval_t pivot_ratio, ratio;
                qval_init(pivot_ratio); qval_init(ratio);
                int i;
                for (i = 0; i < tbl->nbconstrs; i++) {
                        constr_p constr = tbl->constrs[i];
                        constr_get_coeff(ratio, constr, var);
                        if (qval_cmp_i(ratio, 0, 1) > 0) {
                                assert(qval_cmp_i(constr->cst, 0, 1) >= 0);
                                qval_div(ratio, constr->cst, ratio);
                                if (pivot_row == -1 || qval_cmp(ratio, pivot_ratio) < 0) {
                                        pivot_row = i;
                                        pivot_assoc = table_get_assocvar(tbl, pivot_row);
                                        qval_set(pivot_ratio, ratio);
                                }
                                else if (qval_cmp(ratio, pivot_ratio) == 0) {
                                        var_t assoc = table_get_assocvar(tbl, i);
                                        if (assoc < pivot_assoc) {
                                                pivot_row = i;
                                                pivot_assoc = assoc;
                                        }
                                }
                        }
                }
                qval_clear(pivot_ratio); qval_clear(ratio);
        }
        return pivot_row;
}

References assert, constr_get_coeff, table_s::constrs, constr_s::cst, table_s::nbconstrs, qval_clear, qval_cmp, qval_cmp_i, qval_div, qval_init, qval_set, table_get_assocvar(), and VAR_NULL.

Referenced by table_get_pivot().

Here is the call graph for this function:

Here is the caller graph for this function:

table_get_pivotvar()

static var_t table_get_pivotvar ( table_p  tbl )

static

Get the next pivot variable in @tbl.

Bland's rule is used to ensure termination: pivot variable is the lowest-numbered variable whose objective coefficient is negative.

Definition at line 765 of file sc_simplex_feasibility.h.

{
        var_t var = VAR_NULL;
        vec_p vec;
        for (vec = tbl->obj->vec; vec != VEC_NULL; vec = vec->succ) {
                if (qval_cmp_i(vec->coeff, 0, 1) > 0) {
                        var = vec->var;
                }
        }
        return var;
}

References vec_s::coeff, table_s::obj, qval_cmp_i, vec_s::succ, vec_s::var, VAR_NULL, and VEC_NULL.

Referenced by table_get_pivot().

Here is the caller graph for this function:

table_init()

static void table_init ( table_p  tbl, int  nbconstrs  )

static

Initialize tbl, with room for nbconstrs constraints.

Definition at line 536 of file sc_simplex_feasibility.h.

{
        constr_init(tbl->obj);
        tbl->constrs = safe_malloc(nbconstrs * sizeof(constr_t));
        int i;
        for (i = 0; i < nbconstrs; i++) {
                constr_init(tbl->constrs[i]);
        }
        tbl->nbvars = 0;
        tbl->nbconstrs = nbconstrs;
}

References constr_init(), table_s::constrs, table_s::nbconstrs, table_s::nbvars, table_s::obj, and safe_malloc().

Referenced by table_init_set_systeme().

Here is the call graph for this function:

Here is the caller graph for this function:

table_init_set_systeme()

static void table_init_set_systeme ( table_p  tbl, Psysteme  sys  )

static

Initialize tbl from sys.

Definition at line 1054 of file sc_simplex_feasibility.h.

{
        vartbl_t vartbl;
        vartbl_init(vartbl);
        table_init(tbl, sys->nb_eq + sys->nb_ineq);
        int i = 0;
        Pcontrainte constr;
        for (constr = sys->egalites; constr != NULL; constr = constr->succ) {
                constr_set_contrainte(vartbl, tbl->constrs[i], constr, false);
                i++;
        }
        for (constr = sys->inegalites; constr != NULL; constr = constr->succ) {
                constr_set_contrainte(vartbl, tbl->constrs[i], constr, true);
                i++;
        }
        tbl->nbvars = vartbl->nbvars;
        vartbl_clear(vartbl);
}

References constr_set_contrainte(), table_s::constrs, Ssysteme::egalites, Ssysteme::inegalites, Ssysteme::nb_eq, Ssysteme::nb_ineq, table_s::nbvars, Scontrainte::succ, table_init(), vartbl_clear, and vartbl_init().

Referenced by sc_get_feasibility().

Here is the call graph for this function:

Here is the caller graph for this function:

table_makepos()

static void table_makepos ( table_p  tbl )

static

Turn constraints into tbl into equivalent ones, whose constant term is non-negative.

All constraints must be equalities.

Definition at line 576 of file sc_simplex_feasibility.h.

{
        int i;
        for (i = 0; i < tbl->nbconstrs; i++) {
                constr_makepos(tbl->constrs[i]);
        }
}

References constr_makepos(), table_s::constrs, and table_s::nbconstrs.

Referenced by table_canonicalize().

Here is the call graph for this function:

Here is the caller graph for this function:

table_prepare()

static void table_prepare ( table_p  tbl )

static

Canonicalize tbl, set the objective and add objective variables.

Definition at line 748 of file sc_simplex_feasibility.h.

{
        table_canonicalize(tbl);
        table_set_obj(tbl);
        table_addobjvars(tbl);
        DEBUG(
                fprintf(stderr, "\nWith objective:\n");
                table_fprint(stderr, tbl);
                fprintf(stderr, "\n");
        );
}

References DEBUG, fprintf(), table_addobjvars(), table_canonicalize(), table_fprint(), and table_set_obj().

Referenced by table_get_feasibility().

Here is the call graph for this function:

Here is the caller graph for this function:

table_run_simplex()

static void table_run_simplex ( table_p  tbl )

static

Run simplex algorithm on @tbl.

Definition at line 888 of file sc_simplex_feasibility.h.

{
        int i = 0;
        while (true) {
                var_t var;
                int row;
                if (table_get_pivot(tbl, &var, &row)) {
                        table_apply_pivot(tbl, var, row);
                        i++;
                        DEBUG(
                                fprintf(stderr, "After iteration %d:\n", i);
                                fprintf(stderr, "Pivot variable: ");
                                var_fprint(stderr, var);
                                fprintf(stderr, "\nPivot row: %d\nTable:\n", row);
                                table_fprint(stderr, tbl);
                                fprintf(stderr, "\n");
                                if (i > 200) {
                                        fprintf(stderr, "Seems to long, exiting...\n");
                                        exit(42);
                                }
                        );
                }
                else {
                        break;
                }
        }
}

References DEBUG, exit, fprintf(), table_apply_pivot(), table_fprint(), table_get_pivot(), and var_fprint.

Referenced by table_get_feasibility().

Here is the call graph for this function:

Here is the caller graph for this function:

table_set_obj()

static void table_set_obj ( table_p  tbl )

static

Initialize the objective function and value from constraints in tbl.

Definition at line 714 of file sc_simplex_feasibility.h.

{
        constr_p obj = tbl->obj;
        int i;
        for (i = 0; i < tbl->nbconstrs; i++) {
                constr_p constr = tbl->constrs[i];
                constr_iadd(obj, constr);
        }
}

References constr_iadd(), table_s::constrs, table_s::nbconstrs, and table_s::obj.

Referenced by table_prepare().

Here is the call graph for this function:

Here is the caller graph for this function:

vartbl_find()

static var_t vartbl_find ( vartbl_p  vartbl, Variable  name  )

static

Get the variable index associated to name, creating a new one if necessary.

Definition at line 1004 of file sc_simplex_feasibility.h.

{
        int i;
        for (i = 0; i < vartbl->nbvars; i++) {
                if (vartbl->names[i] == name) {
                        return i;
                }
        }
        vartbl->names[vartbl->nbvars] = name;
        return vartbl->nbvars++;
}

References vartbl_s::names, and vartbl_s::nbvars.

Referenced by vec_set_vecteur().

Here is the caller graph for this function:

vartbl_init()

static void vartbl_init ( vartbl_p  vartbl )

static

Initialize @vartbl to an empty table.

Definition at line 990 of file sc_simplex_feasibility.h.

{
        vartbl->nbvars = 0;
}

References vartbl_s::nbvars.

Referenced by table_init_set_systeme().

Here is the caller graph for this function:

vec_append()

static void vec_append ( vec_p *  pvec, var_t  var, qval_t  coeff  )

static

Add the element (var, coeff) to pvec.

Definition at line 182 of file sc_simplex_feasibility.h.

{
        if (!qval_equal_i(coeff, 0, 1)) {
                while (*pvec != VEC_NULL && (*pvec)->var > var) {
                        pvec = &(*pvec)->succ;
                }
        }
        vec_append_atfirst(pvec, var, coeff);
}

References vec_s::coeff, qval_equal_i, vec_s::succ, vec_s::var, vec_append_atfirst(), and VEC_NULL.

Referenced by vec_set_vecteur().

Here is the call graph for this function:

Here is the caller graph for this function:

vec_append_atfirst()

static void vec_append_atfirst ( vec_p *  pvec, var_t  var, qval_t  coeff  )

static

Add the element (var, @coeff) to pvec, in first position.

var must be greater to any variable in pvec s.t. pvec remains consistent.

Definition at line 169 of file sc_simplex_feasibility.h.

{
        assert(*pvec == VEC_NULL || (*pvec)->var < var);
        vec_p hd = safe_malloc(sizeof(vec_s));
        hd->var = var;
        qval_init(hd->coeff); qval_set(hd->coeff, coeff);
        hd->succ = *pvec;
        *pvec = hd;
}

References assert, vec_s::coeff, qval_init, qval_set, safe_malloc(), vec_s::succ, vec_s::var, and VEC_NULL.

Referenced by table_addobjvars(), table_addofsvars(), table_addsignvars(), and vec_append().

Here is the call graph for this function:

Here is the caller graph for this function:

vec_clear()

static void vec_clear ( vec_p *  pvec )

static

Free the space occupied by pvec.

Definition at line 130 of file sc_simplex_feasibility.h.

{
        while (*pvec != VEC_NULL) {
                vec_p succ = (*pvec)->succ;
                qval_clear((*pvec)->coeff);
                free(*pvec);
                *pvec = succ;
        }
}

References free(), qval_clear, vec_s::succ, and VEC_NULL.

Referenced by constr_clear(), vec_imul(), vec_set(), and vec_set_vecteur().

Here is the call graph for this function:

Here is the caller graph for this function:

vec_fprint()

static int NOWUNUSED vec_fprint ( FILE *  stream, vec_p  vec  )

static

Output vec on stdio stream stream.

Definition at line 318 of file sc_simplex_feasibility.h.

{
        if (vec == VEC_NULL) {
                return fprintf(stream, "0");
        }
        else {
                int c = qval_fprint(stream, vec->coeff);
                c += fprintf(stream, " ");
                c += var_fprint(stream, vec->var);
                for (vec = vec->succ; vec != VEC_NULL; vec = vec->succ) {
                        if (qval_cmp_i(vec->coeff, 0, 1) > 0) {
                                c += fprintf(stream, " + ");
                                c += qval_fprint(stream, vec->coeff);
                        }
                        else {
                                c += fprintf(stream, " - ");
                                qval_neg(vec->coeff, vec->coeff);
                                c += qval_fprint(stream, vec->coeff);
                                qval_neg(vec->coeff, vec->coeff);
                        }
                        c += fprintf(stream, " ");
                        c += var_fprint(stream, vec->var);
                }
                return c;
        }
}

References vec_s::coeff, fprintf(), qval_cmp_i, qval_fprint, qval_neg, vec_s::succ, vec_s::var, var_fprint, and VEC_NULL.

Referenced by constr_fprint().

Here is the call graph for this function:

Here is the caller graph for this function:

vec_get_coeff()

static void vec_get_coeff ( qval_t  coeff, vec_p  vec, var_t  var  )

static

Get the value associated to var in vec, and store it into coeff.

Definition at line 195 of file sc_simplex_feasibility.h.

{
        while (vec != VEC_NULL && vec->var > var) {
                vec = vec->succ;
        }
        if (vec != VEC_NULL && vec->var == var) {
                qval_set(coeff, vec->coeff);
        }
        else {
                qval_set_i(coeff, 0, 1);
        }
}

References vec_s::coeff, qval_set, qval_set_i, vec_s::succ, vec_s::var, and VEC_NULL.

vec_iadd()

static void vec_iadd ( vec_p *  pvec, vec_p  vec  )

static

Set pvec to pvec + vec.

Definition at line 211 of file sc_simplex_feasibility.h.

{
        for (; vec != VEC_NULL; vec = vec->succ) {
                var_t var = vec->var;
                while (*pvec != VEC_NULL && (*pvec)->var > var) {
                        pvec = &(*pvec)->succ;
                }
                if (*pvec == VEC_NULL || (*pvec)->var < var) {
                        // a new variable is added
                        vec_p hd = safe_malloc(sizeof(vec_s));
                        hd->var = var;
                        qval_init(hd->coeff); qval_set(hd->coeff, vec->coeff);
                        hd->succ = *pvec;
                        *pvec = hd;
                        pvec = &(*pvec)->succ;
                }
                else {
                        // the variable is present in the original vector
                        assert((*pvec)->var == var);
                        qval_add((*pvec)->coeff, (*pvec)->coeff, vec->coeff);
                        if (qval_equal_i((*pvec)->coeff, 0, 1)) {
                                vec_p tl = (*pvec)->succ;
                                qval_clear((*pvec)->coeff);
                                free(*pvec);
                                *pvec = tl;
                        }
                        else {
                                pvec = &(*pvec)->succ;
                        }
                }
        }
}

References assert, vec_s::coeff, free(), qval_add, qval_clear, qval_equal_i, qval_init, qval_set, safe_malloc(), vec_s::succ, vec_s::var, and VEC_NULL.

Referenced by constr_iadd().

Here is the call graph for this function:

Here is the caller graph for this function:

vec_iaddmul()

static void vec_iaddmul ( vec_p *  pvec, qval_t  coeff, vec_p  vec  )

static

Set pvec to pvec + coeff times vec.

Definition at line 263 of file sc_simplex_feasibility.h.

{
        if (qval_equal_i(coeff, 0, 1)) {
                return;
        }
        else {
                qval_t tmp;
                qval_init(tmp);
                for (; vec != VEC_NULL; vec = vec->succ) {
                        var_t var = vec->var;
                        while (*pvec != VEC_NULL && (*pvec)->var > var) {
                                pvec = &(*pvec)->succ;
                        }
                        if (*pvec == VEC_NULL || (*pvec)->var < var) {
                                // a new variable is added
                                vec_p hd = safe_malloc(sizeof(vec_s));
                                hd->var = var;
                                qval_init(hd->coeff); qval_mul(hd->coeff, coeff, vec->coeff);
                                hd->succ = *pvec;
                                *pvec = hd;
                                pvec = &(*pvec)->succ;
                        }
                        else {
                                // the variable is present in the original vector
                                assert((*pvec)->var == var);
                                qval_mul(tmp, coeff, vec->coeff);
                                qval_add((*pvec)->coeff, (*pvec)->coeff, tmp);
                                if (qval_equal_i((*pvec)->coeff, 0, 1)) {
                                        vec_p tl = (*pvec)->succ;
                                        qval_clear((*pvec)->coeff);
                                        free(*pvec);
                                        *pvec = tl;
                                }
                                else {
                                        pvec = &(*pvec)->succ;
                                }
                        }
                }
                qval_clear(tmp);
        }
}

References assert, vec_s::coeff, free(), qval_add, qval_clear, qval_equal_i, qval_init, qval_mul, safe_malloc(), vec_s::succ, vec_s::var, and VEC_NULL.

Referenced by constr_iaddmul().

Here is the call graph for this function:

Here is the caller graph for this function:

vec_imul()

static void vec_imul ( vec_p *  pvec, qval_t  coeff  )

static

Set pvec to coeff times pvec.

Definition at line 247 of file sc_simplex_feasibility.h.

{
        if (qval_equal_i(coeff, 0, 1)) {
                vec_clear(pvec);
        }
        else {
                vec_p vec;
                for (vec = *pvec; vec != VEC_NULL; vec = vec->succ) {
                        qval_mul(vec->coeff, vec->coeff, coeff);
                }
        }
}

References vec_s::coeff, qval_equal_i, qval_mul, vec_s::succ, vec_clear(), and VEC_NULL.

Referenced by constr_imul().

Here is the call graph for this function:

Here is the caller graph for this function:

vec_ineg()

static void vec_ineg ( vec_p  vec )

static

Set vec to -vec.

Definition at line 308 of file sc_simplex_feasibility.h.

{
        for (; vec != VEC_NULL; vec = vec->succ) {
                qval_neg(vec->coeff, vec->coeff);
        }
}

References vec_s::coeff, qval_neg, vec_s::succ, and VEC_NULL.

Referenced by constr_makepos().

Here is the caller graph for this function:

vec_set()

static void vec_set ( vec_p *  pvec, vec_p  vec  )

static

Copy vec into pvec.

Definition at line 143 of file sc_simplex_feasibility.h.

{
        vec_clear(pvec);
        bool first = true;
        vec_p* last = NULL;
        for (; vec != VEC_NULL; vec = vec->succ) {
                *last = safe_malloc(sizeof(vec_s));
                (*last)->var = vec->var;
                qval_init((*last)->coeff);
                qval_set((*last)->coeff, vec->coeff);
                if (first) {
                        *pvec = *last;
                        first = false;
                }
                last = &(*last)->succ;
        }
        if (!first) {
                *last = VEC_NULL;
        }
}

References vec_s::coeff, qval_init, qval_set, safe_malloc(), vec_s::succ, vec_s::var, vec_clear(), and VEC_NULL.

Referenced by constr_set().

Here is the call graph for this function:

Here is the caller graph for this function:

vec_set_vecteur()

static void vec_set_vecteur ( vartbl_t  vartbl, vec_p *  pvec, Pvecteur  vec  )

static

Copy vec into pvec.

Definition at line 1019 of file sc_simplex_feasibility.h.

{
        vec_clear(pvec);
        qval_t coeff;
        qval_init(coeff);
        for (; vec != NULL; vec = vec->succ) {
                if (vec->var != TCST) {
                        var_t var = vartbl_find(vartbl, vec->var);
                        qval_set_i(coeff, vec->val, 1);
                        vec_append(pvec, var, coeff);
                }
        }
        qval_clear(coeff);
}

References qval_clear, qval_init, qval_set_i, Svecteur::succ, TCST, Svecteur::val, Svecteur::var, vartbl_find(), vec_append(), and vec_clear().

Referenced by constr_set_contrainte().

Here is the call graph for this function:

Here is the caller graph for this function: