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.HashMap;
035
036import org.graphstream.graph.Edge;
037import org.graphstream.graph.Graph;
038import org.graphstream.graph.Node;
039
040/**
041 * This class implements the synchronous version of the
042 * "Epidemic Community Detection Algorithm" as presented by Raghavan <i>et
043 * al</i>.
044 * 
045 * @reference U. N. Raghavan, R. Albert, and S. Kumara, “Near Linear Time Al-
046 *            gorithm to Detect Community Structures in Large-scale Networks,”
047 *            Physical Review E (Statistical, Nonlinear, and Soft Matter
048 *            Physics), vol. 76, no. 3, 2007.
049 * 
050 * @author Guillaume-Jean Herbiet
051 * 
052 */
053public class SyncEpidemicCommunityAlgorithm extends EpidemicCommunityAlgorithm {
054
055        /**
056         * Identify the current iteration of this algorithm to ensure synchronous
057         * behavior.
058         */
059        protected int iteration = 0;
060
061        public SyncEpidemicCommunityAlgorithm() {
062                super();
063        }
064
065        public SyncEpidemicCommunityAlgorithm(Graph graph) {
066                super(graph);
067        }
068
069        public SyncEpidemicCommunityAlgorithm(Graph graph, String marker) {
070                super(graph, marker);
071        }
072
073        @Override
074        public void terminate() {
075                iteration = 0;
076        }
077
078        @Override
079        public void compute() {
080                super.compute();
081                iteration++;
082        }
083
084        @Override
085        public void computeNode(Node node) {
086
087                /*
088                 * Save the node community to previous
089                 */
090                if (node.hasAttribute(marker))
091                        node.setAttribute(marker + ".previous", node.getAttribute(marker));
092
093                /*
094                 * Perform same assignment as in asynchronous mode difference is in the
095                 * redefinition of the communityScores() method
096                 */
097                super.computeNode(node);
098
099                /*
100                 * Save the iteration at which the node was last updated
101                 */
102                node.setAttribute(marker + ".step", iteration);
103        }
104
105        @Override
106        protected void communityScores(Node u) {
107                /*
108                 * Reset the scores for each communities
109                 */
110                communityScores = new HashMap<Object, Double>();
111
112                /*
113                 * Iterate over the nodes that this node "hears"
114                 */
115                for (Edge e : u.getEnteringEdgeSet()) {
116                        Node v = e.getOpposite(u);
117
118                        /*
119                         * Update the count for this community
120                         */
121                        if (v.hasAttribute(marker + ".step")) {
122
123                                /*
124                                 * Set the marker based on the neighbor node current update
125                                 * status
126                                 */
127                                String syncMarker = marker;
128                                int updateStep = ((Integer) v.getAttribute(marker + ".step"))
129                                                .intValue();
130
131                                /*
132                                 * The neighbor node has been updated for this step use the
133                                 * previous marker
134                                 */
135                                if (updateStep == iteration) {
136                                        syncMarker += ".previous";
137                                }
138
139                                /*
140                                 * Update the community score based on the selected marker
141                                 */
142                                if (v.hasAttribute(syncMarker))
143                                        if (communityScores.get(v.getAttribute(syncMarker)) == null)
144                                                communityScores.put(v.getAttribute(syncMarker), 1.0);
145                                        else
146                                                communityScores
147                                                                .put(v.getAttribute(syncMarker),
148                                                                                communityScores.get(v
149                                                                                                .getAttribute(syncMarker)) + 1.0);
150                        }
151                }
152        }
153}