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}