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}