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.Collections;
035import java.util.HashMap;
036import java.util.HashSet;
037import java.util.LinkedList;
038import java.util.Map;
039import java.util.Set;
040import java.util.concurrent.atomic.AtomicInteger;
041
042import org.graphstream.graph.Graph;
043import org.graphstream.graph.implementations.DefaultGraph;
044
045import static java.lang.Math.min;
046import static java.lang.Math.pow;
047import static java.lang.Math.atan;
048
049/**
050 * Generate a <b>social</b> dynamic graph. Graph is composed of high-connected
051 * group of nodes, modeling organizations, and few connections between
052 * organizations.
053 * 
054 * This is done by creating <i>points of interest</i>. Nodes can be interested
055 * by these points or loose them interest. When two nodes are interested by at
056 * least one common point, then there are connected.
057 * 
058 * Some probabilities can be set defining the following events :
059 * <ul>
060 * <li>remove a node ;</li>
061 * <li>add a node ;</li>
062 * <li>remove a point of interest ;</li>
063 * <li>add a point of interest.</li>
064 * </ul>
065 * 
066 * Initial parameters are :
067 * <ul>
068 * <li>initial count of points of interest ;</li>
069 * <li>initial count of nodes ;</li>
070 * </ul>
071 * 
072 * @author Guilhelm Savin
073 * 
074 */
075public class PointsOfInterestGenerator extends BaseGenerator {
076        /**
077         * Defines a point of interest. It is just a set of <i>addicted</i> nodes.
078         */
079        protected class PointOfInterest {
080                /**
081                 * Set of nodes interested by this point.
082                 */
083                Set<Addict> addict;
084
085                PointOfInterest() {
086                        addict = new HashSet<Addict>();
087                }
088
089                /**
090                 * Registers a node as an addict of this point. The node will be linked
091                 * to all nodes already addict of this point. The list of points of
092                 * interest of the node will be updated.
093                 * 
094                 * @param addictA
095                 *            the addicted node
096                 */
097                void newAddict(Addict addictA) {
098                        if (!addict.contains(addictA)) {
099                                for (Addict addictB : addict)
100                                        addictA.link(addictB);
101
102                                addict.add(addictA);
103                                addictA.pointsOfInterest.add(this);
104                        }
105                }
106
107                /**
108                 * Unregisters a node. The node will be unlinked to all nodes already
109                 * addict of this point. The list of points of interest of the node will
110                 * be updated.
111                 * 
112                 * @param addictA
113                 *            the addicted node
114                 */
115                void delAddict(Addict addictA) {
116                        if (addict.contains(addictA)) {
117                                addict.remove(addictA);
118                                addictA.pointsOfInterest.remove(this);
119
120                                for (Addict addictB : addict)
121                                        addictA.unlink(addictB);
122                        }
123                }
124
125                /**
126                 * Check is a node is addict of this point.
127                 * 
128                 * @param a
129                 *            the addict
130                 * @return true if a is addict of this point
131                 */
132                boolean isAddict(Addict a) {
133                        return addict.contains(a);
134                }
135        }
136
137        protected static class AddictNeighbor {
138                AtomicInteger counter;
139                boolean connected;
140
141                public AddictNeighbor() {
142                        this.counter = new AtomicInteger(0);
143                        this.connected = false;
144                }
145
146                public AddictNeighbor(AtomicInteger i) {
147                        this.counter = i;
148                        this.connected = false;
149                }
150
151                int incrementAndGet() {
152                        return counter.incrementAndGet();
153                }
154
155                int decrementAndGet() {
156                        return counter.decrementAndGet();
157                }
158
159                boolean isConnected() {
160                        return connected;
161                }
162        }
163
164        /**
165         * Defines data of a node. We have to keep id of the node and to backup
166         * points of interest of this node and neighbor of the node.
167         */
168        protected class Addict {
169                /**
170                 * Id of the node.
171                 */
172                String id;
173
174                /**
175                 * List of points of interest of this node.
176                 */
177                LinkedList<PointOfInterest> pointsOfInterest;
178
179                /**
180                 * List of neighbors.
181                 */
182                Map<Addict, AddictNeighbor> neighbor;
183
184                Addict(String id) {
185                        this.id = id;
186                        pointsOfInterest = new LinkedList<PointOfInterest>();
187                        neighbor = new HashMap<Addict, AddictNeighbor>();
188                }
189
190                /**
191                 * Defines a step for a node. Node will iterate over points-of-interest.
192                 * For each point p, if node is already interest by p, node will check
193                 * if it is still interested by this point (according to
194                 * <i>lostInterestProbability</i> probability). Else, node will checked
195                 * if it can be interested by p, according to
196                 * <i>haveInterestProbability</i> probability and its points count (the
197                 * probability will decrease when the count of points increases).
198                 */
199                void step() {
200                        //
201                        // Avoid that all nodes are interested by the same point.
202                        //
203                        Collections.shuffle(
204                                        PointsOfInterestGenerator.this.pointsOfInterest, random);
205
206                        for (PointOfInterest poi : PointsOfInterestGenerator.this.pointsOfInterest) {
207                                if (pointsOfInterest.contains(poi)) {
208                                        if (random.nextFloat() < lostInterestProbability)
209                                                poi.delAddict(this);
210                                } else {
211                                        double p = atan(20.0
212                                                        * min(pointsOfInterest.size(),
213                                                                        averagePointsOfInterestCount)
214                                                        / (double) averagePointsOfInterestCount - 10);
215                                        p = (p - atan(-10)) / (atan(10) - atan(-10));
216
217                                        if (random.nextFloat() < haveInterestProbability * (1 - p))// pow(
218                                                                                                                                                                // haveInterestProbability,
219                                                                                                                                                                // 1.2
220                                                                                                                                                                // *
221                                                                                                                                                                // pointsOfInterest.size()
222                                                                                                                                                                // )
223                                                                                                                                                                // )
224                                                poi.newAddict(this);
225                                }
226                        }
227                }
228
229                /**
230                 * Link this node to another. Both nodes will share a common counter.
231                 * Links these two nodes will increase the counter and so unlink will
232                 * decrease the counter. If counter not exists, it is initialized and
233                 * edge is created. Else, if counter is equal to zero, counter is
234                 * removed and edge is removed too.
235                 * 
236                 * @param a
237                 *            the node to link
238                 */
239                void link(Addict a) {
240                        if (!neighbor.containsKey(a)) {
241                                AddictNeighbor an = new AddictNeighbor();
242                                neighbor.put(a, an);
243                                a.neighbor.put(this, an);
244                        }
245
246                        AddictNeighbor an = neighbor.get(a);
247
248                        if (an.incrementAndGet() >= linksNeededToCreateEdge
249                                        && !an.connected) {
250                                if (random.nextDouble() < pow(linkProbability,
251                                                1.0 / (double) (an.counter.get()
252                                                                - linksNeededToCreateEdge + 1))) {
253                                        an.connected = true;
254                                        PointsOfInterestGenerator.this.addEdge(getEdgeId(id, a.id),
255                                                        id, a.id);
256                                }
257                        }
258                }
259
260                /**
261                 * Unlink this node with another. Links-counter between these two nodes
262                 * is decreased and edge is removed is needed.
263                 * 
264                 * @param a
265                 *            the node to unlink
266                 */
267                void unlink(Addict a) {
268                        if (neighbor.containsKey(a)) {
269                                if (neighbor.get(a).decrementAndGet() < linksNeededToCreateEdge) {
270                                        neighbor.remove(a);
271                                        a.neighbor.remove(this);
272                                        PointsOfInterestGenerator.this.delEdge(getEdgeId(id, a.id));
273                                }
274                        }
275                }
276
277                /**
278                 * Unlink all neighbor.
279                 */
280                void fullUnlink() {
281                        for (Addict a : neighbor.keySet()) {
282                                a.neighbor.remove(this);
283                                PointsOfInterestGenerator.this.delEdge(getEdgeId(id, a.id));
284                        }
285
286                        neighbor.clear();
287                }
288        }
289
290        protected static String getEdgeId(String nodeA, String nodeB) {
291                return nodeA.compareTo(nodeB) < 0 ? String.format("%s---%s", nodeA,
292                                nodeB) : String.format("%s---%s", nodeB, nodeA);
293        }
294
295        public static enum Parameter {
296                INITIAL_PEOPLE_COUNT, ADD_PEOPLE_PROBABILITY, DEL_PEOPLE_PROBABILITY, INITIAL_POINT_OF_INTEREST_COUNT, AVERAGE_POINTS_OF_INTEREST_COUNT, ADD_POINT_OF_INTEREST_PROBABILITY, DEL_POINT_OF_INTEREST_PROBABILITY, HAVE_INTEREST_PROBABILITY, LOST_INTEREST_PROBABILITY, LINKS_NEEDED_TO_CREATE_EDGE, LINK_PROBABILITY
297        }
298
299        /**
300         * Initial count of nodes.
301         */
302        protected int initialPeopleCount;
303
304        /**
305         * Probability to add a node during a step.
306         */
307        protected float addPeopleProbability;
308
309        /**
310         * Probability to remove a node during a step.
311         */
312        protected float delPeopleProbability;
313
314        /**
315         * Probability that a node becomes interested in a point-of-interest it was
316         * not already interested.
317         */
318        protected float haveInterestProbability;
319
320        /**
321         * Probability that a node looses its interest for a point-of-interest.
322         */
323        protected float lostInterestProbability;
324
325        /**
326         * Initial count of point-of-interest.
327         */
328        protected int initialPointOfInterestCount;
329
330        /**
331         * Probability to add a new point-of-interest.
332         */
333        protected float addPointOfInterestProbability;
334
335        /**
336         * Probability to remove a point-of-interest.
337         */
338        protected float delPointOfInterestProbability;
339
340        /**
341         * Average points of interest by addict.
342         */
343        protected float averagePointsOfInterestCount;
344
345        protected int linksNeededToCreateEdge;
346
347        protected float linkProbability;
348
349        /**
350         * List of addicts.
351         */
352        protected LinkedList<Addict> addicts;
353        /**
354         * List of point-of-interest.
355         */
356        protected LinkedList<PointOfInterest> pointsOfInterest;
357
358        private long currentId;
359
360        private long currentStep;
361
362        public PointsOfInterestGenerator() {
363                setUseInternalGraph(false);
364
365                initialPeopleCount = 500;
366                addPeopleProbability = delPeopleProbability = 0.001f;
367
368                haveInterestProbability = 0.001f;
369                lostInterestProbability = 0.005f;
370
371                initialPointOfInterestCount = 15;
372                addPointOfInterestProbability = delPointOfInterestProbability = 0.001f;
373
374                linkProbability = 0.3f;
375                averagePointsOfInterestCount = 3;
376                linksNeededToCreateEdge = 2;
377
378                addicts = new LinkedList<Addict>();
379                pointsOfInterest = new LinkedList<PointOfInterest>();
380
381                currentStep = 0;
382        }
383
384        public void setParameter(Parameter p, Object value) {
385                switch (p) {
386                case INITIAL_PEOPLE_COUNT:
387                        this.initialPeopleCount = (Integer) value;
388                        break;
389                case ADD_PEOPLE_PROBABILITY:
390                        this.addPeopleProbability = (Float) value;
391                        break;
392                case DEL_PEOPLE_PROBABILITY:
393                        this.delPeopleProbability = (Float) value;
394                        break;
395                case INITIAL_POINT_OF_INTEREST_COUNT:
396                        this.initialPointOfInterestCount = (Integer) value;
397                        break;
398                case AVERAGE_POINTS_OF_INTEREST_COUNT:
399                        this.averagePointsOfInterestCount = (Float) value;
400                        break;
401                case ADD_POINT_OF_INTEREST_PROBABILITY:
402                        this.addPointOfInterestProbability = (Float) value;
403                        break;
404                case DEL_POINT_OF_INTEREST_PROBABILITY:
405                        this.delPointOfInterestProbability = (Float) value;
406                        break;
407                case HAVE_INTEREST_PROBABILITY:
408                        this.haveInterestProbability = (Float) value;
409                        break;
410                case LOST_INTEREST_PROBABILITY:
411                        this.lostInterestProbability = (Float) value;
412                        break;
413                case LINKS_NEEDED_TO_CREATE_EDGE:
414                        this.linksNeededToCreateEdge = (Integer) value;
415                        break;
416                case LINK_PROBABILITY:
417                        this.linkProbability = ((Number) value).floatValue();
418                        break;
419                }
420        }
421
422        /**
423         * Add initial count of points of interest, and initial count of people.
424         * 
425         * @see org.graphstream.algorithm.generator.Generator#begin()
426         */
427        public void begin() {
428                pointsOfInterest.clear();
429
430                for (int i = 0; i < initialPointOfInterestCount; i++)
431                        addPointOfInterest();
432
433                for (int i = 0; i < initialPeopleCount; i++)
434                        addAddict();
435        }
436
437        /**
438         * Step of the generator. Try to remove a node according to the
439         * {@link #delPeopleProbability}. Try to add a node according to the
440         * {@link #addPeopleProbability}. Try to remove a point of interest
441         * according to the {@link #delPointOfInterestProbability}. Try to add a
442         * point of interest according to the {@link #addPointOfInterestProbability}
443         * . Then, step of <i>addicts</i>.
444         * 
445         * @see PointsOfInterestGenerator.Addict#step()
446         * @see org.graphstream.algorithm.generator.Generator#nextEvents()
447         */
448        public boolean nextEvents() {
449                sendStepBegins(sourceId, currentStep++);
450
451                if (random.nextDouble() < delPeopleProbability)
452                        killSomeone();
453
454                if (random.nextDouble() < addPeopleProbability)
455                        addAddict();
456
457                if (random.nextDouble() < delPointOfInterestProbability)
458                        removeRandomPointOfInterest();
459
460                if (random.nextDouble() < addPointOfInterestProbability)
461                        addPointOfInterest();
462
463                for (Addict a : addicts)
464                        a.step();
465
466                return true;
467        }
468
469        /*
470         * (non-Javadoc)
471         * 
472         * @see org.graphstream.algorithm.generator.Generator#end()
473         */
474        @Override
475        public void end() {
476                super.end();
477        }
478
479        protected void addPointOfInterest() {
480                pointsOfInterest.add(new PointOfInterest());
481        }
482
483        protected void removePointOfInterest(PointOfInterest poi) {
484                pointsOfInterest.remove(poi);
485
486                for (Addict a : poi.addict)
487                        poi.delAddict(a);
488        }
489
490        protected void removeRandomPointOfInterest() {
491                pointsOfInterest.remove(random.nextInt(pointsOfInterest.size()));
492        }
493
494        protected void addAddict() {
495                Addict a = new Addict(String.format("%08x", currentId++));
496
497                addicts.add(a);
498                addNode(a.id);
499        }
500
501        protected void killAddict(Addict a) {
502                while (a.pointsOfInterest.size() > 0)
503                        a.pointsOfInterest.peek().delAddict(a);
504
505                a.fullUnlink();
506
507                addicts.remove(a);
508                delNode(a.id);
509
510                a.id = null;
511                a.pointsOfInterest.clear();
512                a.pointsOfInterest = null;
513        }
514
515        protected void killSomeone() {
516                killAddict(addicts.get(random.nextInt(addicts.size())));
517        }
518
519        public static void main(String... args) {
520                PointsOfInterestGenerator gen = new PointsOfInterestGenerator();
521
522                gen.setParameter(Parameter.INITIAL_PEOPLE_COUNT, 300);
523                gen.setParameter(Parameter.ADD_PEOPLE_PROBABILITY, 0.01f);
524                gen.setParameter(Parameter.DEL_PEOPLE_PROBABILITY, 0.01f);
525                gen.setParameter(Parameter.INITIAL_POINT_OF_INTEREST_COUNT, 30);
526                gen.setParameter(Parameter.AVERAGE_POINTS_OF_INTEREST_COUNT, 5.0f);
527                gen.setParameter(Parameter.ADD_POINT_OF_INTEREST_PROBABILITY, 0.0f);
528                gen.setParameter(Parameter.DEL_POINT_OF_INTEREST_PROBABILITY, 0.0f);
529                gen.setParameter(Parameter.HAVE_INTEREST_PROBABILITY, 0.1f);
530                gen.setParameter(Parameter.LOST_INTEREST_PROBABILITY, 0.001f);
531                gen.setParameter(Parameter.LINKS_NEEDED_TO_CREATE_EDGE, 2);
532                gen.setParameter(Parameter.LINK_PROBABILITY, 0.05f);
533
534                Graph g = new DefaultGraph("theGraph");
535                gen.addSink(g);
536
537                String stylesheet = "graph { " + "  fill-color: white;"
538                                + "  padding: 50px;" + "}" + "node { " + "  fill-color: black;"
539                                + "}" + "edge {" + "  fill-color: black;" + "}";
540
541                g.addAttribute("ui.stylesheet", stylesheet);
542                g.addAttribute("ui.quality");
543                // g.addAttribute( "ui.antialias" );
544
545                g.display();
546
547                gen.begin();
548
549                while (true) {
550                        gen.nextEvents();
551
552                        try {
553                                Thread.sleep(60);
554                        } catch (Exception e) {
555                                e.printStackTrace();
556                        }
557                }
558        }
559}