File: polyhedron_minimize.c

package info (click to toggle)
isl 0.20-2
  • links: PTS
  • area: main
  • in suites: buster, sid
  • size: 12,708 kB
  • sloc: ansic: 125,702; python: 5,770; sh: 4,291; cpp: 1,057; makefile: 497; lisp: 54; perl: 9
file content (105 lines) | stat: -rw-r--r-- 2,436 bytes parent folder | download | duplicates (22)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/*
 * Copyright 2008-2009 Katholieke Universiteit Leuven
 *
 * Use of this software is governed by the MIT license
 *
 * Written by Sven Verdoolaege, K.U.Leuven, Departement
 * Computerwetenschappen, Celestijnenlaan 200A, B-3001 Leuven, Belgium
 */

#include <assert.h>
#include <isl/set.h>
#include <isl/vec.h>
#include <isl_ilp_private.h>
#include <isl_seq.h>
#include <isl_vec_private.h>

/* The input of this program is the same as that of the "polytope_minimize"
 * program from the barvinok distribution.
 *
 * Constraints of set is PolyLib format.
 * Linear or affine objective function in PolyLib format.
 */

static struct isl_vec *isl_vec_lin_to_aff(struct isl_vec *vec)
{
	struct isl_vec *aff;

	if (!vec)
		return NULL;
	aff = isl_vec_alloc(vec->ctx, 1 + vec->size);
	if (!aff)
		goto error;
	isl_int_set_si(aff->el[0], 0);
	isl_seq_cpy(aff->el + 1, vec->el, vec->size);
	isl_vec_free(vec);
	return aff;
error:
	isl_vec_free(vec);
	return NULL;
}

/* Rotate elements of vector right.
 * In particular, move the constant term from the end of the
 * vector to the start of the vector.
 */
static struct isl_vec *vec_ror(struct isl_vec *vec)
{
	int i;

	if (!vec)
		return NULL;
	for (i = vec->size - 2; i >= 0; --i)
		isl_int_swap(vec->el[i], vec->el[i + 1]);
	return vec;
}

int main(int argc, char **argv)
{
	struct isl_ctx *ctx = isl_ctx_alloc();
	struct isl_basic_set *bset;
	struct isl_vec *obj;
	struct isl_vec *sol;
	isl_int opt;
	unsigned dim;
	enum isl_lp_result res;
	isl_printer *p;

	isl_int_init(opt);
	bset = isl_basic_set_read_from_file(ctx, stdin);
	assert(bset);
	obj = isl_vec_read_from_file(ctx, stdin);
	assert(obj);
	dim = isl_basic_set_total_dim(bset);
	assert(obj->size >= dim && obj->size <= dim + 1);
	if (obj->size != dim + 1)
		obj = isl_vec_lin_to_aff(obj);
	else
		obj = vec_ror(obj);
	res = isl_basic_set_solve_ilp(bset, 0, obj->el, &opt, &sol);
	switch (res) {
	case isl_lp_error:
		fprintf(stderr, "error\n");
		return -1;
	case isl_lp_empty:
		fprintf(stdout, "empty\n");
		break;
	case isl_lp_unbounded:
		fprintf(stdout, "unbounded\n");
		break;
	case isl_lp_ok:
		p = isl_printer_to_file(ctx, stdout);
		p = isl_printer_print_vec(p, sol);
		p = isl_printer_end_line(p);
		p = isl_printer_print_isl_int(p, opt);
		p = isl_printer_end_line(p);
		isl_printer_free(p);
	}
	isl_basic_set_free(bset);
	isl_vec_free(obj);
	isl_vec_free(sol);
	isl_ctx_free(ctx);
	isl_int_clear(opt);

	return 0;
}