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}