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}