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.measure; 033 034import java.util.HashMap; 035import java.util.HashSet; 036 037import org.graphstream.algorithm.DynamicAlgorithm; 038import org.graphstream.graph.Graph; 039import org.graphstream.graph.Node; 040import org.graphstream.stream.SinkAdapter; 041 042import static org.graphstream.algorithm.Toolkit.communities; 043 044/** 045 * Computes and updates an absolute measure based on the current community 046 * assignment on a given graph as it evolves. 047 * 048 * @reference M. E. Newman and M. Girvan, “Finding and Evaluating Community 049 * Structure in Networks,” <i>Physical Review E (Statistical, 050 * Nonlinear, and Soft Matter Physics)</i>, vol. 69, no. 2, pp. 026 051 * 113+, Feb 2004. 052 * 053 * @author Guillaume-Jean Herbiet 054 */ 055public abstract class CommunityMeasure extends SinkAdapter implements 056 DynamicAlgorithm { 057 /** 058 * The graph for which the modularity will be computed. 059 */ 060 protected Graph graph; 061 062 /** 063 * Name of the attribute marking the communities. 064 */ 065 protected String marker; 066 067 /** 068 * All communities indexed by their marker value. 069 */ 070 protected HashMap<Object, HashSet<Node>> communities; 071 072 /** 073 * Set to false after {@link #compute()}. 074 */ 075 protected boolean graphChanged = true; 076 077 /** 078 * Last value computed. 079 */ 080 protected double M; 081 082 /** 083 * New measure algorithm with a given marker for communities. 084 * 085 * @param marker 086 * name of the attribute marking the communities. 087 */ 088 public CommunityMeasure(String marker) { 089 this.marker = marker; 090 } 091 092 // /** 093 // * New measure algorithm based on the results provided by the specified 094 // * algorithm. 095 // * 096 // * @param algo 097 // * Algorithm which results will be used for measurement. 098 // */ 099 // public CommunityMeasure(CommunityAlgorithm algo) { 100 // this.marker = algo.getMarker(); 101 // } 102 103 /** 104 * The last computed measure. 105 * 106 * @complexity O(1) 107 * @return The last computed measure. 108 */ 109 public double getLastComputedValue() { 110 return M; 111 } 112 113 /** 114 * Compute the measure (if the graph changed since the last computation). 115 * 116 * @complexity Depends on the actual measure 117 * @return The current measure. 118 */ 119 public double getMeasure() { 120 compute(); 121 return M; 122 } 123 124 /* 125 * (non-Javadoc) 126 * 127 * @see 128 * org.graphstream.algorithm.Algorithm#init(org.graphstream.graph.Graph) 129 */ 130 public void init(Graph graph) { 131 if (graph != this.graph) { 132 if (this.graph != null) { 133 this.graph.removeSink(this); 134 } 135 136 this.graph = graph; 137 138 if (this.graph != null) { 139 this.graph.addSink(this); 140 initialize(); 141 } 142 } 143 } 144 145 /* 146 * (non-Javadoc) 147 * 148 * @see org.graphstream.algorithm.Algorithm#compute() 149 */ 150 public abstract void compute(); 151 152 /* 153 * (non-Javadoc) 154 * 155 * @see org.graphstream.algorithm.DynamicAlgorithm#terminate() 156 */ 157 public void terminate() { 158 // NOP. 159 } 160 161 protected void initialize() { 162 communities = communities(graph, marker); 163 } 164 165 /* 166 * @see org.graphstream.stream.Sink#nodeAdded(java.lang.String, long, 167 * java.lang.String) 168 */ 169 @Override 170 public void nodeAdded(String graphId, long timeId, String nodeId) { 171 Node n = graph.getNode(nodeId); 172 assignNode(nodeId, n.getAttribute(marker), communities); 173 } 174 175 /* 176 * (non-Javadoc) 177 * 178 * @see org.graphstream.stream.Sink#nodeRemoved(java.lang.String, long, 179 * java.lang.String) 180 */ 181 @Override 182 public void nodeRemoved(String graphId, long timeId, String nodeId) { 183 Node n = graph.getNode(nodeId); 184 unassignNode(nodeId, n.getAttribute(marker), communities); 185 } 186 187 /* 188 * (non-Javadoc) 189 * 190 * @see org.graphstream.stream.Sink#edgeAdded(java.lang.String, long, 191 * java.lang.String, java.lang.String, java.lang.String, boolean) 192 */ 193 @Override 194 public void edgeAdded(String graphId, long timeId, String edgeId, 195 String fromNodeId, String toNodeId, boolean directed) { 196 graphChanged = true; 197 } 198 199 /* 200 * (non-Javadoc) 201 * 202 * @see org.graphstream.stream.Sink#edgeRemoved(java.lang.String, long, 203 * java.lang.String) 204 */ 205 @Override 206 public void edgeRemoved(String graphId, long timeId, String edgeId) { 207 graphChanged = true; 208 } 209 210 /* 211 * (non-Javadoc) 212 * 213 * @see org.graphstream.stream.Sink#graphCleared(java.lang.String, long) 214 */ 215 @Override 216 public void graphCleared(String graphId, long timeId) { 217 graphChanged = true; 218 } 219 220 /* 221 * (non-Javadoc) 222 * 223 * @see org.graphstream.stream.Sink#nodeAttributeAdded(java.lang.String, 224 * long, java.lang.String, java.lang.String, java.lang.Object) 225 */ 226 @Override 227 public void nodeAttributeAdded(String graphId, long timeId, String nodeId, 228 String attribute, Object value) { 229 nodeAttributeChanged(graphId, timeId, nodeId, attribute, null, value); 230 } 231 232 /* 233 * (non-Javadoc) 234 * 235 * @see org.graphstream.stream.Sink#nodeAttributeChanged(java.lang.String, 236 * long, java.lang.String, java.lang.String, java.lang.Object, 237 * java.lang.Object) 238 */ 239 @Override 240 public void nodeAttributeChanged(String graphId, long timeId, 241 String nodeId, String attribute, Object oldValue, Object newValue) { 242 if (attribute.equals(marker) && oldValue != newValue) { 243 unassignNode(nodeId, oldValue, communities); 244 assignNode(nodeId, newValue, communities); 245 } 246 } 247 248 /** 249 * Put the node referred by nodeId to the community referred by newValue in 250 * the assignment referred by assignment. 251 * 252 * @param nodeId 253 * @param newValue 254 * @param assignment 255 */ 256 protected void assignNode(String nodeId, Object newValue, 257 HashMap<Object, HashSet<Node>> assignment) { 258 // A node added, put it in the communities. 259 Node node = graph.getNode(nodeId); 260 if (node != null) { 261 Object communityKey = newValue; 262 263 if (communityKey == null) 264 communityKey = "NULL_COMMUNITY"; 265 HashSet<Node> community = assignment.get(communityKey); 266 267 if (community == null) { 268 community = new HashSet<Node>(); 269 assignment.put(communityKey, community); 270 } 271 community.add(node); 272 273 graphChanged = true; 274 } 275 } 276 277 /** 278 * Remove the node referred by nodeId from the community referred by 279 * oldValue in the assignment referred by assignment. 280 * 281 * @param nodeId 282 * @param oldValue 283 * @param assignment 284 */ 285 protected void unassignNode(String nodeId, Object oldValue, 286 HashMap<Object, HashSet<Node>> assignment) { 287 Node node = graph.getNode(nodeId); 288 if (node != null) { 289 Object communityKey = oldValue; 290 291 if (communityKey == null) 292 communityKey = "NULL_COMMUNITY"; 293 HashSet<Node> community = assignment.get(communityKey); 294 295 assert community != null : "Removing a node that was not placed in any community !!"; 296 297 if (community != null) { 298 community.remove(node); 299 if (community.size() == 0) { 300 assignment.remove(communityKey); 301 } 302 } 303 graphChanged = true; 304 } 305 } 306 307}