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 = &quot;DGS004\n&quot; + &quot;my 0 0\n&quot; + &quot;an A \n&quot; + &quot;an B \n&quot;
073 *                      + &quot;an C \n&quot; + &quot;an D \n&quot; + &quot;an E \n&quot; + &quot;an F \n&quot; + &quot;an G \n&quot;
074 *                      + &quot;ae AB A B \n&quot; + &quot;ae BC B C \n&quot; + &quot;ae CD C D \n&quot; + &quot;ae DE D E \n&quot;
075 *                      + &quot;ae DF D F \n&quot; + &quot;ae DG D G \n&quot;;
076 * 
077 *      public static void main(String[] args) throws IOException {
078 *              Graph graph = new DefaultGraph(&quot;Centroid Test&quot;);
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(&quot;eccentricity&quot;);
095 * 
096 *                      System.out.printf(&quot;%s is%s in the eccentricity.\n&quot;, n.getId(), in ? &quot;&quot;
097 *                                      : &quot; not&quot;);
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}