home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / src / mactech / volume18_2002 / 18.05.sit / 18.05 / PC / SxChartApp.cp < prev    next >
Text File  |  2002-01-30  |  15KB  |  586 lines
  1. //////////////////////////////////////////////////////////////////////
  2. //
  3. // S*xChart (MacTech Programmer's Challenge, February 2002)
  4. // Written by Allen Stenger, January 2002
  5. //
  6. // This file includes portions of:
  7. //     CBasicApp.cp, ©1994-2001 Metrowerks Inc. All rights reserved.
  8. // Project is based on the Metrowerks Basic Application stationery.
  9. //
  10. // We assume the files are in the same folder as the application.
  11. // We assume the files are numbered starting at 00.
  12. //
  13. // Our strategy:
  14. //
  15. // The challenge is to produce a planar embedding (or almost planar)
  16. // of a given graph. We determine the connected components of the
  17. // given graph and apply a "spring embedder" algorithm to each
  18. // component (the spring embedder doesn't work on disconnected
  19. // graphs). Then we shift each component so they are stacked 
  20. // vertically, not intersecting each other. More details of the
  21. // spring embedder are given with its code.
  22. //
  23. // To display the graph, we create a Picture in memory and draw
  24. // the Picture into the display window.
  25. //
  26. //////////////////////////////////////////////////////////////////////
  27.  
  28. #include "SxChartApp.h"
  29. #include "CGraphEmbedder.h"
  30. #include "CGraphWindow.h"
  31.  
  32. #include <LGrowZone.h>
  33. #include <PP_Messages.h>
  34. #include <PP_Resources.h>
  35. #include <UDrawingState.h>
  36. #include <UMemoryMgr.h>
  37. #include <URegistrar.h>
  38. #include <LActiveScroller.h>
  39.  
  40. #include <LWindow.h>
  41. #include <LCaption.h>
  42.  
  43. #include <ctime>
  44. #include <fstream>
  45. #include <sstream>
  46. #include <string>
  47. #include <vector>
  48.  
  49. // ===========================================================================
  50. //    • main
  51. // ===========================================================================
  52.  
  53. int main()
  54. {                            
  55.         // Set Debugging options
  56.     SetDebugThrow_(debugAction_Alert);
  57.     SetDebugSignal_(debugAction_Alert);
  58.  
  59.         // Initialize Memory Manager. Parameter is the number of
  60.         // master pointer blocks to allocate
  61.     InitializeHeap(3);
  62.     
  63.         // Initialize standard Toolbox managers
  64.     UQDGlobals::InitializeToolbox();
  65.     
  66.         // Install a GrowZone to catch low-memory situations    
  67.     new LGrowZone(20000);
  68.  
  69.         // Create the application object and run
  70.     SxChartApp    theApp;
  71.     theApp.Run();
  72.     
  73.     return 0;
  74. }
  75.  
  76.  
  77. // ---------------------------------------------------------------------------
  78. //    • SxChartApp                                        [public]
  79. // ---------------------------------------------------------------------------
  80. //    Application object constructor
  81.  
  82. SxChartApp::SxChartApp()
  83. {
  84.     RegisterClasses();
  85. }
  86.  
  87.  
  88. // ---------------------------------------------------------------------------
  89. //    • ~SxChartApp                                    [public, virtual]
  90. // ---------------------------------------------------------------------------
  91. //    Application object destructor
  92.  
  93. SxChartApp::~SxChartApp()
  94. {
  95.     // Nothing
  96. }
  97.  
  98.  
  99. // ---------------------------------------------------------------------------
  100. //    • ObeyCommand                                    [public, virtual]
  101. // ---------------------------------------------------------------------------
  102. //    Respond to Commands. Returns true if the Command was handled, false if not.
  103.  
  104. Boolean
  105. SxChartApp::ObeyCommand(
  106.     CommandT    inCommand,
  107.     void*        ioParam)
  108. {
  109.     Boolean        cmdHandled = true;    // Assume we'll handle the command
  110.  
  111.     switch (inCommand) {
  112.  
  113.         case cmd_RunAllTests:
  114.         {
  115.             UCursor::SetWatch();    // a slow operation - show watch
  116.             RunAllTests();
  117.         }
  118.         break;
  119.         
  120.         case cmd_RunOneTest:
  121.         {
  122.             int runOneNumber;
  123.             if (AskForTestNumber(&runOneNumber))
  124.             {
  125.                 UCursor::SetWatch();    // a slow operation - show watch
  126.                 RunAndLog(runOneNumber, runOneNumber);
  127.             }
  128.         }
  129.         break;
  130.         
  131.         case cmd_DrawGraph:
  132.         {
  133.             int drawOneNumber;
  134.             if (AskForTestNumber(&drawOneNumber))
  135.             {
  136.                 DrawGraph(drawOneNumber);
  137.             }
  138.         }
  139.         break;
  140.         
  141.         default: {
  142.             cmdHandled = LApplication::ObeyCommand(inCommand, ioParam);
  143.             break;
  144.         }
  145.     }
  146.     
  147.     return cmdHandled;
  148. }
  149.  
  150.  
  151. // ---------------------------------------------------------------------------
  152. //    • FindCommandStatus                                [public, virtual]
  153. // ---------------------------------------------------------------------------
  154. //    Determine the status of a Command for the purposes of menu updating.
  155.  
  156. void
  157. SxChartApp::FindCommandStatus(
  158.     CommandT    inCommand,
  159.     Boolean&    outEnabled,
  160.     Boolean&    outUsesMark,
  161.     UInt16&        outMark,
  162.     Str255        outName)
  163. {
  164.     switch (inCommand) {
  165.  
  166.         case cmd_RunAllTests:
  167.         {
  168.             outEnabled = true;
  169.         }
  170.         break;
  171.         
  172.         case cmd_RunOneTest:
  173.         {
  174.             outEnabled = true;
  175.         }
  176.         break;
  177.         
  178.         case cmd_DrawGraph:
  179.         {
  180.             outEnabled = true;
  181.         }
  182.         break;
  183.         
  184.         default: {
  185.             LApplication::FindCommandStatus(inCommand, outEnabled,
  186.                                             outUsesMark, outMark, outName);
  187.             break;
  188.         }
  189.     }
  190. }
  191.  
  192.  
  193. // ---------------------------------------------------------------------------
  194. //    • RegisterClasses                                [protected]
  195. // ---------------------------------------------------------------------------
  196. //    To reduce clutter within the Application object's constructor, class
  197. //    registrations appear here in this separate function for ease of use.
  198.  
  199. void
  200. SxChartApp::RegisterClasses()
  201. {
  202.     RegisterClass_(LWindow);
  203.     RegisterClass_(LCaption);
  204.     RegisterClass_(LDialogBox);
  205.     RegisterClass_(LEditField);
  206.     RegisterClass_(LStdButton);
  207.     RegisterClass_(LActiveScroller);
  208.     RegisterClass_(CGraphWindow);
  209.     RegisterClass_(CGraphView);
  210. }
  211.  
  212. //////////////////////////////////////////////////////////////////////
  213. // SxChartApp-specific functions
  214. //////////////////////////////////////////////////////////////////////
  215.  
  216. std::string SxChartApp::TestNumberToString(int testNumber)
  217. {
  218.     std::ostringstream fileNumberStream;
  219.     fileNumberStream.width(2);
  220.     fileNumberStream.fill('0');
  221.     fileNumberStream << testNumber;
  222.     return fileNumberStream.str();
  223. }
  224.  
  225. void SxChartApp::SayFileError(const std::string &rFileName)
  226. {
  227.     std::string errorString = "Sorry, could not open the file " + 
  228.                                 rFileName + ".";
  229.     Str255 errorPString;
  230.     ::CopyCStringToPascal(errorString.c_str(), errorPString);    
  231.     ::ParamText(errorPString, "\p", "\p", "\p");
  232.     UModalAlerts::StopAlert(kBlankALRT);
  233. }
  234.  
  235. void SxChartApp::RunAllTests()
  236. {
  237.     // fetch number of tests, run each test, and output log entry
  238.     std::ifstream numTestsStream("SexChart.in");
  239.     if (!numTestsStream.is_open())
  240.     {
  241.         SxChartApp::SayFileError("SexChart.in");
  242.         return;        // give up
  243.     }
  244.     int numTests = 0;
  245.     numTestsStream >> numTests;
  246.     numTestsStream.close();
  247.     
  248.     RunAndLog(0, numTests - 1);
  249. }
  250.  
  251. void SxChartApp::RunAndLog(int startCase, int endCase)
  252. {
  253.     std::ofstream logStream("logfile.txt");
  254.     if (!logStream.is_open())
  255.     {
  256.         SxChartApp::SayFileError("logfile.txt");
  257.         return;        // give up
  258.     }
  259.     
  260.     for (int i = startCase; i <= endCase; i++)
  261.     {
  262.         std::clock_t startTime, endTime, elapsedTimeClocks;
  263.         
  264.         startTime = std::clock();
  265.         RunOneTest(i);
  266.         endTime = std::clock();
  267.         
  268.         elapsedTimeClocks = endTime - startTime;
  269.         long elapsedTimeMS = 
  270.             std::floor((1000 * elapsedTimeClocks) / CLOCKS_PER_SEC + 0.5);
  271.         logStream << elapsedTimeMS << std::endl;
  272.     }
  273.     
  274.     logStream.close();
  275. }
  276.  
  277. void SxChartApp::RunOneTest(int testNumber)
  278. {
  279.     bool bOkSoFar = true;
  280.     CTestRunner aRunner(testNumber);
  281.     bOkSoFar = aRunner.LoadNames();
  282.     if (bOkSoFar)
  283.         bOkSoFar = aRunner.LoadHookups();
  284.     if (bOkSoFar)
  285.     {
  286.         aRunner.MakeEmbeddedGraph();
  287.         aRunner.WriteLocations();
  288.         aRunner.WriteSegments();
  289.     }
  290.  
  291. }
  292.  
  293. bool SxChartApp::AskForTestNumber(int *pTestNumber)
  294. {
  295.     SInt32 ioNumber = 0;
  296.     bool bOk = UModalDialogs::AskForOneNumber(
  297.                                 this,
  298.                                 kAskTestNumberDLOG,
  299.                                 kAskTestNumberEditPane,
  300.                                 ioNumber);
  301.     if (bOk)
  302.         *pTestNumber = ioNumber;
  303.         
  304.     return bOk;
  305. }
  306.  
  307. void SxChartApp::DrawGraph(int testNumber)
  308. {
  309.     LWindow *pGraphWindow = LWindow::CreateWindow(kGraphWindow, this);
  310.     std::string titleString = "Graph" + TestNumberToString(testNumber);
  311.     Str255 titlePString;
  312.     ::CopyCStringToPascal(titleString.c_str(), titlePString);
  313.     pGraphWindow->SetDescriptor(titlePString);
  314.     CGraphView *pGraphView = 
  315.         static_cast<CGraphView *>(pGraphWindow->FindPaneByID(kGraphView));
  316.     pGraphView->LoadGraph(testNumber);
  317. }
  318.  
  319.  
  320.  
  321. //////////////////////////////////////////////////////////////////////
  322. // CTestRunner implementation
  323. //////////////////////////////////////////////////////////////////////
  324.  
  325. CTestRunner::CTestRunner(int testNumber) :
  326. fNumVertices(0),
  327. fNumHookups(0),
  328. fpGraph(0)
  329. {
  330.     fFileNumberString = SxChartApp::TestNumberToString(testNumber);
  331. }
  332.  
  333. CTestRunner::~CTestRunner()
  334. {
  335.     delete fpGraph;
  336.     fpGraph = 0;
  337. }
  338.     
  339. bool CTestRunner::LoadNames()
  340. {
  341.     // open correct name file
  342.     std::ostringstream fileNameStream;
  343.     fileNameStream << "names" << fFileNumberString << ".in";
  344.     std::string fileName(fileNameStream.str());
  345.     std::ifstream nameStream(fileName.c_str());
  346.     if (!nameStream.is_open())
  347.     {
  348.         SxChartApp::SayFileError(fileName);
  349.         return false;        // give up
  350.     }
  351.     
  352.     // read number of names
  353.     std::string numNamesString;
  354.     std::getline(nameStream, numNamesString);
  355.     int numVertices = std::atoi(numNamesString.c_str());
  356.     
  357.     // read all name lines
  358.     for (fNumVertices = 0; 
  359.         fNumVertices < numVertices && !nameStream.eof(); 
  360.         fNumVertices++)
  361.     {
  362.         std::string nameLine;
  363.         std::getline(nameStream, nameLine);
  364.         fNames.push_back(nameLine);
  365.     }
  366.     nameStream.close();
  367.     
  368.     // create graph this size
  369.     fpGraph = new CMyGraph(fNumVertices);
  370.     
  371.     // sort names
  372.     std::sort(fNames.begin(), fNames.end());
  373.     
  374.     return true;
  375. }
  376.  
  377. bool CTestRunner::LoadHookups()
  378. {
  379.     // open correct hookups file
  380.     std::ostringstream fileNameStream;
  381.     fileNameStream << "hookups" << fFileNumberString << ".in";
  382.     std::string fileName(fileNameStream.str());
  383.     std::ifstream hookupsStream(fileName.c_str());
  384.     if (!hookupsStream.is_open())
  385.     {
  386.         SxChartApp::SayFileError(fileName);
  387.         return false;        // give up
  388.     }
  389.     
  390.     // read number of hookups
  391.     std::string numHookupsString;
  392.     std::getline(hookupsStream, numHookupsString);
  393.     int numHookups = std::atoi(numHookupsString.c_str());
  394.     
  395.     // read all hookup lines
  396.     for (fNumHookups = 0; 
  397.         fNumHookups < numHookups && !hookupsStream.eof(); 
  398.         fNumHookups++)
  399.     {
  400.         std::string hookupLine;
  401.         std::getline(hookupsStream, hookupLine);
  402.         LoadOneHookup(hookupLine);
  403.     }
  404.     hookupsStream.close();
  405.     return true;
  406. }
  407.  
  408. void CTestRunner::LoadOneHookup(const std::string& rHookupLine)
  409. {
  410.     // format of line is 
  411.     // personA,personB
  412.     std::string::size_type firstComma = rHookupLine.find(',');
  413.     std::string personAName = rHookupLine.substr(0, firstComma);
  414.     std::string personBName = rHookupLine.substr(firstComma + 1);
  415.  
  416.     std::vector<std::string>::iterator iter = 
  417.         std::lower_bound(fNames.begin(), fNames.end(), personAName);
  418.     int personAIndex = iter - fNames.begin();
  419.     iter = std::lower_bound(fNames.begin(), fNames.end(), personBName);
  420.     int personBIndex = iter - fNames.begin();
  421.  
  422.     fpGraph->SetAdjacent(personAIndex, personBIndex);
  423. }
  424.  
  425. void CTestRunner::MakeEmbeddedGraph()
  426. {
  427.     // find out the connected components
  428.     fpGraph->FindConnectedComponents();
  429.     
  430.     // Lay out all the points.
  431.     // We place the points at the vertices of a regular n-gon
  432.     // of fixed diameter; this is somewhat arbitrary; if we had
  433.     // some idea of the final graph we could places the points
  434.     // closer to their final position.
  435.     const int kDiam = 1000;    
  436.         // diameter of circle circumscribing n-gon. units: pixels
  437.     const float kPi = 3.14159;
  438.     for (int i = 0; i < fNumVertices; i++)
  439.     {
  440.         Point vertex;
  441.         double angle = i * 2 * kPi / fNumVertices;
  442.         vertex.h = static_cast<int>(0.5 + 
  443.                         kDiam * 0.5 * (1 + std::cos(angle)));
  444.         vertex.v = static_cast<int>(0.5 + 
  445.                         kDiam * 0.5 * (1 + std::sin(-angle)));
  446.         fpGraph->SetVertex(i, vertex);
  447.     
  448.     }
  449.     
  450.     // embed each component in a plane, then shift it so it doesn't
  451.     // collide with the other components. We align each component flush
  452.     // left and just below the previous component.
  453.     int newCompTop = 0;    // where to put next component vertically
  454.     int numComps = fpGraph->GetNumComponents();
  455.     for (int whichComp = 0; whichComp < numComps; whichComp++)
  456.     {
  457.         CGraphEmbedder aEmbedder(*fpGraph, whichComp);
  458.         aEmbedder.EmbedComponent();
  459.         
  460.         Rect compBounds;
  461.         FindComponentBounds(whichComp, &compBounds);
  462.         
  463.         MoveComponent(whichComp, -compBounds.left, 
  464.                             newCompTop - compBounds.top);
  465.         
  466.         // figure out where to put next component;
  467.         // allow a little margin between components
  468.         const int kMargin = 20;    // units: pixels
  469.         newCompTop += (compBounds.bottom - compBounds.top) + kMargin;
  470.     }
  471. }
  472.  
  473. void CTestRunner::WriteLocations()
  474. {
  475.     // open correct output file
  476.     std::ostringstream fileNameStream;
  477.     fileNameStream << "locations" << fFileNumberString << ".out";
  478.     std::string fileName(fileNameStream.str());
  479.     std::ofstream locationsStream(fileName.c_str());
  480.     if (!locationsStream.is_open())
  481.     {
  482.         SxChartApp::SayFileError(fileName);
  483.         return;        // give up
  484.     }
  485.     
  486.     for (int i = 0; i < fNumVertices; i++)
  487.     {
  488.         Point vertex = fpGraph->GetVertex(i);
  489.         locationsStream << vertex.h << ',';
  490.         locationsStream << vertex.v << ',';
  491.         locationsStream << fNames[i] << std::endl;
  492.     }
  493.     locationsStream.close();
  494. }
  495.  
  496. void CTestRunner::WriteSegments()
  497. {
  498.     // open correct output file
  499.     std::ostringstream fileNameStream;
  500.     fileNameStream << "segments" << fFileNumberString << ".out";
  501.     std::string fileName(fileNameStream.str());
  502.     std::ofstream segmentsStream(fileName.c_str());
  503.     if (!segmentsStream.is_open())
  504.     {
  505.         SxChartApp::SayFileError(fileName);
  506.         return;        // give up
  507.     }
  508.     
  509.     // we only need to generate lines in one direction, so we'll 
  510.     // always go from lower to higher indexes
  511.     for (int startVertex = 0; 
  512.             startVertex < fNumVertices; 
  513.             startVertex++)
  514.     {
  515.         for (int endVertex = startVertex + 1; 
  516.                 endVertex < fNumVertices; 
  517.                 endVertex++)
  518.         {
  519.             if (fpGraph->AreAdjacent(startVertex, endVertex))
  520.             {
  521.                 // we generate only straight-line segments, so
  522.                 // the number of points is always 2
  523.                 segmentsStream << "2" << std::endl;
  524.                 Point point1 = fpGraph->GetVertex(startVertex);
  525.                 segmentsStream << point1.h << ',' << 
  526.                                 point1.v << std::endl;
  527.                 Point point2 = fpGraph->GetVertex(endVertex);
  528.                 segmentsStream << point2.h << ',' << 
  529.                                 point2.v << std::endl;
  530.             }
  531.         }
  532.     }
  533.     segmentsStream.close();
  534. }
  535.  
  536. void CTestRunner::FindComponentBounds(int whichComp, Rect *pCompBounds)
  537. {
  538.     Rect bounds = {0, 0, 0, 0};
  539.     bool    bBoundsEmpty = true;
  540.  
  541.     for (int whichVertex = 0; whichVertex < fNumVertices; whichVertex++)
  542.     {
  543.         if (fpGraph->GetComponentNumber(whichVertex) == whichComp)
  544.         {
  545.             Point aVertex = fpGraph->GetVertex(whichVertex);
  546.             if (bBoundsEmpty)
  547.             {
  548.                 bBoundsEmpty = false;
  549.                 bounds.top = aVertex.v;
  550.                 bounds.left = aVertex.h;
  551.                 bounds.bottom = bounds.top + 1;
  552.                 bounds.right = bounds.left + 1;
  553.             }
  554.             else if (!::PtInRect(aVertex, &bounds))
  555.             {
  556.                 if (aVertex.v < bounds.top)
  557.                     bounds.top = aVertex.v;
  558.                 else if (aVertex.v >= bounds.bottom)
  559.                     bounds.bottom = aVertex.v + 1;
  560.                     
  561.                 if (aVertex.h < bounds.left)
  562.                     bounds.left = aVertex.h;
  563.                 else if (aVertex.h == bounds.right)
  564.                     bounds.right = aVertex.h + 1;
  565.             }
  566.         }
  567.     }
  568.     
  569.     *pCompBounds = bounds;
  570. }
  571.  
  572. void CTestRunner::MoveComponent(int whichComp, int offsetH, int offsetV)
  573. {
  574.     for (int whichVertex = 0; whichVertex < fNumVertices; whichVertex++)
  575.     {
  576.         if (fpGraph->GetComponentNumber(whichVertex) == whichComp)
  577.         {
  578.             Point aVertex = fpGraph->GetVertex(whichVertex);
  579.             aVertex.h += offsetH;
  580.             aVertex.v += offsetV;
  581.             fpGraph->SetVertex(whichVertex, aVertex);
  582.         }
  583.     }    
  584. }
  585.  
  586.