Volume Number: 18 (2002)
Issue Number: 05
Column Tag: Programmer's Challenge

by Bob Boonstra, Westford, MA

I do jigsaw puzzles in streaks. I’ll go for years without doing one. After all, there is something fundamentally wasteful about spending countless hours on putting something together that is destined to be disassembled and put back into the box. Then again, I’ll find myself on vacation welcomed by several days of soaking rain, and I’ll start one. If you’re like me, it’s impossible to start a puzzle without finishing it. Doing so would be admitting defeat, and one cannot allow oneself to be defeated by something that lives in a box in the closet. I also refuse, unlike some members of my immediate family, to cheat by using the picture on the box cover to help solve the puzzle. At least I don’t do that while anyone is looking. Occasionally, some sadist will give me a puzzle as a gift, usually one that has some impossible picture, or one that has impossible shapes, or one that is a single color, etc. This month, thanks to the suggestion of Peter Lewis, it’s my turn to torture you with a jigsaw puzzle Challenge. And I’m not giving you a box cover to work with, just in case you’re inclined to cheat.

Your puzzle has no color information to help you in assembling it – you’ll have to rely entirely on the shapes of the pieces to determine where each piece belongs. When assembled, the puzzle has a rectangular shape. The puzzle is presented to you as a bitmap of 16-bit pixels. Each piece consists of contiguous pixels with a unique nonzero pixel value. The pieces are rotated by a multiple of one-quarter turn, and are scattered throughout a rectangle, with no overlap between pieces. Pixels not containing part of a puzzle piece have the value 0. To eliminate any ambiguity in the orientation of the reassembled puzzle, the top left corner piece will be located in its final position at location (0,0) of the puzzle rectangle. Your job is to reassemble a series of these puzzles as efficiently as you can.

The file challenge.in contains a single line with the number of test cases your program needs to process. The input for each test case is provided in file jigsawNN.in, where NN ranges from 1 to the number of test cases. Each input file contains (2+puzzleHeight*puzzleWidth) 16-bit values, corresponding to this JigsawPuzzle structure:

typedef struct JigsawPuzzle {
   short puzzleHeight;   /* number of rows in the puzzle or bitmap */
   short puzzleWidth;   /* number of columns in the puzzle or bitmap */
   short *puzzleValue;
      /* puzzleValue[row*puzzleWidth+col] is the (row,col) puzzle value */
      /* puzzleValue == 0 is an empty pixel */
      /* puzzleValue == n is part of piece n */
} JigsawPuzzle;

Your code needs to read each input file, reassemble the puzzle by rotating and translating individual pieces, and output a JigsawPuzzle structure containing the solved puzzle to the file jigsawNN.out. With no space between the reassembled puzzle pieces, the reassembled puzzle will have a smaller width and height than the input bitmap.

Your program should produce a challenge.log file, with one line per test case containing the integer number of microseconds used by your application to solve that test case, including the time to read the input, find the solution, and produce the output file. The method used to measure execution time may vary based on the development environment you use for your solution, but you should measure time with microsecond precision if possible.

You can improve your chances of winning by incorporating optional features into your solution. For this jigsaw puzzle problem, you might want to optionally display your solution’s progress in solving the puzzle. The timing of your solution should exclude any optional display features.

Scoring will be based on minimizing execution time, on a subjective evaluation of additional features, and on the clarity of your code, including the commentary that describes your solution, use of consistent naming conventions, and the readability of your code. Your base score will be 1 penalty point for each microsecond of execution time. Penalty points will be decreased by up to 25% based on any optional features you might incorporate into your solution, and by another 25% based on a subjective evaluation of the clarity of your code.

This will be a native PowerPC Challenge, using the development environment of your choice, provided I have or can obtain a copy - email progchallenge@mactech.com to check before you start. You can develop for Mac OS 9 or Mac OS X. Your solution should be a complete Macintosh application, and your submission should provide everything needed to build your application, as well as documentation of the features you have implemented, to ensure that I don’t overlook anything.

Congratulations to Allen Stenger for winning the February S*xChart Challenge. This Challenge involved converting a set of input nodes and connection information, inspired by a mildly salacious web story involving “connections” among members of the internet community, in a way that minimized intersections between lines in the resulting graph, and also minimized execution time. Allen’s solution produced significantly fewer intersections than the second-place (and only other submitted) solution by Ernst Munter.

Allen and Ernst used very different techniques to generate their graphs. Allen always connected vertices using a single line segment; Ernst used multiple line segments to connect vertices. Allen used a “spring embedder” algorithm to iterate toward a planar graph, with a repulsive force between nonconnected vertices and a spring-like force between connected vertices that tends to keep vertices some nominal distance apart. The algorithm is described in the commentary to file CGraphEmbedder.cp, and in a referenced article in Dr. Dobbs Journal. Ernst focused more directly on minimizing the number of intersections between line segments. As it turned out, Allen’s solution required much more execution time, but generated fewer line intersections.

Allen also provided more optional features in his submission, taking advantage of PowerPlant to produce his application. Both contestants provided scrolling and window resizing capabilities that allowed the entire graph to be displayed. Allen also provided a zoom capability and menu options that provided independent control of the creation and the display of individual graphs in the test data sets. Ernst’s display was somewhat more attractive, placing all nodes completely within the visible area of the graph and framing the names associated with each node. Allen won a slightly higher bonus score for optional features, as well as a larger penalty for execution time, but his win was due to the significantly smaller number of graph intersections produced by his solution.

The table below lists, for each of the solutions submitted, the number of intersections in the graphs generated, the total execution time in milliseconds, the bonus awarded for optional program features, and the cumulative score. It also lists the code size (excluding the PowerPlant code in Stenger’s solution), data size, and programming language of each entry. As usual, the number in parentheses after the entrant’s name is the total number of Challenge points earned in all Challenges prior to this one.

Listed here are the Top Contestants for the Programmer’s Challenge, including everyone who has accumulated 20 or more points during the past two years. The numbers below include points awarded over the 24 most recent contests, including points earned by this month’s entrants.

In order to give some recognition to other participants in the Challenge, we also list the high scores for contestants who have accumulated points without taking first place in a Challenge during the past two years. Listed here are all of those contestants who have accumulated 6 or more points during the past two years.

There are three ways to earn points: (1) scoring in the top 5 of any Challenge, (2) being the first person to find a bug in a published winning solution or, (3) being the first person to suggest a Challenge that I use. The points you can win are:

Here is Allen’s winning S*xChart solution:

SxChartApp.cpp
Copyright © 2002
Allen Stenger

//////////////////////////////////////////////////////////////////////
//
// S*xChart (MacTech Programmer’s Challenge, February 2002)
// Written by Allen Stenger, January 2002
//
// This file includes portions of:
//     CBasicApp.cp, ©1994-2001 Metrowerks Inc. All rights reserved.
// Project is based on the Metrowerks Basic Application stationery.
//
// We assume the files are in the same folder as the application.
// We assume the files are numbered starting at 00.
//
// Our strategy:
//
// The challenge is to produce a planar embedding (or almost planar)
// of a given graph. We determine the connected components of the
// given graph and apply a “spring embedder” algorithm to each
// component (the spring embedder doesn’t work on disconnected
// graphs). Then we shift each component so they are stacked 
// vertically, not intersecting each other. More details of the
// spring embedder are given with its code.
//
// To display the graph, we create a Picture in memory and draw
// the Picture into the display window.
//
//////////////////////////////////////////////////////////////////////

#include “SxChartApp.h”
#include “CGraphEmbedder.h”
#include “CGraphWindow.h”

#include <LGrowZone.h>
#include <PP_Messages.h>
#include <PP_Resources.h>
#include <UDrawingState.h>
#include <UMemoryMgr.h>
#include <URegistrar.h>
#include <LActiveScroller.h>

#include <LWindow.h>
#include <LCaption.h>

#include <ctime>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>

// ==========================================================
//   • main
// ==========================================================

int main()
{                     
      // Set Debugging options
   SetDebugThrow_(debugAction_Alert);
   SetDebugSignal_(debugAction_Alert);

      // Initialize Memory Manager. Parameter is the number of
      // master pointer blocks to allocate
   InitializeHeap(3);
   
      // Initialize standard Toolbox managers
   UQDGlobals::InitializeToolbox();
   
      // Install a GrowZone to catch low-memory situations   
   new LGrowZone(20000);

      // Create the application object and run
   SxChartApp   theApp;
   theApp.Run();
   
   return 0;
}


// —————————————————————————————————————-
//   • SxChartApp                              [public]
// —————————————————————————————————————-
//   Application object constructor

SxChartApp::SxChartApp()
{
   RegisterClasses();
}


// —————————————————————————————————————-
//   • ~SxChartApp                           [public, virtual]
// —————————————————————————————————————-
//   Application object destructor

SxChartApp::~SxChartApp()
{
   // Nothing
}


// —————————————————————————————————————-
//   • ObeyCommand                           [public, virtual]
// —————————————————————————————————————-
//   Respond to Commands. Returns true if the Command was handled, false if not.

Boolean
SxChartApp::ObeyCommand(
   CommandT   inCommand,
   void*      ioParam)
{
   Boolean      cmdHandled = true;   // Assume we’ll handle the command

   switch (inCommand) {

      case cmd_RunAllTests:
      {
         UCursor::SetWatch();   // a slow operation - show watch
         RunAllTests();
      }
      break;
      
      case cmd_RunOneTest:
      {
         int runOneNumber;
         if (AskForTestNumber(&runOneNumber))
         {
            UCursor::SetWatch();   // a slow operation - show watch
            RunAndLog(runOneNumber, runOneNumber);
         }
      }
      break;
      
      case cmd_DrawGraph:
      {
         int drawOneNumber;
         if (AskForTestNumber(&drawOneNumber))
         {
            DrawGraph(drawOneNumber);
         }
      }
      break;
      
      default: {
         cmdHandled = LApplication::ObeyCommand(inCommand, ioParam);
         break;
      }
   }
   
   return cmdHandled;
}


// —————————————————————————————————————-
//   • FindCommandStatus                        [public, virtual]
// —————————————————————————————————————-
//   Determine the status of a Command for the purposes of menu updating.

void
SxChartApp::FindCommandStatus(
   CommandT   inCommand,
   Boolean&   outEnabled,
   Boolean&   outUsesMark,
   UInt16&      outMark,
   Str255      outName)
{
   switch (inCommand) {

      case cmd_RunAllTests:
      { outEnabled = true; }
      break;
      
      case cmd_RunOneTest:
      { outEnabled = true; }
      break;
      
      case cmd_DrawGraph:
      { outEnabled = true; }
      break;
      
      default: {
         LApplication::FindCommandStatus(inCommand, outEnabled,
                                 outUsesMark, outMark, outName);
         break;
      }
   }
}


// —————————————————————————————————————-
//   • RegisterClasses                        [protected]
// —————————————————————————————————————-
//   To reduce clutter within the Application object’s constructor, class
//   registrations appear here in this separate function for ease of use.

void
SxChartApp::RegisterClasses()
{
   RegisterClass_(LWindow);
   RegisterClass_(LCaption);
   RegisterClass_(LDialogBox);
   RegisterClass_(LEditField);
   RegisterClass_(LStdButton);
   RegisterClass_(LActiveScroller);
   RegisterClass_(CGraphWindow);
   RegisterClass_(CGraphView);
}

//////////////////////////////////////////////////////////////////////
// SxChartApp-specific functions
//////////////////////////////////////////////////////////////////////

std::string SxChartApp::TestNumberToString(int testNumber)
{
   std::ostringstream fileNumberStream;
   fileNumberStream.width(2);
   fileNumberStream.fill(‘0’);
   fileNumberStream << testNumber;
   return fileNumberStream.str();
}

void SxChartApp::SayFileError(const std::string &rFileName)
{
   std::string errorString = “Sorry, could not open the file “ + 
                        rFileName + “.”;
   Str255 errorPString;
   ::CopyCStringToPascal(errorString.c_str(), errorPString);   
   ::ParamText(errorPString, “\p”, “\p”, “\p”);
   UModalAlerts::StopAlert(kBlankALRT);
}

void SxChartApp::RunAllTests()
{
   // fetch number of tests, run each test, and output log entry
   std::ifstream numTestsStream(“SexChart.in”);
   if (!numTestsStream.is_open())
   {
      SxChartApp::SayFileError(“SexChart.in”);
      return;      // give up
   }
   int numTests = 0;
   numTestsStream >> numTests;
   numTestsStream.close();
   
   RunAndLog(0, numTests - 1);
}

void SxChartApp::RunAndLog(int startCase, int endCase)
{
   std::ofstream logStream(“logfile.txt”);
   if (!logStream.is_open())
   {
      SxChartApp::SayFileError(“logfile.txt”);
      return;      // give up
   }
   
   for (int i = startCase; i <= endCase; i++)
   {
      std::clock_t startTime, endTime, elapsedTimeClocks;
      
      startTime = std::clock();
      RunOneTest(i);
      endTime = std::clock();
      
      elapsedTimeClocks = endTime - startTime;
      long elapsedTimeMS = 
         std::floor((1000 * elapsedTimeClocks) / 
                     CLOCKS_PER_SEC + 0.5);
      logStream << elapsedTimeMS << std::endl;
   }
   
   logStream.close();
}

void SxChartApp::RunOneTest(int testNumber)
{
   bool bOkSoFar = true;
   CTestRunner aRunner(testNumber);
   bOkSoFar = aRunner.LoadNames();
   if (bOkSoFar)
      bOkSoFar = aRunner.LoadHookups();
   if (bOkSoFar)
   {
      aRunner.MakeEmbeddedGraph();
      aRunner.WriteLocations();
      aRunner.WriteSegments();
   }

}

bool SxChartApp::AskForTestNumber(int *pTestNumber)
{
   SInt32 ioNumber = 0;
   bool bOk = UModalDialogs::AskForOneNumber(
                        this,
                        kAskTestNumberDLOG,
                        kAskTestNumberEditPane,
                        ioNumber);
   if (bOk)
      *pTestNumber = ioNumber;
      
   return bOk;
}

void SxChartApp::DrawGraph(int testNumber)
{
   LWindow *pGraphWindow = LWindow::CreateWindow(kGraphWindow, 
                                                                  this);
   std::string titleString = “Graph” + 
                        TestNumberToString(testNumber);
   Str255 titlePString;
   ::CopyCStringToPascal(titleString.c_str(), titlePString);
   pGraphWindow->SetDescriptor(titlePString);
   CGraphView *pGraphView = 
      static_cast<CGraphView *>
                  (pGraphWindow->FindPaneByID(kGraphView));
   pGraphView->LoadGraph(testNumber);
}



//////////////////////////////////////////////////////////////////////
// CTestRunner implementation
//////////////////////////////////////////////////////////////////////

CTestRunner::CTestRunner(int testNumber) :
fNumVertices(0),
fNumHookups(0),
fpGraph(0)
{
   fFileNumberString = SxChartApp::TestNumberToString(testNumber);
}

CTestRunner::~CTestRunner()
{
   delete fpGraph;
   fpGraph = 0;
}
   
bool CTestRunner::LoadNames()
{
   // open correct name file
   std::ostringstream fileNameStream;
   fileNameStream << “names” << fFileNumberString << “.in”;
   std::string fileName(fileNameStream.str());
   std::ifstream nameStream(fileName.c_str());
   if (!nameStream.is_open())
   {
      SxChartApp::SayFileError(fileName);
      return false;      // give up
   }
   
   // read number of names
   std::string numNamesString;
   std::getline(nameStream, numNamesString);
   int numVertices = std::atoi(numNamesString.c_str());
   
   // read all name lines
   for (fNumVertices = 0; 
      fNumVertices < numVertices && !nameStream.eof(); 
      fNumVertices++)
   {
      std::string nameLine;
      std::getline(nameStream, nameLine);
      fNames.push_back(nameLine);
   }
   nameStream.close();
   
   // create graph this size
   fpGraph = new CMyGraph(fNumVertices);
   
   // sort names
   std::sort(fNames.begin(), fNames.end());
   
   return true;
}

bool CTestRunner::LoadHookups()
{
   // open correct hookups file
   std::ostringstream fileNameStream;
   fileNameStream << “hookups” << fFileNumberString << “.in”;
   std::string fileName(fileNameStream.str());
   std::ifstream hookupsStream(fileName.c_str());
   if (!hookupsStream.is_open())
   {
      SxChartApp::SayFileError(fileName);
      return false;      // give up
   }
   
   // read number of hookups
   std::string numHookupsString;
   std::getline(hookupsStream, numHookupsString);
   int numHookups = std::atoi(numHookupsString.c_str());
   
   // read all hookup lines
   for (fNumHookups = 0; 
      fNumHookups < numHookups && !hookupsStream.eof(); 
      fNumHookups++)
   {
      std::string hookupLine;
      std::getline(hookupsStream, hookupLine);
      LoadOneHookup(hookupLine);
   }
   hookupsStream.close();
   return true;
}

void CTestRunner::LoadOneHookup(const std::string& rHookupLine)
{
   // format of line is 
   // personA,personB
   std::string::size_type firstComma = rHookupLine.find(‘,’);
   std::string personAName = rHookupLine.substr(0, firstComma);
   std::string personBName = rHookupLine.substr(firstComma + 1);

   std::vector<std::string>::iterator iter = 
      std::lower_bound(fNames.begin(), fNames.end(), personAName);
   int personAIndex = iter - fNames.begin();
   iter = std::lower_bound(fNames.begin(), fNames.end(), 
                                       personBName);
   int personBIndex = iter - fNames.begin();

   fpGraph->SetAdjacent(personAIndex, personBIndex);
}

void CTestRunner::MakeEmbeddedGraph()
{
   // find out the connected components
   fpGraph->FindConnectedComponents();
   
   // Lay out all the points.
   // We place the points at the vertices of a regular n-gon
   // of fixed diameter; this is somewhat arbitrary; if we had
   // some idea of the final graph we could places the points
   // closer to their final position.
   const int kDiam = 1000;   
      // diameter of circle circumscribing n-gon. units: pixels
   const float kPi = 3.14159;
   for (int i = 0; i < fNumVertices; i++)
   {
      Point vertex;
      double angle = i * 2 * kPi / fNumVertices;
      vertex.h = static_cast<int>(0.5 + 
                  kDiam * 0.5 * (1 + std::cos(angle)));
      vertex.v = static_cast<int>(0.5 + 
                  kDiam * 0.5 * (1 + std::sin(-angle)));
      fpGraph->SetVertex(i, vertex);
   
   }
   
   // embed each component in a plane, then shift it so it doesn’t
   // collide with the other components. We align each component flush
   // left and just below the previous component.
   int newCompTop = 0;   // where to put next component vertically
   int numComps = fpGraph->GetNumComponents();
   for (int whichComp = 0; whichComp < numComps; whichComp++)
   {
      CGraphEmbedder aEmbedder(*fpGraph, whichComp);
      aEmbedder.EmbedComponent();
      
      Rect compBounds;
      FindComponentBounds(whichComp, &compBounds);
      
      MoveComponent(whichComp, -compBounds.left, 
                     newCompTop - compBounds.top);
      
      // figure out where to put next component;
      // allow a little margin between components
      const int kMargin = 20;   // units: pixels
      newCompTop += (compBounds.bottom - compBounds.top) + kMargin;
   }
}

void CTestRunner::WriteLocations()
{
   // open correct output file
   std::ostringstream fileNameStream;
   fileNameStream << “locations” << fFileNumberString << “.out”;
   std::string fileName(fileNameStream.str());
   std::ofstream locationsStream(fileName.c_str());
   if (!locationsStream.is_open())
   {
      SxChartApp::SayFileError(fileName);
      return;      // give up
   }
   
   for (int i = 0; i < fNumVertices; i++)
   {
      Point vertex = fpGraph->GetVertex(i);
      locationsStream << vertex.h << ‘,’;
      locationsStream << vertex.v << ‘,’;
      locationsStream << fNames[i] << std::endl;
   }
   locationsStream.close();
}

void CTestRunner::WriteSegments()
{
   // open correct output file
   std::ostringstream fileNameStream;
   fileNameStream << “segments” << fFileNumberString << “.out”;
   std::string fileName(fileNameStream.str());
   std::ofstream segmentsStream(fileName.c_str());
   if (!segmentsStream.is_open())
   {
      SxChartApp::SayFileError(fileName);
      return;      // give up
   }
   
   // we only need to generate lines in one direction, so we’ll 
   // always go from lower to higher indexes
   for (int startVertex = 0; 
         startVertex < fNumVertices; 
         startVertex++)
   {
      for (int endVertex = startVertex + 1; 
            endVertex < fNumVertices; 
            endVertex++)
      {
         if (fpGraph->AreAdjacent(startVertex, endVertex))
         {
            // we generate only straight-line segments, so
            // the number of points is always 2
            segmentsStream << “2” << std::endl;
            Point point1 = fpGraph->GetVertex(startVertex);
            segmentsStream << point1.h << ‘,’ << 
                        point1.v << std::endl;
            Point point2 = fpGraph->GetVertex(endVertex);
            segmentsStream << point2.h << ‘,’ << 
                        point2.v << std::endl;
         }
      }
   }
   segmentsStream.close();
}

void CTestRunner::FindComponentBounds(int whichComp, Rect *pCompBounds)
{
   Rect bounds = {0, 0, 0, 0};
   bool   bBoundsEmpty = true;

   for (int whichVertex = 0; whichVertex < fNumVertices; 
                                                   whichVertex++)
   {
      if (fpGraph->GetComponentNumber(whichVertex) == whichComp)
      {
         Point aVertex = fpGraph->GetVertex(whichVertex);
         if (bBoundsEmpty)
         {
            bBoundsEmpty = false;
            bounds.top = aVertex.v;
            bounds.left = aVertex.h;
            bounds.bottom = bounds.top + 1;
            bounds.right = bounds.left + 1;
         }
         else if (!::PtInRect(aVertex, &bounds))
         {
            if (aVertex.v < bounds.top)
               bounds.top = aVertex.v;
            else if (aVertex.v >= bounds.bottom)
               bounds.bottom = aVertex.v + 1;
               
            if (aVertex.h < bounds.left)
               bounds.left = aVertex.h;
            else if (aVertex.h == bounds.right)
               bounds.right = aVertex.h + 1;
         }
      }
   }
   
   *pCompBounds = bounds;
}

void CTestRunner::MoveComponent(int whichComp, int offsetH, int offsetV)
{
   for (int whichVertex = 0; whichVertex < fNumVertices; 
                                 whichVertex++)
   {
      if (fpGraph->GetComponentNumber(whichVertex) == whichComp)
      {
         Point aVertex = fpGraph->GetVertex(whichVertex);
         aVertex.h += offsetH;
         aVertex.v += offsetV;
         fpGraph->SetVertex(whichVertex, aVertex);
      }
   }   
}

CGraphEmbedder.cpp

//////////////////////////////////////////////////////////////////////
//
// Graph Embedder
// Written by Allen Stenger, January 2002
//
//////////////////////////////////////////////////////////////////////

#include “CGraphEmbedder.h”
#include <string>

//////////////////////////////////////////////////////////////////////
// CGraphEmbedder implementation
//
// We use a “spring embedder” algorithm. There are many varieties of
// these; for a complicated example see:
//     “Simulating Graphs as Physical Systems”
//     Arne Frick, Georg Sander, and Kathleen Wang
//     Dr. Dobb’s Journal, August 1999
// The spring embedder pretends that:
// 1. the vertices are freely moveable in the plane
// 2. each edge is represented as a spring that has some nominal size;
//    stretching or compressing the spring creates a restoring force
//    that tries to return the spring to its nominal size
// 3. between each pair of vertices is a repulsive force; this force is
//    significantly smaller than the spring forces, and acts to keep
//    non-adjacent vertices from drifting close to each other.
// 4. allowing these forces to act by moving the vertices causes an
//    approximate planar embedding of the graph
// 5. the forces are implemented by a discrete simulation; we calculate
//    the forces on each point, then move all points simultaneously
//    to their new positions.
//
// Note: vertices in different components do not act on each other.
//
// Movement in each simulation step is clamped to a limit. Some spring 
// embedders use a “temperature” setting to reduce the limit as the 
// embedding progresses, but we do not.
//
// We don’t use any units for the force; if we measure a force of N,
// that means we move the vertex N pixels in the direction of the
// force.
//
// We always generate straight lines between vertices; the Challenge
// statement allows multi-segment lines.
//
// The iteration terminates when a steady-state appears to have been
// reached (that is, all the forces are small), or when the number
// of steps passes a limit. The limit is somewhat empirical; large
// graphs tend to occupy an area proportional to the number of vertices
// and therefore to have a width and height proportional the the square
// root of the number of vertices. Meanwhile the number of steps
// required to move each vertex into place is probably proportional
// to the width or height (because we limit the amount of movement on
// each step). Therefore the number of steps in the iteration is
// roughly proportional to sqrt(number of vertices), and this is how
// we set the iteration limit for large graphs. (For small graphs we
// use a fixed limit.)
//
// For the spring forces we use a Hooke’s law:
//
//     force = const * unit vector * (nominal length - distance);
//
// if the distance is greater than nominal, the force
// vector points toward the other point, meaning the 
// spring is stretched and we are going to move toward the
// other point.
// The Hooke’s law constant represents what fraction of
// the distance to the nominal state we would like to
// move in one step; therefore it is necessarily less
// than 1. Note also that if there are several vertices pulling a
// vertex in the same direction, the resultant force may be very
// large, large enough to cause the vertex to overshoot the optimal
// position. This wouldn’t happen with real springs, because the 
// forces continually change as the particles move, but it is an
// artifact of our discrete simulation. We attempt to work around
// this by keeping the Hooke’s law constant small, so that even if
// there are several vertices, the force will not become excesssive.
// This has the drawback that convergence may be slow. (The Hooke’s
// law constant can also be thought of as a gain in this system.)
// A similar problem is that when two vertices are connected, they
// pull each other, and the resulting force may actually pull them
// past each other, which would lead to oscillation. Again we try to
// avoid this by using a small Hooke’s law constant.
//
// For all vertices there is a repulsive force between pairs of
// vertices. We use an inverse square law:
//
//     force = const * unit vector / (distance ^2)
//
// The repulsive constant should be chosen so that it causes
// a significant force (that is, one greater than we would
// stop iterating at) when points are closer than the nominal
// distance. So for example if the insignificant force is 5,
// and the nominal distance is 100, we would pick the
// constant to be 5 * 100^2.
// The repulsive force is supposed to be a gentle force that will
// cause nearby points to pivot away from each other, so we
// will clamp the amount of the force that can be applied
// in one move. This avoids generating a ridiculously large
// force when points are very near each other.
// The repulsive force is needed to keep far-away portions
// of the graph from rotating and overlapping each other.
//
// The calculation of the repulsive force is by far the slowest part
// of the algorithm, because it is a O(n^2) process (each pair of
// vertices has to be considered. In contrast, if we assume a
// bounded number of edges incident to each vertex, the spring
// force calculation is only a O(n) process.
//
//////////////////////////////////////////////////////////////////////

// parameters controlling the spring embedder
const float kMaxForceSquared = 200 * 200;   // max force to apply in one step
const float kSteadyStateForce = 5.0;   // stop if all forces less than this
const float kSteadyStateForceSquared = kSteadyStateForce * kSteadyStateForce;
const float kNominalLength = 100.0;   // spring length. units: pixels
const float kHooke = 0.10;   // Hooke’s law constant (or gain)
const float kRepulsiveConstant = 5 * kNominalLength * 
                        kNominalLength;      // for inverse square law
const float kMaxRepulsiveForce = 20.0;   // limit on amount of repulsion


CGraphEmbedder::CGraphEmbedder(CMyGraph& aGraph, 
         int whichComponent) :
   fGraph(aGraph),
   fComponentNumber(whichComponent),
   fpSpringForcesX(0),
   fpSpringForcesY(0),
   fpParticleForcesX(0),
   fpParticleForcesY(0)
{
   int numVertices = aGraph.GetNumVertices();
   fpSpringForcesX = new float[numVertices];
   fpSpringForcesY = new float[numVertices];
   fpParticleForcesX = new float[numVertices];
   fpParticleForcesY = new float[numVertices];
}

CGraphEmbedder::~CGraphEmbedder()
{
   delete [] fpSpringForcesX;
   fpSpringForcesX = 0;
   delete [] fpSpringForcesY;
   fpSpringForcesY = 0;
   delete [] fpParticleForcesX;
   fpParticleForcesX = 0;
   delete [] fpParticleForcesY;
   fpParticleForcesY = 0;
}
   
void CGraphEmbedder::EmbedComponent()
{
   int numVertices = fGraph.GetNumVertices();
   int maxIterations = 5 * 
            static_cast<int>(std::sqrt(numVertices));
   if (maxIterations < 50)
      maxIterations = 50;
   for (int i = 0; i < maxIterations; i++)
   {
      // We split apart the spring and particle forces for
      // experimental purposes. It turns out not to be
      // useful to run the particle forces part-time, so
      // we run them all the time.
      bool bUseParticles = true;
      FindAllForces(bUseParticles);   
         
      // move all vertices
      bool bSteadyState = true;
      for (int whichVertex = 0; whichVertex < numVertices; 
                                    whichVertex++)
      {
         if (fGraph.GetComponentNumber(whichVertex) == 
                                    fComponentNumber)
         {
            float forceX = fpSpringForcesX[whichVertex];
            float forceY = fpSpringForcesY[whichVertex];
            if (bUseParticles)
            {
               forceX += fpParticleForcesX[whichVertex];
               forceY += fpParticleForcesY[whichVertex];
            }
            float forceSquared = forceX * forceX + forceY * forceY;
            if (forceSquared >= kSteadyStateForceSquared)
               bSteadyState = false;
            
            // limit force if necessary
            if (forceSquared > kMaxForceSquared)
            {
               const float kScaleFactor = 
                  std::sqrt(kMaxForceSquared / forceSquared);
               forceX = forceX * kScaleFactor;
               forceY = forceY * kScaleFactor;
            }
            
            // now move the vertex
            Point aVertex = fGraph.GetVertex(whichVertex);
            aVertex.h += forceX;
            aVertex.v += forceY;
            fGraph.SetVertex(whichVertex, aVertex);
         }
      }
      
      if (bSteadyState)
      {
         break;   // all done!
      }
   }
}

void CGraphEmbedder::FindAllForces(bool bFindParticles)
{
   int numVertices = fGraph.GetNumVertices();
   for (int whichVertex = 0; whichVertex < numVertices; 
                                 whichVertex++)
   {
      if (fGraph.GetComponentNumber(whichVertex) == 
                              fComponentNumber)
      {
         FindOneSpringForce(whichVertex, 
            &fpSpringForcesX[whichVertex], 
            &fpSpringForcesY[whichVertex]);
         if (bFindParticles)
         {
            FindOneParticleForce(whichVertex, 
               &fpParticleForcesX[whichVertex], 
               &fpParticleForcesY[whichVertex]);
         }
      }
   }
}

void CGraphEmbedder::FindOneSpringForce(int centerVertex, 
                  float *pForceX, float *pForceY)
{
   // Note: it is possible that the component has only one vertex
   // Note: it is possible that two vertices are at the same point
   Point aVertex = fGraph.GetVertex(centerVertex);
   int numVertices = fGraph.GetNumVertices();
   // force vector in the direction we are going to move;
   // this accumulates the spring restoring forces of all points 
   // acting on this point
   float accumForceX = 0.0, accumForceY = 0.0;
      
   for (int otherVertex = 0; otherVertex < numVertices; 
                              otherVertex++)
   {
      if (otherVertex == centerVertex)
         continue;      // there’s no force from vertex to itself
         
      // for adjacent vertices, figure out the 
      // restoring force due to the spring
      if (fGraph.AreAdjacent(centerVertex, otherVertex))
      {
         Point bVertex = fGraph.GetVertex(otherVertex);
         float deltaX = aVertex.h - bVertex.h;   // point differences
         float deltaY = aVertex.v - bVertex.v;
         float distanceSquared = deltaX * deltaX + deltaY * deltaY;
         if (distanceSquared < 1.0)
            distanceSquared = 1.0;   // just in case two points coincide
         float distance = std::sqrt(distanceSquared);
         
         // unit vector pointing to us from other point;
         // forces in this direction cause us to move away from
         // the other point
         float unitX = deltaX / distance;
         float unitY = deltaY / distance;
      
         accumForceX += kHooke * unitX * (kNominalLength - distance);
         accumForceY += kHooke * unitY * (kNominalLength - distance);
      }
   }
   
   *pForceX = accumForceX;
   *pForceY = accumForceY;
}

void CGraphEmbedder::FindOneParticleForce(int centerVertex, 
                  float *pForceX, float *pForceY)
{
   // Note: it is possible that the component has only one vertex
   // Note: it is possible that two vertices are at the same point
   Point aVertex = fGraph.GetVertex(centerVertex);
   int numVertices = fGraph.GetNumVertices();
   
   // force vector in the direction we are going to move;
   float accumForceX = 0.0, accumForceY = 0.0;
      
   for (int otherVertex = 0; otherVertex < numVertices; 
                     otherVertex++)
   {
      if (otherVertex == centerVertex)
         continue;      // there’s no force from vertex to itself
         
      Point bVertex = fGraph.GetVertex(otherVertex);
      float deltaX = aVertex.h - bVertex.h;   // point differences
      float deltaY = aVertex.v - bVertex.v;
      float distanceSquared = deltaX * deltaX + deltaY * deltaY;
      if (distanceSquared < 1.0)
         distanceSquared = 1.0;   // just in case two points coincide
      float distance = std::sqrt(distanceSquared);
      
      // unit vector pointing to us from other point;
      // forces in this direction cause us to move away from
      // the other point
      float unitX = deltaX / distance;
      float unitY = deltaY / distance;
      
      float repAmount = kRepulsiveConstant / distanceSquared;
      if (repAmount > kMaxRepulsiveForce)
         repAmount = kMaxRepulsiveForce;
      accumForceX += repAmount * unitX;
      accumForceY += repAmount * unitY;
   }
   *pForceX = accumForceX;
   *pForceY = accumForceY;
}

//////////////////////////////////////////////////////////////////////
// CMyGraph implementation
//////////////////////////////////////////////////////////////////////

CMyGraph::CMyGraph(int numVertices) :
   fNumVertices(numVertices),
   fpAdjacencies(0),
   fpVertexPoints(0),
   fNumComponents(0),
   fpComponentNumbers(0)
{
   fpAdjacencies = new char[numVertices * numVertices];
   std::memset(fpAdjacencies, 0, 
                           numVertices * numVertices * sizeof(char));
   fpVertexPoints = new Point[numVertices];
   std::memset(fpVertexPoints, 0, numVertices * sizeof(Point));
   fpComponentNumbers = new int[numVertices];
   std::memset(fpComponentNumbers, 255, 
                        numVertices * sizeof(int));
}

CMyGraph::~CMyGraph()
{
   delete [] fpAdjacencies;
   fpAdjacencies = 0;
   delete [] fpVertexPoints;
   fpVertexPoints = 0;
   delete [] fpComponentNumbers;
   fpComponentNumbers = 0;
}
   
void CMyGraph::SetVertex(int whichVertex, const Point& rPoint)
{
   fpVertexPoints[whichVertex] = rPoint;
}

Point CMyGraph::GetVertex(int whichVertex) const
{
   return fpVertexPoints[whichVertex];
}
   
int CMyGraph::GetNumVertices() const
{
   return fNumVertices;
}

void CMyGraph::SetAdjacent(int aVertex, int bVertex)
{
   // set both [a,b] and [b,a] because the matrix is symmetric
   fpAdjacencies[aVertex * fNumVertices + bVertex] = 1;
   fpAdjacencies[bVertex * fNumVertices + aVertex] = 1;
}

bool CMyGraph::AreAdjacent(int aVertex, int bVertex) const
{
   // only have to test one of two symmetric entries
   return (fpAdjacencies[aVertex * fNumVertices + bVertex] == 1);
}


void CMyGraph::FindConnectedComponents()
{
   // we start at each vertex and recursively mark all the
   // vertices it is connected to.
   for (int whichVertex = 0; whichVertex < fNumVertices; 
                  whichVertex++)
   {
      if (fpComponentNumbers[whichVertex] == -1)
      {
         // start new connected component
         int thisMark = fNumComponents;
         fNumComponents++;
         fpComponentNumbers[whichVertex] = thisMark;
         MarkConnectedVertices(whichVertex, thisMark);
      }
   }
}

void CMyGraph::MarkConnectedVertices(int whichVertex, int thisMark)
{
   // examine each connected vertex, if not already marked then
   // mark it and call ourselves recursively on it
   int rowOffset = fNumVertices * whichVertex;
   for (int col = 0; col < fNumVertices; col++)
   {
      if (fpAdjacencies[rowOffset + col] &&
         fpComponentNumbers[col] == -1)
      {
         fpComponentNumbers[col] = thisMark;
         MarkConnectedVertices(col, thisMark);
      }
   }
}

int CMyGraph::GetNumComponents()
{
   return fNumComponents;
}

int CMyGraph::GetComponentNumber(int aVertex)
{
   return fpComponentNumbers[aVertex];
}

CGraphEmbedder.cpp

//////////////////////////////////////////////////////////////////////
//
// Graph Window
// Written by Allen Stenger, January 2002
//
// This draws the graph in a window.
//
// This reads in the graph descriptions from file and creates a 
// document window with a drawing of the graph inside. It also takes
// care of scrolling and redrawing the document window.
//
//////////////////////////////////////////////////////////////////////

#include “CGraphWindow.h”
#include “SxChartApp.h”

#include <fstream>
#include <sstream>

static const Rect kPicClipRect = {0, 0, 32767, 32767};   
                  // Picture’s clipping rect

static const int kMaxZoom = 1 << 8;   // 2^(max number of zoom outs)

//////////////////////////////////////////////////////////////////////
// CGraphWindow implementation
//////////////////////////////////////////////////////////////////////

// class static variables
std::vector<CGraphWindow *> CGraphWindow::fgGraphWindows;

CGraphWindow::CGraphWindow(LStream *pStream) :
LWindow(pStream),
fpGraphView(0)
{
   // add ourselves to list
   fgGraphWindows.push_back(this);
   
   // add a placeholder title to the Window menu
   // (we don’t know our title yet)
   LMenu *pWindowMenu = 
      LMenuBar::GetCurrentMenuBar()->FetchMenu(kWindowMENU);
   pWindowMenu->InsertCommand( “\p “, cmd_UseMenuItem, 16000 );
   LCommander::SetUpdateCommandStatus(true);
}

CGraphWindow::~CGraphWindow()
{
   // remove ourselves from Window menu
   LMenu *pWindowMenu = 
      LMenuBar::GetCurrentMenuBar()->FetchMenu(kWindowMENU);
   std::vector<CGraphWindow *>::iterator iter =
      std::lower_bound(fgGraphWindows.begin(), 
                  fgGraphWindows.end(), this);
   int itemNumber = iter - fgGraphWindows.begin() + 1;
   pWindowMenu->RemoveItem(itemNumber);
   LCommander::SetUpdateCommandStatus(true);
   
   // remove ourselves from list -
   // use erase-remove idiom (see Meyers, “Effective STL” item 32)
   fgGraphWindows.erase(
      std::remove(fgGraphWindows.begin(), 
                           fgGraphWindows.end(), this),
      fgGraphWindows.end());
}

void CGraphWindow::FindCommandStatus(
                        CommandT         inCommand,
                        Boolean&         outEnabled,
                        Boolean&         outUsesMark,
                        UInt16&            outMark,
                        Str255            outName)
{
   ResIDT   theMenuID;
   SInt16   theMenuItem;
   if (IsSyntheticCommand(inCommand, theMenuID, theMenuItem) &&
      theMenuID == kWindowMENU && theMenuItem > 0)
   {
      // window items are always enabled;
      // place checkmark next to frontmost window;
      // supply the window title because we didn’t know
      // it at window creation time
      LWindow   *pWindow = fgGraphWindows[theMenuItem -1];
      pWindow->GetDescriptor(outName);
      outEnabled = true;
      outUsesMark = true;
      outMark = noMark;

      if (pWindow == UDesktop::FetchTopRegular())         
         outMark = checkMark;
   }
   else
   {
      switch (inCommand)
      {
         case cmd_ZoomOut:
         {
            int zoom1 = fpGraphView->GetZoomFactor();
            if (zoom1 < kMaxZoom)
               outEnabled = true;
         }
         break;
         
         case cmd_ZoomIn:
         {
            int zoom2 = fpGraphView->GetZoomFactor();
            if (zoom2 > 1)
               outEnabled = true;
         }
         break;
         
         default: 
         {
            LWindow::FindCommandStatus(inCommand, outEnabled,
                              outUsesMark, outMark, outName);
         }
         break;
      }
   }
}

Boolean CGraphWindow::ObeyCommand(
                        CommandT         inCommand,
                        void*            ioParam)
{
   ResIDT   theMenuID;
   SInt16   theMenuItem;
   Boolean cmdHandled = true;
   if (IsSyntheticCommand(inCommand, theMenuID, theMenuItem) &&
      theMenuID == kWindowMENU && theMenuItem > 0)
   {
      // bring desired window to front
      CGraphWindow *pWindow = fgGraphWindows[theMenuItem - 1];
      UDesktop::SelectDeskWindow(pWindow);
   }
   else
   {
      switch (inCommand)
      {
         case cmd_ZoomOut:
         {
            int zoom1 = fpGraphView->GetZoomFactor();
            fpGraphView->SetZoomFactor(2 * zoom1);
         }
         break;

         case cmd_ZoomIn:
         {
            int zoom2 = fpGraphView->GetZoomFactor();
            fpGraphView->SetZoomFactor(zoom2 / 2);
         }
         break;
         
         default: 
         {
            cmdHandled = LWindow::ObeyCommand(inCommand, ioParam);
         }
         break;
      }
   }
   
   return cmdHandled;
}

void CGraphWindow::FinishCreateSelf()
{
   fpGraphView = static_cast<CGraphView *>(FindPaneByID(kGraphView));
   
   // add attachment to handling page up/down etc. keys
   AddAttachment(new LKeyScrollAttachment(fpGraphView));
   
   LWindow::FinishCreateSelf();
}

//////////////////////////////////////////////////////////////////////
// CGraphWindow implementation
//////////////////////////////////////////////////////////////////////

CGraphView::CGraphView(LStream *pStream) :
LView(pStream),
fhPicture(0),
fZoomFactor(1)
{
   fPicFrame.top = fPicFrame.left = 0;
   fPicFrame.bottom = fPicFrame.right = 0;
}

CGraphView::~CGraphView()
{
   if (fhPicture)
      ::DisposeHandle(reinterpret_cast<Handle>(fhPicture));
   fhPicture = 0;
}
   
void CGraphView::LoadGraph(int testNumber)
{
   fFileNumberString = SxChartApp::TestNumberToString(testNumber);
   
   // How we will handle the unknown picture size:
   // we don’t know yet the actual extent of the graph, so
   // we’ll use a big source and clipping rectangle, but
   // we’ll also keep track of the actual size needed.
   // Then we’ll set the view’s image size to the actual size.
   // However we will draw into the large sized area to avoid 
   // scaling the picture.
   // We assume the graph will alway start somewhere near (0,0),
   // so that will be our view’s initial top left display,
   // even if there’s no data around there.
   
   OpenCPicParams myOpenCPicParams;
   myOpenCPicParams.srcRect = kPicClipRect;
   myOpenCPicParams.hRes = 0x00480000;
   myOpenCPicParams.vRes = 0x00480000;
   myOpenCPicParams.version = 2;
   myOpenCPicParams.reserved1 = 0;
   myOpenCPicParams.reserved2 = 0;
   fhPicture = ::OpenCPicture(&myOpenCPicParams);
   
   // set up Picture the way we want it
   ::ClipRect(&kPicClipRect);
   ::PenNormal();
   TextFont(1);   // application font
   TextFace(0);   // plain
   TextMode(srcCopy);   // plain
   TextSize(9);   // 9 point
   
   DrawEdges();
   DrawNames();
   
   ::ClosePicture();
   
   // make image the size of the useful parts of the picture
   ResizeImageTo(
      (fPicFrame.right - fPicFrame.left) / fZoomFactor,
      (fPicFrame.bottom - fPicFrame.top) / fZoomFactor,
      false);

   // force redraw now that we have something to draw
   Refresh();
}
   
void CGraphView::DrawSelf()
{
   // code swiped from LPicture::DrawSelf; we don’t use
   // LPicture because it requires the picture to be in a resource
   if (fhPicture != nil) 
   {
      Rect destRect = kPicClipRect;
      destRect.top /= fZoomFactor;
      destRect.left /= fZoomFactor;
      destRect.right /= fZoomFactor;
      destRect.bottom /= fZoomFactor;
      ::DrawPicture(fhPicture, &destRect);
   } 
   else 
   {
      Rect   frame;
      CalcLocalFrameRect(frame);
      ::PenNormal();

      Pattern      ltGrayPat;
      ::MacFillRect(&frame, 
                  UQDGlobals::GetLightGrayPat(<GrayPat));

      ::MacFrameRect(&frame);
   }
}

void CGraphView::SetZoomFactor(int factor)
{
   // attempt to scroll to the same center after zooming
   SDimension16 frameSize;
   GetFrameSize(frameSize);
   SPoint32   imageLocation;
   GetImageLocation(imageLocation);
   SPoint32 viewCenter;
   viewCenter.h = -imageLocation.h + (frameSize.width / 2);
   viewCenter.v = -imageLocation.v + (frameSize.height / 2);
   viewCenter.h *= fZoomFactor;
   viewCenter.v *= fZoomFactor;

   // now do the zoom
   fZoomFactor = factor;
   ResizeImageTo(
      (fPicFrame.right - fPicFrame.left) / fZoomFactor,
      (fPicFrame.bottom - fPicFrame.top) / fZoomFactor,
      false);

   // try to re-center
   viewCenter.h /= fZoomFactor;
   viewCenter.v /= fZoomFactor;
   imageLocation.h = (frameSize.width / 2) - viewCenter.h;
   imageLocation.v = (frameSize.height / 2) - viewCenter.v;
   ScrollPinnedImageTo(-imageLocation.h, -imageLocation.v, false);
   Refresh();   // redraw ourself
}

int CGraphView::GetZoomFactor()
{
   return fZoomFactor;
}

void CGraphView::DrawEdges()
{
   // open correct segments file
   std::ostringstream fileNameStream;
   fileNameStream << “segments” << fFileNumberString << “.out”;
   std::string fileName(fileNameStream.str());
   std::ifstream segmentsStream(fileName.c_str());
   if (!segmentsStream.is_open())
   {
      SxChartApp::SayFileError(fileName);
      return;      // give up
   }
   
   // file format is: several blocks of form
   //     number of points
   //     point1horiz,point1vert
   //     ...
   
   // read all blocks
   while (!segmentsStream.eof())
   {
      // read number of points in block
      std::string numPtsString;
      std::getline(segmentsStream, numPtsString);
      int numPts = std::atoi(numPtsString.c_str());
      
      // read all points in block
      for (int i = 0; i < numPts; i++)
      {
         std::string pointLine;
         std::getline(segmentsStream, pointLine);
         std::string::size_type firstComma = pointLine.find(‘,’);
         std::string horizString = pointLine.substr(0, firstComma);
         std::string vertString = pointLine.substr(firstComma + 1);
         Point aVertex;
         aVertex.h = std::atoi(horizString.c_str());
         aVertex.v = std::atoi(vertString.c_str());
         
         // draw segment
         if (i == 0)
            ::MoveTo(aVertex.h, aVertex.v);
         else
            ::LineTo(aVertex.h, aVertex.v);
      }
   }
   

}

void CGraphView::DrawNames()
{
   // we also keep a running set of bounds for the vertices
   int maxH = 0;
   int maxV = 0;

   // open correct locations file
   std::ostringstream fileNameStream;
   fileNameStream << “locations” << fFileNumberString << “.out”;
   std::string fileName(fileNameStream.str());
   std::ifstream locationsStream(fileName.c_str());
   if (!locationsStream.is_open())
   {
      SxChartApp::SayFileError(fileName);
      return;      // give up
   }
   
   // file format is: several blocks of form
   //     pointhoriz,pointvert,personname
   
   // read all lines
   while (!locationsStream.eof())
   {
      std::string pointLine;
      std::getline(locationsStream, pointLine);
      std::string::size_type firstComma = pointLine.find(‘,’);
      std::string::size_type secondComma = 
                     pointLine.find(‘,’, firstComma + 1);
      std::string horizString = pointLine.substr(0, firstComma);
      std::string vertString = 
         pointLine.substr(firstComma + 1, secondComma - firstComma - 1);
      std::string personName = pointLine.substr(secondComma + 1);
      Point aVertex;
      aVertex.h = std::atoi(horizString.c_str());
      aVertex.v = std::atoi(vertString.c_str());
      
      // draw name at vertex, attempt to center on the vertex;
      // do not draw left of or above 0.
      const int kCharHalfHeight = 5;   // assuming 9 point type
      const char *pPersonString = personName.c_str();
      size_t nameCharLen = personName.length();
      int nameWidth = ::TextWidth(pPersonString, 0, nameCharLen);   
                        // width in pixels
      aVertex.h -= (nameWidth / 2);
      aVertex.v += kCharHalfHeight;
      if (aVertex.h < 0)
         aVertex.h = 0;
      if (aVertex.v < 2 * kCharHalfHeight)
         aVertex.v = 2 * kCharHalfHeight;
         
      ::MoveTo(aVertex.h, aVertex.v);
      ::MacDrawText(personName.c_str(), 0, personName.length());
            
      // update bounds
      if (aVertex.h > maxH)
         maxH = aVertex.h;
      if (aVertex.v > maxV)
         maxV = aVertex.v;
   }
   
   // update bounding rect - we somewhat arbitrarily pad it
   // to avoid having the labels clipped off
   const int kPadding = 100;   // units: pixels
   maxV += kPadding;
   maxH += kPadding;
   Rect tempRect = {0, 0, maxV, maxH};
   fPicFrame = tempRect;
}

xChartApp.h

//////////////////////////////////////////////////////////////////////
//
// S*xChart (MacTech Programmer’s Challenge, February 2002)
// Written by Allen Stenger, January 2002
// This file includes portions of:
//     CBasicApp.h, ©1994-2001 Metrowerks Inc. All rights reserved.
//
//////////////////////////////////////////////////////////////////////

#pragma once

#include <LApplication.h>
#include <string>
#include <vector>

// our commands
static const CommandT cmd_RunAllTests = 2000;   // File> Run All Tests
static const CommandT cmd_RunOneTest = 2002;   // File> Run One Test
static const CommandT cmd_DrawGraph = 2001;   // File> Draw Graph
static const CommandT cmd_ZoomIn = 2010;   // Zoom> Zoom In
static const CommandT cmd_ZoomOut = 2011;   // Zoom> Zoom Out

// our ResIDs
static const ResIDT      kWindowMENU = 133;   // Window menu
static const ResIDT    kAskTestNumberDLOG = 1000;   // ask for test number
static const PaneIDT   kAskTestNumberEditPane = 3;   // edit pane
static const ResIDT    kGraphWindow = 1001;   // graph window
static const PaneIDT   kGraphView = 1;   // display pane in graph window
static const ResIDT      kBlankALRT = 1002;   // Alert - fill in text
static const PaneIDT   kALRTTextPane = 1;   // fill in text for above
   

class CMyGraph;

class SxChartApp : public LApplication {

public:
                     SxChartApp();
   virtual               ~SxChartApp();

   virtual Boolean         ObeyCommand(
                        CommandT         inCommand,
                        void*            ioParam = nil);   

   virtual void         FindCommandStatus(
                        CommandT         inCommand,
                        Boolean&         outEnabled,
                        Boolean&         outUsesMark,
                        UInt16&            outMark,
                        Str255            outName);

   // utility to convert a test number to a 2-character string
   static std::string      TestNumberToString(int testNumber);
   
   // utility to say we got a file error
   static void SayFileError(const std::string &rFileName);
   
protected:
         void         RegisterClasses();
         
private:

   // used in implementation
   void RunAllTests();   
      // read in all tests from file and run them
   void RunAndLog(int startCase, int endCase);   
      // run tests startCase-endCase and log times
   void RunOneTest(int testNumber);   // run one test
   bool AskForTestNumber(int *pTestNumber);   
      // get test number, returns false if user cancels
   void DrawGraph(int testNumber);      
      // create and fill graph window
};


// class for running one test
class CTestRunner
{
public:
   explicit CTestRunner(int testNumber);
   ~CTestRunner();
   
   bool LoadNames();   // returns true if loaded OK
   bool LoadHookups();   // returns true if loaded OK
   void MakeEmbeddedGraph();
   void WriteLocations();
   void WriteSegments();

private:
   // used in implementation
   void LoadOneHookup(const std::string& rHookupLine);
   void FindComponentBounds(int whichComp, Rect *pCompBounds);
   void MoveComponent(int whichComp, int offsetH, int offsetV);

   // member variables
   std::string   fFileNumberString;   // holds suffix for this test, e.g., “01”
   int         fNumVertices;      // number of vertices = number of names
   int         fNumHookups;      // number of hookups
   std::vector<std::string> 
            fNames;            // person names, sorted alphabetically
   CMyGraph   *fpGraph;         // graph being embedded; created by LoadNames
};

CGraphEmbedder.h

//////////////////////////////////////////////////////////////////////
//
// Graph Embedder
// Written by Allen Stenger, January 2002
//
//////////////////////////////////////////////////////////////////////

#pragma once

class CMyGraph;

//////////////////////////////////////////////////////////////////////
// this class implements a graph embedder

class CGraphEmbedder
{
public:
   CGraphEmbedder(CMyGraph& aGraph, int whichComponent);
   ~CGraphEmbedder();
   
   void EmbedComponent();
   
private:
   ////////////////////////////
   // used in implementation
   
   void FindAllForces(bool bFindParticles);

   // find resultant force of all points acting on one vertex   
   void FindOneSpringForce(int centerVertex, 
                  float *pForceX, float *pForceY);
   void FindOneParticleForce(int centerVertex, 
                  float *pForceX, float *pForceY);

   ////////////////////////////
   // member variables
   CMyGraph&    fGraph;      // graph being embedded
   int         fComponentNumber;   // which component to embed
   
   // forces, indexed by vertex number
   float      *fpSpringForcesX;   
   float      *fpSpringForcesY;
   float      *fpParticleForcesX;
   float      *fpParticleForcesY;
};

//////////////////////////////////////////////////////////////////////
// This class is how the graph gets passed in and out of the embedder.
// it is essentially an adjacency matrix along with a set of Points
// for each vertex. Vertices are numbered 0 to numVertices - 1.
// We also maintain information on the connected components of the
// graph.

class CMyGraph
{
public:
   explicit CMyGraph(int numVertices);
   ~CMyGraph();
   
   void SetVertex(int whichVertex, const Point& rPoint);
   Point GetVertex(int whichVertex) const;
   int GetNumVertices() const;
   
   // we deal with undirected graphs; setting a adjacent to b
   // also makes b adjacent to a
   void SetAdjacent(int aVertex, int bVertex);
   bool AreAdjacent(int aVertex, int bVertex) const;
   
   // accessing the components, i.e., the connected subgraphs
   void FindConnectedComponents();   // scan graph, determine components
   int GetNumComponents();      // number of components
   int GetComponentNumber(int aVertex); // this vertex’s component’s number
   
private:
   // used in implementation
   void MarkConnectedVertices(int whichVertex, int thisMark);
   
   // member variables
   
   int fNumVertices;      // number of vertices in graph
   
   // the adjacencies matrix is symmetric, and we store both entries
   // (*fpAdjacencies)[i][j] = 0 or 1 as vertices i and j are
   // adjacent (have an edge connecting them) or not.
   // Note: a vertex is never adjacent to itself.
   char *fpAdjacencies;
   
   // the vertices, indexed by vertex number
   Point *fpVertexPoints;
   
   // which component each vertex is in, indexed by vertex number
   // The value is a number from 0 through num components - 1;
   // giving the component number. Initially all values are -1.
   int fNumComponents;
   int *fpComponentNumbers;
};

CGraphWindow.h

//////////////////////////////////////////////////////////////////////
//
// Graph Window
// Written by Allen Stenger, January 2002
//
// This draws the graph in a window.
//
//////////////////////////////////////////////////////////////////////

#pragma once

#include <string>
#include <vector>

class CGraphView;

//////////////////////////////////////////////////////////////////////
// class for window holding a graph
//////////////////////////////////////////////////////////////////////
class CGraphWindow : public LWindow
{
public:
   enum { class_ID = FOUR_CHAR_CODE(‘CGWN’) };

   CGraphWindow(LStream *pStream);
   virtual ~CGraphWindow();
   
   // overrides
   virtual void      FindCommandStatus(
                        CommandT         inCommand,
                        Boolean&         outEnabled,
                        Boolean&         outUsesMark,
                        UInt16&            outMark,
                        Str255            outName);
   virtual Boolean      ObeyCommand(
                        CommandT         inCommand,
                        void*            ioParam = nil);
                        
protected:
   // overrides
   virtual void      FinishCreateSelf();

private:
   CGraphView   *fpGraphView;   // our graph view
   
   // list of all our windows, in creation order;
   // used for Window menu
   static std::vector<CGraphWindow *> fgGraphWindows;
};

//////////////////////////////////////////////////////////////////////
// class for a scrollable view holding the graph
//////////////////////////////////////////////////////////////////////
class CGraphView : public LView
{
public:
   enum { class_ID = FOUR_CHAR_CODE(‘CGVW’) };
   
   CGraphView(LStream *pStream);
   virtual ~CGraphView();
   
   void LoadGraph(int testNumber);
   
   virtual void DrawSelf();   // override
   
   // zoom access
   void SetZoomFactor(int factor);
   int GetZoomFactor();

private:
   // used in implementation
   void DrawEdges();
   void DrawNames();

   // member variables
   PicHandle   fhPicture;   // picture holding our graph
   Rect      fPicFrame;   // extent of picture with drawable data
   std::string   fFileNumberString;   // file suffix, e.g., “01”
   int         fZoomFactor;   // 2^n if zoom out n times
};