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.LinkedList;
035
036/**
037 * Generate a Lobster tree. Lobster are trees where the distance between any
038 * node and a root path is less than 2. In this generator, the max distance can
039 * be customized.
040 */
041public class LobsterGenerator extends BaseGenerator {
042        /**
043         * Max distance from any node to a node of the root path.
044         */
045        protected int maxDistance = 2;
046        /**
047         * Max degree of nodes.
048         */
049        protected int maxDegree = 10;
050        /**
051         * Delete some node in step.
052         */
053        protected boolean delete = false;
054        /**
055         * Average node count. Used in delete-mode to maintain an average count of
056         * nodes.
057         */
058        protected int averageNodeCount = 200;
059        /**
060         * Used to generate new node index.
061         */
062        protected int currentIndex = 0;
063        /**
064         * Node data.
065         */
066        protected LinkedList<Data> nodes;
067
068        /**
069         * Main constructor to a Lobster generator.
070         */
071        public LobsterGenerator() {
072                this(2, -1);
073        }
074
075        /**
076         * Constructor allowing to customize maximum distance to the root path and
077         * maximum degree of nodes.
078         * 
079         * @param maxDistance
080         *            max distance to root path
081         * @param maxDegree
082         *            max degree of nodes
083         */
084        public LobsterGenerator(int maxDistance, int maxDegree) {
085                this.maxDistance = maxDistance;
086                this.maxDegree = maxDegree;
087                this.nodes = new LinkedList<Data>();
088        }
089
090        /**
091         * Constructor allowing to customize maximum distance to the root path.
092         * 
093         * @param maxDistance
094         *            max distance to root path
095         */
096        public LobsterGenerator(int maxDistance) {
097                this(maxDistance, -1);
098        }
099
100        /*
101         * (non-Javadoc)
102         * 
103         * @see org.graphstream.algorithm.generator.Generator#begin()
104         */
105        public void begin() {
106                nodes.clear();
107                add(new Data(newNodeId(), 0, true));
108        }
109
110        /*
111         * (non-Javadoc)
112         * 
113         * @see org.graphstream.algorithm.generator.Generator#nextEvents()
114         */
115        public boolean nextEvents() {
116                Data connectTo = null;
117
118                do {
119                        connectTo = nodes.get(random.nextInt(nodes.size()));
120                } while (connectTo.distance >= maxDistance
121                                || (maxDegree > 0 && connectTo.degree() >= maxDegree));
122
123                Data newData = null;
124
125                if (connectTo.path && connectTo.degree() <= 1)
126                        newData = new Data(newNodeId(), 0, true);
127                else
128                        newData = new Data(newNodeId(), connectTo.distance + 1, false);
129
130                add(newData);
131                connect(connectTo, newData);
132
133                if (delete && nodes.size() > 1) {
134                        double d = Math.min(nodes.size() - averageNodeCount,
135                                        averageNodeCount / 10);
136
137                        d /= averageNodeCount / 10.0;
138
139                        if (d > 0 && random.nextFloat() < d) {
140                                Data delete = null;
141
142                                do {
143                                        delete = nodes.get(random.nextInt(nodes.size()));
144                                } while (delete.degree() > 1);
145
146                                delNode(delete);
147                        }
148                }
149
150                return true;
151        }
152
153        protected void add(Data data) {
154                nodes.add(data);
155                addNode(data.id);
156        }
157
158        protected void connect(Data d1, Data d2) {
159                d1.connected.add(d2);
160                d2.connected.add(d1);
161
162                addEdge(getEdgeId(d1, d2), d1.id, d2.id);
163        }
164
165        protected void delNode(Data d) {
166                for (Data c : d.connected) {
167                        delEdge(getEdgeId(d, c));
168                        c.connected.remove(d);
169                }
170
171                delNode(d.id);
172                nodes.remove(d);
173        }
174
175        protected String newNodeId() {
176                return String.format("%04d", currentIndex++);
177        }
178
179        protected String getEdgeId(Data d1, Data d2) {
180                if (d1.hashCode() > d2.hashCode()) {
181                        Data t = d1;
182                        d1 = d2;
183                        d2 = t;
184                }
185
186                return String.format("%s--%s", d1.id, d2.id);
187        }
188
189        protected static class Data {
190                String id;
191                int distance;
192                boolean path;
193                LinkedList<Data> connected;
194
195                Data(String id, int distance, boolean path) {
196                        this.id = id;
197                        this.distance = distance;
198                        this.connected = new LinkedList<Data>();
199                        this.path = path;
200                }
201
202                int degree() {
203                        return connected.size();
204                }
205        }
206}