Graph Visualization in Delphi

For a project at Oasis Digital, we need to show the end user a graphical representation of a graph (in the “graph theory” sense of the word). The application is written in Delphi, and in looking around I didn’t find any native Delphi components for doing that.

I did find GraphViz, and a COM Wrapper for it called WinGraphViz. Wiring the latter up to Delphi turned out to be quite easy. The minimal code to do it, for a demo app, is below. To make this compile you’ll need to import the type library for WinGraphviz.

procedure TExampleForm.DrawGraphForData(Data: string);
var
Dot: IDot;
Image: IBinaryImage;
ImageFileName: string;
begin
ImageFileName := 'c:image.gif';
Dot := CoDOT.Create;
Image := Dot.ToGIF(Data);
Image.Save(ImageFileName);
WebBrowser1.Navigate('file:///C:/image.gif');
end;

Production code would probably use a better way of getting the generated graph on to the screen. GraphViz support imagemaps, making it easy to make the notes clickable. It can draw various arrow types, node shapes, etc., and tries to lay out graphs in a readable way, without crossing lines, etc.

A trivial sample app looks like this:

Update: a correspondent pointed out that the graphic example above is a bit ugly, with non-anti-aliased lines and fonts. To resolve that, I turned to SVG; GraphViz can produce output in SVG format (among others), and the freely downloadable Adobe SVG Viewer can display them.

With slightly different code:

ImageFileName := 'c:image.svg';
Dot := CoDOT.Create;
Image := Dot.ToSVGZ(Data);
Image.Save(ImageFileName);
WebBrowser1.Navigate('file:///C:/image.svg');

We get an application with this appearance:

You can download the Delphi WinGraphViz Sample Application Source code.

More Bowling

In my last post, I presented an enhancement to a "bowling score calculator" problem being discussed on the Extreme Programming Mailing List. My solution extended a not-very-OO
solution presented here; though not object oriented, it was short and clear. I generally write intensively OO code, so I found this interesting.

A contention on the list, though, was that the procedural solution could not be extended to support more features easily. Today I’d added even more features, just to see if this is true:

  • Know how many pins are standing, and prevent the caller from knocking down
    more pins than are up.
  • Know which rolls occurred in which frame; be able to answer "what were
    the rolls in frame N?"
  • Present an HTML representation of the state of the game after each roll.

As usual, I added this features a test at a time a bit at a time. It turned out to be easy to keep track of which rolls go in which frame. The updated source code can be downloaded: bowling-java-3c.tgz and is also on github. As before the download includes the tests also. I’ve renamed a few things for greater clarity. (I’ve updated the file a couple of times since posting it, to fix a problem in the final output, and separate some tests I had combined.)

I was surprised to find that adding these features didn’t add much complexity to the code. When I look at this code, it cries out to have a class of some kind extracted – but I’ve tried extracting, for example, the idea of a Frame and been unsatisfied. Perhaps I’ll explore that more another day. These variable:

  private int[] frameScores = new int[NUM_FRAMES];
  private int[] firstRollInFrame = new int[NUM_FRAMES + 1];
  private int scoredFrame;
  private int finishedFrame;

could form the starting point for that, like so:

class Frame {
    private int score;
    private int firstRoll;
    private boolean scored;
    private boolean finished;
}

The Game class is in its entirety is
available here (syntax highlighted HTML) or in the download above.

I implemented the HTML rendering of frames without aid of test cases. The code is included
in the download above, and produces output like the sample run below. The output looks
much better when not included inside a WordPress post – the sample below is
partially mangled.

The main
loop of the demo program biases the random numbers toward high scores:

        while (!game.gameOver()) {
          // Bias our guy toward good rolls:
          int n = rnd.nextInt(game.pinsStanding() + 4);
          int pins = Math.min(n, game.pinsStanding());
          renderer.tellAboutPins(pins);
          game.roll(pins);
          renderer.printGame(game);
        }

Rolling… 7 pins

7

Rolling… 3 pins

7 3

Rolling… 10 pins

7 3

20

10

Rolling… 4 pins

7 3

20

10
4

Rolling… 2 pins

7 3

20

10

36

4 2

42

Rolling… 10 pins

7 3

20

10

36

4 2

42

10

Rolling… 0 pins

7 3

20

10

36

4 2

42

10
0

Rolling… 3 pins

7 3

20

10

36

4 2

42

10

55

0 3

58

Rolling… 10 pins

7 3

20

10

36

4 2

42

10

55

0 3

58

10

Rolling… 3 pins

7 3

20

10

36

4 2

42

10

55

0 3

58

10
3

Rolling… 5 pins

7 3

20

10

36

4 2

42

10

55

0 3

58

10

76

3 5

84

Rolling… 10 pins

7 3

20

10

36

4 2

42

10

55

0 3

58

10

76

3 5

84

10

Rolling… 4 pins

7 3

20

10

36

4 2

42

10

55

0 3

58

10

76

3 5

84

10
4

Rolling… 0 pins

7 3

20

10

36

4 2

42

10

55

0 3

58

10

76

3 5

84

10

98

4 0

102

Rolling… 1 pins

7 3

20

10

36

4 2

42

10

55

0 3

58

10

76

3 5

84

10

98

4 0

102

1

Rolling… 1 pins

7 3

20

10

36

4 2

42

10

55

0 3

58

10

76

3 5

84

10

98

4 0

102

1 1

104


Comments welcome, via email (address below).

How Many (Java) Classes Do You Need To Go (XP) Bowling?

An object-oriented developer searches for a reason to add more of them.

Ron Jeffries recently posted a couple of articles on simple design, with the
specific example of code to score a bowling game:

In a thread on the subject on the XP Mailing List, various posters expressed
a preference for one solution or the other.

With the caveat that I’m normally a very object-oriented guy, I prefer the
second (procedural) solution, in that I find has approriately simple design:
it work, expresses the programmer’s intentions, has (almost) no duplication
of ideas, and has the minimal amount of code needed to do all those things.

The point was made, though, that perhaps the procedural solution would fall
apart once the complexity of the problem increased. To test this idea, I decided
to extend it with the following features:

  • Know what frame the bowler is current done with / working one
  • Know the score of each frame
  • Know if the game is over
  • Reject erroneous input data

My first step was to convert the example C# code to Java. (I like C# at least
as much as Java, but for the moment I’m happier with the code-editing features
of Eclipse compared to VS.NET.) Here’s the Java code, the starting point before
adding any features:

/*
 * Trivial port of Ron Jeffries' Bowling to Java
 */
package bowling;

import java.util.ArrayList;

public class BowlingGame {

  ArrayList rolls = new ArrayList();

  public void roll(int roll) {
    rolls.add(new Integer(roll));
  }

  public int score() {
    int rollIndex = 0;
    int total = 0;
    for (int frame = 0; frame < 10; frame++) {
      if (strike(rollIndex)) {
        total += 10 + pinCount(rollIndex + 1) + pinCount(rollIndex + 2);
        rollIndex++;
      } else if (spare(rollIndex)) {
        total += 10 + pinCount(rollIndex + 2);
        rollIndex += 2;
      } else {
        total += pinCount(rollIndex) + pinCount(rollIndex + 1);
        rollIndex += 2;
      }
    }
    return total;
  }

  private boolean strike(int rollIndex) {
    return pinCount(rollIndex) == 10;
  }

  private boolean spare(int rollIndex) {
    return pinCount(rollIndex) + pinCount(rollIndex + 1) == 10;
  }

  private int pinCount(int pinPosition) {
    return ((Integer) rolls.get(pinPosition)).intValue();
  }
}

I also converted the NUnit tests to JUnit. (Formerly this was available for download,
but I’ve misplaced the file since then.)

With this in hand, I started adding tests for my new features. An example test:

  public void testStrikeWithFrameCounting() {
    game.roll(10);
    assertEquals(1, game.finishedFrames());
    assertEquals(0, game.scoredFrames());
    game.roll(5);
    assertEquals(1, game.finishedFrames());
    assertEquals(0, game.scoredFrames());
    game.roll(3);
    assertEquals(2, game.finishedFrames());
    assertEquals(2, game.scoredFrames());
    game.roll(2);
    assertEquals(2, game.finishedFrames());
    game.roll(1);
    assertEquals(3, game.finishedFrames());
    assertEquals(3, game.scoredFrames());
    rollMany(14, 0);
    assertEquals(10, game.finishedFrames());
    assertEquals(10, game.scoredFrames());
    assertEquals(29, game.score());
  }

This test, and others like it, verify that after each roll, the game object
know what frame has been completed, what frame is scorable, and when the game
is over. (I also added the feature to report the score of each frame, but didn’t
get around to testing it explicitly. I found that to get things right, I needed
a variety of tests for things happening in the last frame, since there are special
rules there.

Without further ado, here is working code to score the game, with the new features:

/*
 * Bowling Scorer, converted to Java, extended to know what
 * frame we are on, what frame has been scored, whether the
 * game is over, and the score of each frame
 */
package bowling;

public class BowlingGame {

  private static final int NUM_FRAMES = 10;
  private static final int NUM_PINS = 10;
  private static final int MAX_ROLLS_IN_GAME = NUM_FRAMES*2 + 1;

  // Input state:
  private int[] rolls = new int[MAX_ROLLS_IN_GAME];
  private int rollSoFar = 0;

  // Output state:
  private int[] frameScores = new int[10];
  private int scoredFrame;
  private int finishedFrame;

  // Processing variables; these would be locals, but
  // this class essentially is a "method object", so we
  // use instance variables instead of param passing
  private int scoringFrame;
  private int scoringRoll;

  public void roll(int roll) {
    if(roll<0 || roll>NUM_PINS)
      throw new RuntimeException("Roll out of range");

    if(gameOver())
      throw new RuntimeException("The game is over, no more rolls allowed.");

    rolls[rollSoFar++] = roll;
    calculate();
  }

  private void calculate() {
    scoredFrame = 0;
    finishedFrame = 0;
    scoringRoll = 0;
    for (scoringFrame = 1; scoringFrame <= NUM_FRAMES; scoringFrame++) {
      if (isStrike()) {
        scoreStrike();
      } else if (isSpare()) {
        scoreSpare();
      } else {
        scoreNormal();
      }
    }
  }

  private boolean isStrike() {
    return rolls[scoringRoll] == NUM_PINS;
  }

  private void scoreStrike() {
    storeFrameScore(NUM_PINS + rolls[scoringRoll + 1] + rolls[scoringRoll + 2]);
    frameIsScoredIfWeHaveRollOffset(2);

    if(scoringTheLastFrame())
      frameIsDoneIfWeHaveRollOffset(2);
    else
      frameIsDoneIfWeHaveRollOffset(0);
  }

  private boolean isSpare() {
    return rolls[scoringRoll] + rolls[scoringRoll + 1] == NUM_PINS;
  }

  private void scoreSpare() {
    storeFrameScore(NUM_PINS + rolls[scoringRoll + 2]);
    frameIsScoredIfWeHaveRollOffset(2);

    if(scoringTheLastFrame())
      frameIsDoneIfWeHaveRollOffset(2);
    else
      frameIsDoneIfWeHaveRollOffset(1);
  }

  private void scoreNormal() {
    storeFrameScore(rolls[scoringRoll] + rolls[scoringRoll + 1]);
    frameIsScoredIfWeHaveRollOffset(1);
    frameIsDoneIfWeHaveRollOffset(1);
  }

  private boolean scoringTheLastFrame() {
    return scoringFrame == NUM_FRAMES;
  }

  private void storeFrameScore(int frameScore) {
    frameScores[scoringFrame - 1] = frameScore;
  }

  private void frameIsDoneIfWeHaveRollOffset(int rollOffset) {
    if(scoringRoll + rollOffset < rollSoFar) {
      finishedFrame = scoringFrame;
    }
    // Continue scoring at the roll after the last one
    // on this frame:
    scoringRoll += rollOffset + 1;
  }

  private void frameIsScoredIfWeHaveRollOffset(int rollOffset) {
    if(scoringRoll + rollOffset < rollSoFar) {
      scoredFrame = scoringFrame;
    }
  }

  // The public interface has a few more methods for the new features:

  public int score() {
    int totalScore = 0;
    for(int i=0; i<frameScores.length; i++)
    totalScore += frameScores[i];
    return totalScore;
  }

  public int scoredFrames() {
    return scoredFrame;
  }

  public int finishedFrames() {
    return finishedFrame;
  }

  public int scoreForFrame(int frame) {
    return frameScores[frame-1];
  }

  public boolean gameOver() {
    return finishedFrame == NUM_FRAMES;
  }
}

Here is what I like about this solution:

  • There are tests to show that it actually works
  • The method names are, at least to me, intention-revealing
  • The methods are short and straightforward
  • The main scoring loop, which still happens in one straight-line pass, is
    simply this:

        for (scoringFrame = 1; scoringFrame <= NUM_FRAMES; scoringFrame++) {
          if (isStrike()) {
            scoreStrike();
          } else if (isSpare()) {
            scoreSpare();
          } else {
            scoreNormal();
          }
        }
  • There’s not much duplication left in there; perhaps someone can suggest
    a way to get rid of the bits that remain

The real question, of course, is whether this is too much for one class to
do – whether there are any parts of this code that should be a separate class.
The obvious candidates are the pairs of methods: should isStrike() and scoreStrike()
somehow be in a Strike class? They have an obvious parallel structure, a form
of duplication that I might be able to get rid of by adding classes.

I thought these new features would push me there – but they didn’t. Perhaps
a future story would do so. This implementation is still not quite “finished”,
in that I know there are more kinds of error conditions to consider, test for,
and implement. I don’t see any reason to think that adding those now would add
much to the conversation, so I didn’t add them.

One lesson of this exercrise, to me, is a common one: the problem space is
not the solution space
. Just because we have a thing called a Foo in the problem
domain, doesn’t mean we need a class Foo in the solution. We might, we might
not; with test-driven design, the need for a Foo should eventually become obvious.

Comments welcome, via email (address below) or on the XP mailing list.

Word Chains Kata Solution

I worked out a solution for “Pragmatic” Dave Thomas’s Code Kata 19 (Word Chains) in Java; it’s somewhat different than Dave’s published solution.

I’ve been watching PragDave’s Code Katas with interest, since I am also in the habit of occassionally solve a small, standalone programming problem just for the learning experience. Today I worked out a solution for Kata 19, Word Chains. I did this Kata the “pure” way, i.e. without looking at any of the discussion of solution approaches before coding. Here are the results (also on github). I wrote the code this time in Java.

Unlike Dave’s published solution, I didn’t precalculate adjacency lists; rather I took the more brute-force approach of scanning the word list at each step looking for neighbor words. In spite of that non-optimization, this still calculates the word chains for a bunch of examples in a few seconds (total).

I was curious how much of the program’s time is spent checking for neighbor words; this provided a good reason to try out a profiler plug for Eclipse, available on SourceForge. The profiler worked fine, and told me, as I would have guessed, that the program spends approximately 100% of it’s time looking at words to decide if they are neighbors (in the word-chains sense). Of course the usual optimization advice applies: it would have been actively stupid of me to optimize without measuring where the slow parts are.

Upcoming talk at SD 2004

I’m giving a talk on data handling in a disconnected mode appliction next year at SD Expo 2004.

I’m giving a talk on data handling in a disconnected mode appliction next year at SD Expo 2004. This applies to wireless / mobile applications running on notebook PCs, PDAs, even smaller devices like “SmartPhones”.

Details are here

Javascript Talk at St. Louis OOSIG

Notes from my OOSIG talk on JavaScript, a classless (prototype-based) OO language

On October 16, 2003, I spoke on “Objects without Classes”, the non-class-based object model implemented by JavaScript and some other OO languages. The (brief) presentation is available here:

Talk in Powerpoint format

The plain text of the slides (which is, frankly, plenty good enough) follows:

Continue reading “Javascript Talk at St. Louis OOSIG”