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 org.graphstream.algorithm.APSP;
035import org.graphstream.algorithm.APSP.APSPInfo;
036import org.graphstream.graph.Graph;
037import org.graphstream.graph.Node;
038
039/**
040 * Compute closeness centrality.
041 * 
042 */
043public class ClosenessCentrality extends AbstractCentrality {
044        public static final String DEFAULT_ATTRIBUTE_KEY = "closeness";
045        
046        /**
047         * Flag indicating if APSP should be computed in this algorithm. If false,
048         * user needs to compute APSP himself to provide {@link APSPInfo} object in
049         * nodes attribute {@link APSPInfo#ATTRIBUTE_NAME}.
050         */
051        protected boolean computeAPSP;
052
053        /**
054         * Flag indicating if computation should use Dangalchev method rather than
055         * the classical method. This method is more adapted for disconnected graph.
056         */
057        protected boolean useDangalchevMethod = false;
058
059        // APSP algorithm if computed in this algorithm.
060        private APSP apsp;
061        
062        /**
063         * Default construtor. Same as calling `ClosenessCentrality("closeness")`.
064         */
065        public ClosenessCentrality() {
066                this(DEFAULT_ATTRIBUTE_KEY);
067        }
068
069        /**
070         * Construtor allowing to configure centrality attribute. Same as calling
071         * `ClosenessCentrality(attribute, false)`.
072         * 
073         * @param attribute
074         *            attribute where centrality will be stored
075         */
076        public ClosenessCentrality(String attribute) {
077                this(attribute, NormalizationMode.NONE);
078        }
079
080        /**
081         * Constructor allowing to configure attribute and normalize flag. Same as
082         * calling `ClosenessCentrality(attribute, normalize, true, false)`.
083         * 
084         * @param attribute
085         *            attribute where centrality will be stored
086         * @param normalize
087         *            defines the normalization mode
088         */
089        public ClosenessCentrality(String attribute, NormalizationMode normalize) {
090                this(attribute, normalize, true, false);
091        }
092
093        /**
094         * Fully configurable construtor.
095         * 
096         * @param centralityAttribute
097         *            attribute where centrality will be stored
098         * @param normalize
099         *            defines the normalization mode
100         * @param computeAPSP
101         *            if true, apsp will be computed in this algorithm
102         * @param useDangalchevMethod
103         *            if true, Dangelchev method will be used in this algorithm
104         */
105        public ClosenessCentrality(String centralityAttribute, NormalizationMode normalize,
106                        boolean computeAPSP, boolean useDangalchevMethod) {
107                super(centralityAttribute, normalize);
108                this.computeAPSP = computeAPSP;
109                this.useDangalchevMethod = useDangalchevMethod;
110        }
111
112        @Override
113        public void init(Graph graph) {
114                super.init(graph);
115                
116                if (computeAPSP) {
117                        apsp = new APSP();
118                        apsp.init(graph);
119                }
120        }
121        
122        /*
123         * (non-Javadoc)
124         * 
125         * @see
126         * org.graphstream.algorithm.measure.AbstractCentrality#computeCentrality()
127         */
128        protected void computeCentrality() {
129                int count = graph.getNodeCount();
130                Node node, other;
131
132                if (computeAPSP)
133                        apsp.compute();
134
135                for (int idx = 0; idx < count; idx++) {
136                        node = graph.getNode(idx);
137                        data[idx] = 0;
138
139                        APSP.APSPInfo info = node.getAttribute(APSPInfo.ATTRIBUTE_NAME);
140
141                        if (info == null)
142                                System.err
143                                                .printf("APSPInfo missing. Did you compute APSP before ?\n");
144
145                        for (int idx2 = 0; idx2 < count; idx2++) {
146                                if (idx != idx2) {
147                                        other = graph.getNode(idx2);
148                                        double d = info.getLengthTo(other.getId());
149
150                                        if (useDangalchevMethod)
151                                                data[idx] += Math.pow(2, -d);
152                                        else {
153                                                if (d < 0)
154                                                        System.err
155                                                                        .printf("Found a negative length value in centroid algorithm. "
156                                                                                        + "Is graph connected ?\n");
157                                                else
158                                                        data[idx] += d;
159                                        }
160                                }
161                        }
162
163                        if (!useDangalchevMethod)
164                                data[idx] = 1 / data[idx];
165                }
166        }
167}