source: tspsg-svn/trunk/docs/html/class_c_t_s_p_solver.html @ 76

Last change on this file since 76 was 76, checked in by laleppa, 15 years ago
  • TCandidate should, actually, be SCandidate (struct, not typedef). Renamed it.
  • Documentation update.
File size: 16.6 KB
Line 
1<!-- This comment will put IE 6, 7 and 8 in quirks mode -->
2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
3<html xmlns="http://www.w3.org/1999/xhtml">
4<head>
5<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
6<title>TSPSG: TSP Solver and Generator: CTSPSolver Class Reference</title>
7<link href="tabs.css" rel="stylesheet" type="text/css"/>
8<link href="search/search.css" rel="stylesheet" type="text/css"/>
9<script type="text/javaScript" src="search/search.js"></script>
10<link href="doxygen.css" rel="stylesheet" type="text/css"/>
11</head>
12<body onload='searchBox.OnSelectItem(0);'>
13<!-- Generated by Doxygen 1.6.1 -->
14<script type="text/javascript"><!--
15var searchBox = new SearchBox("searchBox", "search",false,'Search');
16--></script>
17<script type="text/javascript">
18<!--
19function changeDisplayState (e){
20  var num=this.id.replace(/[^[0-9]/g,'');
21  var button=this.firstChild;
22  var sectionDiv=document.getElementById('dynsection'+num);
23  if (sectionDiv.style.display=='none'||sectionDiv.style.display==''){
24    sectionDiv.style.display='block';
25    button.src='open.gif';
26  }else{
27    sectionDiv.style.display='none';
28    button.src='closed.gif';
29  }
30}
31function initDynSections(){
32  var divs=document.getElementsByTagName('div');
33  var sectionCounter=1;
34  for(var i=0;i<divs.length-1;i++){
35    if(divs[i].className=='dynheader'&&divs[i+1].className=='dynsection'){
36      var header=divs[i];
37      var section=divs[i+1];
38      var button=header.firstChild;
39      if (button!='IMG'){
40        divs[i].insertBefore(document.createTextNode(' '),divs[i].firstChild);
41        button=document.createElement('img');
42        divs[i].insertBefore(button,divs[i].firstChild);
43      }
44      header.style.cursor='pointer';
45      header.onclick=changeDisplayState;
46      header.id='dynheader'+sectionCounter;
47      button.src='closed.gif';
48      section.id='dynsection'+sectionCounter;
49      section.style.display='none';
50      section.style.marginLeft='14px';
51      sectionCounter++;
52    }
53  }
54}
55window.onload = initDynSections;
56-->
57</script>
58<div class="navigation" id="top">
59  <div class="tabs">
60    <ul>
61      <li><a href="index.html"><span>Main&nbsp;Page</span></a></li>
62      <li><a href="pages.html"><span>Related&nbsp;Pages</span></a></li>
63      <li class="current"><a href="annotated.html"><span>Classes</span></a></li>
64      <li><a href="files.html"><span>Files</span></a></li>
65      <li>
66        <div id="MSearchBox" class="MSearchBoxInactive">
67        <img id="MSearchSelect" src="search/search.png"
68             onmouseover="return searchBox.OnSearchSelectShow()"
69             onmouseout="return searchBox.OnSearchSelectHide()"
70             alt=""/>
71        <input type="text" id="MSearchField" value="Search" accesskey="S"
72             onfocus="searchBox.OnSearchFieldFocus(true)" 
73             onblur="searchBox.OnSearchFieldFocus(false)" 
74             onkeyup="searchBox.OnSearchFieldChange(event)"/>
75        <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
76        </div>
77      </li>
78    </ul>
79  </div>
80  <div class="tabs">
81    <ul>
82      <li><a href="annotated.html"><span>Class&nbsp;List</span></a></li>
83      <li><a href="hierarchy.html"><span>Class&nbsp;Hierarchy</span></a></li>
84      <li><a href="functions.html"><span>Class&nbsp;Members</span></a></li>
85    </ul>
86  </div>
87</div>
88<div class="contents">
89<h1>CTSPSolver Class Reference</h1><!-- doxytag: class="CTSPSolver" -->
90<p>This class solves Travelling Salesman Problem task. 
91<a href="#_details">More...</a></p>
92
93<p><code>#include &lt;<a class="el" href="tspsolver_8h_source.html">tspsolver.h</a>&gt;</code></p>
94<div class="dynheader">
95Collaboration diagram for CTSPSolver:</div>
96<div class="dynsection">
97<div class="center"><img src="class_c_t_s_p_solver__coll__graph.png" border="0" usemap="#_c_t_s_p_solver_coll__map" alt="Collaboration graph"/></div>
98<map name="_c_t_s_p_solver_coll__map" id="_c_t_s_p_solver_coll__map">
99<area shape="rect" id="node2" href="struct_s_step.html" title="This structure represents one step of solving." alt="" coords="241,101,297,129"/>
100<area shape="rect" id="node4" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qlist.html" title="QList\&lt; QList\&lt; double \&gt; \&gt;" alt="" coords="5,6,173,34"/>
101<area shape="rect" id="node7" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qlist.html" title="QList\&lt; SCandidate \&gt;" alt="" coords="197,6,341,34"/>
102<area shape="rect" id="node9" href="struct_s_candidate.html" title="A structure that represents a candidate for branching." alt="" coords="365,6,453,34"/>
103<area shape="rect" id="node11" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qhash.html" title="QHash\&lt; int, int \&gt;" alt="" coords="387,101,507,129"/>
104</map>
105<center><span class="legend">[<a href="graph_legend.html">legend</a>]</span></center></div>
106
107<p><a href="class_c_t_s_p_solver-members.html">List of all members.</a></p>
108<table border="0" cellpadding="0" cellspacing="0">
109<tr><td colspan="2"><h2>Public Member Functions</h2></td></tr>
110<tr><td class="memItemLeft" align="right" valign="top"><a class="anchor" id="aa5e45813d8f5e1c039b1bb9746d367bd"></a><!-- doxytag: member="CTSPSolver::CTSPSolver" ref="aa5e45813d8f5e1c039b1bb9746d367bd" args="()" -->
111&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_c_t_s_p_solver.html#aa5e45813d8f5e1c039b1bb9746d367bd">CTSPSolver</a> ()</td></tr>
112<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Class constructor. <br/></td></tr>
113<tr><td class="memItemLeft" align="right" valign="top"><a class="elRef" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qstring.html">QString</a>&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_c_t_s_p_solver.html#a57556c971a25e3556c4aa3cc1fd2d3d0">getSortedPath</a> () const </td></tr>
114<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns the sorted optimal path, starting from City 1.  <a href="#a57556c971a25e3556c4aa3cc1fd2d3d0"></a><br/></td></tr>
115<tr><td class="memItemLeft" align="right" valign="top">bool&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_c_t_s_p_solver.html#a28d546e840cf53c639b45c0f26419f7a">isOptimal</a> () const </td></tr>
116<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns whether or not the solution is definitely optimal.  <a href="#a28d546e840cf53c639b45c0f26419f7a"></a><br/></td></tr>
117<tr><td class="memItemLeft" align="right" valign="top"><a class="el" href="struct_s_step.html">SStep</a> *&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_c_t_s_p_solver.html#a9a6545dd05e449151aabe325f4058edd">solve</a> (int numCities, <a class="elRef" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qlist.html">TMatrix</a> task, <a class="elRef" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qwidget.html">QWidget</a> *parent=0)</td></tr>
118<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Solves the given task.  <a href="#a9a6545dd05e449151aabe325f4058edd"></a><br/></td></tr>
119<tr><td colspan="2"><h2>Static Public Member Functions</h2></td></tr>
120<tr><td class="memItemLeft" align="right" valign="top">static <a class="elRef" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qstring.html">QString</a>&nbsp;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_c_t_s_p_solver.html#a677a878c4c8a06316a5d8d5a4fc8ab65">getVersionId</a> ()</td></tr>
121<tr><td class="mdescLeft">&nbsp;</td><td class="mdescRight">Returns CTSPSolver's version ID.  <a href="#a677a878c4c8a06316a5d8d5a4fc8ab65"></a><br/></td></tr>
122</table>
123<hr/><a name="_details"></a><h2>Detailed Description</h2>
124<p>This class solves Travelling Salesman Problem task. </p>
125<dl class="author"><dt><b>Author:</b></dt><dd>Copyright &copy; 2007-2009 Lёppa &lt;contacts[at]oleksii[dot]name&gt;</dd></dl>
126<dl class="todo"><dt><b><a class="el" href="todo.html#_todo000003">Todo:</a></b></dt><dd>TODO: Deletion of solution tree on destroy and cleanup. </dd></dl>
127<hr/><h2>Member Function Documentation</h2>
128<a class="anchor" id="a57556c971a25e3556c4aa3cc1fd2d3d0"></a><!-- doxytag: member="CTSPSolver::getSortedPath" ref="a57556c971a25e3556c4aa3cc1fd2d3d0" args="() const " -->
129<div class="memitem">
130<div class="memproto">
131      <table class="memname">
132        <tr>
133          <td class="memname"><a class="elRef" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qstring.html">QString</a> CTSPSolver::getSortedPath </td>
134          <td>(</td>
135          <td class="paramname"></td>
136          <td>&nbsp;)&nbsp;</td>
137          <td> const</td>
138        </tr>
139      </table>
140</div>
141<div class="memdoc">
142
143<p>Returns the sorted optimal path, starting from City 1. </p>
144<dl class="return"><dt><b>Returns:</b></dt><dd>A string, containing sorted optimal path. </dd></dl>
145
146<p><div class="dynheader">
147Here is the call graph for this function:</div>
148<div class="dynsection">
149<div class="center"><img src="class_c_t_s_p_solver_a57556c971a25e3556c4aa3cc1fd2d3d0_cgraph.png" border="0" usemap="#class_c_t_s_p_solver_a57556c971a25e3556c4aa3cc1fd2d3d0_cgraph_map" alt=""></div>
150<map name="class_c_t_s_p_solver_a57556c971a25e3556c4aa3cc1fd2d3d0_cgraph_map" id="class_c_t_s_p_solver_a57556c971a25e3556c4aa3cc1fd2d3d0_cgraph">
151<area shape="rect" id="node3" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qstring.html#arg" title="QString::arg" alt="" coords="248,5,339,33"/>
152<area shape="rect" id="node5" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qhash.html#isEmpty" title="QHash::isEmpty" alt="" coords="235,55,352,83"/>
153<area shape="rect" id="node7" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qhash.html#size" title="QHash::size" alt="" coords="247,106,340,134"/>
154</map>
155</div>
156</p>
157
158</div>
159</div>
160<a class="anchor" id="a677a878c4c8a06316a5d8d5a4fc8ab65"></a><!-- doxytag: member="CTSPSolver::getVersionId" ref="a677a878c4c8a06316a5d8d5a4fc8ab65" args="()" -->
161<div class="memitem">
162<div class="memproto">
163      <table class="memname">
164        <tr>
165          <td class="memname"><a class="elRef" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qstring.html">QString</a> CTSPSolver::getVersionId </td>
166          <td>(</td>
167          <td class="paramname"></td>
168          <td>&nbsp;)&nbsp;</td>
169          <td><code> [static]</code></td>
170        </tr>
171      </table>
172</div>
173<div class="memdoc">
174
175<p>Returns CTSPSolver's version ID. </p>
176<dl class="return"><dt><b>Returns:</b></dt><dd>A string: <b>$Id: tspsolver.cpp 74 2009-12-16 22:22:05Z laleppa $</b>. </dd></dl>
177
178</div>
179</div>
180<a class="anchor" id="a28d546e840cf53c639b45c0f26419f7a"></a><!-- doxytag: member="CTSPSolver::isOptimal" ref="a28d546e840cf53c639b45c0f26419f7a" args="() const " -->
181<div class="memitem">
182<div class="memproto">
183      <table class="memname">
184        <tr>
185          <td class="memname">bool CTSPSolver::isOptimal </td>
186          <td>(</td>
187          <td class="paramname"></td>
188          <td>&nbsp;)&nbsp;</td>
189          <td> const</td>
190        </tr>
191      </table>
192</div>
193<div class="memdoc">
194
195<p>Returns whether or not the solution is definitely optimal. </p>
196<dl class="return"><dt><b>Returns:</b></dt><dd><code>true</code> if solution is definitely optimal, otherwise <code>false</code>.</dd></dl>
197<p>The solution may need some further interations to determine whether it is optimal. In such cases this function returns <code>false</code>. </p>
198
199</div>
200</div>
201<a class="anchor" id="a9a6545dd05e449151aabe325f4058edd"></a><!-- doxytag: member="CTSPSolver::solve" ref="a9a6545dd05e449151aabe325f4058edd" args="(int numCities, TMatrix task, QWidget *parent=0)" -->
202<div class="memitem">
203<div class="memproto">
204      <table class="memname">
205        <tr>
206          <td class="memname"><a class="el" href="struct_s_step.html">SStep</a> * CTSPSolver::solve </td>
207          <td>(</td>
208          <td class="paramtype">int&nbsp;</td>
209          <td class="paramname"> <em>numCities</em>, </td>
210        </tr>
211        <tr>
212          <td class="paramkey"></td>
213          <td></td>
214          <td class="paramtype"><a class="elRef" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qlist.html">TMatrix</a>&nbsp;</td>
215          <td class="paramname"> <em>task</em>, </td>
216        </tr>
217        <tr>
218          <td class="paramkey"></td>
219          <td></td>
220          <td class="paramtype"><a class="elRef" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qwidget.html">QWidget</a> *&nbsp;</td>
221          <td class="paramname"> <em>parent</em> = <code>0</code></td><td>&nbsp;</td>
222        </tr>
223        <tr>
224          <td></td>
225          <td>)</td>
226          <td></td><td></td><td></td>
227        </tr>
228      </table>
229</div>
230<div class="memdoc">
231
232<p>Solves the given task. </p>
233<dl><dt><b>Parameters:</b></dt><dd>
234  <table border="0" cellspacing="2" cellpadding="0">
235    <tr><td valign="top"></td><td valign="top"><em>numCities</em>&nbsp;</td><td>Number of cities in the task. </td></tr>
236    <tr><td valign="top"></td><td valign="top"><em>task</em>&nbsp;</td><td>The matrix of city-to-city travel costs. </td></tr>
237    <tr><td valign="top"></td><td valign="top"><em>parent</em>&nbsp;</td><td>The parent widget for displaying messages and dialogs. </td></tr>
238  </table>
239  </dd>
240</dl>
241<dl class="return"><dt><b>Returns:</b></dt><dd>Pointer to the root of the solution tree.</dd></dl>
242<dl class="todo"><dt><b><a class="el" href="todo.html#_todo000002">Todo:</a></b></dt><dd>TODO: Comment the algorithm. </dd></dl>
243
244<p><div class="dynheader">
245Here is the call graph for this function:</div>
246<div class="dynsection">
247<div class="center"><img src="class_c_t_s_p_solver_a9a6545dd05e449151aabe325f4058edd_cgraph.png" border="0" usemap="#class_c_t_s_p_solver_a9a6545dd05e449151aabe325f4058edd_cgraph_map" alt=""></div>
248<map name="class_c_t_s_p_solver_a9a6545dd05e449151aabe325f4058edd_cgraph_map" id="class_c_t_s_p_solver_a9a6545dd05e449151aabe325f4058edd_cgraph">
249<area shape="rect" id="node3" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qprogressdialog.html#reset" title="QProgressDialog::reset" alt="" coords="187,5,341,33"/>
250<area shape="rect" id="node5" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qprogressdialog.html#setBar" title="QProgressDialog::setBar" alt="" coords="181,55,347,83"/>
251<area shape="rect" id="node7" doxygen="qt-4.6.tag:http://doc.trolltech.com/4.6/" href="http://doc.trolltech.com/4.6/qhash.html#size" title="QHash::size" alt="" coords="217,106,311,134"/>
252</map>
253</div>
254</p>
255
256</div>
257</div>
258<hr/>The documentation for this class was generated from the following files:<ul>
259<li>src/<a class="el" href="tspsolver_8h_source.html">tspsolver.h</a></li>
260<li>src/tspsolver.cpp</li>
261</ul>
262</div>
263<!--- window showing the filter options -->
264<div id="MSearchSelectWindow"
265     onmouseover="return searchBox.OnSearchSelectShow()"
266     onmouseout="return searchBox.OnSearchSelectHide()"
267     onkeydown="return searchBox.OnSearchSelectKey(event)">
268<a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark">&nbsp;</span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark">&nbsp;</span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark">&nbsp;</span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark">&nbsp;</span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark">&nbsp;</span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark">&nbsp;</span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark">&nbsp;</span>Defines</a></div>
269
270<!-- iframe showing the search results (closed by default) -->
271<div id="MSearchResultsWindow">
272<iframe src="" frameborder="0" 
273        name="MSearchResults" id="MSearchResults">
274</iframe>
275</div>
276
277<hr size="1"/><address style="text-align: right;"><small>Generated on Thu Dec 17 00:37:32 2009 for TSPSG: TSP Solver and Generator by&nbsp;
278<a href="http://www.doxygen.org/index.html">
279<img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.6.1 </small></address>
280</body>
281</html>
Note: See TracBrowser for help on using the repository browser.