Brian's Waste of Time

Mon, 09 Aug 2004

Algorithmic Fun-ness

I spent a chunk of time on Saturday cleaning up grafolia (and importing into ASF CVS) and plunking in the hooks between it and OJB to let grafolia manage OJB's object states. It works really nicely. One of the big goals (personally) for me was to support statement reordering in a robust way. This has been fun =)

Topological sorting is fun =) I haven't been exposed to this particular problem before (though it smells like other directed graph problems), so am trying to come up with a not-too-inefficient algorithm on my own, before I go research the best fit i can find for my class of problem.

If you want to try, a basic comparator function might look like:

public static class TopologicalComparator
    public static final int BEFORE = -1;
    public static final int AFTER = 1;
    public static final int EQUAL = 0;
    public static final int NO_COMPARISON = Integer.MAX_VALUE;

    public int compare(final Change changeOne, final Change changeTwo) {
        /* ... */

That said, the comparator function is probably the wrong apporach and building a directed graph of dependencies and traversing naively will probably yield an easier-to-follow (maintain) algorithm. Wheee, fun fun.

8 writebacks [/src/java/ojb] permanent link