Tree display program (update)

Well, I handed in a rather inconclusive version of the essay I mentioned. It and the program used to generate the trees are both here.

I'd love it if anyone found the program useful - and anyone's more than welcome to do anything with the code, although I'd appreciate a heads-up out of interest. Enjoy!

Tree display program

I've been writing away at a compulsory second year essay for what seems ages now. In particular, this one's about Goodstein's Theorem. When it's done (which will definitely be before the deadline in 3 weeks' time), I'll see what I can do about posting a version.

However, for now, I've been working on a bit in the proof of the theorem. What you need to do is express a number in hereditary base-n notation which is explained on the Wikipedia article I just linked to. Now suppose you draw a rooted finite tree in the following way (let's express 93 in base 2).

First note that:

Now build a tree one level of branches at a time. In the first level, is a branch for each term in the expansion above. Then a child of each node has children that are the terms in the exponent of that child... It'll make more sense with a picture:



I hope :)

So what I wrote was a program that would generate that sort of picture because I needed some in the essay and couldn't find something on the internet to draw it. To save problems with file formats etc., the program actually exports to SVG - to generate png images for here and for PdfLatex in the essay I used the command "inkscape -f file.svg -e file.png", which I found here. So I'm going to try and post the code below. The command line options are:

Options:

--help                       produce help message
-b [ --base ] arg (=2)       set base of expansion
-s [ --stroke ] arg (=black) set colour of stroke
-f [ --fill ] arg (=red)     set colour of fill
-w [ --width ] arg (=800)    width of image
-h [ --height ] arg (=600)   height of image
-o [ --output ] arg (=-)     Output file

And to make the picture above, use:

maketree 93 -b 2

To compile, you just need boost program options.



Anyway, here are the sources:



Makefile:

maketree: maketree.o NumberTree.o SVGOut.o
g++ -g -lboost_program_options -o $@ $^

%.o: %.cc
g++ -O0 -g -I/usr/include/my-boost -Wall -c $<

clean:
rm *.o

NumberTree.cc:

#include "NumberTree.hh"
#include <math.h>
#include <boost/foreach.hpp>
#include <sstream>

using std::ostream;

NumberTree::NumberTree( long n, int b )
: output_width(800), output_height(600), width(-1), height(-1),
  base(b)
{
while( n ) {
  int hp = find_hipow(n,b);

  children.push_back( TreePtr(new NumberTree(hp,b)) );
  n -= static_cast<int>(pow(b,hp));
}
}

void
NumberTree::BracketPrint( ostream& os ) const
{
os << "(";
for( unsigned int i=0; i<children.size(); i++ ) {
  children[i]->BracketPrint(os);
  if(i<children.size()-1)
    os << ",";
}
os << ")";
}

int
NumberTree::find_hipow( long n, int b ) const // TESTED
{
if(n < 1 || b < 2)
  throw "Invalid parameters";
return static_cast<int>(floor(log(n)/log(b)));
}

long
NumberTree::eval( int b ) const // TESTED
{
long total=0;

BOOST_FOREACH( const TreePtr& pt, children ) {
  total += static_cast<long>(pow(b, pt->eval(b)));
}

return total;
}

void
NumberTree::printSVG( SVGOut& so )
{
so.start();

std::ostringstream os;
os << eval(base);
so.annotated_circle(0.5,0,os.str());
printSVGBranches(so,0,1,1,0,0.5,
                 1.0/calcHeight(),1.0/calcWidths());
so.end();
}

int
NumberTree::calcWidths()
{
if( widths.size() ) return width;

if(!children.size()) return 0;

int w = 0;
BOOST_FOREACH( TreePtr& pt, children ) {
  int t = pt->calcWidths();
  w += t+1;
  widths.push_back(t);
}

return width = w-1; // subtract one to lose padding on RHS
}

int
NumberTree::calcHeight()
{
if( height != -1 ) return height;

int max=-1;
BOOST_FOREACH( TreePtr& pt, children ) {
  int th = pt->calcHeight();
  if(max<th) max = th;
}
return height = max+1;
}

void
NumberTree::printSVGBranches( SVGOut& o,
                            float l, float t, float r, float b,
                            float px, float lineheight, float xscale )
{
int lhs = 0;

BOOST_FOREACH( const TreePtr& pt, children ) {
  int w = pt->calcWidths();

  float newmid = lhs + w/2.0;
  if(calcWidths() == 0)
    newmid = 0;
  else
    newmid /= calcWidths();
  newmid *= r-l;
  newmid += l;

  std::ostringstream os;
  os << pt->eval(base);
  o.annotated_circle(newmid, lineheight+b, os.str());

  o.line(newmid,lineheight+b,px,b);

  pt->printSVGBranches(o, l+lhs*xscale, t, l+(lhs+w)*xscale,
                       b+lineheight, newmid, lineheight, xscale );

  lhs += w+1;
}
}

NumberTree.hh:

#ifndef NUMBERTREE_HH
#define NUMBERTREE_HH

#include <iostream>
#include <vector>
#include <boost/shared_ptr.hpp>
#include "SVGOut.hh"

class NumberTree
{
public:
/* Construct tree from n with given base */
NumberTree( long n, int b );

/* Print as parentheses */
void BracketPrint( std::ostream& os ) const;

/* Evaluate as powers of b */
long eval( int b ) const;

/* Output SVG to stream */
void printSVG( SVGOut& so );

private:
/* Find the largest power of b that is less than n */
int find_hipow( long n, int b ) const;
/* Find the width in branches of the tree and populate knowledge of
 * widths of our immediate children */
int calcWidths();
/* Find the height of the subtree below us */
int calcHeight();
/* Draw our subtree to SVG */
void printSVGBranches( SVGOut& os,
                       float l, float t, float r, float b,
                       float px, float lineheight, float xscale );

/* Output sizes for SVG */
int output_width, output_height;

/* The actual important data! */
typedef boost::shared_ptr<NumberTree> TreePtr;
std::vector<TreePtr> children;

/* Widths for printing */
std::vector<int> widths;
/* Width - must be dirtied to -1 if we change something */
int width;
/* Height - must be dirtied to -1 if we change something */
int height;

/* Base of expansion */
int base;
};

#endif

SVGOut.cc:

#include "SVGOut.hh"
#include <cmath>

using std::string;

SVGOut::SVGOut( std::ostream& os, int width, int height, int margin )
: o(os), top(margin), left(margin), right(width-margin),
  bottom(height-margin), _margin(margin), fill("black"),
  stroke("black")
{
set_circle_radius(0.01);
set_font_size(0.03);
}

void
SVGOut::start()
{
o << "<?xml version=\"1.0\" encoding=\"ISO-8859-1\" standalone=\"no\"?>\n"
  << "<!DOCTYPE svg PUBLIC \"-//W3C//DTD SVG 20010904//EN\"\n"
  << "\"http://www.w3.org/TR/2001/REC-SVG-20010904/DTD/svg10.dtd\">\n"
  << "<svg xmlns=\"http://www.w3.org/2000/svg\"\n"
  << "     xmlns:xlink=\"http://www.w3.org/1999/xlink\"\n"
  << "     width=\""
  << static_cast<int>(fabs(right-left) + 2*_margin)
  << "\" height=\""
  << static_cast<int>(fabs(top-bottom) + 2*_margin)
  << "\">\n";
}

void
SVGOut::end()
{
o << "\n</svg>\n";
}

void
SVGOut::circle( float x, float y )
{
boost::tuple<float,float> ddpos = xyToSVG(x,y);

o << "  <circle cx=\""
  << ddpos.get<0>()
  << "\" cy=\""
  << ddpos.get<1>()
  << "\" r=\"" << circle_radius << "\" style=\"stroke: "
  << stroke << "; fill: " << fill << ";\"/>\n";
}

void
SVGOut::line( float x1, float y1, float x2, float y2 )
{
boost::tuple<float,float>
  ddpos1 = xyToSVG(x1,y1),
  ddpos2 = xyToSVG(x2,y2);

o << "  <line x1=\""
  << ddpos1.get<0>() << "\" y1=\""
  << ddpos1.get<1>() << "\" x2=\""
  << ddpos2.get<0>() << "\" y2=\""
  << ddpos2.get<1>() << "\" style=\"stroke: "
  << stroke << ";\"/>\n";
}

boost::tuple<float,float>
SVGOut::xyToSVG( float x, float y ) const
{
return
  boost::make_tuple( float( (right-left)*x + left ),
                     float( (top-bottom)*y + bottom ) );
}

void
SVGOut::text( const string& s, float x, float y )
{
boost::tuple<float,float> ddpos = xyToSVG(x,y);

o << "  <text x=\"" << ddpos.get<0>() << "\" y=\"" << ddpos.get<1>()
  << "\" font-family=\"Verdana\" font-size=\""
  << font_size << "\" fill=\"black\">"
  << s
  << "</text>\n";
}

void
SVGOut::set_fill_colour( const string& colour )
{
fill = colour;
}

void
SVGOut::set_stroke_colour( const string& colour )
{
stroke = colour;
}

void
SVGOut::set_circle_radius( float rad )
{
circle_radius = rad*fabs(right-left);
vanilla_circle_radius = rad;
}

void
SVGOut::set_font_size( float size )
{
font_size = size*fabs(top-bottom);
}

void
SVGOut::annotated_circle( float x, float y, const std::string& s )
{
circle(x,y);
text(s, x+vanilla_circle_radius*1.1, y );
}

SVGOut.hh:

#ifndef SVGOUT_HH
#define SVGOUT_HH

#include <iostream>
#include <string>
#include <boost/tuple/tuple.hpp>

class SVGOut
{
public:
SVGOut( std::ostream& os, int width, int height, int margin );

void set_fill_colour( const std::string& colour );
void set_stroke_colour( const std::string& colour );
// rad, size are compared to the [0,1]x[0,1] canvas!
void set_circle_radius( float rad );
void set_font_size( float size );

void start();
void end();

/* Element creation functions */
void circle( float x, float y );
void line( float x1, float y1, float x2, float y2 );
void text( const std::string& s, float x, float y );
void annotated_circle( float x, float y, const std::string& s );

private:
boost::tuple<float,float> xyToSVG( float x, float y ) const;

/* Output stream ref */
std::ostream& o;
/* Input sizes */
float top,left,right,bottom;
float _margin;
/* Colours */
std::string fill, stroke;

/* Other settings: Only change throught set_ functions */
float circle_radius, font_size;
float vanilla_circle_radius;
};

#endif

maketree.cc:

#include <iostream>
#include <string>
#include <errno.h>
#include <boost/program_options.hpp>
#include <fstream>
#include "NumberTree.hh"
#include "SVGOut.hh"

void usage()
{
std::cerr << "I need exactly 1 argument, which is a number.\n";
exit(1);
}

int main( int argc, char* argv[] )
{
using std::string;

namespace po = boost::program_options;
po::options_description standard("Options");
standard.add_options()
  ("help", "produce help message")
  ("base,b", po::value<unsigned int>()->default_value(2), "set base of expansion")
  ("stroke,s", po::value<string>()->default_value("black"), "set colour of stroke")
  ("fill,f", po::value<string>()->default_value("red"), "set colour of fill")
  ("width,w", po::value<unsigned int>()->default_value(800), "width of image")
  ("height,h", po::value<unsigned int>()->default_value(600), "height of image")
  ("output,o", po::value<string>()->default_value("-"), "Output file")
  ;

po::options_description hidden("Options");
hidden.add_options()
  ("number", po::value<unsigned long int>(), "number to be represented");

po::options_description all("Options");
all.add(standard).add(hidden);

po::positional_options_description pos;
pos.add("number", 1);

po::variables_map vm;
po::store(po::command_line_parser(argc, argv).
          options(all).positional(pos).run(), vm);
po::notify(vm);

if (vm.count("help")) {
  std::cerr << standard << "\n";
  return 1;
}

string output = vm["output"].as<string>();

std::ostream* os;
if( output == "-" ) os = &std::cout;
else {
  os = new std::ofstream(output.c_str());
  if(!os) {
    std::cerr << "Could not open output file.";
    return 1;
  }
}

if (vm.count("number")) {
  NumberTree tree(vm["number"].as<unsigned long int>(),
                  vm["base"].as<unsigned int>() );
  SVGOut sout(*os,
              vm["width"].as<unsigned int>(),
              vm["height"].as<unsigned int>(),
              30);

  sout.set_fill_colour( vm["fill"].as<string>() );
  sout.set_stroke_colour( vm["stroke"].as<string>() );

  tree.printSVG(sout);
}

if( output != "-" ) delete os;
}