001/*
002 * Copyright 2006 - 2013
003 *     Stefan Balev     <stefan.balev@graphstream-project.org>
004 *     Julien Baudry    <julien.baudry@graphstream-project.org>
005 *     Antoine Dutot    <antoine.dutot@graphstream-project.org>
006 *     Yoann Pigné      <yoann.pigne@graphstream-project.org>
007 *     Guilhelm Savin   <guilhelm.savin@graphstream-project.org>
008 * 
009 * This file is part of GraphStream <http://graphstream-project.org>.
010 * 
011 * GraphStream is a library whose purpose is to handle static or dynamic
012 * graph, create them from scratch, file or any source and display them.
013 * 
014 * This program is free software distributed under the terms of two licenses, the
015 * CeCILL-C license that fits European law, and the GNU Lesser General Public
016 * License. You can  use, modify and/ or redistribute the software under the terms
017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by
019 * the Free Software Foundation, either version 3 of the License, or (at your
020 * option) any later version.
021 * 
022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY
023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
024 * PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more details.
025 * 
026 * You should have received a copy of the GNU Lesser General Public License
027 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
028 * 
029 * The fact that you are presently reading this means that you have had
030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms.
031 */
032package org.graphstream.ui.layout.springbox;
033
034/**
035 * Represent the history of energy values for a force-based layout algorithm.
036 * 
037 * <p>
038 * The main intended usage is with the various force layout algorithms that use a
039 * an "energy" minimization process to compute a layout. This class allows to store
040 * the energy at a current step of layout computation and to remember a history of
041 * such steps.
042 * </p>
043 * 
044 * <p>
045 * At a current step of layout computation, one can accumulate energy in the current
046 * cell of the energies buffer using {@link #accumulateEnergy(double)}. When the step
047 * finishes, one calls {@link #storeEnergy()} to store this accumulated energy in 
048 * a cell of the memory, push a new cell on the memory and therefore start a new step.
049 * </p>
050 * 
051 * <p>
052 * At any time you can get the last energy value computed with {@link #getEnergy()}.
053 * Be careful this is not the energy currently accumulated but the value of the last
054 * energy stored with {@link #storeEnergy()}. You can also get at any time the average
055 * energy in the memory with {@link #getAverageEnergy()}, as well as an estimate of
056 * the stabilization (how much the energies are varying) using {@link #getStabilization()}.
057 * </p>
058 */
059public class Energies {
060        /**
061         * Global current energy (maybe actually updated). This is where users of this
062         * class add energy for their current computation step. When finished this
063         * energy value is stored in the energy buffer and cleared.
064         */
065        protected double energy;
066
067        /**
068         * The last computed energy.
069         */
070        protected double lastEnergy;
071
072        /**
073         * Memory. The number of energy values remembered.
074         */
075        protected int energiesBuffer = 256;
076
077        /**
078         * A circular array of the last values of energy.
079         */
080        protected double[] energies = new double[energiesBuffer];
081
082        /**
083         * The current position in the energies array.
084         */
085        protected int energiesPos = 0;
086        
087        /**
088         * The sum of all memorized energies.
089         */
090        protected double energySum = 0;
091
092        /**
093         * The last computed energy value.
094         * 
095         * @return The actual level of energy.
096         */
097        public double getEnergy() {
098                return lastEnergy;
099        }
100
101        /**
102         * The number of energy values remembered, the memory.
103         */
104        public int getBufferSize() {
105                return energiesBuffer;
106        }
107
108        /**
109         * A number in [0..1] with 1 meaning fully stabilized.
110         * 
111         * @return A value that indicates the level of stabilization in [0-1].
112         */
113        public double getStabilization() {
114                // The stability is attained when the global energy of the graph do not
115                // vary anymore.
116
117                int    range  = 200;
118                double eprev1 = getPreviousEnergyValue(range);
119                double eprev2 = getPreviousEnergyValue(range-10);
120                double eprev3 = getPreviousEnergyValue(range-20);
121                double eprev  = (eprev1+eprev2+eprev3)/3.0;
122                double diff   = Math.abs(lastEnergy - eprev);
123
124                diff = diff < 1 ? 1 : diff;
125                
126                return 1.0/diff;
127        }
128        
129        /**
130         * The average energy in the whole buffer.
131         * @return The average energy.
132         */
133        public double getAverageEnergy() {
134                return energySum / energies.length;
135        }
136
137        /**
138         * A previous energy value.
139         * 
140         * @param stepsBack
141         *            The number of steps back in history. This number must not be larger than
142         *            the size of the memory (energy buffer) else it is set to this size.
143         * @return The energy value at stepsBack in time.
144         */
145        public double getPreviousEnergyValue(int stepsBack) {
146                if (stepsBack >= energies.length)
147                        stepsBack = energies.length - 1;
148
149                int pos = (energies.length + (energiesPos - stepsBack))
150                                % energies.length;
151
152                return energies[pos];
153        }
154
155        /**
156         * Accumulate some energy in the current energy cell.
157         * 
158         * @param value
159         *            The value to accumulate to the current cell.
160         */
161        public void accumulateEnergy(double value) {
162                energy += value;
163        }
164
165        /**
166         * Add a the current accumulated energy value in the set.
167         */
168        public void storeEnergy() {
169                energiesPos = (energiesPos + 1) % energies.length;
170
171                energySum -= energies[energiesPos];
172                energies[energiesPos] = energy;
173                energySum += energy;
174                lastEnergy = energy;
175                energy = 0;
176        }
177
178        /**
179         * Randomize the energies array.
180         */
181        protected void clearEnergies() {
182                for (int i = 0; i < energies.length; ++i)
183                        energies[i] = ((Math.random() * 2000) - 1000);
184        }
185}