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}