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.Iterator; 035 036import org.graphstream.graph.Edge; 037import org.graphstream.graph.Graph; 038 039/** 040 * Base for spanning tree algorithms. 041 * 042 * <p> 043 * The result is stored in an edge attribute which name is defined by 044 * {@link #flagAttribute} and value is {@link #flagOn} if the edge is in the 045 * tree or {@link #flagOff} if not. If {@link #flagAttribute} is {@code null} 046 * nothing is stored in the edges. If {@link #flagOn} is {@code null} edges in 047 * the tree are not tagged. If {@link #flagOff} is {@code null} edges out of the 048 * tree are not tagged. 049 * </p> 050 * 051 * 052 * <h2>Creating a spanning tree algorithm</h2> 053 * 054 * <p> 055 * Spanning tree algorithms have to extend this class and to implements the 056 * {@link #makeTree()} and {@link #getTreeEdgesIterator()} methods. 057 * {@link #edgeOn(Edge)} and {@link #edgeOff(Edge)} methods have to be used to 058 * properly tag edges. 059 * </p> 060 * 061 * <p> 062 * A call to compute reset the values of edges attribute. Then a call to 063 * {@link #makeTree()} is made. 064 * </p> 065 * 066 * <h2>Highlight the spanning tree in viewer</h2> 067 * 068 * <p> 069 * Using the CSS, it is possible to highlight the spanning tree result using 070 * classes. Considering two css edge classes have been defined in the CSS, for 071 * example : 072 * 073 * <pre> 074 * edge .in { 075 * size: 3px; 076 * fill-color: black; 077 * } 078 * 079 * edge .notin { 080 * size: 2px; 081 * fill-color: gray; 082 * } 083 * </pre> 084 * 085 * <p> 086 * You can tell the algorithm to set up the value of the "ui.class" attribute of 087 * edges to "in" when the edge is in the tree or "notin" when edge is not in the 088 * tree. 089 * </p> 090 * 091 * <p> 092 * This can be done by setting the {@link #flagAttribute} of the algorithm using 093 * the setter {@link #setFlagAttribute(String)} and the flag values 094 * {@link #flagOn} and {@link #flagOff} with {@link #setFlagOn(Object)} and 095 * {@link #setFlagOff(Object)} setters. 096 * </p> 097 * 098 * <pre> 099 * Graph graph = ...; 100 * AbstractSpanningTree sp = ...; 101 * 102 * ... 103 * 104 * sp.setFlagAttribute("ui.class"); 105 * sp.setFlagOn("in"); 106 * sp.setFlagOff("notin"); 107 * 108 * sp.init(graph); 109 * sp.compute(); 110 * 111 * graph.display(); 112 * 113 * .. 114 * </pre> 115 */ 116public abstract class AbstractSpanningTree implements SpanningTree { 117 /** 118 * The graph on which algorithm try to extract a spanning tree. 119 */ 120 protected Graph graph; 121 122 /** 123 * Attribute which will be used to set is an edge is in the spanning tree or 124 * not. 125 */ 126 protected String flagAttribute; 127 128 /** 129 * Value of the <i>flagAttribute</i> if the edge is in the spanning tree. 130 */ 131 protected Object flagOn; 132 133 /** 134 * Value of the <i>flagAttribute</i> if the edge is not in the spanning 135 * tree. 136 */ 137 protected Object flagOff; 138 139 /** 140 * Create a new SpanningTree algorithm. By default edges are not tagged. 141 */ 142 public AbstractSpanningTree() { 143 this(null, null, null); 144 } 145 146 /** 147 * Create a new SpanningTree algorithm. Default flag attribute values are 148 * {@code true} for edges in the tree and {@code false} for the remaining 149 * edges. 150 * 151 * @param flagAttribute 152 * attribute used to compare edges 153 */ 154 public AbstractSpanningTree(String flagAttribute) { 155 this(flagAttribute, true, false); 156 } 157 158 /** 159 * Create a new SpanningTree algorithm. 160 * 161 * @param flagAttribute 162 * attribute used to set if an edge is in the spanning tree 163 * @param flagOn 164 * value of the <i>flagAttribute</i> if edge is in the spanning 165 * tree 166 * @param flagOff 167 * value of the <i>flagAttribute</i> if edge is not in the 168 * spanning tree 169 */ 170 public AbstractSpanningTree(String flagAttribute, Object flagOn, 171 Object flagOff) { 172 graph = null; 173 this.flagAttribute = flagAttribute; 174 this.flagOn = flagOn; 175 this.flagOff = flagOff; 176 } 177 178 /* (non-Javadoc) 179 * @see org.graphstream.algorithm.SpanningTree#getFlagAttribute() 180 */ 181 public String getFlagAttribute() { 182 return flagAttribute; 183 } 184 185 /* (non-Javadoc) 186 * @see org.graphstream.algorithm.SpanningTree#setFlagAttribute(java.lang.String) 187 */ 188 public void setFlagAttribute(String flagAttribute) { 189 if (graph != null) 190 throw new IllegalStateException( 191 "Flag attribute can be set only before the algorithm is initialized"); 192 this.flagAttribute = flagAttribute; 193 } 194 195 196 /* (non-Javadoc) 197 * @see org.graphstream.algorithm.SpanningTree#getFlagOn() 198 */ 199 public Object getFlagOn() { 200 return flagOn; 201 } 202 203 /* (non-Javadoc) 204 * @see org.graphstream.algorithm.SpanningTree#setFlagOn(java.lang.Object) 205 */ 206 public void setFlagOn(Object flagOn) { 207 if (graph != null) 208 throw new IllegalStateException( 209 "Flag values can be set only before the algorithm is initialized"); 210 this.flagOn = flagOn; 211 } 212 213 /* (non-Javadoc) 214 * @see org.graphstream.algorithm.SpanningTree#getFlagOff() 215 */ 216 public Object getFlagOff() { 217 return flagOff; 218 } 219 220 /* (non-Javadoc) 221 * @see org.graphstream.algorithm.SpanningTree#setFlagOff(java.lang.Object) 222 */ 223 public void setFlagOff(Object flagOff) { 224 if (graph != null) 225 throw new IllegalStateException( 226 "Flag values can be set only before the algorithm is initialized"); 227 this.flagOff = flagOff; 228 } 229 230 // Protected Access 231 232 /** 233 * Add an edge to the spanning tree. 234 * 235 * @param e 236 * edge to add 237 */ 238 protected void edgeOn(Edge e) { 239 if (flagAttribute != null) { 240 if (flagOn != null) 241 e.changeAttribute(flagAttribute, flagOn); 242 else 243 e.removeAttribute(flagAttribute); 244 } 245 } 246 247 /** 248 * Remove an edge of the spanning tree. 249 * 250 * @param e 251 * edge to remove 252 */ 253 protected void edgeOff(Edge e) { 254 if (flagAttribute != null) { 255 if (flagOff != null) 256 e.changeAttribute(flagAttribute, flagOff); 257 else 258 e.removeAttribute(flagAttribute); 259 } 260 } 261 262 /** 263 * Reset flag attribute values. All edges are tagged as being out of the 264 * tree. 265 */ 266 protected void resetFlags() { 267 for (Edge edge : graph.getEachEdge()) 268 edgeOff(edge); 269 } 270 271 // Abstract methods to be implemented by subclasses 272 273 /** 274 * Method that will be implemented by spanning tree's algorithms to build 275 * the tree. 276 */ 277 protected abstract void makeTree(); 278 279 /* (non-Javadoc) 280 * @see org.graphstream.algorithm.SpanningTree#getTreeEdgesIterator() 281 */ 282 public abstract <T extends Edge> Iterator<T> getTreeEdgesIterator(); 283 284 /* (non-Javadoc) 285 * @see org.graphstream.algorithm.SpanningTree#getTreeEdges() 286 */ 287 public <T extends Edge> Iterable<T> getTreeEdges() { 288 return new Iterable<T>() { 289 public Iterator<T> iterator() { 290 return getTreeEdgesIterator(); 291 } 292 }; 293 } 294 295 /* (non-Javadoc) 296 * @see org.graphstream.algorithm.SpanningTree#clear() 297 */ 298 public void clear() { 299 if (flagAttribute != null) 300 for (Edge edge : graph.getEachEdge()) 301 edge.removeAttribute(flagAttribute); 302 } 303 304 // Algorithm interface 305 306 /* 307 * (non-Javadoc) 308 * 309 * @see 310 * org.graphstream.algorithm.Algorithm#init(org.graphstream.graph.Graph) 311 */ 312 public void init(Graph graph) { 313 this.graph = graph; 314 } 315 316 /* 317 * (non-Javadoc) 318 * 319 * @see org.graphstream.algorithm.Algorithm#compute() 320 */ 321 public void compute() { 322 if (this.graph == null) { 323 return; 324 } 325 326 resetFlags(); 327 makeTree(); 328 } 329}