| 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: src/tspsolver.h Source File</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"><!-- |
|---|
| 15 | var searchBox = new SearchBox("searchBox", "search",false,'Search'); |
|---|
| 16 | --></script> |
|---|
| 17 | <script type="text/javascript"> |
|---|
| 18 | <!-- |
|---|
| 19 | function 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 | } |
|---|
| 31 | function 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 | } |
|---|
| 55 | window.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 Page</span></a></li> |
|---|
| 62 | <li><a href="pages.html"><span>Related Pages</span></a></li> |
|---|
| 63 | <li><a href="annotated.html"><span>Classes</span></a></li> |
|---|
| 64 | <li class="current"><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="files.html"><span>File List</span></a></li> |
|---|
| 83 | <li><a href="globals.html"><span>File Members</span></a></li> |
|---|
| 84 | </ul> |
|---|
| 85 | </div> |
|---|
| 86 | <h1>src/tspsolver.h</h1><a href="tspsolver_8h.html">Go to the documentation of this file.</a><div class="fragment"><pre class="fragment"><a name="l00001"></a>00001 |
|---|
| 87 | <a name="l00028"></a>00028 <span class="preprocessor">#ifndef TSPSOLVER_H</span> |
|---|
| 88 | <a name="l00029"></a>00029 <span class="preprocessor"></span><span class="preprocessor">#define TSPSOLVER_H</span> |
|---|
| 89 | <a name="l00030"></a>00030 <span class="preprocessor"></span> |
|---|
| 90 | <a name="l00031"></a>00031 <span class="preprocessor">#include "<a class="code" href="globals_8h.html" title="Contains TSPSG global defines.">globals.h</a>"</span> |
|---|
| 91 | <a name="l00032"></a>00032 |
|---|
| 92 | <a name="l00033"></a>00033 <span class="preprocessor">#include "<a class="code" href="tspmodel_8h.html" title="Defines CTSPModel class.">tspmodel.h</a>"</span> |
|---|
| 93 | <a name="l00034"></a>00034 |
|---|
| 94 | <a name="l00036"></a><a class="code" href="tspsolver_8h.html#a96b95c574161e5013286210c96c581ba">00036</a> <span class="keyword">typedef</span> QList<QList<double> > <a class="code" href="tspsolver_8h.html#a96b95c574161e5013286210c96c581ba" title="A matrix of city-to-city travel costs.">tMatrix</a>; |
|---|
| 95 | <a name="l00037"></a>00037 |
|---|
| 96 | <a name="l00043"></a>00043 |
|---|
| 97 | <a name="l00044"></a><a class="code" href="structs_step.html">00044</a> <span class="keyword">struct </span><a class="code" href="structs_step.html" title="This structure represents one step of solving.">sStep</a> { |
|---|
| 98 | <a name="l00045"></a><a class="code" href="structs_step.html#a0b16ffd0c21e19482d8080559a4ebea7">00045</a> <a class="code" href="tspsolver_8h.html#a96b95c574161e5013286210c96c581ba" title="A matrix of city-to-city travel costs.">tMatrix</a> <a class="code" href="structs_step.html#a0b16ffd0c21e19482d8080559a4ebea7" title="This step&#39;s matrix.">matrix</a>; |
|---|
| 99 | <a name="l00046"></a><a class="code" href="structs_step.html#addaeb82c9ddd12c50b753ad2988ceafc">00046</a> <span class="keywordtype">double</span> <a class="code" href="structs_step.html#addaeb82c9ddd12c50b753ad2988ceafc" title="The price of travel to this step.">price</a>; |
|---|
| 100 | <a name="l00047"></a>00047 <span class="keyword">struct </span>{ |
|---|
| 101 | <a name="l00048"></a><a class="code" href="structs_step.html#afa2175a8daa72a3b0cb510b4dd41b3e2">00048</a> <span class="keywordtype">int</span> <a class="code" href="structs_step.html#afa2175a8daa72a3b0cb510b4dd41b3e2" title="A zero-based row number of the candidate.">nRow</a>; |
|---|
| 102 | <a name="l00049"></a><a class="code" href="structs_step.html#a907c1872b0e7881130f0034145169fb1">00049</a> <span class="keywordtype">int</span> <a class="code" href="structs_step.html#a907c1872b0e7881130f0034145169fb1" title="A zero-based column number of the candidate.">nCol</a>; |
|---|
| 103 | <a name="l00050"></a>00050 } <a class="code" href="structs_step.html#a46e252aac4c84cc53d412c76f63fa6fd" title="A candiadate for branching in the current matrix.">candidate</a>; |
|---|
| 104 | <a name="l00051"></a><a class="code" href="structs_step.html#aabaeab5d890e4497a76c7a30a3f85cfa">00051</a> <span class="keywordtype">bool</span> <a class="code" href="structs_step.html#aabaeab5d890e4497a76c7a30a3f85cfa" title="Indicates whether or not matrix has alternative candidates.">alts</a>; |
|---|
| 105 | <a name="l00052"></a><a class="code" href="structs_step.html#a7a984255a80c651dff62ac9571079a53">00052</a> <a class="code" href="structs_step.html" title="This structure represents one step of solving.">sStep</a> *<a class="code" href="structs_step.html#a7a984255a80c651dff62ac9571079a53" title="Pointer to the left branch step.">plNode</a>; |
|---|
| 106 | <a name="l00053"></a><a class="code" href="structs_step.html#a9f14c4a0df25ba8b109c6732d4a68216">00053</a> <a class="code" href="structs_step.html" title="This structure represents one step of solving.">sStep</a> *<a class="code" href="structs_step.html#a9f14c4a0df25ba8b109c6732d4a68216" title="Pointer to the right branch step.">prNode</a>; |
|---|
| 107 | <a name="l00054"></a>00054 |
|---|
| 108 | <a name="l00056"></a><a class="code" href="structs_step.html#aa172f0fca5234cfa240121e6363e6951">00056</a> <a class="code" href="structs_step.html#aa172f0fca5234cfa240121e6363e6951" title="Assigns default values.">sStep</a>() { |
|---|
| 109 | <a name="l00057"></a>00057 <a class="code" href="structs_step.html#addaeb82c9ddd12c50b753ad2988ceafc" title="The price of travel to this step.">price</a> = <a class="code" href="structs_step.html#a46e252aac4c84cc53d412c76f63fa6fd" title="A candiadate for branching in the current matrix.">candidate</a>.nRow = <a class="code" href="structs_step.html#a46e252aac4c84cc53d412c76f63fa6fd" title="A candiadate for branching in the current matrix.">candidate</a>.nCol = -1; |
|---|
| 110 | <a name="l00058"></a>00058 <a class="code" href="structs_step.html#aabaeab5d890e4497a76c7a30a3f85cfa" title="Indicates whether or not matrix has alternative candidates.">alts</a> = <span class="keyword">false</span>; |
|---|
| 111 | <a name="l00059"></a>00059 <a class="code" href="structs_step.html#a7a984255a80c651dff62ac9571079a53" title="Pointer to the left branch step.">plNode</a> = <a class="code" href="structs_step.html#a9f14c4a0df25ba8b109c6732d4a68216" title="Pointer to the right branch step.">prNode</a> = NULL; |
|---|
| 112 | <a name="l00060"></a>00060 } |
|---|
| 113 | <a name="l00061"></a>00061 }; |
|---|
| 114 | <a name="l00062"></a>00062 |
|---|
| 115 | <a name="l00069"></a><a class="code" href="class_c_t_s_p_solver.html">00069</a> <span class="keyword">class </span><a class="code" href="class_c_t_s_p_solver.html" title="This class solves Travelling Salesman Problem task.">CTSPSolver</a> |
|---|
| 116 | <a name="l00070"></a>00070 { |
|---|
| 117 | <a name="l00071"></a>00071 Q_DECLARE_TR_FUNCTIONS(<a class="code" href="class_c_t_s_p_solver.html" title="This class solves Travelling Salesman Problem task.">CTSPSolver</a>) |
|---|
| 118 | <a name="l00072"></a>00072 |
|---|
| 119 | <a name="l00073"></a>00073 <span class="keyword">public</span>: |
|---|
| 120 | <a name="l00074"></a>00074 <a class="code" href="class_c_t_s_p_solver.html#aa5e45813d8f5e1c039b1bb9746d367bd" title="Class constructor.">CTSPSolver</a>(); |
|---|
| 121 | <a name="l00075"></a>00075 QString <a class="code" href="class_c_t_s_p_solver.html#a57556c971a25e3556c4aa3cc1fd2d3d0" title="Returns the sorted optimal path, starting from City 1.">getSortedPath</a>() <span class="keyword">const</span>; |
|---|
| 122 | <a name="l00076"></a>00076 <span class="keyword">static</span> QString <a class="code" href="class_c_t_s_p_solver.html#a677a878c4c8a06316a5d8d5a4fc8ab65" title="Returns CTSPSolver&#39;s version ID.">getVersionId</a>(); |
|---|
| 123 | <a name="l00077"></a>00077 <span class="keywordtype">bool</span> <a class="code" href="class_c_t_s_p_solver.html#a28d546e840cf53c639b45c0f26419f7a" title="Returns whether or not the solution is definitely optimal.">isOptimal</a>() <span class="keyword">const</span>; |
|---|
| 124 | <a name="l00078"></a>00078 <a class="code" href="structs_step.html" title="This structure represents one step of solving.">sStep</a> *<a class="code" href="class_c_t_s_p_solver.html#a9dab2bba56c384663fb21f5e4d1f2743" title="Solves the given task.">solve</a>(<span class="keywordtype">int</span>, <a class="code" href="tspsolver_8h.html#a96b95c574161e5013286210c96c581ba" title="A matrix of city-to-city travel costs.">tMatrix</a>, QWidget *parent = 0); |
|---|
| 125 | <a name="l00079"></a>00079 |
|---|
| 126 | <a name="l00080"></a>00080 <span class="keyword">private</span>: |
|---|
| 127 | <a name="l00081"></a>00081 <span class="keywordtype">bool</span> mayNotBeOptimal; |
|---|
| 128 | <a name="l00082"></a>00082 <span class="keywordtype">int</span> nCities; |
|---|
| 129 | <a name="l00083"></a>00083 <a class="code" href="structs_step.html" title="This structure represents one step of solving.">sStep</a> *root; |
|---|
| 130 | <a name="l00084"></a>00084 QHash<int,int> route; |
|---|
| 131 | <a name="l00085"></a>00085 <span class="comment">// QHash<int,int> forbidden;</span> |
|---|
| 132 | <a name="l00086"></a>00086 |
|---|
| 133 | <a name="l00087"></a>00087 <span class="keywordtype">double</span> align(<a class="code" href="tspsolver_8h.html#a96b95c574161e5013286210c96c581ba" title="A matrix of city-to-city travel costs.">tMatrix</a> &); |
|---|
| 134 | <a name="l00088"></a>00088 <span class="keywordtype">void</span> cleanup(); |
|---|
| 135 | <a name="l00089"></a>00089 <span class="keywordtype">bool</span> findCandidate(<a class="code" href="tspsolver_8h.html#a96b95c574161e5013286210c96c581ba" title="A matrix of city-to-city travel costs.">tMatrix</a>, <span class="keywordtype">int</span> &, <span class="keywordtype">int</span> &); |
|---|
| 136 | <a name="l00090"></a>00090 <span class="keywordtype">double</span> findMinInCol(<span class="keywordtype">int</span>, <a class="code" href="tspsolver_8h.html#a96b95c574161e5013286210c96c581ba" title="A matrix of city-to-city travel costs.">tMatrix</a>, <span class="keywordtype">int</span> exr = -1); |
|---|
| 137 | <a name="l00091"></a>00091 <span class="keywordtype">double</span> findMinInRow(<span class="keywordtype">int</span>, <a class="code" href="tspsolver_8h.html#a96b95c574161e5013286210c96c581ba" title="A matrix of city-to-city travel costs.">tMatrix</a>, <span class="keywordtype">int</span> exc = -1); |
|---|
| 138 | <a name="l00092"></a>00092 <span class="keywordtype">bool</span> hasSubCycles(<span class="keywordtype">int</span>, <span class="keywordtype">int</span>); |
|---|
| 139 | <a name="l00093"></a>00093 <span class="keywordtype">void</span> subCol(<a class="code" href="tspsolver_8h.html#a96b95c574161e5013286210c96c581ba" title="A matrix of city-to-city travel costs.">tMatrix</a> &, <span class="keywordtype">int</span>, <span class="keywordtype">double</span>); |
|---|
| 140 | <a name="l00094"></a>00094 <span class="keywordtype">void</span> subRow(<a class="code" href="tspsolver_8h.html#a96b95c574161e5013286210c96c581ba" title="A matrix of city-to-city travel costs.">tMatrix</a> &, <span class="keywordtype">int</span>, <span class="keywordtype">double</span>); |
|---|
| 141 | <a name="l00095"></a>00095 }; |
|---|
| 142 | <a name="l00096"></a>00096 |
|---|
| 143 | <a name="l00097"></a>00097 <span class="preprocessor">#endif // TSPSOLVER_H</span> |
|---|
| 144 | </pre></div></div> |
|---|
| 145 | <!--- window showing the filter options --> |
|---|
| 146 | <div id="MSearchSelectWindow" |
|---|
| 147 | onmouseover="return searchBox.OnSearchSelectShow()" |
|---|
| 148 | onmouseout="return searchBox.OnSearchSelectHide()" |
|---|
| 149 | onkeydown="return searchBox.OnSearchSelectKey(event)"> |
|---|
| 150 | <a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(0)"><span class="SelectionMark"> </span>All</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(1)"><span class="SelectionMark"> </span>Classes</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(2)"><span class="SelectionMark"> </span>Files</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(3)"><span class="SelectionMark"> </span>Functions</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(4)"><span class="SelectionMark"> </span>Variables</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(5)"><span class="SelectionMark"> </span>Typedefs</a><a class="SelectItem" href="javascript:void(0)" onclick="searchBox.OnSelectItem(6)"><span class="SelectionMark"> </span>Defines</a></div> |
|---|
| 151 | |
|---|
| 152 | <!-- iframe showing the search results (closed by default) --> |
|---|
| 153 | <div id="MSearchResultsWindow"> |
|---|
| 154 | <iframe src="" frameborder="0" |
|---|
| 155 | name="MSearchResults" id="MSearchResults"> |
|---|
| 156 | </iframe> |
|---|
| 157 | </div> |
|---|
| 158 | |
|---|
| 159 | <hr size="1"/><address style="text-align: right;"><small>Generated on Sat Oct 24 16:33:19 2009 for TSPSG: TSP Solver and Generator by |
|---|
| 160 | <a href="http://www.doxygen.org/index.html"> |
|---|
| 161 | <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.6.1 </small></address> |
|---|
| 162 | </body> |
|---|
| 163 | </html> |
|---|
