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