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; 033 034import java.util.HashSet; 035 036import org.graphstream.graph.Graph; 037import org.graphstream.graph.Node; 038 039/** 040 * Compute the eccentricity of a connected graph. 041 * 042 * <p> 043 * In a graph G, if d(u,v) is the shortest length between two nodes u and v (ie 044 * the number of edges of the shortest path) let e(u) be the d(u,v) such that v 045 * is the farthest of u. Eccentricity of a graph G is a subgraph induced by 046 * vertices u with minimum e(u). 047 * </p> 048 * 049 * <h2>Requirements</h2> 050 * 051 * <p> 052 * This algorithm needs that APSP algorithm has been computed before its own 053 * computation. 054 * </p> 055 * 056 * <h2>Example</h2> 057 * 058 * <pre> 059 * import java.io.StringReader; 060 * import java.io.IOException; 061 * 062 * import org.graphstream.algorithm.Centroid; 063 * import org.graphstream.graph.Graph; 064 * import org.graphstream.graph.implementations.DefaultGraph; 065 * import org.graphstream.stream.file.FileSourceDGS; 066 * 067 * // +--- E 068 * // A --- B --- C -- D -|--- F 069 * // +--- G 070 * 071 * public class EccentriciyTest { 072 * static String my_graph = "DGS004\n" + "my 0 0\n" + "an A \n" + "an B \n" 073 * + "an C \n" + "an D \n" + "an E \n" + "an F \n" + "an G \n" 074 * + "ae AB A B \n" + "ae BC B C \n" + "ae CD C D \n" + "ae DE D E \n" 075 * + "ae DF D F \n" + "ae DG D G \n"; 076 * 077 * public static void main(String[] args) throws IOException { 078 * Graph graph = new DefaultGraph("Centroid Test"); 079 * StringReader reader = new StringReader(my_graph); 080 * 081 * FileSourceDGS source = new FileSourceDGS(); 082 * source.addSink(graph); 083 * source.readAll(reader); 084 * 085 * APSP apsp = new APSP(); 086 * apsp.init(graph); 087 * apsp.compute(); 088 * 089 * Eccentricity eccentricity = new Eccentricity(); 090 * eccentricity.init(graph); 091 * eccentricity.compute(); 092 * 093 * for (Node n : graph.getEachNode()) { 094 * Boolean in = n.getAttribute("eccentricity"); 095 * 096 * System.out.printf("%s is%s in the eccentricity.\n", n.getId(), in ? "" 097 * : " not"); 098 * } 099 * 100 * // Output will be : 101 * // 102 * // A is not in the eccentricity 103 * // B is not in the eccentricity 104 * // C is in the eccentricity 105 * // D is not in the eccentricity 106 * // E is not in the eccentricity 107 * // F is not in the eccentricity 108 * // G is not in the eccentricity 109 * } 110 * } 111 * </pre> 112 * 113 * @complexity O(n2) 114 * @see org.graphstream.algorithm.APSP.APSPInfo 115 * @reference F. Harary, Graph Theory. Westview Press, Oct. 1969. [Online]. 116 * Available: http://www.amazon.com/exec/obidos/ 117 * redirect?tag=citeulike07-20\&path=ASIN/0201410338 118 */ 119public class Eccentricity implements Algorithm { 120 121 /** 122 * The graph on which centroid is computed. 123 */ 124 protected Graph graph; 125 /** 126 * Attribute in which APSPInfo are stored. 127 */ 128 protected String apspInfoAttribute = APSP.APSPInfo.ATTRIBUTE_NAME; 129 /** 130 * Attribute to store eccentricity information. 131 */ 132 protected String eccentricityAttribute = "eccentricity"; 133 /** 134 * Value of the attribute if node is in the eccentricity. 135 */ 136 protected Object isInEccentricity = Boolean.TRUE; 137 /** 138 * Value of the attribute if node is not in the eccentricity. 139 */ 140 protected Object isNotInEccentricity = Boolean.FALSE; 141 142 /** 143 * Build a new eccentricity algorithm with default parameters. 144 */ 145 public Eccentricity() { 146 this("eccentricity"); 147 } 148 149 /** 150 * Build a new eccentricity algorithm, specifying the attribute name of the 151 * computation result 152 * 153 * @param eccentricityAttribute 154 * attribute name of the computation result. 155 */ 156 public Eccentricity(String eccentricityAttribute) { 157 this(eccentricityAttribute, Boolean.TRUE, Boolean.FALSE); 158 } 159 160 /** 161 * Build a new eccentricity as in {@link #Eccentricity(String)} but 162 * specifying values of eccentricity membership. 163 * 164 * @param eccentricityAttribute 165 * attribute name of the computation result. 166 * @param isInEccentricity 167 * the value of elements eccentricity attribute when this element 168 * is in the eccentricity. 169 * @param isNotInEccentricity 170 * the value of elements eccentricity attribute when this element 171 * is not in the eccentricity. 172 */ 173 public Eccentricity(String eccentricityAttribute, Object isInEccentricity, 174 Object isNotInEccentricity) { 175 this(eccentricityAttribute, Boolean.TRUE, Boolean.FALSE, 176 APSP.APSPInfo.ATTRIBUTE_NAME); 177 } 178 179 /** 180 * Build a new eccentricity algorithm as in 181 * {@link #Eccentricity(String, Object, Object)} but specifying the name of 182 * the attribute where the APSP informations are stored. 183 * 184 * @param eccentricityAttribute 185 * attribute name of the computation result. 186 * @param isInEccentricity 187 * the value of elements eccentricity attribute when this element 188 * is in the eccentricity. 189 * @param isNotInEccentricity 190 * the value of elements eccentricity attribute when this element 191 * is not in the eccentricity. 192 * @param apspInfoAttribute 193 * the name of the attribute where the APSP informations are 194 * stored 195 */ 196 public Eccentricity(String eccentricityAttribute, Object isInEccentricity, 197 Object isNotInEccentricity, String apspInfoAttribute) { 198 this.eccentricityAttribute = eccentricityAttribute; 199 this.isInEccentricity = isInEccentricity; 200 this.isNotInEccentricity = isNotInEccentricity; 201 this.apspInfoAttribute = apspInfoAttribute; 202 } 203 204 /* 205 * (non-Javadoc) 206 * 207 * @see 208 * org.graphstream.algorithm.Algorithm#init(org.graphstream.graph.Graph) 209 */ 210 public void init(Graph graph) { 211 this.graph = graph; 212 } 213 214 /* 215 * (non-Javadoc) 216 * 217 * @see org.graphstream.algorithm.Algorithm#compute() 218 */ 219 public void compute() { 220 double min = Double.MAX_VALUE; 221 HashSet<Node> eccentricity = new HashSet<Node>(); 222 223 for (Node node : graph.getEachNode()) { 224 double m = Double.MIN_VALUE; 225 APSP.APSPInfo info = node.getAttribute(apspInfoAttribute); 226 227 if (info == null) 228 System.err 229 .printf("APSPInfo missing. Did you compute APSP before ?\n"); 230 231 for (Node other : graph.getEachNode()) { 232 if (node != other) { 233 double d = info.getLengthTo(other.getId()); 234 235 if (d < 0) 236 System.err 237 .printf("Found a negative length value in eccentricity algorithm. " 238 + "Is graph connected ?\n"); 239 else if (d > m) 240 m = d; 241 } 242 } 243 244 if (m < min) { 245 eccentricity.clear(); 246 eccentricity.add(node); 247 min = m; 248 } else if (m == min) { 249 eccentricity.add(node); 250 } 251 } 252 253 for (Node node : graph.getEachNode()) 254 node.setAttribute(eccentricityAttribute, eccentricity 255 .contains(node) ? isInEccentricity : isNotInEccentricity); 256 257 eccentricity.clear(); 258 } 259 260 /** 261 * Get the APSP info attribute name. 262 * 263 * @return the name of the attribute where the APSP informations are stored. 264 */ 265 public String getAPSPInfoAttribute() { 266 return apspInfoAttribute; 267 } 268 269 /** 270 * Set the APSP info attribute name. 271 * 272 * @param attribute 273 * the name of the attribute where the APSP informations are 274 * stored. 275 */ 276 public void setAPSPInfoAttribute(String attribute) { 277 apspInfoAttribute = attribute; 278 } 279 280 /** 281 * Get the value of the eccentricity attribute when element is in the 282 * eccentricity. Default value is Boolean.TRUE. 283 * 284 * @return the value of elements eccentricity attribute when this element is 285 * in the eccentricity. 286 */ 287 public Object getIsInEccentricityValue() { 288 return isInEccentricity; 289 } 290 291 /** 292 * Set the value of the eccentricity attribute when element is in the 293 * eccentricity. On computation, this value is used to set the eccentricity 294 * attribute. 295 * 296 * @param value 297 * the value of elements eccentricity attribute when this element 298 * is in the eccentricity. 299 */ 300 public void setIsInEccentricityValue(Object value) { 301 isInEccentricity = value; 302 } 303 304 /** 305 * Get the value of the eccentricity attribute when element is not in the 306 * eccentricity. Default value is Boolean.FALSE. 307 * 308 * @return the value of elements eccentricity attribute when this element is 309 * not in the eccentricity. 310 */ 311 public Object getIsNotInEccentricityValue() { 312 return isNotInEccentricity; 313 } 314 315 /** 316 * Set the value of the eccentricity attribute when element is not in the 317 * eccentricity. On computation, this value is used to set the eccentricity 318 * attribute. 319 * 320 * @param value 321 * the value of elements eccentricity attribute when this element 322 * is not in the eccentricity. 323 */ 324 public void setIsNotInEccentricityValue(Object value) { 325 isNotInEccentricity = value; 326 } 327 328 /** 329 * Get the name of the attribute where computation result is stored. Value 330 * of this attribute can be {@link #getIsInEccentricityValue()} if the 331 * element is in the eccentricity, {@link #getIsNotInEccentricityValue()} 332 * else. 333 * 334 * @return the eccentricity attribute name. 335 */ 336 public String getEccentricityAttribute() { 337 return eccentricityAttribute; 338 } 339 340 /** 341 * Set the name of the attribute where computation result is stored. 342 * 343 * @param eccentricityAttribute 344 * the name of the element attribute where computation result is 345 * stored. 346 */ 347 public void setEccentricityAttribute(String eccentricityAttribute) { 348 this.eccentricityAttribute = eccentricityAttribute; 349 } 350}