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.algorithm.generator;
033
034import java.util.ArrayList;
035import java.util.Random;
036
037import org.graphstream.graph.Graph;
038import org.graphstream.graph.implementations.AdjacencyListGraph;
039import org.graphstream.stream.SourceBase;
040
041/**
042 * Base graph generator.
043 * 
044 * <p>
045 * This class is a base to implement generators. It it has facilities to
046 * generate edges or nodes, and provides services to add attributes on them and
047 * to choose if the edge is directed or not.
048 * </p>
049 * 
050 * <p>
051 * Indeed, This generator has the ability to add randomly chosen numerical
052 * values on arbitrary attributes on edges or nodes of the graph, and to
053 * randomly choose a direction for edges.
054 * </p>
055 * 
056 * <p>
057 * A list of attributes can be given for nodes and edges. In this case each new
058 * node or edge added will have this attribute and the value will be a randomly
059 * chosen number. The range in which these numbers are chosen can be specified.
060 * </p>
061 * 
062 * <p>
063 * By default, edges are not oriented. It is possible to ask orientation, and in
064 * addition to ask that the direction be chosen randomly (by default, if edges
065 * must be oriented, the order given for the two nodes to connect is used).
066 * </p>
067 * 
068 * @since 2007
069 */
070public abstract class BaseGenerator extends SourceBase implements Generator {
071
072        // Attributes
073
074        /**
075         * Are edges directed ?
076         */
077        protected boolean directed = false;
078
079        /**
080         * If directed, choose the direction randomly?.
081         */
082        protected boolean randomlyDirected = false;
083
084        /**
085         * List of attributes to put on nodes with a randomly chosen numerical
086         * value.
087         */
088        protected ArrayList<String> nodeAttributes = new ArrayList<String>();
089
090        /**
091         * List of attributes to put on edges with a randomly chosen numerical
092         * value.
093         */
094        protected ArrayList<String> edgeAttributes = new ArrayList<String>();
095
096        /**
097         * If node attributes are added, in which range are the numbers chosen ?.
098         */
099        protected double[] nodeAttributeRange = new double[2];
100
101        /**
102         * If edge attributes are added, in which range are the numbers chosen ?.
103         */
104        protected double[] edgeAttributeRange = new double[2];
105
106        /**
107         * The random number generator.
108         */
109        protected Random random = new Random();
110
111        /**
112         * Set the node label attribute using the identifier?.
113         */
114        protected boolean addNodeLabels = false;
115
116        /**
117         * Set the edge label attribute using the identifier?.
118         */
119        protected boolean addEdgeLabels = false;
120
121        /**
122         * Flag to know if generator has to use an internal graph. Generator which
123         * want to use this feature have to use the
124         * {@link #setUseInternalGraph(boolean)} method to set this flag.
125         */
126        private boolean useInternalGraph;
127
128        /**
129         * When {@link #useInternalGraph} is on, nodes and edges are stored in this
130         * graph.
131         */
132        protected Graph internalGraph;
133
134        /**
135         * Used to created unique generatorId.
136         */
137        private volatile static int generatorId;
138
139        // Constructors
140
141        /**
142         * New base graph generator. By default no attributes are added to nodes and
143         * edges, and edges are not directed.
144         */
145        public BaseGenerator() {
146                this(false, false);
147        }
148
149        /**
150         * New base graph generator. By default no attributes are added to nodes and
151         * edges. It is possible to make edge randomly directed.
152         * 
153         * @param directed
154         *            If true the edges are directed.
155         * @param randomlyDirectedEdges
156         *            If true edge, are directed and the direction is chosen
157         *            randomly.
158         */
159        public BaseGenerator(boolean directed, boolean randomlyDirectedEdges) {
160                super(String.format("generator-%08x", generatorId++));
161                setDirectedEdges(directed, randomlyDirectedEdges);
162
163                nodeAttributeRange[0] = 0;
164                nodeAttributeRange[1] = 1;
165                edgeAttributeRange[0] = 0;
166                edgeAttributeRange[1] = 1;
167        }
168
169        /**
170         * New base graph generator.
171         * 
172         * @param directed
173         *            If true the edges are directed.
174         * @param randomlyDirectedEdges
175         *            It true, edges are directed and the direction is choosed
176         *            randomly.
177         * @param nodeAttribute
178         *            put an attribute by that name on each node with a random
179         *            numeric value.
180         * @param edgeAttribute
181         *            put an attribute by that name on each edge with a random
182         *            numeric value.
183         */
184        public BaseGenerator(boolean directed, boolean randomlyDirectedEdges,
185                        String nodeAttribute, String edgeAttribute) {
186                this(directed, randomlyDirectedEdges);
187
188                addNodeAttribute(nodeAttribute);
189                addEdgeAttribute(edgeAttribute);
190        }
191
192        // Commands
193
194        /**
195         * End the graph generation by finalizing it. Once the {@link #nextEvents()}
196         * method returned false (or even if you stop before), this method must be
197         * called to finish the graph.
198         * 
199         * In addition, BaseGenerator adds a "clear" operations that removes all the
200         * kept edges and nodes identifiers and the associated data.
201         */
202        public void end() {
203                clearKeptData();
204        }
205
206        /**
207         * Set the random seed used for random number generation.
208         * 
209         * @param seed
210         *            The seed.
211         */
212        public void setRandomSeed(long seed) {
213                random.setSeed(seed);
214        }
215
216        /**
217         * Allow to add label attributes on nodes. The label is the identifier of
218         * the node.
219         * 
220         * @param on
221         *            If true labels are added.
222         */
223        public void addNodeLabels(boolean on) {
224                addNodeLabels = on;
225        }
226
227        /**
228         * Allow to add label attributes on edges. The label is the identifier of
229         * the edge.
230         * 
231         * @param on
232         *            If true labels are added.
233         */
234        public void addEdgeLabels(boolean on) {
235                addEdgeLabels = on;
236        }
237
238        /**
239         * Make each generated edge directed or not. If the new edge created are
240         * directed, the direction is chosen randomly.
241         * 
242         * @param directed
243         *            It true, edge will be directed.
244         * @param randomly
245         *            If true, not only edges are directed, but the direction is
246         *            chosen randomly.
247         */
248        public void setDirectedEdges(boolean directed, boolean randomly) {
249                this.directed = directed;
250
251                if (directed && randomly)
252                        randomlyDirected = randomly;
253        }
254
255        /**
256         * Add this attribute on all nodes generated. This attribute will have a
257         * numerical value chosen in a range that is by default [0-1].
258         * 
259         * @param name
260         *            The attribute name.
261         * @see #setNodeAttributesRange(double, double)
262         * @see #removeNodeAttribute(String)
263         */
264        public void addNodeAttribute(String name) {
265                nodeAttributes.add(name);
266        }
267
268        /**
269         * Remove an automatic attribute for nodes.
270         * 
271         * @param name
272         *            The attribute name.
273         * @see #addNodeAttribute(String)
274         */
275        public void removeNodeAttribute(String name) {
276                int pos = nodeAttributes.indexOf(name);
277
278                if (pos >= 0)
279                        nodeAttributes.remove(pos);
280        }
281
282        /**
283         * Add this attribute on all edges generated. This attribute will have a
284         * numerical value chosen in a range that is by default [0-1].
285         * 
286         * @param name
287         *            The attribute name.
288         * @see #setEdgeAttributesRange(double, double)
289         * @see #removeEdgeAttribute(String)
290         */
291        public void addEdgeAttribute(String name) {
292                edgeAttributes.add(name);
293        }
294
295        /**
296         * Remove an automatic attribute for edges.
297         * 
298         * @param name
299         *            The attribute name.
300         * @see #addEdgeAttribute(String)
301         */
302        public void removeEdgeAttribute(String name) {
303                int pos = edgeAttributes.indexOf(name);
304
305                if (pos >= 0)
306                        edgeAttributes.remove(pos);
307        }
308
309        /**
310         * If node attributes are added automatically, choose in which range the
311         * values are choosed.
312         * 
313         * @see #addNodeAttribute(String)
314         */
315        public void setNodeAttributesRange(double low, double hi) {
316                nodeAttributeRange[0] = low;
317                nodeAttributeRange[1] = hi;
318        }
319
320        /**
321         * If edge attributes are added automatically, choose in which range the
322         * values are choosed.
323         * 
324         * @see #addEdgeAttribute(String)
325         */
326        public void setEdgeAttributesRange(double low, double hi) {
327                edgeAttributeRange[0] = low;
328                edgeAttributeRange[1] = hi;
329        }
330
331        /**
332         * Enable or disable the use of an internal graph. If enable, nodes, edges
333         * and their attributes are stored in an internal graph.
334         * 
335         * This is useful if the generator needs to remember informations like node
336         * id.
337         * 
338         * @param on
339         *            true if the internal graph has to be enable.
340         */
341        public void setUseInternalGraph(boolean on) {
342                useInternalGraph = on;
343
344                if (!on && internalGraph != null) {
345                        internalGraph.clear();
346                        internalGraph = null;
347                }
348
349                if (on && internalGraph == null) {
350                        internalGraph = new AdjacencyListGraph(getClass().getName()
351                                        + "-internal_graph");
352                        internalGraph.setStrict(false);
353                }
354        }
355
356        /**
357         * Flag to know if an internal graph is in use.
358         * 
359         * @return true if nodes and edges are stored in an internal graph.
360         */
361        public boolean isUsingInternalGraph() {
362                return useInternalGraph;
363        }
364
365        /**
366         * Same as {@link #addNode(String)} but specify attributes to position the
367         * node on a plane.
368         * 
369         * @param id
370         *            The node identifier.
371         * @param x
372         *            The node abscissa.
373         * @param y
374         *            The node ordinate.
375         */
376        protected void addNode(String id, double x, double y) {
377                addNode(id);
378                sendNodeAttributeAdded(sourceId, id, "xy", new Double[] {
379                                new Double(x), new Double(y) });
380
381                if (useInternalGraph)
382                        internalGraph.getNode(id).addAttribute("xy",
383                                        (Object) (new Double[] { new Double(x), new Double(y) }));
384        }
385
386        /**
387         * Add a node and put attributes on it if needed.
388         * 
389         * @param id
390         *            The new node identifier.
391         */
392        protected void addNode(String id) {
393                sendNodeAdded(sourceId, id);
394
395                if (addNodeLabels)
396                        sendNodeAttributeAdded(sourceId, id, "label", id);
397
398                if (useInternalGraph)
399                        internalGraph.addNode(id);
400
401                double value;
402
403                for (String attr : nodeAttributes) {
404                        value = (random.nextDouble() * (nodeAttributeRange[1] - nodeAttributeRange[0]))
405                                        + nodeAttributeRange[0];
406                        sendNodeAttributeAdded(sourceId, id, attr, value);
407
408                        if (useInternalGraph)
409                                internalGraph.getNode(id).addAttribute(attr, value);
410                }
411        }
412
413        /**
414         * Remove a node.
415         * 
416         * @param id
417         *            id of the node to remove
418         */
419        protected void delNode(String id) {
420                if (useInternalGraph)
421                        internalGraph.removeNode(id);
422
423                sendNodeRemoved(sourceId, id);
424        }
425
426        /**
427         * Add an edge, choosing randomly its orientation if needed and putting
428         * attribute on it if needed.
429         * 
430         * @param id
431         *            The edge identifier, if null, the identifier is created from
432         *            the nodes identifiers.
433         * @param from
434         *            The source node (can be inverted randomly with the target
435         *            node).
436         */
437        protected void addEdge(String id, String from, String to) {
438                if (directed && randomlyDirected && (random.nextFloat() > 0.5f)) {
439                        String tmp = from;
440                        from = to;
441                        to = tmp;
442                }
443
444                if (id == null)
445                        id = from + "_" + to;
446
447                sendEdgeAdded(sourceId, id, from, to, directed);
448
449                if (useInternalGraph)
450                        internalGraph.addEdge(id, from, to, directed);
451
452                if (addEdgeLabels)
453                        sendEdgeAttributeAdded(sourceId, id, "label", id);
454
455                for (String attr : edgeAttributes) {
456                        double value = (random.nextDouble() * (edgeAttributeRange[1] - edgeAttributeRange[0]))
457                                        + edgeAttributeRange[0];
458                        sendEdgeAttributeAdded(sourceId, id, attr, value);
459
460                        if (useInternalGraph)
461                                internalGraph.getEdge(id).addAttribute(attr, value);
462                }
463        }
464
465        /**
466         * Remove an edge.
467         * 
468         * @param edgeId
469         *            id of the edge to remove
470         */
471        protected void delEdge(String edgeId) {
472                sendEdgeRemoved(sourceId, edgeId);
473
474                if (useInternalGraph)
475                        internalGraph.removeEdge(edgeId);
476        }
477
478        /**
479         * Clear the internal graph if {@link #useInternalGraph} is enable.
480         * 
481         * This method is called in {@link #end()} to ensure the next generation
482         * will start freshly anew.
483         */
484        protected void clearKeptData() {
485                if (useInternalGraph)
486                        internalGraph.clear();
487        }
488}