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.community;
033
034import java.util.*;
035
036import org.graphstream.algorithm.DynamicAlgorithm;
037import org.graphstream.graph.*;
038import org.graphstream.stream.Sink;
039
040/**
041 * Base class for all distributed community detection algorithm. They all
042 * implement the DynamicAlgorithm and Sink interfaces.
043 * 
044 * @author Guillaume-Jean Herbiet
045 * 
046 */
047public abstract class DecentralizedCommunityAlgorithm implements
048                DynamicAlgorithm, Sink {
049        /**
050         * The graph to apply the algorithm.
051         */
052        protected Graph graph;
053
054        /**
055         * Name of the attribute marking the communities. Default is "community".
056         * This is prefixed by the algorithm class and memory location to make this
057         * unique for each instance of the algorithm.
058         */
059        protected String marker;
060        protected String nonUniqueMarker;
061
062        /**
063         * Set to false after {@link #compute()}, unless static mode is set.
064         */
065        protected boolean graphChanged = true;
066
067        /**
068         * Force algorithm to perform even if the graph is static.
069         */
070        protected boolean staticMode = false;
071
072        /**
073         * Random number generator used to shuffle the nodes. Shall be used by all
074         * inherited algorithms for random number generation
075         */
076        protected Random rng;
077
078        /**
079         * Create a new distributed community detection algorithm, without attaching
080         * it to a graph
081         */
082        public DecentralizedCommunityAlgorithm() {
083        }
084
085        /**
086         * Create a new distributed community detection algorithm, attached to the
087         * specified graph
088         * 
089         * @param graph
090         *            The graph on which the community assignment will be performed
091         */
092        public DecentralizedCommunityAlgorithm(Graph graph) {
093                this();
094                init(graph);
095        }
096
097        /**
098         * Create a new distributed community detection algorithm, attached to the
099         * specified graph, and using the specified marker to store the community
100         * attribute
101         * 
102         * @param graph
103         *            The graph on which the community assignment will be performed
104         * @param marker
105         *            Marker string used to store the current community of a node
106         */
107        public DecentralizedCommunityAlgorithm(Graph graph, String marker) {
108                this();
109                setMarker(marker);
110                init(graph);
111        }
112
113        /**
114         * Initialize the distributed community detection algorithm, attaching it to
115         * the specified graph, and using the specified marker to store the
116         * community attribute
117         * 
118         * @param graph
119         * @param marker
120         */
121        public void init(Graph graph, String marker) {
122                setMarker(marker);
123                init(graph);
124        }
125
126        /**
127         * Initialize the distributed community detection algorithm, attaching it to
128         * the specified graph, and using the default marker to store the community
129         * attribute.
130         * 
131         * By default an uncontrolled random number generator will be used. For sake
132         * of reproducibility, use the {@link #setRandom(Random)} function to use a
133         * controlled random number generator with this algorithm.
134         * 
135         * @param graph
136         */
137//      @Override
138        public void init(Graph graph) {
139                /*
140                 * Set the marker to a default value unless set when instantiating the
141                 * class
142                 */
143                if (this.marker == null)
144                        setMarker(null);
145                this.graph = graph;
146
147                /*
148                 * Initiate an uncontrolled random network generator
149                 */
150                if (this.rng == null)
151                        rng = new Random();
152        }
153
154//      @Override
155        public void terminate() {
156        }
157
158        /**
159         * Enable the static mode. In this mode, algorithm will perform even if the
160         * graph hasn't changed (useful for static graphs).
161         */
162        public void staticMode() {
163                staticMode = true;
164        }
165
166        /**
167         * Set the marker used to store the community assignment to the specified
168         * value. The given value will be prefixed by
169         * [AlgorithmClass].[InstanceNumber] to make this unique for each instance
170         * of the algorithm.
171         * 
172         * @param marker
173         */
174        public void setMarker(String marker) {
175                if (marker == null) {
176                        this.nonUniqueMarker = "community";
177                } else {
178                        this.nonUniqueMarker = marker;
179                }
180                this.marker = this.toString() + "." + nonUniqueMarker;
181        }
182
183        /**
184         * Get the marker used to store the community assignment
185         * 
186         * @return the complete (i.e. prefixed) marker
187         */
188        public String getMarker() {
189                return this.marker;
190        }
191
192        /**
193         * Set the random number generator for this algorithm. For sake of
194         * reproducibility, the given random number generator shall be initiated
195         * with a controlled seed.
196         * 
197         * @param rng
198         *            an initialized java.util.Random object.
199         */
200        public void setRandom(Random rng) {
201                this.rng = rng;
202        }
203
204        /**
205         * Get the random number generator currently used for this algorithm.
206         * 
207         * @return the current random number generator.
208         */
209        public Random getRandom() {
210                return this.rng;
211        }
212
213        /**
214         * Compute an iteration of the algorithm for all the nodes of the network.
215         * 
216         * @complexity N times the complexity of the computeNode() function, where N
217         *             is the number of nodes in the network.
218         */
219//      @Override
220        public void compute() {
221                /*
222                 * This simply calls the computeNode method for all nodes in the graph.
223                 * Nodes are processed in a random order. Computation only occurs if the
224                 * graph has changed since last call
225                 */
226                if (graphChanged) {
227                        ArrayList<Node> nodeSet = new ArrayList<Node>(graph.getNodeSet());
228                        Collections.shuffle(nodeSet, rng);
229                        for (Node node : nodeSet) {
230                                computeNode(node);
231                                updateDisplayClass(node);
232                        }
233                        graphChanged = staticMode;
234                }
235        }
236
237        /**
238         * Perform computation of one iteration of the algorithm on a given node.
239         * 
240         * @param node
241         */
242        public abstract void computeNode(Node node);
243
244        /**
245         * Generate a new original community and attribute it to a node
246         * 
247         * @param node
248         *            The node that will originate the new community
249         */
250        protected void originateCommunity(Node node) {
251                node.addAttribute(marker, new Community());
252        }
253
254        /**
255         * Update the display class of the node based on its current community.
256         * 
257         * The class name is [marker]_[id] where "marker" is the attribute name used
258         * to store the current community, and [id] the id of this community.
259         * 
260         * @param node
261         */
262        protected void updateDisplayClass(Node node) {
263                node.setAttribute(
264                                "ui.class",
265                                nonUniqueMarker + "_"
266                                                + ((Community) node.getAttribute(marker)).getId());
267        }
268
269        public void attributeChanged(Element element, String attribute,
270                        Object oldValue, Object newValue) {
271        }
272
273        public void nodeAdded(String graphId, long timeId, String nodeId) {
274                graphChanged = true;
275        }
276
277        public void nodeRemoved(String graphId, long timeId, String nodeId) {
278                graphChanged = true;
279        }
280
281        public void edgeAdded(String graphId, long timeId, String edgeId,
282                        String fromNodeId, String toNodeId, boolean directed) {
283                graphChanged = true;
284        }
285
286        public void edgeRemoved(String graphId, long timeId, String edgeId) {
287                graphChanged = true;
288        }
289
290        public void graphCleared(String graphId, long timeId) {
291                graphChanged = true;
292        }
293
294        public void stepBegins(String graphId, long timeId, double time) {
295        }
296
297        public void graphAttributeAdded(String graphId, long timeId,
298                        String attribute, Object value) {
299        }
300
301        public void graphAttributeChanged(String graphId, long timeId,
302                        String attribute, Object oldValue, Object newValue) {
303        }
304
305        public void graphAttributeRemoved(String graphId, long timeId,
306                        String attribute) {
307        }
308
309        public void nodeAttributeAdded(String graphId, long timeId, String nodeId,
310                        String attribute, Object value) {
311                nodeAttributeChanged(graphId, timeId, nodeId, attribute, null, value);
312        }
313
314        public void nodeAttributeChanged(String graphId, long timeId,
315                        String nodeId, String attribute, Object oldValue, Object newValue) {
316        }
317
318        public void nodeAttributeRemoved(String graphId, long timeId,
319                        String nodeId, String attribute) {
320        }
321
322        public void edgeAttributeAdded(String graphId, long timeId, String edgeId,
323                        String attribute, Object value) {
324        }
325
326        public void edgeAttributeChanged(String graphId, long timeId,
327                        String edgeId, String attribute, Object oldValue, Object newValue) {
328        }
329
330        public void edgeAttributeRemoved(String graphId, long timeId,
331                        String edgeId, String attribute) {
332        }
333
334}