zonohedra (version 0.3-0)

simplify: simplify and unsimplify

Description

A simple matroid has no loops and no multiple groups. Simplification is the process of removing all loops, and every point except one from each multiple group. The result is a simple matroid.
The functions below simplify a matroid, or an explicit list of hyperplanes.
The hyperplanes can be unsimplified if the original loops and multiple groups are known.

Usage

# S3 method for matroid
getsimplified( x, ... )
# S3 method for list
simplify( x, ground=NULL, ... )
# S3 method for list
unsimplify( x, loop=NULL, multiple=NULL, ground=NULL, ... )

Value

If x is a matroid, getsimplified(x) returns x

when x is simple, and a member of x when x is not simple. It does not do any real work.

If x is a list, simplify(x) returns a list of the same length, but with all loops removed, and every point except one from each multiple group removed. The integer that remains is the smallest one in the group. The order of the sets is preserved. It also sets the 'lmdata' attribute of the returned list to a list of 2 objects - the loop and multiple group data found in x.

If x is a list, unsimplify(x) returns a list of the same length, but with the loops and multiples added back. The order of the sets is preserved.

In case of error, e.g. invalid x etc., the function prints an error message and returns NULL.

Arguments

x

x can be a matroid object, as returned from the constructor matroid()
x can also be a list of vectors of positive integers, which are thought of as sets. All must be subsets of ground. They do not have to satisfy the matroid hyperplane axioms. For a definition of loop and multiple group in this case, see Details.

ground

The ground set of the sets in x (both simplify() and unsimplify()). It must be a vector of positive integers in strictly increasing order (not verified). If ground is NULL, it is set to the union of the sets in x.

loop

a vector of positive integers, the loops, to add to the list x; loop must be disjoint from ground (verified). If loop is NULL, the function looks for loop in the attribute data attr(x,'lmdata'). If there is no such attribute, loop is set to the empty set.

multiple

a list of vectors of positive integers, the multiple groups, to add to the list x; these groups must be pairwise disjoint and disjoint from loop (not verified). Each group must intersect the ground set in exactly one point (verified). If multiple is NULL, the function looks for multiple in the attribute data attr(x,'lmdata'). If there is no such attribute, multiple is set to the empty list.

...

not used

Details

First consider the case when x is a list of vectors of positive integers. Each vector represents a subset of the ground set. They are not required to satisfy the hyperplane axioms, but by abuse of language we will call them hyperplanes in this paragraph. A loop is a point (an integer in the ground set) that is in every hyperplane. Imagine now that all loops have been removed. Say that two points \(p\) and \(q\) are multiples iff for every hyperplane \(H\), \(p \in H\) iff \(q \in H\). This is an equivalence relation, and the multiple groups are the equivalence classes with more than one point. For computation it is convenient to think of a boolean incidence matrix. There is a column for each point in the ground set, and a row for each hyperplane. An entry is TRUE iff the point is in the hyperplane. A loop is then a column of all TRUEs. A multiple group is a maximal set of duplicate columns. This is basically how simplify() is implemented, except with optimizations that avoid computing the very large incidence matrix.

Now consider the case when x is a matroid object. When x was constructed, the simplification of x was computed (with help from the *previous* simplify()) and stored as a member of x (unless x was already simple). So in this case getsimplified(x) does not do any real work and only takes microseconds.

These functions are accelerated with C/C++.

References

Matroid - Wikipedia. https://en.wikipedia.org/w/index.php?title=Matroid&oldid=1086234057

See Also

rank(), matroid()

Examples

# an example using simplify.list() and unsimplify.list()
# get the matrix for CIE XYZ at 5 nm step size
mat3x81 = colorimetry.genlist[[1]]

# create the matroid
mat5 = matroid( mat3x81 )

#  test for simplicity
is_simple(mat5)
##  [1] FALSE

# get the list of hyperplanes, and simplify
hyper = gethyperplane( mat5 )
hypersimple = simplify( hyper )

# print the loop and multiple data found
attr(hypersimple,'lmdata')

# unsimplify and compare to the originals
# the list attr(hypersimple,'lmdata') is 'secretly' used in unsimplify()
identical( unsimplify(hypersimple), hyper )
##  [1] TRUE