Djinni  2.2
Hacking

We sincerely hope you will find hacking on Djinni to be a pleasant and rewarding experience.

Djinni's annealers use C++ in fairly standard industry idioms. You will need to be familiar with the basic concepts of object oriented analysis and design, as well as the use of templates and generic programming, particularly partial template specialization.

We will not be covering the Annealer constructors, member functions or other details here. The reader is referred to the API documentation for those matters.

Tools Necessary

In addition to the tools required for compiling Djinni, you will also need the GNU Autotools toolchain. Please use the most recent version available. In hacking Djinni, we use:

Hacking the Annealer

An annealer is parameterized by its penalty function and the kind of solution upon which it's working. Penalty functions govern the behavior of the lambda term in the annealing equasion. Solutions represent hyperplanes within larger solution spaces.

Since these are template parameters, there is no PenaltyFunc superclass, nor any SolutionType superclass. Something is a PenaltyFunc if it passes the duck test--if it quacks like a duck, flies like a duck and looks like a duck, it's a duck.

Hacking Annealer Penalty Functions

A PenaltyFunc must make a public typedef:

... substituting your own lambda term's value type for foo, of course. This typedef is used by Annealer to know what type of data to expect from the lambda term. Almost always your PenaltyFunc will yield a value of type double, but we see no reason to confine you to that. If your PenaltyFunc needs to yield a complex custom data type, you can do that just fine, as long as it has basic mathematical operators available for it.

A PenaltyFunc must implement a method signature compatible to:

... by 'compatible to' we mean that it can accept any parameter, as long as an implicit conversion exists between uint32_t and its parameter type. For instance, you could have operator()(const double) , since an implicit conversion exists from int to const double.

If your PenaltyFunc implements that one typedef and that one method signature, then it can be used as a PenaltyFunc with Annealer.

Hacking Annealer Solution Types

A SolutionType has a lot of responsibilities. It must keep track of its solution, offer facilities for generating a new SolutionType which adjoins itself in the solution space, provide accessors for the feasible and infeasible costs of the solution, and other details.

Keeping track of the solution space is entirely your responsibility. Djinni is entirely agnostic on how solution spaces should be represented. Our provided sample SolutionType, TSPRoute, shares a pointer to a data structure representing the solution space for an instance of the Traveling Salesman Problem. Please do not think you must do likewise. Please do not confuse architectural choice with architectural necessity.

With that said, TSPRoute is close to the minimal set of methods which will pass the duck test for a SolutionType. To wit, SolutionTypes must provide methods with signatures compatible to:

Of these, please note that update and compute may very well be empty functions for certain kinds of solutions. However, given that annealing is inherently stochastic, we strongly recommend your randomize method do what's expected.

Additionally, SolutionTypes must have std::ostream& operator<<(std::ostream&, const SolutionType&) overloaded appropriately for them. Annealer uses streams to create human-readable output of solutions.

Partial Template Specialization

Some PenaltyFuncs may require Annealer to handle things slightly differently. If this is the case, make a partial template specialization, as we did for Annealer<Compressed, SolutionType>.

Putting It All Together

If you're writing a new penalty function, please consider adding it to the file Penalties.h . Typically penalty functions are small and terse, making them easy to put in one single header file.

If you're writing a new solution type, please consider making a new subdirectory off src/ and put it in there.

You will need to understand Autotools to hack on the build system. Autotools is a nontrivial piece of software. Please ask your local Autotools guru for help.

Once this is done, it's time to hack the swig/swig.i file. You may want to refer to the SWIG documentation for this. The hand-holding here is not meant, in any way, to replace the SWIG documentation.

The first line you see, %module, just gives the name by which the resulting Python module will be known. If you've got Djinni installed successfully and you want to leave your existing Djinni alone while you further develop it, you may want to rename this Djinni_dev. (Or Elvis, for all we care. Hail to the King, baby.)

The second thing you see, %{ ... %}, encapsulates a list of header files. This is C++ code which SWIG must insert into its own self-generated C++ code in order to work properly. As a rule of thumb, if you're going to have SWIG generate Python bindings for an object, you need to #include the header file containg the definition for that object.

The third thing you see are %include statements. These are commands to SWIG, telling it to read through those files and generate bindings for everything it sees. SWIG also comes with some libraries that are very useful, such as automagically converting std::strings into Python strings: those, too, are included here.

Finally, you'll see some %template parameters. These are necessary because of an irreconcilable difference between C++ and libraries. C++ templates exist in header files, not libraries. There is no executable code associated with a template; a template is just a set of rules telling the compiler how to generate executable code in the event it's needed. This is problematic if you're trying to create a library for Python to call out to!

Thus, we need to explicitly tell SWIG to instantiate a few templates. %template(foo) bar; tells SWIG to instantiate the fully parameterized template class bar and to make that available within the generated Python library under the name foo.

As of SWIG 1.3.17, SWIG is a little touchy with respect to using typedefed names. For instance, TravelingSalesman is a typedef for TSPRoute<TSPTWWorld>; yet, if we try to %template(TSP) TravelingSalesman, SWIG will complain about a syntax error. Using the typedefed name as a parameter type, as we do with the CA_TSP and SA_TSP template instantiations, causes no error. If you're sure your code is fine but SWIG is still complaining, try avoiding all typedefs in the base name and its parameterization.

Rolling Your Own (Package, That Is)

Once all of this is done, you'll be ready to go. First, enter the directory above src/ (i.e., where you uncompressed Djinni) and clean up your tree with make clean. Then do a dance of aclocal -I m4 && autoconf && automake && libtoolize. From there you can reconfigure, remake, and reinstall.

If all else fails...

If all else fails, you can email the core Djinni developers at rjh@sixdemonbag.org or tthiede@thetiredsaint.com. If our schedules permit, we'd be happy to help you with your hacking and packaging. However, we don't work for free. For UI students, we typically charge a good meal at the Summit and a cold beer to wash it down afterwards.