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

Dropbox 193.4.5594 - Cloud backup and sy...
Dropbox is a file hosting service that provides cloud storage, file synchronization, personal cloud, and client software. It is a modern workspace that allows you to get to all of your files, manage... Read more
Google Chrome 122.0.6261.57 - Modern and...
Google Chrome is a Web browser by Google, created to be a modern platform for Web pages and applications. It utilizes very fast loading of Web pages and has a V8 engine, which is a custom built... Read more
Skype 8.113.0.210 - Voice-over-internet...
Skype is a telecommunications app that provides HD video calls, instant messaging, calling to any phone number or landline, and Skype for Business for productive cooperation on the projects. This... Read more
Tor Browser 13.0.10 - Anonymize Web brow...
Using Tor Browser you can protect yourself against tracking, surveillance, and censorship. Tor was originally designed, implemented, and deployed as a third-generation onion-routing project of the U.... Read more
Deeper 3.0.4 - Enable hidden features in...
Deeper is a personalization utility for macOS which allows you to enable and disable the hidden functions of the Finder, Dock, QuickTime, Safari, iTunes, login window, Spotlight, and many of Apple's... Read more
OnyX 4.5.5 - Maintenance and optimizatio...
OnyX is a multifunction utility that you can use to verify the startup disk and the structure of its system files, to run miscellaneous maintenance and cleaning tasks, to configure parameters in the... Read more
Hopper Disassembler 5.14.1 - Binary disa...
Hopper Disassembler is a binary disassembler, decompiler, and debugger for 32- and 64-bit executables. It will let you disassemble any binary you want, and provide you all the information about its... Read more
WhatsApp 24.3.78 - Desktop client for Wh...
WhatsApp is the desktop client for WhatsApp Messenger, a cross-platform mobile messaging app which allows you to exchange messages without having to pay for SMS. WhatsApp Messenger is available for... Read more
War Thunder 2.33.0.135 - Multiplayer war...
In War Thunder, aircraft, attack helicopters, ground forces and naval ships collaborate in realistic competitive battles. You can choose from over 1,500 vehicles and an extensive variety of combat... Read more
Iridient Developer 4.2 - Powerful image-...
Iridient Developer (was RAW Developer) is a powerful image-conversion application designed specifically for OS X. Iridient Developer gives advanced photographers total control over every aspect of... Read more

Latest Forum Discussions

See All

Gorgeous Tactical Puzzle Game ‘Howl’ is...
Following its release on PC and Nintendo Switch this past November, and it’s arrival on Xbox and PlayStation back in January, publisher Astragon Entertainment and developer Mi’pu’mi Games are now bringing their super stylish tactical puzzler Howl to... | Read more »
Best iPhone Game Updates: ‘Shoot the Moo...
Hello everyone, and welcome to the week! It’s time once again for our look back at the noteworthy updates of the last seven days. It feels like a bit of a dry spell this week, at least in terms of really interesting updates. I mean, I found some... | Read more »
Celebrate Phobies spooky second annivers...
Get ready to have that classic song stuck in your head, as Phobies celebrates its second anniversary with the release of its latest update; Birthday Bash, Monster Mash. Starting March 5th and lasting for four weeks, it will be a month of... | Read more »
‘Dissidia Final Fantasy Opera Omnia’ Sto...
Square Enix finally shut down Dissidia Final Fantasy Opera Omnia (Free) on iOS and Android last week following the end of service announcement back in November last year. Following the game shutting down, Square Enix | Read more »
‘Monster Hunter Now’ Is Celebrating the...
Niantic and Capcom have begun celebrating the 20th anniversary of Capcom’s best franchise from today inside Monster Hunter Now (Free) on iOS and Android for a limited time. | Read more »
New ‘Warframe Mobile’ Update Adds 60fps...
Warframe Mobile (Free) launched worldwide on iOS just under two weeks ago. I’ve been playing it for review across multiple iOS devices, but have also been picking it up on Steam Deck and Switch to compare. Right from launch, I was impressed with... | Read more »
Passionate About Fidget Toys – The Touch...
In this week’s episode of The TouchArcade Show we kick things off with some passionate discussion about… fidget toys? For some reason? We quickly change gears to talk about the card-based rogulike Balatro, which we’ve both been playing and enjoying... | Read more »
TouchArcade Game of the Week: ‘Flying Ta...
For me Hexage is one of those developers that harkens back to the early days of the App Store and really the beginnings of iPhone gaming. I have spent many collective hours playing the likes of Totemo, Radiant, Radiant Defense, EVAC, Reaper… the... | Read more »
SwitchArcade Round-Up: ‘Ufouria 2: The S...
Hello gentle readers, and welcome to the SwitchArcade Round-Up for March 1st, 2024. In today’s article, we’re looking at the remaining releases of the week. There are a few really good ones today, but the bin bunch certainly isn’t going home hungry... | Read more »
Steam Deck Weekly: Reviews of PowerWash...
Welcome to the first Steam Deck Weekly of March and this week’s edition is bigger than usual. I was a bit unwell last week and had to push some reviews to this week. Alongside that, there have been many notable announcements, releases, and new Steam... | Read more »

Price Scanner via MacPrices.net

Deal Alert! B&H is now selling 13-inch M2...
B&H Photo has 13″ MacBook Airs with M2 CPUs and 256GB of storage in stock and on sale for $100 off Apple’s new MSRP, now only $899. Free 1-2 day delivery is available to most US addresses. Their... Read more
At $999, Apple’s 13-inch M2 MacBook Air is th...
With today’s introduction of the new 13-inch M3 MacBook Air for $1099, Apple dropped prices on the previous-generation 13-inch M2 MacBook Air to $999. At the same time, Apple discontinued the 13-inch... Read more
Apple discontinues 15-inch M2 MacBook Airs, d...
With today’s introduction of new M3-powered 15″ MacBook Airs, Apple has dropped prices on clearance, Certified Refurbished, 15″ M2 MacBook Airs to a new low of $1019. These are the cheapest 15″... Read more
Price Drop! 13-inch M2 MacBook Airs at Apple...
Apple has dropped prices on Certified Refurbished 13″ M2 MacBook Airs to a new low of $849. These are the cheapest M2-powered MacBooks for sale at Apple. Apple’s one-year warranty is included,... Read more
Apple finally discontinues the 13-inch M1 Mac...
With the introduction of M3-powered 13″ MacBook Airs today, Apple has dropped prices on clearance 13″ M1 MacBook Airs, Certified Refurbished, to $759 for 8-Core CPU/7-Core GPU/256GB models and $929... Read more
Updated Apple iPad Price Trackers
Our Apple award-winning iPad Price Trackers are the best place to find the latest information on iPad sales and deals. We track prices from 20+ Apple retailers, including Apple, Amazon, Best Buy,... Read more
Updated Apple MacBook Price Trackers
Our Apple award-winning MacBook Price Trackers are continually updated with the latest information on prices, bundles, and availability for 16″, 14″, and (recently-discontinued) 13″ MacBook Pros... Read more
Mac Studios with Apple M2 Max and M2 Ultra CP...
B&H Photo has the standard-configuration Mac Studio model with Apple’s M2 Ultra CPU in stock today and on sale for $300 off MSRP, now $3699 (24-Core CPU and 64GB RAM/1TB SSD). B&H Photo has... Read more
Extended: Switch to Verizon and get the Apple...
Verizon has the iPhone 15 on sale for $0 per month when you add a new line if service. Discount is applied to your account monthly over a 36 month term and is valid for the 128GB model. For the first... Read more
Select 16-inch M3 Pro and M3 Max MacBook Pros...
B&H Photo has select 16-inch M3 Pro and M3 Max MacBook Pros on sale for $250 off MSRP. Their prices are the lowest currently available for these configurations. Free 1-2 day shipping is available... Read more

Jobs Board

Teller Part Time *Apple* Valley MN *Apple*...
…is not eligible for Visa sponsorship **Posting Location:** + 15574 Pilot Knod Road Apple Valley, MN 55124 @RWF22 **Posting End Date:** Job posting may come down Read more
*Apple* End User Support Specialist - North...
…that they are performed. + Responsible for support of all College owned Apple computers, mobile ios devices, and peripherals, and for diagnosing and resolving 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
Teller Part Time *Apple* Valley MN *Apple*...
…is not eligible for Visa sponsorship **Posting Location:** + 15574 Pilot Knod Road Apple Valley, MN 55124 @RWF22 **Posting End Date:** Job posting may come down Read more
Nurse Anesthetist - *Apple* Hill Surgery Ce...
Nurse Anesthetist - Apple Hill Surgery Center WellSpan Medical Group, York, PA | Advanced Practice Providers | Certified Registered Nurse Anesthetists | FTE: 1 | Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.