001
002 package algo;
003
004 import java.io.Serializable;
005
006 /**
007 * A Path in a graph implementd as arrays of bytes.
008 * @author Heinz Kredel.
009 */
010 public final class PathByteArray implements Path, Serializable {
011
012 public final Graph graph;
013 public final byte[] used; // points in the path
014 public final byte[] unused; // points not in the path
015 public final double cost;
016 public final int maxsize;
017 public final int length;
018
019
020 /**
021 * @param g the graph.
022 * @param u used points.
023 * @param uu unused points.
024 * @param c cost of this path.
025 */
026 public PathByteArray(Graph g, byte[] u, byte[] uu, double c) {
027 this(g, u, u.length, uu, c);
028 }
029
030
031 /**
032 * @param g the graph.
033 * @param u used points.
034 * @param pos position of last used point in path, e.g. length.
035 * @param uu unused points.
036 * @param c cost of this path.
037 */
038 public PathByteArray(Graph g, byte[] u, int pos, byte[] uu, double c) {
039 graph = g;
040 used = u;
041 unused = uu;
042 cost = c;
043 length = pos;
044 maxsize = graph.size();
045 }
046
047
048 /** Clone / copy this path.
049 * @see java.lang.Object#clone()
050 */
051 public Object clone() {
052 byte[] u = new byte[ length ];
053 System.arraycopy( used, 0, u, 0, length );
054 return new PathByteArray( graph, u, length, unused, cost );
055 }
056
057
058 /**
059 * @return cost of this path.
060 */
061 public double cost() {
062 return cost;
063 }
064
065
066 /**
067 * @return length of this path.
068 */
069 public int length() {
070 return length;
071 }
072
073
074 /**
075 * @return maxsize of this path.
076 */
077 public int maxsize() {
078 return maxsize;
079 }
080
081
082 /**
083 * Empty path, all n points unused.
084 * @param g the graph.
085 * @return a new empty path.
086 */
087 public static PathByteArray emptyPath(Graph g) {
088 byte[] u = new byte[ 0 ];
089 byte[] uu = new byte[ g.size() ];
090 for (byte i = 0; i < g.size(); i++ ){
091 uu[i] = i;
092 }
093 return new PathByteArray(g, u, uu, Double.POSITIVE_INFINITY);
094 }
095
096
097 /**
098 * One path. One point used and other n-1 points unused.
099 * @param g the graph.
100 * @return a new path of one point.
101 */
102 public static PathByteArray onePath(Graph g) {
103 byte[] u = new byte[ 1 ];
104 u[0] = (byte)0;
105 byte[] uu = new byte[ g.size()-1 ];
106 for (byte i = 0; i < g.size()-1; i++ ){
107 uu[i] = (byte)(i+1);
108 }
109 return new PathByteArray(g, u, uu, Double.POSITIVE_INFINITY);
110 }
111
112
113 /**
114 * Standard path from point 0 to point n-1 to 0.
115 * @param g the graph.
116 * @return a new closed path.
117 */
118 public static PathByteArray standardPath(Graph g) {
119 byte[] u = new byte[ g.size() ];
120 byte[] uu = new byte[0];
121 double c = 0.0;
122 u[0] = (byte)0;
123 for (byte i = 1; i < g.size(); i++ ){
124 u[i] = i;
125 c += cost( g.distance(i-1,i) );
126 }
127 // u[ g.size() ] = (byte)0;
128 c += cost( g.distance(g.size()-1,0) ); //for circle
129 PathByteArray p = new PathByteArray(g, u, uu, c);
130 System.out.println("initial = " + p);
131 return p;
132 }
133
134
135 /**
136 * Clone / copy this path, but allocate full length used array.
137 * @return a copy of this with maximal used array.
138 */
139 public Path copyMax() {
140 byte[] u = new byte[ maxsize ];
141 System.arraycopy( used, 0, u, 0, length );
142 return new PathByteArray( graph, u, length, unused, cost );
143 }
144
145
146 /**
147 * Get next possible path reusing used array.
148 * New path shares used array, so do not use in threads.
149 * @param pos position of last valid point in used array.
150 * @return next path.
151 */
152 public Path nextPath(int pos) {
153 //System.out.print("pos = " + pos + " this = " + this);
154 byte[] uu = new byte[ unused.length-1 ];
155 byte m = 0;
156 byte j = -1;
157 for ( byte k = 0; k < unused.length; k++ ) {
158 if ( k == pos ) {
159 j = unused[k];
160 } else {
161 uu[ m ] = unused[k];
162 m++;
163 }
164 }
165 // j != -1
166 used[ length ] = j;
167 // compute new cost
168 double c = 0.0;
169 if ( cost < Double.POSITIVE_INFINITY ) {
170 c = cost;
171 }
172 if ( length > 0 ) {
173 int n1 = used[ length-1 ];
174 c += cost( graph.distance(n1,j) );
175 }
176 // add circle cost
177 if ( length+1 == maxsize ) {
178 //System.out.print("#");
179 int n0 = used[ 0 ];
180 c += cost( graph.distance(j,n0) );
181 }
182 // new path shares used array, so do not use in threads
183 return new PathByteArray( graph, used, length+1, uu, c );
184 }
185
186
187 /**
188 * Get array of next possible paths.
189 * @return all possible path starting with this.
190 */
191 public Path[] nextPaths() {
192 PathByteArray[] pr = new PathByteArray[ unused.length ];
193 for ( byte i = 0; i < unused.length; i++ ) {
194 byte[] uu = new byte[ unused.length-1 ];
195 byte m = 0;
196 byte j = -1;
197 for ( byte k = 0; k < unused.length; k++ ) {
198 if ( k == i ) {
199 j = unused[k];
200 } else {
201 uu[ m ] = unused[k]; m++;
202 }
203 }
204 // j != -1
205 byte[] u = new byte[ used.length+1 ];
206 System.arraycopy( used, 0, u, 0, used.length );
207 u[ used.length ] = j;
208 // compute new cost
209 double c = 0.0;
210 if ( cost < Double.POSITIVE_INFINITY ) {
211 c = cost;
212 }
213 if ( length > 0 ) {
214 int l = used[ length-1 ];
215 int k = j;
216 c += cost( graph.distance(l,k) );
217 }
218 // add circle cost
219 if ( length+1 == maxsize ) {
220 //System.out.print("#");
221 int n = used[ 0 ];
222 int k = j;
223 c += cost( graph.distance(k,n) );
224 }
225 pr[i] = new PathByteArray( graph, u, uu, c );
226 }
227 return pr;
228 }
229
230
231 /* (non-Javadoc)
232 * @see java.lang.Object#toString()
233 */
234 public String toString() {
235 StringBuffer s = new StringBuffer();
236 s.append("[ ");
237 for ( int i = 0; i < length; i++ ) {
238 s.append( used[i] );
239 if ( i+1 < length ) {
240 s.append(",");
241 }
242 }
243 s.append(" | cost="+cost);
244 if ( unused.length > 0 ) {
245 s.append(" | ");
246 for ( int i = 0; i < unused.length; i++ ) {
247 s.append( unused[i] );
248 if ( i+1 < unused.length ) {
249 s.append(",");
250 }
251 }
252 }
253 s.append(" ]");
254 return s.toString();
255 }
256
257
258 /**
259 * Dummy function.
260 * Used to increase computing load or to define different traveling costs.
261 * @param c actual cost.
262 * @return new cost (most likely equal to c).
263 */
264 protected static double cost(double c) {
265 if ( c >= 0.0 ) {
266 return c;
267 }
268 double r = Math.log( c );
269 for (int i = 0; i < 100; i++ ) {
270 r *= c;
271 }
272 r = r/2.0;
273 for (int i = 0; i < 100; i++ ) {
274 r /= c;
275 }
276 r = r/2.0;
277 return Math.exp( r );
278 }
279
280 }