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.ArrayList;
035import java.util.List;
036
037import org.graphstream.graph.Edge;
038import org.graphstream.graph.Graph;
039import org.graphstream.graph.Node;
040import org.graphstream.graph.Path;
041
042/**
043 * Implementation of the Bellman-Ford algorithm that computes single-source
044 * shortest paths in a weighted digraph
045 * <p>
046 * The Bellman-Ford algorithm computes single-source shortest paths in a
047 * weighted digraph (where some of the edge weights may be negative). Dijkstra's
048 * algorithm accomplishes the same problem with a lower running time, but
049 * requires edge weights to be non-negative. Thus, Bellman-Ford is usually used
050 * only when there are negative edge weights (from the <a
051 * href="http://en.wikipedia.org/wiki/Bellman-Ford_algorithm">Wikipedia</a>).
052 * </p>
053 * 
054 * <h2>Example</h2>
055 * <pre>
056 * import java.io.IOException;
057 * import java.io.StringReader;
058 * 
059 * import org.graphstream.algorithm.BellmanFord;
060 * import org.graphstream.graph.Graph;
061 * import org.graphstream.graph.implementations.DefaultGraph;
062 * import org.graphstream.stream.file.FileSourceDGS;
063 * 
064 * public class BellmanFordTest {
065 *      
066 *      //     B-(1)-C
067 *      //    /       \
068 *      //  (1)       (10)
069 *      //  /           \
070 *      // A             F
071 *      //  \           /
072 *      //  (1)       (1)
073 *      //    \       /
074 *      //     D-(1)-E
075 *      static String my_graph = 
076 *              "DGS004\n" 
077 *              + "my 0 0\n" 
078 *              + "an A \n" 
079 *              + "an B \n"
080 *              + "an C \n"
081 *              + "an D \n"
082 *              + "an E \n"
083 *              + "an F \n"
084 *              + "ae AB A B weight:1 \n"
085 *              + "ae AD A D weight:1 \n"
086 *              + "ae BC B C weight:1 \n"
087 *              + "ae CF C F weight:10 \n"
088 *              + "ae DE D E weight:1 \n"
089 *              + "ae EF E F weight:1 \n"
090 *              ;
091 *      
092 *      public static void main(String[] args) throws IOException {
093 *              Graph graph = new DefaultGraph("Bellman-Ford Test");
094 *              StringReader reader  = new StringReader(my_graph);
095 *              
096 *              FileSourceDGS source = new FileSourceDGS();
097 *              source.addSink(graph);
098 *              source.readAll(reader);
099 * 
100 *              BellmanFord bf = new BellmanFord("weight","A");
101 *              bf.init(graph);
102 *              bf.compute();
103 * 
104 *              System.out.println(bf.getShortestPath(graph.getNode("F")));
105 *      }
106 * }
107 * </pre>
108 * <h3>Warning</h3>
109 * <p>
110 * This Implementation is only a stub. For the moment only attributes located on
111 * the edges are supported. If you need more features, consider using the
112 * Dijkstra implementation. If you really need that algorithm, please contact
113 * the team members through the mailing list.
114 * </p>
115 * 
116 * @reference Bellman, Richard "On a routing problem", Quarterly of Applied
117 *            Mathematics 16: 87–90. 1958.
118 * 
119 * @complexity O(VxE) time, where V and E are the number of vertices and edges
120 *             respectively.
121 * 
122 * @author Antoine Dutot
123 * @author Yoann Pigné
124 * 
125 */
126public class BellmanFord implements Algorithm {
127
128        /**
129         * The graph to be computed for shortest path.
130         */
131        protected Graph graph;
132
133        /**
134         * ID of the source node.
135         */
136        protected String source_id;
137
138        protected Node source;
139
140        /**
141         * object-level unique string that identifies tags of this instance on a
142         * graph.
143         */
144        protected String identifier;
145        
146        /**
147         * Name of attribute used to get weight of edges.
148         */
149        protected String weightAttribute;
150
151        /**
152         * Build a new BellmanFord algorithm giving the name of the weight attribute
153         * for edges.
154         * 
155         * @param attribute
156         *            weight attribute of edges
157         */
158        public BellmanFord(String attribute) {
159                this(attribute, null);
160        }
161
162        /**
163         * Same that {@link #BellmanFord(String)} but setting the id of the source
164         * node.
165         * 
166         * @param attribute
167         *            weight attribute of edges
168         * @param sourceNode
169         *            id of the source node
170         */
171        public BellmanFord(String attribute, String sourceNode) {
172                this.identifier = this.toString() + "/BellmanFord";
173                this.source_id = sourceNode;
174                this.weightAttribute = attribute;
175        }
176
177        /**
178         * Set the id of the node used as source.
179         * 
180         * @param nodeId
181         *            id of the source node
182         */
183        public void setSource(String nodeId) {
184                if((source_id == null || ! source_id.equals(nodeId)) && graph!=null){
185                        source = graph.getNode(nodeId);
186                }
187                this.source_id = nodeId;        
188        }
189
190        /**
191         * Get the id of node used as source.
192         * 
193         * @return id of the source node
194         */
195        public String getSource() {
196                return source_id;
197        }
198
199        /**
200         * Constructs all the possible shortest paths from the source node to the
201         * destination (end). Warning: this construction is VERY HEAVY !
202         * 
203         * @param end
204         *            The destination to which shortest paths are computed.
205         * @return a list of shortest paths given with
206         *         {@link org.graphstream.graph.Path} objects.
207         */
208        public List<Path> getPathSetShortestPaths(Node end) {
209                ArrayList<Path> paths = new ArrayList<Path>();
210                pathSetShortestPath_facilitate(end, new Path(), paths);
211                return paths;
212        }
213
214        @SuppressWarnings("unchecked")
215        private void pathSetShortestPath_facilitate(Node current, Path path,
216                        List<Path> paths) {
217                Node source = graph.getNode(this.source_id);
218
219                if (current != source) {
220                        Node next = null;
221                        ArrayList<? extends Edge> predecessors = (ArrayList<? extends Edge>) current
222                                        .getAttribute(identifier+".predecessors");
223                        while (current != source && predecessors.size() == 1) {
224                                Edge e = predecessors.get(0);
225                                next = e.getOpposite(current);
226                                path.add(current, e);
227                                current = next;
228                                predecessors = (ArrayList<? extends Edge>) current
229                                                .getAttribute(identifier+".predecessors");
230                        }
231                        if (current != source) {
232                                for (Edge e : predecessors) {
233                                        Path p = path.getACopy();
234                                        p.add(current, e);
235                                        pathSetShortestPath_facilitate(e.getOpposite(current), p,
236                                                        paths);
237
238                                }
239                        }
240                }
241                if (current == source) {
242                        paths.add(path);
243                }
244        }
245
246        /*
247         * (non-Javadoc)
248         * 
249         * @see
250         * org.graphstream.algorithm.Algorithm#init(org.graphstream.graph.Graph)
251         */
252        public void init(Graph graph) {
253                this.graph = graph;
254                if (getSource() != null){
255                        source = graph.getNode(getSource());
256                }
257        }
258        
259        
260        
261        /**
262         * Set the unique identifier for this instance.
263         * 
264         * @see #getIdentifier()
265         * 
266         * @param identifier
267         *            the unique identifier to set
268         */
269        public void setIdentifier(String identifier) {
270                this.identifier = identifier;
271        }
272        
273        /**
274         * The unique identifier of this instance. Used to tag attributes in the graph.
275         * @return the unique identifier of this graph.
276         */
277        public String getIdentifier() {
278                return this.identifier; 
279        }
280
281        /**
282         * Returns the value of the shortest path between the source node and the
283         * given target according to the attribute specified in the constructor. If
284         * <code>target</code> is not in the same connected component as the source
285         * node, then the method returns <code>Double.POSITIVE_INFINITY</code>
286         * (Infinity).
287         * 
288         * @param target
289         *            The endpoint of the path to compute from the source node given
290         *            in the constructor.
291         * @return A numerical value that represent the distance of the shortest
292         *         path.
293         */
294        public double getShortestPathValue(Node target) {
295                Double d = target.getAttribute(identifier+".distance");
296                if (d != null)
297                        return d;
298                return Double.POSITIVE_INFINITY;
299        }
300        
301        /**
302         * Returns the shortest path between the source node and one given target. 
303         * If multiple shortest paths exist, one of them is returned at random.
304         * 
305         * @param target
306         *            the target of the shortest path starting at the source node
307         *            given in the constructor.
308         * @return A {@link org.graphstream.graph.Path} object that constrains the
309         *         list of nodes and edges that constitute it.
310         */
311        @SuppressWarnings("unchecked")
312        public Path getShortestPath(Node target) {
313                Path p = new Path();
314                if (target == source ) {
315                        return p;
316                }
317                boolean noPath = false;
318                Node v = target;
319                while (v != source && !noPath) {
320                        ArrayList<? extends Edge> list = (ArrayList<? extends Edge>) v
321                                        .getAttribute(identifier+".predecessors");
322                        if (list == null) {
323                                noPath = true;
324                        } else {
325                                Edge parentEdge = list.get(0);
326                                p.add(v, parentEdge);
327                                v = parentEdge.getOpposite(v);
328                        }
329                }
330                return p;
331        }
332
333        
334        
335        
336        
337        
338        /*
339         * (non-Javadoc)
340         * 
341         * @see org.graphstream.algorithm.Algorithm#compute()
342         */
343        @SuppressWarnings("unchecked")
344        public void compute() {
345                Node source = graph.getNode(this.source_id);
346
347                // Step 1: Initialize graph
348
349                
350                for (Node n : graph) {
351                        if (n == source)
352                                n.addAttribute(identifier+".distance", 0.0);
353                        else
354                                n.addAttribute(identifier+".distance", Double.POSITIVE_INFINITY);
355
356                        //n.addAttribute(identifier+".predecessors",(Object)null);
357                }
358        
359                
360                // Step 2: relax edges repeatedly
361
362                for (int i = 0; i < graph.getNodeCount(); i++) {
363                        for (Edge e : graph.getEachEdge()) {
364                                Node n0 = e.getNode0();
365                                Node n1 = e.getNode1();
366                                Double d0 = (Double) n0.getAttribute(identifier+".distance");
367                                Double d1 = (Double) n1.getAttribute(identifier+".distance");
368
369                                Double we = (Double) e.getAttribute(weightAttribute);
370                                if (we == null)
371                                        throw new NumberFormatException(
372                                                        "org.graphstream.algorithm.BellmanFord: Problem with attribute \""
373                                                                        + weightAttribute + "\" on edge " + e);
374
375                                if (d0 != null) {
376                                        if (d1 == null || d1 >= d0 + we) {
377                                                n1.addAttribute(identifier+".distance", d0 + we);
378                                                ArrayList<Edge> predecessors = (ArrayList<Edge>) n1
379                                                                .getAttribute(identifier+".predecessors");
380
381                                                if (d1 != null && d1 == d0 + we) {
382                                                        if (predecessors == null) {
383                                                                predecessors = new ArrayList<Edge>();
384                                                        }
385                                                } else {
386                                                        predecessors = new ArrayList<Edge>();
387                                                }
388                                                if (!predecessors.contains(e)) {
389                                                        predecessors.add(e);
390                                                }
391
392                                                n1.addAttribute(identifier+".predecessors",
393                                                                predecessors);
394                                        }
395                                }
396                        }
397                }
398
399                // Step 3: check for negative-weight cycles
400
401                for (Edge e : graph.getEachEdge()) {
402                        Node n0 = e.getNode0();
403                        Node n1 = e.getNode1();
404                        Double d0 = (Double) n0.getAttribute(identifier+".distance");
405                        Double d1 = (Double) n1.getAttribute(identifier+".distance");
406
407                        Double we = (Double) e.getAttribute(weightAttribute);
408
409                        if (we == null) {
410                                throw new NumberFormatException(
411                                                String.format(
412                                                                "%s: Problem with attribute \"%s\" on edge \"%s\"",
413                                                                BellmanFord.class.getName(), weightAttribute,
414                                                                e.getId()));
415                        }
416
417                        if (d1 > d0 + we) {
418                                throw new NumberFormatException(
419                                                String.format(
420                                                                "%s: Problem: negative weight, cycle detected on edge \"%s\"",
421                                                                BellmanFord.class.getName(), e.getId()));
422                        }
423                }
424        }
425}