Sven Verdoolaege [Fri, 5 Feb 2010 09:40:19 +0000 (10:40 +0100)]
isl_coalesce.c: fix typo in comment
Sven Verdoolaege [Sun, 7 Feb 2010 11:05:21 +0000 (12:05 +0100)]
include/isl_int.h: argument of mp_get_memory_functions should have C linkage
Sven Verdoolaege [Thu, 4 Feb 2010 21:51:15 +0000 (22:51 +0100)]
isl_map_read: accept lists of affine expressions in constraints
Sven Verdoolaege [Thu, 4 Feb 2010 21:48:48 +0000 (22:48 +0100)]
add isl_mat_from_row_vec and isl_mat_vec_concat
Sven Verdoolaege [Thu, 4 Feb 2010 17:26:23 +0000 (18:26 +0100)]
isl_map_read: read extended polylib format
Sven Verdoolaege [Thu, 4 Feb 2010 17:24:43 +0000 (18:24 +0100)]
add isl_stream_next_token_on_same_line
Sven Verdoolaege [Thu, 4 Feb 2010 16:51:11 +0000 (17:51 +0100)]
isl_map_read: make sure polylib constraint coefficients are on a single line
Sven Verdoolaege [Thu, 4 Feb 2010 16:50:36 +0000 (17:50 +0100)]
isl_{map,set}_dim: handle NULL input
Sven Verdoolaege [Thu, 4 Feb 2010 16:46:04 +0000 (17:46 +0100)]
isl_map_read: use more uniform way of reading in polylib constraint coefficients
Sven Verdoolaege [Thu, 4 Feb 2010 13:08:51 +0000 (14:08 +0100)]
isl_transitive_closure.c: fix typo in comment
Sven Verdoolaege [Thu, 4 Feb 2010 12:58:40 +0000 (13:58 +0100)]
isl_map_transitive_closure: use more relaxed exactness check on acyclic graphs
In particular, for the transitive closure, we only need to check that
there is a path of _some_ length with a valid initial segment.
However, we can only do this if the corresponding graph is acyclic.
For now, we restrict ourselves to graphs that are obviously acyclic.
Sven Verdoolaege [Wed, 3 Feb 2010 17:29:52 +0000 (18:29 +0100)]
add isl_map_power and isl_map_transitive_closure
Sven Verdoolaege [Wed, 3 Feb 2010 17:13:49 +0000 (18:13 +0100)]
isl_map_subtract.c: make some internal functions static
Sven Verdoolaege [Wed, 3 Feb 2010 15:53:39 +0000 (16:53 +0100)]
add generic isl_map_project_out
Sven Verdoolaege [Tue, 2 Feb 2010 14:21:58 +0000 (15:21 +0100)]
add isl_{map,set}_add
Sven Verdoolaege [Tue, 2 Feb 2010 13:39:25 +0000 (14:39 +0100)]
rename isl_{map,set}_add to isl_{map,set}_add_basic_{map,set}
Sven Verdoolaege [Tue, 2 Feb 2010 13:23:02 +0000 (14:23 +0100)]
isl_set_project_out: always update dimension, even for empty sets
Sven Verdoolaege [Tue, 2 Feb 2010 11:16:08 +0000 (12:16 +0100)]
isl_dim_join: don't require names of joined variables to match
Sven Verdoolaege [Mon, 1 Feb 2010 16:03:54 +0000 (17:03 +0100)]
add isl_map_from_domain_and_range
Sven Verdoolaege [Mon, 1 Feb 2010 13:04:17 +0000 (14:04 +0100)]
isl_stream: treat "-" as operator rather than as -1
Sven Verdoolaege [Mon, 1 Feb 2010 12:37:32 +0000 (13:37 +0100)]
isl_map_read: accept "strict" inequalities
Sven Verdoolaege [Mon, 1 Feb 2010 12:36:46 +0000 (13:36 +0100)]
isl_input.c: fix memory deallocation problem on missing operator
Sven Verdoolaege [Sun, 31 Jan 2010 20:15:48 +0000 (21:15 +0100)]
add dependence analysis
Sven Verdoolaege [Sun, 31 Jan 2010 21:01:41 +0000 (22:01 +0100)]
add isl_map_{partial_,}lexopt
Sven Verdoolaege [Thu, 14 Jan 2010 20:30:26 +0000 (21:30 +0100)]
add private isl_{set,map}_make_disjoint
Sven Verdoolaege [Sun, 31 Jan 2010 17:47:53 +0000 (18:47 +0100)]
basis_reduction_templ.c: fix typo in comment
Sven Verdoolaege [Sun, 31 Jan 2010 17:29:12 +0000 (18:29 +0100)]
isl_tab_pip.c: find_solutions: break when context becomes empty
Normally, find_solutions: always operates on a non-empty context.
However, when we discover a pure-parametric cut in the main
tableau, the result of adding this cut to the context may be
an empty context. In this case, we need to break out off the
main loop, because most code assumes the context is non-empty.
Sven Verdoolaege [Tue, 26 Jan 2010 14:40:02 +0000 (15:40 +0100)]
isl_dim_equal: don't require names of input and output variables to match
Sven Verdoolaege [Tue, 26 Jan 2010 19:50:12 +0000 (20:50 +0100)]
isl_dim_map: properly duplicate names
Sven Verdoolaege [Tue, 26 Jan 2010 19:49:11 +0000 (20:49 +0100)]
isl_dim_drop: properly adjust length of names array
Sven Verdoolaege [Tue, 26 Jan 2010 12:17:49 +0000 (13:17 +0100)]
doc: a bit more on integers
Sven Verdoolaege [Mon, 25 Jan 2010 21:09:20 +0000 (22:09 +0100)]
doc: describe input/output formats
Sven Verdoolaege [Mon, 25 Jan 2010 21:10:31 +0000 (22:10 +0100)]
doc: fix typo
Sven Verdoolaege [Sun, 24 Jan 2010 21:08:27 +0000 (22:08 +0100)]
add isl_cat test application
Sven Verdoolaege [Mon, 25 Jan 2010 16:57:33 +0000 (17:57 +0100)]
add omega output
Sven Verdoolaege [Mon, 25 Jan 2010 17:02:07 +0000 (18:02 +0100)]
add isl output
Sven Verdoolaege [Sun, 24 Jan 2010 13:23:06 +0000 (14:23 +0100)]
isl_test: use isl_set_read_from_str
Sven Verdoolaege [Sun, 24 Jan 2010 13:22:49 +0000 (14:22 +0100)]
add isl_set_read_from_str
Sven Verdoolaege [Sat, 23 Jan 2010 21:52:02 +0000 (22:52 +0100)]
add isl_map_read_from_str
Sven Verdoolaege [Fri, 22 Jan 2010 12:54:47 +0000 (13:54 +0100)]
isl_map_read_from_file: allow unions in isl format input
Sven Verdoolaege [Fri, 22 Jan 2010 11:48:23 +0000 (12:48 +0100)]
isl_basic_map_read: read definitions of existential variables
Sven Verdoolaege [Fri, 22 Jan 2010 11:45:05 +0000 (12:45 +0100)]
privately export isl_basic_map_add_div_constraints
Sven Verdoolaege [Fri, 22 Jan 2010 10:30:48 +0000 (11:30 +0100)]
isl_basic_map_read: read affine constraint as two affine expressions + operator
Sven Verdoolaege [Sun, 24 Jan 2010 21:30:12 +0000 (22:30 +0100)]
isl_input.c: optionally read parameters from input
Sven Verdoolaege [Thu, 21 Jan 2010 20:21:28 +0000 (21:21 +0100)]
tokenizer: accept "and" keyword
Sven Verdoolaege [Sun, 24 Jan 2010 23:32:03 +0000 (00:32 +0100)]
export isl_map_read_from_file
Sven Verdoolaege [Sat, 16 Jan 2010 15:16:14 +0000 (16:16 +0100)]
export isl_basic_map_read_from_str
Sven Verdoolaege [Sun, 24 Jan 2010 20:55:05 +0000 (21:55 +0100)]
drop redundant input_format argument from reading functions
Sven Verdoolaege [Sun, 24 Jan 2010 18:24:14 +0000 (19:24 +0100)]
isl_input.c: merge functions for reading PolyLib and omega-like input
Sven Verdoolaege [Sun, 24 Jan 2010 18:08:06 +0000 (19:08 +0100)]
isl_input_omega.c: accept PolyLib input
Sven Verdoolaege [Sun, 24 Jan 2010 17:58:24 +0000 (18:58 +0100)]
isl_input_omega.c: prepare for reading parametric unions
Sven Verdoolaege [Fri, 22 Jan 2010 12:58:23 +0000 (13:58 +0100)]
isl_input_omega.c: finalize and simplify resulting basic map
Sven Verdoolaege [Fri, 22 Jan 2010 10:41:19 +0000 (11:41 +0100)]
isl_input_omega.c: fix check for memory allocation error
Sven Verdoolaege [Sun, 24 Jan 2010 13:36:02 +0000 (14:36 +0100)]
isl_stream_next_token: skip comment lines
Sven Verdoolaege [Thu, 21 Jan 2010 09:54:51 +0000 (10:54 +0100)]
isl_tab_basic_map_partial_lexopt: properly handle empty input map
In particular, when no empty set is requested (i.e., empty == NULL),
then we shouldn't try to add the context to the empty set.
Sven Verdoolaege [Wed, 20 Jan 2010 16:50:28 +0000 (17:50 +0100)]
isl_basic_map_set_to_empty: remove sample (if any)
Sven Verdoolaege [Sun, 17 Jan 2010 19:50:31 +0000 (20:50 +0100)]
add isl_set_fast_is_empty
Sven Verdoolaege [Wed, 13 Jan 2010 08:59:16 +0000 (09:59 +0100)]
properly remove piplib submodule
309036c (add copyright statements) accidentally removed the piplib submodule.
Removing the piplib submodule was not a bad idea since we don't really need it
anymore, but it should be done properly.
Sven Verdoolaege [Sun, 29 Nov 2009 17:24:39 +0000 (18:24 +0100)]
isl_basic_map_update_from_tab: re-gauss resulting bmap
Many functions assume that their inputs have been gaussed.
Sven Verdoolaege [Fri, 1 Jan 2010 17:02:30 +0000 (18:02 +0100)]
ax_submodule.m4: don't let --with-module conflict with --with-module-prefix=
Sven Verdoolaege [Sat, 12 Dec 2009 22:43:31 +0000 (23:43 +0100)]
add isl_set_follows_at
Sven Verdoolaege [Thu, 24 Dec 2009 18:02:26 +0000 (19:02 +0100)]
isl_basic_set_compare_at: compute result in terms of maximal (integral) difference
Computing the maximal instead of the minimal difference will allow
us to reuse much of the code in isl_basic_set_follows_at later.
Since we only need the sign of the optimum, we don't really need
the exact value.
Sven Verdoolaege [Thu, 24 Dec 2009 16:59:59 +0000 (17:59 +0100)]
isl_tab_pip.c: add cuts for all non-integer coordinates in lexmin context
The lexmin context applies basically the same algorithm that is
used in the main tableau to the context tableau.
In particular, each cut that is added is immediately used to move
to a lexico-greater point.
It was reported by François Galea, who was working on the implementation
of parametric integer programming in PPL, that first adding cuts
for all non-integer coordinates results in a significant speed
improvement on at least one example.
This patch implements the same idea and results in a similar improvement
on the same example.
Sven Verdoolaege [Sat, 19 Dec 2009 10:20:34 +0000 (11:20 +0100)]
isl_basic_map_gist: don't drop equalities from context
The context isn't cowed, so this dropping of equalities would
be visible to the caller. Instead, drop the equalities after
duplicating the context.
Sven Verdoolaege [Fri, 18 Dec 2009 22:41:29 +0000 (23:41 +0100)]
isl_convex_hull.c: initial_facet_constraint: drop all redundant bounds on face
While constructing an initial facet, we may end up with an intermediate
face that makes some of the as yet unconsidered bounds redundant.
Remove all of them, instead of only those that happen to vanish.
Sven Verdoolaege [Fri, 18 Dec 2009 20:26:31 +0000 (21:26 +0100)]
isl_convex_hull.c: is_independent_bound: normalize bounds
Sven Verdoolaege [Fri, 18 Dec 2009 19:53:46 +0000 (20:53 +0100)]
isl_convex_hull.c: extend: check hull argument
Sven Verdoolaege [Fri, 18 Dec 2009 19:52:33 +0000 (20:52 +0100)]
isl_mat_right_inverse: be more verbose on error condition
Sven Verdoolaege [Fri, 18 Dec 2009 17:26:58 +0000 (18:26 +0100)]
isl_constraint_dup: make sure line refers to equation in constraint's bmap
Sven Verdoolaege [Wed, 16 Dec 2009 19:25:40 +0000 (19:25 +0000)]
add copyright statements
Sven Verdoolaege [Wed, 16 Dec 2009 14:17:19 +0000 (14:17 +0000)]
remove functions for converting between isl and PolyLib
These functions could be seen as being derived work from PolyLib
and would therefore infect the whole library with the GPLv2 license.
They will be moved into a separate isl-polylib library.
Sven Verdoolaege [Wed, 16 Dec 2009 12:53:03 +0000 (12:53 +0000)]
isl_tab_solve_lp: invert optimal value back when computing maximum
A maximum is computed by computing the minimum of the opposite objective
function. The maximal value is then the opposite of the computed value.
Sven Verdoolaege [Sun, 6 Dec 2009 10:54:41 +0000 (11:54 +0100)]
isl_map_intersect: add special case for adding a single constraint
Sven Verdoolaege [Sat, 5 Dec 2009 17:50:12 +0000 (18:50 +0100)]
isl_map_is_subset: break off as soon as difference is known to be non-empty
Sven Verdoolaege [Mon, 7 Dec 2009 16:09:59 +0000 (17:09 +0100)]
compute set difference using a backtracking algorithm
In particular, treat all basic maps in the minuend separately
and only subtract parts of the subtrahend that actually overlap
with the minuend. Moreover, only use non-redundant constraints
when performing this subtraction.
Using only non-redundant constraints in overlapping parts
avoids the minuend being split in several parts unnecessarily.
Treating each basic map separately should help speed up
isl_map_is_subset in a subsequent commit.
Sven Verdoolaege [Tue, 1 Dec 2009 11:42:46 +0000 (12:42 +0100)]
isl_map_subtract.c: extract from isl_map.c
Sven Verdoolaege [Mon, 7 Dec 2009 16:00:15 +0000 (17:00 +0100)]
isl_tab: keep track of isl_basic_map instead of isl_basic_set
Sven Verdoolaege [Sat, 28 Nov 2009 20:47:29 +0000 (21:47 +0100)]
privately export isl_basic_map_contains
Sven Verdoolaege [Sat, 28 Nov 2009 20:44:28 +0000 (21:44 +0100)]
add isl_basic_map_add_ineq and isl_basic_map_add_eq
Sven Verdoolaege [Sat, 28 Nov 2009 19:16:03 +0000 (20:16 +0100)]
isl_tab_detect_redundant: return status instead of isl_tab *
Sven Verdoolaege [Sat, 28 Nov 2009 18:47:58 +0000 (19:47 +0100)]
isl_tab: add isl_tab_freeze_constraint
Sven Verdoolaege [Sat, 28 Nov 2009 15:09:56 +0000 (16:09 +0100)]
isl_tab_add_ineq and isl_tab_mark_empty: return status instead of isl_tab *
isl_tabs are not reference counted, so it's easier to deal with a status
than to have to keep track of whether the isl_tab may have been destroyed.
Sven Verdoolaege [Sun, 29 Nov 2009 18:34:13 +0000 (19:34 +0100)]
add missing AUTHORS file
Sven Verdoolaege [Sun, 29 Nov 2009 17:24:39 +0000 (18:24 +0100)]
isl_basic_set_swap_vars: re-gauss resulting bset
Many functions assume that their inputs have been gaussed.
Sven Verdoolaege [Mon, 16 Nov 2009 14:58:31 +0000 (15:58 +0100)]
add isl_basic_map_first_constraint
Sven Verdoolaege [Sun, 15 Nov 2009 19:28:40 +0000 (20:28 +0100)]
export isl_basic_map_lexmax
Sven Verdoolaege [Sun, 15 Nov 2009 17:22:07 +0000 (18:22 +0100)]
add isl_basic_set_lexmax
Sven Verdoolaege [Sun, 15 Nov 2009 16:31:52 +0000 (17:31 +0100)]
isl_map_drop_basic_map: consistently keep basic map argument
Sven Verdoolaege [Sun, 1 Nov 2009 14:41:28 +0000 (15:41 +0100)]
isl_tab: row is only (obviously) redundant if it does not depend on variables
Variables are not assumed to be nonnegative, but are only marked as being
nonnegative based on the constraints. This nonnegativity can therefore
not be used to mark rows as being redundant as that could lead to
circular reasoning.
Sven Verdoolaege [Sun, 1 Nov 2009 14:34:03 +0000 (15:34 +0100)]
isl_basic_map_simplify: make sure to rerun Gauss when equality has been added
remove_duplicate_constraints failed to set the progress flag when
it replaces a pair of inequalities by an equality, resulting in
the result of isl_basic_map_simplify possibly not having the equalities
in the expected form.
Sven Verdoolaege [Sun, 1 Nov 2009 13:49:46 +0000 (14:49 +0100)]
isl_tab_basic_map_partial_lexopt: use context constraints when detecting equalities
The constraints of the context of the actual map may conspire to form
equalities and we generally want to detect as many equalities as possible.
Therefore, detect equalities in the intersection of the two
and add these equalities to the map.
Note that the equalities are now no longer detected in the map
itself, so we may have to detect equalities again later if
we are ever interested in the equalities of the map itself.
Sven Verdoolaege [Sun, 1 Nov 2009 13:36:32 +0000 (14:36 +0100)]
isl_tab_pip.c: ignore dead columns when checking integrality
The dead columns are zero, which means that it does not matter
that they may have a fractional coefficient.
Moreover, dead columns can't be used to pivot, so it is actually
wrong to take them into account.
Sven Verdoolaege [Wed, 21 Oct 2009 21:49:13 +0000 (23:49 +0200)]
isl_pip: optionally perform some check on the results
Sven Verdoolaege [Wed, 21 Oct 2009 21:39:23 +0000 (23:39 +0200)]
put options in a separate isl_options structure
Sven Verdoolaege [Wed, 21 Oct 2009 21:22:39 +0000 (23:22 +0200)]
add rudimentary argument parsing facility
Sven Verdoolaege [Wed, 21 Oct 2009 19:04:26 +0000 (21:04 +0200)]
isl_tab_compute_reduced_basis: handle empty tables
Sven Verdoolaege [Wed, 21 Oct 2009 12:41:31 +0000 (14:41 +0200)]
isl_basic_set_solve_ilp: handle obviously empty sets
Sven Verdoolaege [Wed, 21 Oct 2009 12:31:22 +0000 (14:31 +0200)]
isl_basic_set_solve_ilp: fix handling of sets with equalities
First, the input set should be protected from being modified,
and second, the test for whether a solution is requested was wrong.
Sven Verdoolaege [Wed, 21 Oct 2009 12:05:13 +0000 (14:05 +0200)]
add isl_set_remove
Sven Verdoolaege [Wed, 21 Oct 2009 12:04:29 +0000 (14:04 +0200)]
add isl_set_fix