TweetFollow Us on Twitter

May 02 Challenge

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

by Bob Boonstra, Westford, MA

Jigsaw Puzzle

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.

Winner of the February, 2002 Challenge

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.

Name Score Intersections Time
(msec)
Alan Stenger (84) 9111.33 9903 185355.00
Ernst Munter (832) 21446.10 26393 219.65
Name Bonus Code Data Lang
Size Size
Alan Stenger 22.50% 113944 26622 C++
Ernst Munter 18.75% 22496 3344 C++

Top Contestants ...

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.

Rank Name Points Wins Total
(24 mo) (24 mo) Points
1. Munter, Ernst 275 10 842
2. Saxton, Tom 52 1 210
3. Wihlborg, Claes 47 2 49
4. Rieken, Willeke 46 2 134
5. Stenger, Allen 39 1 104
6. Taylor, Jonathan 39 1 63
9. Gregg, Xan 20 1 140
10. Mallett, Jeff 20 1 114
11. Cooper, Tony 20 1 20
12. Truskier, Peter 20 1 20

... and the Top Contestants Looking for a Recent Win

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.

Rank Name Points Total
(24 mo) Points
7. Sadetsky, Gregory 22 24
8. Boring, Randy 21 144
13. Shearer, Rob 19 62
14. Schotsman, Jan 16 16
15. Hart, Alan 14 39
16. Nepsund, Ronald 10 57
17. Day, Mark 10 30
18. Desch, Noah 10 10
19. Fazekas, Miklos 10 10
20. Flowers, Sue 10 10
21. Maurer, Sebastian 7 108
22. Leshner, Will 7 7
23. Miller, Mike 7 7

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:

1st place 20 points
2nd place 10 points
3rd place 7 points
4th place 4 points
5th place 2 points
finding bug 2 points
suggesting Challenge 2 points

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
};


 

Community Search:
MacTech Search:

Software Updates via MacUpdate

Notion 2.1.9 - A unified workspace for m...
Notion is the unified workspace for modern teams. Features: Integration with Slack Documents Wikis Tasks More guests: invite up to 10 collaborators, friends & family to your pages Page... Read more
Spotify 1.2.0.1165 - Stream music, creat...
Spotify is a streaming music service that gives you on-demand access to millions of songs. Whether you like driving rock, silky R&B, or grandiose classical music, Spotify's massive catalogue puts... Read more
Thunderbird 102.5.1 - Email client from...
As of July 2012, Thunderbird has transitioned to a new governance model, with new features being developed by the broader free software and open source community, and security fixes and improvements... Read more
Pinegrow 7.03 - Mockup and design web pa...
Pinegrow (was Pinegrow Web Designer) is desktop app that lets you mockup and design webpages faster with multi-page editing, CSS and LESS styling, and smart components for Bootstrap, Foundation,... Read more
Adobe After Effects 2022 23.1 - Create p...
The new, more connected Adobe After Effects can make the impossible possible. Get powerful new features like a Live 3D Pipeline that brings CINEMA 4D scenes in as layers - without intermediate... Read more
SteerMouse 5.6.7 - Powerful third-party...
SteerMouse is an advanced driver for USB and Bluetooth mice. SteerMouse can assign various functions to buttons that Apple's software does not allow, including double-clicks, modifier clicks,... Read more
Wireshark 4.0.2 - Network protocol analy...
Wireshark is one of the world's foremost network protocol analyzers, and is the standard in many parts of the industry. It is the continuation of a project that started in 1998. Hundreds of... Read more
Adobe Premiere Pro 2022 23.1 - Digital v...
Adobe Premiere Pro is available as part of Adobe Creative Cloud for as little as $54.99/month. The price on display is a price for annual by-monthly plan for Adobe Premiere Pro only. Adobe Premiere... Read more
1Password 8.9.10 - Powerful password man...
1Password is a password manager that uniquely brings you both security and convenience. It is the only program that provides anti-phishing protection and goes beyond password management by adding Web... Read more
FotoMagico 6.3 - Powerful slideshow crea...
FotoMagico lets you create professional slideshows from your photos and music with just a few, simple mouse clicks. It sports a very clean and intuitive yet powerful user interface. High image... Read more

Latest Forum Discussions

See All

‘Awaken Legends: Idle RPG’ Celebrates th...
Awaken Legends: Idle RPG is adding its first update since the game was soft-launched in November, letting players get their hands on a new hero “Hera Valen". Players can also look forward to the Covenant of the Dark Knight event and the Wishing Well... | Read more »
‘Horizon Chase 2’ Japan World Tour Expan...
Horizon Chase 2 () from Aquiris is getting a major expansion today on Apple Arcade. The Japan World Tour expansion brings in 11 new races across 9 cities and it should be rolling out now as of this writing. I expect it to be available worldwide... | Read more »
Dark Fantasy Visual Novel ‘The 13th Mont...
Originally announced for release in August, The 13th Month from Japanese developer Kobayashimaru and publisher Kodansha released on PC via Steam worldwide this month. The dark fantasy visual novel that reimagines the classic Sleeping Beauty tale, is... | Read more »
Tom Clancey’s The Divison Resurgence ann...
Ubisoft has announced the latest Live Test dates for Tom Clancy’s The Division Resurgence, the hotly anticipated mobile entry in the Divison series. Starting December 8th and ending on the 22nd, the test will offer a huge amount of content for the... | Read more »
‘Easy Come Easy Golf’ New Update Adds St...
Easy Come Easy Golf () from Clap Hanz is one of my favorite games on Apple Arcade. It has been updated quite a bit since launch bringing in new modes and improvements. It recently launched on Nintendo Switch as well. | Read more »
Out Now: ‘Magic vs Metal’, ‘Suzerain’, ‘...
Each and every day new mobile games are hitting the App Store, and so each week we put together a big old list of all the best new releases of the past seven days. Back in the day the App Store would showcase the same games for a week, and then... | Read more »
SwitchArcade Round-Up: Reviews Featuring...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for December 7th, 2022. Today can be accurately described as Mikhail Madness, with a whopping four reviews from our pal-est of pals. Football Manager 2023 Touch, Wobbledogs, Soccer Story... | Read more »
Alchemy Stars celebrates 1 and a half ye...
It has been one and a half years since Alchemy Stars launched, and Level Infinite is celebrating in style with a host of new content. There will be a new story mission and even a store to explore, and a whole new mode for those budding idol... | Read more »
Fighting Game ‘Art of Fighting 2’ ACA Ne...
Last week, side-scrolling shooter Pulstar hit mobile platforms as the newest ACA NeoGeo series release from Hamster and SNK. Read Shaun’s review of it here. Today, fighting game Art of Fighting 2 has launched on iOS and Android. Art of Fighting 2... | Read more »
‘Genshin Impact’ Version 3.3 Update Now...
HoYoverse recently revealed the next major update for Genshin Impact (Free) in the form of version 3.3 ‘All Senses Clear, All Existence Void’. | Read more »

Price Scanner via MacPrices.net

New! Details on Verizon’s Christmas/Holiday p...
Verizon is offering discounts on iPhones, Apple Watch models, and iPads with specific promo codes as part of their Christmas/Holiday 2022 offerings. Codes are valid when adding a new line of service... Read more
Apple MagSafe accessories are back on Holiday...
Amazon has Apple MagSafe Chargers and Apple’s MagSafe Battery on sale for up to 24% off MSRP again as part of their Christmas/Holiday sale. Shipping is free, and all models are in stock: – MagSafe... Read more
13″ M2 MacBook Airs on sale again for the low...
Amazon has 13″ MacBook Airs with M2 CPUs in stock today and on sale for $150 off MSRP as part of their Christmas/Holiday Sale, prices start at $1049. Shipping is free. They are the lowest prices... Read more
Get an Apple 16″ MacBook Pro for $400 off MSR...
16″ MacBook Pros with Apple’s M1 Pro CPUs are in stock and on sale today at B&H Photo for $300-$400 off Apple’s MSRP for a limited time. Prices start at $2099 for M1 Pro models with 512GB or 1TB... Read more
Holiday clearance sale! Previous-generation A...
Amazon has 2nd generation 32GB and 64GB 4K Apple TVs with Siri remotes and 32GB Apple TV HDs on clearance sale for $80-$90 off original MSRP. Shipping is free, and delivery is available in time for... Read more
Christmas sale at Verizon: Apple AirPods Pro...
Verizon has first-generation Apple AirPods Pro on sale for $159.99 on their online store as part of their continuing Christmas/Holiday sale. Their price is $90 off Apple’s original MSRP, and it’s the... Read more
New Christmas/New Years promo at Xfinity Mobi...
Switch to Xfinity Mobile and open a new line of service, and take $400 off the price of a new iPhone, no trade-in required, through January 10, 2023. The $400 is applied to your account as credits... Read more
Apple iPad Smart Keyboard Folio prices drop u...
Apple iPad Smart Keyboard Folio prices have dropped up to $60 off MSRP at Amazon and Walmart as part of their Christmas/Holiday sales. These are the cheapest prices currently available for these iPad... Read more
Today is the final day for Xfinity Mobile’s $...
If you switch to Xfinity Mobile and open a new line of service, they will take $500 off the price of a new iPhone, no trade-in required. This is the best no trade-in Cyber Monday Apple iPhone 14 deal... Read more
Amazon restocks 10.2″ 64GB 9th-generation iPa...
Amazon has Apple’s 9th generation 10.2″ 64GB WiFi iPads (Silver) in stock and on sale for $269.99 shipped as part of their Christmas/Holiday Sale. Their price is $60 off Apple’s MSRP. Free delivery... Read more

Jobs Board

*Apple* Systems Administrator - JAMF - Activ...
…Administration **Duties and Responsibilities** + Configure and maintain the client's Apple Device Management (ADM) solution. The current solution is JAMF supporting Read more
Cashier - *Apple* Blossom Mall - JCPenney (...
Cashier - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Blossom Mall Read more
Omnichannel Associate - *Apple* Blossom Mal...
Omnichannel Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Sephora Beauty Advisor - *Apple* Blossom Ma...
Sephora Beauty Advisor - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
Operations Associate - *Apple* Blossom Mall...
Operations Associate - Apple Blossom Mall Location:Winchester, VA, United States (https://jobs.jcp.com/jobs/location/191170/winchester-va-united-states) - Apple Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.