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

Latest Forum Discussions

See All

Whitethorn Games combines two completely...
If you have ever gone fishing then you know that it is a lesson in patience, sitting around waiting for a bite that may never come. Well, that's because you have been doing it wrong, since as Whitehorn Games now demonstrates in new release Skate... | Read more »
Call of Duty Warzone is a Waiting Simula...
It's always fun when a splashy multiplayer game comes to mobile because they are few and far between, so I was excited to see the notification about Call of Duty: Warzone Mobile (finally) launching last week and wanted to try it out. As someone who... | Read more »
Albion Online introduces some massive ne...
Sandbox Interactive has announced an upcoming update to its flagship MMORPG Albion Online, containing massive updates to its existing guild Vs guild systems. Someone clearly rewatched the Helms Deep battle in Lord of the Rings and spent the next... | Read more »
Chucklefish announces launch date of the...
Chucklefish, the indie London-based team we probably all know from developing Terraria or their stint publishing Stardew Valley, has revealed the mobile release date for roguelike deck-builder Wildfrost. Developed by Gaziter and Deadpan Games, the... | Read more »
Netmarble opens pre-registration for act...
It has been close to three years since Netmarble announced they would be adapting the smash series Solo Leveling into a video game, and at last, they have announced the opening of pre-orders for Solo Leveling: Arise. [Read more] | Read more »
PUBG Mobile celebrates sixth anniversary...
For the past six years, PUBG Mobile has been one of the most popular shooters you can play in the palm of your hand, and Krafton is celebrating this milestone and many years of ups by teaming up with hit music man JVKE to create a special song for... | Read more »
ASTRA: Knights of Veda refuse to pump th...
In perhaps the most recent example of being incredibly eager, ASTRA: Knights of Veda has dropped its second collaboration with South Korean boyband Seventeen, named so as it consists of exactly thirteen members and a video collaboration with Lee... | Read more »
Collect all your cats and caterpillars a...
If you are growing tired of trying to build a town with your phone by using it as a tiny, ineffectual shover then fear no longer, as Independent Arts Software has announced the upcoming release of Construction Simulator 4, from the critically... | Read more »
Backbone complete its lineup of 2nd Gene...
With all the ports of big AAA games that have been coming to mobile, it is becoming more convenient than ever to own a good controller, and to help with this Backbone has announced the completion of their 2nd generation product lineup with their... | Read more »
Zenless Zone Zero opens entries for its...
miHoYo, aka HoYoverse, has become such a big name in mobile gaming that it's hard to believe that arguably their flagship title, Genshin Impact, is only three and a half years old. Now, they continue the road to the next title in their world, with... | Read more »

Price Scanner via MacPrices.net

B&H has Apple’s 13-inch M2 MacBook Airs o...
B&H Photo has 13″ MacBook Airs with M2 CPUs and 256GB of storage in stock and on sale for up to $150 off Apple’s new MSRP, starting at only $849. Free 1-2 day delivery is available to most US... Read more
M2 Mac minis on sale for $100-$200 off MSRP,...
B&H Photo has Apple’s M2-powered Mac minis back in stock and on sale today for $100-$200 off MSRP. Free 1-2 day shipping is available for most US addresses: – Mac mini M2/256GB SSD: $499, save $... Read more
Mac Studios with M2 Max and M2 Ultra CPUs on...
B&H Photo has standard-configuration Mac Studios with Apple’s M2 Max & Ultra CPUs in stock today and on Easter sale for $200 off MSRP. Their prices are the lowest available for these models... Read more
Deal Alert! B&H Photo has Apple’s 14-inch...
B&H Photo has new Gray and Black 14″ M3, M3 Pro, and M3 Max MacBook Pros on sale for $200-$300 off MSRP, starting at only $1399. B&H offers free 1-2 day delivery to most US addresses: – 14″ 8... Read more
Department Of Justice Sets Sights On Apple In...
NEWS – The ball has finally dropped on the big Apple. The ball (metaphorically speaking) — an antitrust lawsuit filed in the U.S. on March 21 by the Department of Justice (DOJ) — came down following... Read more
New 13-inch M3 MacBook Air on sale for $999,...
Amazon has Apple’s new 13″ M3 MacBook Air on sale for $100 off MSRP for the first time, now just $999 shipped. Shipping is free: – 13″ MacBook Air (8GB RAM/256GB SSD/Space Gray): $999 $100 off MSRP... Read more
Amazon has Apple’s 9th-generation WiFi iPads...
Amazon has Apple’s 9th generation 10.2″ WiFi iPads on sale for $80-$100 off MSRP, starting only $249. Their prices are the lowest available for new iPads anywhere: – 10″ 64GB WiFi iPad (Space Gray or... Read more
Discounted 14-inch M3 MacBook Pros with 16GB...
Apple retailer Expercom has 14″ MacBook Pros with M3 CPUs and 16GB of standard memory discounted by up to $120 off Apple’s MSRP: – 14″ M3 MacBook Pro (16GB RAM/256GB SSD): $1691.06 $108 off MSRP – 14... Read more
Clearance 15-inch M2 MacBook Airs on sale for...
B&H Photo has Apple’s 15″ MacBook Airs with M2 CPUs (8GB RAM/256GB SSD) in stock today and on clearance sale for $999 in all four colors. Free 1-2 delivery is available to most US addresses.... Read more
Clearance 13-inch M1 MacBook Airs drop to onl...
B&H has Apple’s base 13″ M1 MacBook Air (Space Gray, Silver, & Gold) in stock and on clearance sale today for $300 off MSRP, only $699. Free 1-2 day shipping is available to most addresses in... Read more

Jobs Board

Medical Assistant - Surgical Oncology- *Apple...
Medical Assistant - Surgical Oncology- Apple Hill Location: WellSpan Medical Group, York, PA Schedule: Full Time Sign-On Bonus Eligible Remote/Hybrid Regular Apply 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
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
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
Business Analyst | *Apple* Pay - Banco Popu...
Business Analyst | Apple PayApply now " Apply now + Apply Now + Start applying with LinkedIn Start + Please wait Date:Mar 19, 2024 Location: San Juan-Cupey, PR Read more
All contents are Copyright 1984-2011 by Xplain Corporation. All rights reserved. Theme designed by Icreon.