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
034import java.io.FileOutputStream;
035import java.io.PrintStream;
036import java.util.ArrayList;
037import java.util.Collection;
038import java.util.Locale;
039
040import org.graphstream.ui.geom.Vector3;
041import org.miv.pherd.Particle;
042
043/**
044 * Base implementation of a node particle to be used in the {@link BarnesHutLayout}
045 * to represent nodes and choose their positions.
046 * 
047 * <p>
048 * Several abstract methods have to be overrided to provide a computation of the
049 * layout (all the attraction/repulsion computation is done in this class):  
050 * <ul>
051 *              <li>{@link #attraction(Vector3)}</li>
052 *              <li>{@link #repulsionN2(Vector3)}</li>
053 *              <li>{@link #repulsionNLogN(Vector3)}</li>
054 * </ul>
055 * </p>
056 */
057public abstract class NodeParticle extends Particle {
058        /**
059         * Set of edge connected to this node.
060         */
061        public ArrayList<EdgeSpring> neighbours = new ArrayList<EdgeSpring>();
062
063        /**
064         * Should the node move?.
065         */
066        public boolean frozen = false;
067
068        /**
069         * Displacement vector.
070         */
071        public Vector3 disp;
072
073        /**
074         * Last computed displacement vector length.
075         */
076        public double len;
077
078        /**
079         * Attraction energy for this node only.
080         */
081        public double attE;
082
083        /**
084         * Repulsion energy for this node only.
085         */
086        public double repE;
087
088        /**
089         * If non null, all this node statistics will be output to this stream.
090         */
091        public PrintStream out;
092
093        /**
094         * The box.
095         */
096        protected BarnesHutLayout box;
097
098        // Constructors
099
100        /**
101         * New node.
102         * 
103         * The node is placed at random in the space of the simulation.
104         * 
105         * @param box
106         *            The spring box.
107         * @param id
108         *            The node identifier.
109         */
110        public NodeParticle(BarnesHutLayout box, String id) {
111//              this(box, id, box.getCenterPoint().x, box.getCenterPoint().y, box.is3D() ? box.getCenterPoint().z : 0);
112                this(box, id,  box.randomXInsideBounds(), box.randomYInsideBounds(), box.is3D ? box.randomZInsideBounds() : 0); 
113//              this(box, id, (box.random.nextDouble() * 2) - 1, (box.random
114//                              .nextDouble() * 2) - 1,
115//                              box.is3D ? (box.random.nextDouble() * 2) - 1 : 0);
116
117                this.box = box;
118        }
119
120        /**
121         * New node at a given position.
122         * 
123         * @param box
124         *            The spring box.
125         * @param id
126         *            The node identifier.
127         * @param x
128         *            The abscissa.
129         * @param y
130         *            The ordinate.
131         * @param z
132         *            The depth.
133         */
134        public NodeParticle(BarnesHutLayout box, String id, double x, double y,
135                        double z) {
136                super(id, x, y, box.is3D ? z : 0);
137                this.box = box;
138                disp = new Vector3();
139                createDebug();
140        }
141
142        /**
143         * Create a file for statistics about this node.
144         */
145        protected void createDebug() {
146                if (box.outputNodeStats) {
147                        try {
148                                out = new PrintStream(new FileOutputStream("out" + getId()
149                                                + ".data"));
150                        } catch (Exception e) {
151                                e.printStackTrace();
152                                System.exit(1);
153                        }
154                }
155        }
156
157        /**
158         * All the edges connected to this node.
159         * 
160         * @return A set of edges.
161         */
162        public Collection<EdgeSpring> getEdges() {
163                return neighbours;
164        }
165
166        @Override
167        public void move(int time) {
168                if (!frozen) {
169                        disp.fill(0);
170
171                        Vector3 delta = new Vector3();
172
173                        repE = 0;
174                        attE = 0;
175
176                        if (box.viewZone < 0)
177                                repulsionN2(delta);
178                        else
179                                repulsionNLogN(delta);
180
181                        attraction(delta);
182                        
183                        if(box.gravity != 0)
184                                gravity(delta);
185
186                        disp.scalarMult(box.force);
187
188                        len = disp.length();
189
190                        if (len > (box.area / 2)) {
191                                disp.scalarMult((box.area / 2) / len);
192                                len = box.area / 2;
193                        }
194
195                        box.avgLength += len;
196
197                        if (len > box.maxMoveLength)
198                                box.maxMoveLength = len;
199                }
200        }
201
202        @Override
203        public void nextStep(int time) {
204                if (!frozen) {
205                        nextPos.x = pos.x + disp.data[0];
206                        nextPos.y = pos.y + disp.data[1];
207
208                        if (box.is3D)
209                                nextPos.z = pos.z + disp.data[2];
210
211                        box.nodeMoveCount++;
212                        moved = true;
213                } else {
214                        nextPos.x = pos.x;
215                        nextPos.y = pos.y;
216                        if (box.is3D)
217                                nextPos.z = pos.z;
218                }
219
220                if (out != null) {
221                        out.printf(Locale.US, "%s %f %f %f%n", getId(), len, attE, repE);
222                        out.flush();
223                }
224
225                super.nextStep(time);
226        }
227
228        /**
229         * Force a node to move from a given vector.
230         * 
231         * @param dx
232         *            The x component.
233         * @param dy
234         *            The y component.
235         * @param dz
236         *            The z component.
237         */
238        public void moveOf(double dx, double dy, double dz) {
239                pos.set(pos.x + dx, pos.y + dy, pos.z + dz);
240        }
241
242        /**
243         * Force a node to move at a given position.
244         * 
245         * @param x
246         *            The new x.
247         * @param y
248         *            The new y.
249         * @param z
250         *            The new z.
251         */
252        public void moveTo(double x, double y, double z) {
253                pos.set(x, y, z);
254                moved = true;
255        }
256
257        /**
258         * Compute the repulsion for each other node. This is the most precise way,
259         * but the algorithm is a time hog : complexity is O(n^2).
260         * 
261         * @param delta
262         *            The computed displacement vector.
263         */
264        protected abstract void repulsionN2(Vector3 delta);
265
266        /**
267         * Compute the repulsion for each node in the viewing distance, and use the
268         * n-tree to find them. For a certain distance the node repulsion is
269         * computed one by one. At a larger distance the repulsion is computed using
270         * nodes barycenters.
271         * 
272         * @param delta
273         *            The computed displacement vector.
274         */
275        protected abstract void repulsionNLogN(Vector3 delta);
276
277        /**
278         * Compute the global attraction toward each connected node.
279         * @param delta
280         *                      The computed displacement vector.
281         */
282        protected abstract void attraction(Vector3 delta);
283
284        /**
285         * Compute the global attraction toward the layout center (if enabled).
286         * @param delta
287         *                      The computed displacement vector.
288         * @see BarnesHutLayout#useGravity
289         */
290        protected abstract void gravity(Vector3 delta);
291        
292        /**
293         * The given edge is connected to this node.
294         * 
295         * @param e
296         *            The edge to connect.
297         */
298        public void registerEdge(EdgeSpring e) {
299                neighbours.add(e);
300        }
301
302        /**
303         * The given edge is no more connected to this node.
304         * 
305         * @param e
306         *            THe edge to disconnect.
307         */
308        public void unregisterEdge(EdgeSpring e) {
309                int i = neighbours.indexOf(e);
310
311                if (i >= 0) {
312                        neighbours.remove(i);
313                }
314        }
315
316        /**
317         * Remove all edges connected to this node.
318         */
319        public void removeNeighborEdges() {
320                ArrayList<EdgeSpring> edges = new ArrayList<EdgeSpring>(neighbours);
321
322                for (EdgeSpring edge : edges)
323                        box.removeEdge(box.getLayoutAlgorithmName(), edge.id);
324
325                neighbours.clear();
326        }
327
328        @Override
329        public void inserted() {
330        }
331
332        @Override
333        public void removed() {
334        }
335}