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.

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:

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:

could form the starting point for that, like so:

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:


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:

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:

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:

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:
  • 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