View of Manhattan from Brooklyn Heights Home Page
Software Development

Oid - An Interactive Software System For Experimenting With Matroids

Click here to download Oid and learn more about it. Read further for a brief description.

Oid is an open source, interactive, extensible software system for experimenting with matroids. It allows the user to enter a matroid in different formats (matrix over a finite field, set of basis etc.). It computes most matroid invariants using the best possible algorithm from an array of choices using rudimentry intelligence and also computes several things relevant for matroid structure results such as deletions/contractions, extensions/coextensions, minors etc. It can play an analogous role in matroid research to that of GAP in group theory research if there were more people in matroid theory who also know how to code.

Oid was designed to treat algorithms as data and by that I mean algorithms are plug-ins for Oid. So new algorithms can be added without recompiling the existing code. This makes it easy to add new procedures quickly and with minimal effort. In other words, it is built to last a long time without getting outdated.

Further since graphs, codes, and linear spaces can be viewed as matroids, Oid handles these objects too. Ina nutshell, Oid serves as a platform for experimenting with combinatorial objects and helps in pbtaining examples, conjectures, proof ideas etc.

The name Oid comes from a humorous paper called "Oids and their ilk" that gently makes fun of our tendency to work with the most abstract possible object.

Read further if you know something about designing software.

Oid models combinatorial objects using Java interfaces. A combinatorial object may be entered and stored in the system in many different ways. Each such representation is modeled by a class that implements the object's interface. Algorithms in the system are also modeled by classes that implement generic algorithm interfaces. At runtime, a simple intelligent system delegates tasks to the appropriate algorithm.

In designing Oid, we also designed a framework for systems that work with a specific family of objects and treat algorithms for those objects as data. Gamma et al in their book Design Patterns: Elements of Reusable Object-Oriented Software define a framework as a set of cooperating classes that make up a reusable design for a specific class of software. The framework can be used to create other systems that work with a specific family of objects and treat algorithims for those objects as data.

There are a number of reasons to write a framework that treats algorithms as data. As mathematicians we frequently devise procedures to look for patterns in the objects we are studying. This system allows us to quickly code algorithms without having to think of any other programming details and it is flexible enough to accomodate a variety of perspectives.

DESIGN DETAILS

Java is an object-oriented language with broad cross-platform support and a rich set of libraries for GUI elements, for which compilers and other development tools are freely available. It is easy to learn and does not require explicit handling of pointers. Java also provides a set of reflection classes which allow a system to refer to object classes as data. This is important to the system's ability to accept new algorithms without changes to the core of the system itself. So, we decided to implement the framework in Java. We followed the guidelines in Gamma, et al for object-oriented design using patterns, and particularly follow these principles:

  1. Program to an interface, not an implementation.
    All of the major object classes in the system are accessed through Java interfaces, which allow the classes themselves to be modified or added to without breaking the system.

  2. Favor object composition over class inheritance.
    To the extent possible, the object classes have been designed to be small and independent, to make them reusable in new representations and algorithms.

  3. Use delegation to allow composition of behaviors at run-time.
    The system operates by accepting user input and passing that input to a "toolkit'' class which delegates the command to a "smart" matroid class, which in turn selects a matroid representation and algorithm to perform the task. Therefore, a developer adding an algorithm to the system need to be concerned with the inner workings of the system.

Interfaces

An interface is a specification of a set of methods or member functions. An object class is said to implement an interface if it has as member functions all of the functions specified in the interface. When an object class implements an interface, an instance of the object can be referred to using only the interface, instead of the object's intrinsic type. Each combinatorial object in the system has its own Java interface and all representations of the object perform the functions specified in the interface. At present, the system has a 'Matroid' interface and two matroid representation classes 'GFpMatroid' class and a 'BasisMatroid' class that implement the interface. The 'Matroid' interface specifies the matroid oracles that should be in each matroid representation class.

Interfaces are useful because they allow portions of a system to be modified without affecting the rest of the system. An object class can be modified, but nothing else needs to change as long as it continues to implement the interface that the rest of the system uses to refer to it. Furthermore, since an interface specifies a general set of behaviors for classes that implement it, new matroid representation classes can be added without changing the rest of the system.

Each algorithm class must specifiy which representations it works with and must implement one of the five algorithm interfaces listed below. These five interfaces are not meant to be exhaustive, rather just a reflection of our limited knowledge of what would be useful.

  1. 'SubsetLister' interface: Algorithms that implement this interface accept a matroid as input, and produce a collection of subsets as output. Examples include algorithms that list circuits, independent sets, and flats.

  2. 'PropertyCalculator' interface: Algorithms that implement this interface accept a matroid as input and produce a numerical value.

  3. 'SingleConstructor' interface: Algorithms that implement this interface accept a matroid as input and return another matroid as output. Examples include an algorithm which contracts a specified element from a matroid.

  4. 'CollectionConstructor' interface: Algorithms that implement this interface accept a matroid as input, and generate a collection of matroids as output. Examples include algorithms to generate all single-element contractions of a single matroid.

  5. 'Combiner' interface: Algorithms that implement this interface accept a collection of matroids as input, and generate a single matroid as output.

The above interfaces are actually specified in terms of Java objects, not matroids. The methods which are used to provide input to the algorithms simply reject inappropriate input by throwing an exception. So these same interfaces can be used in other systems developed with this framework. The framework should be viewed as an evolving structure for which new parts can be added with varying levels of difficulty. It is easier to add a new representation to an existing combinatorial object (whose interface is already there) than to add a new combinatorial object (which needs a new interface). It is relatively easy to add new algorithm interfaces as the need for them arises. It is easiest of all to add a new algorithm; the entire framework is geared to this purpose. We can reduce the process of adding algorithms to a fill-in-the-blanks template.

Self-Referentiality

With all of these representations and algorithms that work for some but not all representations, the system needs at least rudimentary intelligence for keeping track of what representations and algorithms are available and optimal for the task at hand. It does this by using self-referentiality. Representations and algorithms are self-referential; that is, they can provide an estimate of the number of steps required to execute their methods.

When a matroid in a particular representation is entered and a task selected, the system can determine not only the fastest algorithm for that particular representation, but the fastest combination of algorithm and representation. For example, given a choice between a GFpMatroid instance and a 'BasisMatroid' instance, the system will generally choose the 'BasisMatroid' instance if it is generating a list of independent sets. On the other hand, if the number of bases is larger than the number of steps required to determine rank of a subset, the system will choose GFpMatroid.

To provide these estimates, each matroid representation and algorithm implements an interface called 'ComplexityProvider'. This interface specifies methods that return estimates of the number of steps required for various matroid methods to execute. 'ComplexityProvider' methods can return a flag value of -1 to indicate that a particular method cannot be executed with the indicated input; for example, if an algorithm requires a specific matroid representation, its complexity estimating methods will return a-1 if asked to provide an estimate with a different representation.

Smart Objects

Each combinatorial object also has a "smart" class that implements the object's interface and keeps track of the different representations and algorithms. For example, the 'SmartMatroid' class stores a collection of different representations of a single matroid, and determines which algorithm and representation to use in response to a user request. It selects the algorithm and matroid representation that, together, provide the lowest complexity estimate for the class, and uses that combination to complete the task. We will enhance this ability to include some planning capability; for example, in some cases it may be faster to use one representation to create an instance of another representation and then execute an algorithm than to simply run the algorithm with the existing representation.

As we add other combinatorial objects to the system, we will include other varieties of "smart objects''. For example, we are currently working on adding graph functionality to the system. As we write graph algorithms, a 'SmartGraph' class will optimize their use in the same way that SmartMatroid optimizes matroid algorithms. Moreover, since a graph can be thought of as a matroid, all Oid graph representations will include methods that allow them to be converted to equivalent matroid representations. As other object classes are added to Oid, they will be given similar capabilities, in parallel to the relationships between the combinatorial objects they model.

STEPS FOR ADDING A NEW ALGORITHM

  1. Choose the right algorithm interface from the five mentioned in Design Details, and write the algorithm to implement the interface. It is easiest to begin with the skeleton provided by the interface, and then add code particular to the algorithm.

  2. Specify which representations the algorithm works for. It should generate an exception if not given the correct representation.

  3. Write methods to estimate the complexity of the algorithm. The algorithm should implement the ComplexityProvider interface. The algorithm's complexity estimating methods may, in turn, rely on its input representation's complexity estimating methods. This enables the system to determine, for example, whether using a GFpMatroid representation or a BasisMatroid representation of a given matroid will result in faster execution.

  4. The system reads a text file, matroidTaskAlgorithmList.txt, to determine which algorithms are available. When more than one algorithm is available to perform a specific task, each must implement the same algorithm interface. If the algorithm performs a new task, that is not already listed in the Tasks menu, add a line to matroidTaskAlgorithmList.txt describing the task as follows:

    task taskName interfaceNametaskDescription

    Here, interfaceName refers to the algorithm interface the new algorithm implements, and taskDescription refers to the description to be displayed on the Tasks menu.

  5. Add another line describing the new algorithm as follows:

    algorithm className taskName representationClass algorithmDescription

    Here, className is the name of the Java class containing the algorithm, taskName is the same as in Step 4, representationClass is the matroid representation accepted by the algorithm as input, and algorithmDescription is the menu description for the algorithm. This description will appear only if there is more than one non-trivial algorithm for a specific task, in which case the system provides the user with a choice of algorithms on the Tasks menu.

  6. Compile only the new algorithm class and run Oid. The new algorithm should appear on the Tasks menu.