1 /*
2 * Copyright (c) 2003, the JUNG Project and the Regents of the University
3 * of California
4 * All rights reserved.
5 *
6 * This software is open-source under the BSD license; see either
7 * "license.txt" or
8 * http://jung.sourceforge.net/license.txt for a description.
9 */
10 package edu.uci.ics.jung.algorithms.util;
11
12
13
14 /**
15 * Provides basic infrastructure for iterative algorithms. Services provided include:
16 * <ul>
17 * <li> storage of current and max iteration count </li>
18 * <li> framework for initialization, iterative evaluation, and finalization </li>
19 * <li> test for convergence </li>
20 * <li> etc. </li>
21 * </ul>
22 * <p>
23 * Algorithms that subclass this class are typically used in the following way: <br>
24 * <pre>
25 * FooAlgorithm foo = new FooAlgorithm(...)
26 * foo.setMaximumIterations(100); //set up conditions
27 * ...
28 * foo.evaluate(); //key method which initiates iterative process
29 * foo.getSomeResult();
30 * </pre>
31 *
32 * @author Scott White (originally written by Didier Besset)
33 */
34 public abstract class IterativeProcess implements IterativeContext {
35 /**
36 * Number of iterations performed.
37 */
38 private int iterations;
39 /**
40 * Maximum allowed number of iterations.
41 */
42 private int maximumIterations = 50;
43 /**
44 * Desired precision.
45 */
46 private double desiredPrecision = Double.MIN_VALUE;
47 /**
48 * Achieved precision.
49 */
50 private double precision;
51
52
53 /**
54 * Generic constructor.
55 */
56 public IterativeProcess() {
57 }
58
59 /**
60 * Performs the iterative process.
61 * Note: this method does not return anything because Java does not
62 * allow mixing double, int, or objects
63 */
64 public void evaluate() {
65 iterations = 0;
66 initializeIterations();
67 while (iterations++ < maximumIterations) {
68 step();
69 precision = getPrecision();
70 if (hasConverged())
71 break;
72 }
73 finalizeIterations();
74 }
75
76 /**
77 * Evaluate the result of the current iteration.
78 */
79 abstract public void step();
80
81 /**
82 * Perform eventual clean-up operations
83 * (must be implement by subclass when needed).
84 */
85 protected void finalizeIterations() {
86 }
87
88 /**
89 * Returns the desired precision.
90 */
91 public double getDesiredPrecision() {
92 return desiredPrecision;
93 }
94
95 /**
96 * Returns the number of iterations performed.
97 */
98 public int getIterations() {
99 return iterations;
100 }
101
102 /**
103 * Returns the maximum allowed number of iterations.
104 */
105 public int getMaximumIterations() {
106 return maximumIterations;
107 }
108
109 /**
110 * Returns the attained precision.
111 */
112 public double getPrecision() {
113 return precision;
114 }
115
116 /**
117 * @param precision the precision to set
118 */
119 public void setPrecision(double precision) {
120 this.precision = precision;
121 }
122
123 /**
124 *
125 * Check to see if the result has been attained.
126 * @return boolean
127 */
128 public boolean hasConverged() {
129 return precision < desiredPrecision;
130 }
131
132 public boolean done() {
133 return hasConverged();
134 }
135
136 /**
137 * Initializes internal parameters to start the iterative process.
138 */
139 protected void initializeIterations() {
140 }
141
142 /**
143 *
144 */
145 public void reset() {
146 }
147
148 /**
149 * @return double
150 * @param epsilon double
151 * @param x double
152 */
153 public double relativePrecision(double epsilon, double x) {
154 return x > desiredPrecision ? epsilon / x: epsilon;
155 }
156
157 /**
158 * Defines the desired precision.
159 */
160 public void setDesiredPrecision(double prec) throws IllegalArgumentException {
161 if (prec <= 0)
162 throw new IllegalArgumentException("Non-positive precision: " + prec);
163 desiredPrecision = prec;
164 }
165
166 /**
167 * Defines the maximum allowed number of iterations.
168 */
169 public void setMaximumIterations(int maxIter) throws IllegalArgumentException {
170 if (maxIter < 1)
171 throw new IllegalArgumentException("Non-positive maximum iteration: " + maxIter);
172 maximumIterations = maxIter;
173 }
174 }