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.*;
035
036import org.graphstream.graph.Edge;
037import org.graphstream.graph.Graph;
038import org.graphstream.graph.Node;
039import org.graphstream.graph.Path;
040import org.graphstream.stream.SinkAdapter;
041
042/**
043 * All-pair shortest paths lengths.
044 * 
045 * <p>
046 * This class implements the Floyd-Warshall all pair shortest path algorithm
047 * where the shortest path from any node to any destination in a given weighted
048 * graph (with positive or negative edge weights) is performed.
049 * </p>
050 * <p>
051 * The computational complexity is O(n^3), this may seems a very large, however
052 * this algorithm may perform better than running several Dijkstra on all node
053 * pairs of the graph (that would be of complexity O(n^2 log(n))) when the graph
054 * becomes dense.
055 * </p>
056 * <p>
057 * Note that all the possible paths are not explicitly computed and stored.
058 * Instead, the weight is computed and a data structure similar to network
059 * routing tables is created directly on the graph. This allows a linear
060 * reconstruction of the wanted paths, on demand, minimizing the memory
061 * consumption.
062 * </p>
063 * <p>
064 * For each node of the graph, a {@link org.graphstream.algorithm.APSP.APSPInfo} attribute is stored. The name of
065 * this attribute is {@link org.graphstream.algorithm.APSP.APSPInfo#ATTRIBUTE_NAME}.
066 * </p>
067 * <h2>Usage</h2>
068 * <p>
069 * The implementation of this algorithm is made with two main classes that
070 * reflect the two main steps of the algorithm that are:
071 * </p>
072 * <ol>
073 * <li>compute pairwise weights for all nodes;</li>
074 * <li>retrieve actual paths from some given sources to some given destinations.
075 * </li>
076 * </ol>
077 * 
078 * <p>
079 * For the first step (the real shortest path computation) you need to create an
080 * APSP object with 3 parameters:
081 * </p>
082 * 
083 * <ul>
084 * <li>a reference to the graph to be computed;</li>
085 * <li>a string that indicates the name of the attribute to consider for the
086 * weighting;</li>
087 * <li>a boolean that indicates whether the computation considers edges
088 * direction or not.</li>
089 * </ul>
090 * 
091 * <p>
092 * Those 3 parameters can be set in a ran in the constructor
093 * {@link #APSP(Graph,String,boolean)} or by using separated setters (see example
094 * below).
095 * </p>
096 * <p>
097 * Then the actual computation takes place by calling the {@link #compute()} method
098 * which is implemented from the "Algorithm" interface. This method actually
099 * does the computation.
100 * </p>
101 * <p>
102 * Secondly, when the weights are computed, one can retrieve paths with the help
103 * of another class: "APSPInfo". Such object are stored in each node and hold
104 * routing tables that can help rebuild shortest paths.
105 * </p>
106 * <p>
107 * Retrieving an "APSPInfo" instance from a node is done for instance for a
108 * node of id "F", like this::
109 * </p>
110 * 
111 * <pre>
112 * APSPInfo info = graph.getNode("F").getAttribute(APSPInfo.ATTRIBUTE_NAME);
113 * </pre>
114 * <p>
115 * then the shortest path from a "F" to another node (say "A") is given by::
116 * </p>
117 * 
118 * <pre>
119 * info.getShortestPathTo("A")
120 * </pre>
121 * 
122 * 
123 * <h2>Example</h2>
124 * 
125 * <pre>
126 * import java.io.ByteArrayInputStream;
127 * import java.io.IOException;
128 * 
129 * import org.graphstream.algorithm.APSP;
130 * import org.graphstream.algorithm.APSP.APSPInfo;
131 * import org.graphstream.graph.Graph;
132 * import org.graphstream.graph.implementations.DefaultGraph;
133 * import org.graphstream.stream.file.FileSourceDGS;
134 * 
135 * public class APSPTest {
136 * 
137 * //     B-(1)-C
138 * //    /       \
139 * //  (1)       (10)
140 * //  /           \
141 * // A             F
142 * //  \           /
143 * //  (1)       (1)
144 * //    \       /
145 * //     D-(1)-E
146 * 
147 *      static String my_graph = "DGS004\n" 
148 *                      + "my 0 0\n" 
149 *                      + "an A \n" 
150 *                      + "an B \n"
151 *                      + "an C \n" 
152 *                      + "an D \n" 
153 *                      + "an E \n" 
154 *                      + "an F \n"
155 *                      + "ae AB A B weight:1 \n" 
156 *                      + "ae AD A D weight:1 \n"
157 *                      + "ae BC B C weight:1 \n" 
158 *                      + "ae CF C F weight:10 \n"
159 *                      + "ae DE D E weight:1 \n" 
160 *                      + "ae EF E F weight:1 \n";
161 * 
162 *      public static void main(String[] args) throws IOException {
163 *              Graph graph = new DefaultGraph("APSP Test");
164 *              ByteArrayInputStream bs = new ByteArrayInputStream(my_graph.getBytes());
165 * 
166 *              FileSourceDGS source = new FileSourceDGS();
167 *              source.addSink(graph);
168 *              source.readAll(bs);
169 * 
170 *              APSP apsp = new APSP();
171 *              apsp.init(graph); // registering apsp as a sink for the graph
172 *              apsp.setDirected(false); // undirected graph
173 *              apsp.setWeightAttributeName("weight"); // ensure that the attribute name
174 *                                                                                              // used is "weight"
175 *              apsp.compute(); // the method that actually computes shortest paths
176 * 
177 *              APSPInfo info = graph.getNode("F")
178 *                              .getAttribute(APSPInfo.ATTRIBUTE_NAME);
179 *              System.out.println(info.getShortestPathTo("A"));
180 *      }
181 * }
182 * </pre>
183 * 
184 * <h2>Other Features</h2>
185 * 
186 * <h3>Digraphs</h3>
187 * <p>
188 * This algorithm can use directed graphs and only compute paths according to
189 * this direction. You can choose to ignore edge orientation by calling
190 * {@link #setDirected(boolean)} method with "false" as value (or use the
191 * appropriate constructor).
192 * </p>
193 * 
194 * 
195 * <h2>Shortest Paths with weighted edges</2>
196 * <p>
197 * You can also specify that edges have "weights" or "importance" that value
198 * them. You store these values as attributes on the edges. The default name for
199 * these attributes is "weight" but you can specify it using the
200 * {@link #setWeightAttributeName(String)} method (or by using the appropriate
201 * constructor). The weight attribute must contain an object that implements
202 * java.lang.Number.
203 * </p>
204 * 
205 * <h2>How shortest paths are stored in the graph?</h2>
206 * <p>
207 * All the shortest paths are not literally stored in the graph because it would
208 * require to much memory to do so. Instead, only useful data, allowing the fast
209 * reconstruction of any path, is stored. The storage approach is alike network
210 * routing tables where each node maintains a list of all possible targets
211 * linked with the next hop neighbor to go through.
212 * </p>
213 * <p>
214 * Technically, on each node, for each target, we only store the target node
215 * name and if the path is made of more than one edge, one "pass-by" node. As
216 * all shortest path that is made of more than one edge is necessarily made of
217 * two other shortest paths, it is easy to reconstruct a shortest path between
218 * two arbitrary nodes knowing only a pass-by node. This approach still stores a
219 * lot of data on the graph, however far less than if we stored complete paths.
220 * </p>
221 * 
222 * @complexity O(n^3) with n the number of nodes.
223 * 
224 * @reference Floyd, Robert W. "Algorithm 97: Shortest Path". Communications of
225 *            the ACM 5 (6): 345. doi:10.1145/367766.368168. 1962.
226 * @reference Warshall, Stephen. "A theorem on Boolean matrices". Journal of the
227 *            ACM 9 (1): 11–12. doi:10.1145/321105.321107. 1962.
228 * 
229 */
230public class APSP extends SinkAdapter implements Algorithm {
231        // Attribute
232
233        /**
234         * The graph to use.
235         */
236        protected Graph graph;
237
238        /**
239         * Does the graph changed between two calls to {@link #compute()}?.
240         */
241        protected boolean graphChanged = false;
242
243        /**
244         * If false, do not take edge orientation into account.
245         */
246        protected boolean directed = true;
247
248        /**
249         * Name of the attribute on each edge indicating the weight of the edge.
250         * This attribute must contain a descendant of Number.
251         */
252        protected String weightAttributeName;
253        
254        protected Progress progress = null;
255
256        // Construction
257
258        public APSP() {
259                this(null);
260        }
261
262        /**
263         * New APSP algorithm working on the given graph. The edge weight attribute
264         * name by default is "weight" and edge orientation is taken into account.
265         * 
266         * @param graph
267         *            The graph to use.
268         */
269        public APSP(Graph graph) {
270                this(graph, "weight", true);
271        }
272
273        /**
274         * New APSP algorithm working on the given graph. To fetch edges importance,
275         * the algorithm use the given string as attribute name for edge weights.
276         * Weights must be a descendant of Number.
277         * 
278         * @param graph
279         *            The graph to use.
280         * @param weightAttributeName
281         *            The edge weight attribute name.
282         * @param directed
283         *            If false, edge orientation is ignored.
284         */
285        public APSP(Graph graph, String weightAttributeName, boolean directed) {
286                this.graph = graph;
287                this.weightAttributeName = weightAttributeName;
288                this.directed = directed;
289
290                init(graph);
291        }
292
293        // Access
294
295        /**
296         * True if the algorithm must take edge orientation into account.
297         * 
298         * @return True if directed.
299         */
300        public boolean isDirected() {
301                return directed;
302        }
303
304        /**
305         * The name of the attribute to use for retrieving edge weights.
306         * 
307         * @return An attribute name.
308         */
309        public String getWeightAttributeName() {
310                return weightAttributeName;
311        }
312
313        /**
314         * Access to the working graph.
315         * 
316         * @return graph being used
317         */
318        public Graph getGraph() {
319                return graph;
320        }
321
322        // Commands
323
324        /**
325         * Choose to use or ignore edge orientation.
326         * 
327         * @param on
328         *            If true edge orientation is used.b
329         */
330        public void setDirected(boolean on) {
331                directed = on;
332        }
333
334        /**
335         * Specify an interface to call in order to indicate the algorithm progress.
336         * Pass null to remove the progress indicator. The progress indicator will
337         * be called regularly to indicate the computation progress.
338         */
339        public void registerProgressIndicator(Progress progress) {
340                this.progress = progress;
341        }
342
343        /**
344         * Choose the name of the attribute used to retrieve edge weights. Edge
345         * weights attribute must contain a value that inherit Number.
346         * 
347         * @param name
348         *            The attribute name.
349         */
350        public void setWeightAttributeName(String name) {
351                weightAttributeName = name;
352        }
353
354        /**
355         * @see Algorithm#init(Graph)
356         */
357        public void init(Graph graph) {
358                if (this.graph != null)
359                        this.graph.removeSink(this);
360
361                this.graph = graph;
362
363                if (this.graph != null){
364                        graphChanged = true;
365                        this.graph.addSink(this);
366                }
367        }
368
369        /**
370         * Run the APSP computation. When finished, the graph is equipped with
371         * specific attributes of type
372         * {@link org.graphstream.algorithm.APSP.APSPInfo}. These attributes contain
373         * a map of length toward each other attainable node. The attribute name is
374         * given by {@link org.graphstream.algorithm.APSP.APSPInfo#ATTRIBUTE_NAME}.
375         * 
376         * @complexity O(n^3) where n is the number of nodes in the graph.
377         */
378        public void compute() {
379                if (graphChanged) {
380                        // Make a list of all nodes, and equip them with APSP informations.
381                        // The APSPInfo constructor add in each info item all the paths from
382                        // the node to all its neighbour. It set the distance to 1 if there
383                        // are no weights on edges.
384
385                        ArrayList<Node> nodeList = new ArrayList<Node>();
386
387                        for (Node node : graph) {
388                                node.addAttribute(APSPInfo.ATTRIBUTE_NAME, new APSPInfo(node,
389                                                weightAttributeName, directed));
390                                nodeList.add(node);
391                        }
392
393                        // The Floyd-Warshall algorithm. You can easily see it is in O(n^3)..
394
395                        // int z = 0;
396                        double prog = 0;
397                        double max  = nodeList.size();
398                        max *= max;
399
400                        for (Node k : nodeList) {
401                                for (Node i : nodeList) {
402                                        for (Node j : nodeList) {
403                                                APSPInfo I = (APSPInfo) i.getAttribute(
404                                                                APSPInfo.ATTRIBUTE_NAME, APSPInfo.class);
405                                                APSPInfo J = (APSPInfo) j.getAttribute(
406                                                                APSPInfo.ATTRIBUTE_NAME, APSPInfo.class);
407                                                APSPInfo K = (APSPInfo) k.getAttribute(
408                                                                APSPInfo.ATTRIBUTE_NAME, APSPInfo.class);
409
410                                                double Dij = I.getLengthTo(J.source.getId());
411                                                double Dik = I.getLengthTo(K.source.getId());
412                                                double Dkj = K.getLengthTo(J.source.getId());
413
414                                                // Take into account non-existing paths.
415
416                                                if (Dik >= 0 && Dkj >= 0) {
417                                                        double sum = Dik + Dkj;
418
419                                                        if (Dij >= 0) {
420                                                                if (sum < Dij) {
421                                                                        I.setLengthTo(J, sum, K);
422                                                                }
423                                                        } else {
424                                                                I.setLengthTo(J, sum, K);
425                                                        }
426                                                }
427                                        }
428                                        
429                                        if (progress != null)
430                                                progress.progress(prog / max);
431                                        
432                                        prog += 1;
433                                }
434
435                                // z++;
436                                // System.err.printf( "%3.2f%%%n", (z/((double)n))*100 );
437                        }
438                }
439
440                graphChanged = false;
441        }
442
443        /**
444         * Information stored on each node of the graph giving the length of the
445         * shortest paths toward each other node.
446         */
447        public static class APSPInfo {
448                public static final String ATTRIBUTE_NAME = "APSPInfo";
449
450                /**
451                 * The start node name. This information is stored inside this node.
452                 */
453                public Node source;
454
455                /**
456                 * Maximum number of hops to attain another node in the graph from the
457                 * "from" node.
458                 * XXX this is the maximum value seen during compute not the maximum shortest path XXX
459                 */
460                public double maxLength = Double.MIN_VALUE;
461
462                /**
463                 * Minimum number of hops to attain another node in the graph from the
464                 * "from" node.
465                 * XXX this is the minimum value seen during compute not the minimum shortest path XXX
466                 */
467                public double minLength = Double.MAX_VALUE;
468
469                /**
470                 * Shortest paths toward all other accessible nodes.
471                 */
472                public HashMap<String, TargetPath> targets = new HashMap<String, TargetPath>();
473
474                /**
475                 * Create the new information and put in it all the paths between this
476                 * node and all its direct neighbours.
477                 * 
478                 * @param node
479                 *            The node to start from.
480                 * @param weightAttributeName
481                 *            The key used to retrieve the weight attributes of edges.
482                 *            This attribute but store a value that inherit Number.
483                 * @param directed
484                 *            If false, the edge orientation is not taken into account.
485                 */
486                public APSPInfo(Node node, String weightAttributeName, boolean directed) {
487                        double weight = 1;
488                        Iterable<? extends Edge> edges = node.getLeavingEdgeSet();
489
490                        source = node;
491
492                        if (!directed)
493                                edges = node.getEdgeSet();
494
495                        for (Edge edge : edges) {
496                                Node other = edge.getOpposite(node);
497
498                                if (edge.hasAttribute(weightAttributeName))
499                                        weight = edge.getNumber(weightAttributeName);
500
501                                targets.put(other.getId(), new TargetPath(other, weight, null));
502                        }
503                }
504
505                /**
506                 * The node represented by this APSP information.
507                 * 
508                 * @return A node identifier.
509                 */
510                public String getNodeId() {
511                        return source.getId();
512                }
513
514                /**
515                 * Minimum distance between this node and another. This returns -1 if
516                 * there is no path stored yet between these two nodes.
517                 * 
518                 * @param other
519                 *            The other node identifier.
520                 * @return The distance or -1 if no path is stored yet between the two
521                 *         nodes.
522                 */
523                public double getLengthTo(String other) {
524                        if (targets.containsKey(other))
525                                return targets.get(other).distance;
526
527                        return -1;
528                }
529
530                /**
531                 * The minimum distance between this node and another.
532                 * XXX this is the minimum value seen during compute not the minimum shortest path XXX
533                 * 
534                 * @return A distance.
535                 */
536                public double getMinimumLength() {
537                        return minLength;
538                }
539
540                /**
541                 * The maximum distance between this node and another.
542                 * XXX this is the maximum value seen during compute not the maximum shortest path XXX
543                 * 
544                 * @return A distance.
545                 */
546                public double getMaximumLength() {
547                        return maxLength;
548                }
549
550                /**
551                 * Add or change the length between this node and another and update the
552                 * minimum and maximum lengths seen so far.
553                 * 
554                 * @param other
555                 *            The other node APSP info.
556                 * @param length
557                 *            The new minimum path lengths between these nodes.
558                 */
559                public void setLengthTo(APSPInfo other, double length, APSPInfo passBy) {
560                        targets.put(other.source.getId(), new TargetPath(other.source,
561                                        length, passBy));
562
563                        if (length < minLength)
564                                minLength = length;
565
566                        if (length > maxLength)
567                                maxLength = length;
568                }
569
570                public Path getShortestPathTo(String other) {
571                        TargetPath tpath = targets.get(other);
572
573                        // XXX Probably a bug here in the Path class usage.
574                        // TODO update this to create an edge path to be compatible with
575                        // multi-graphs.
576
577                        if (tpath != null) {
578                                Path path = new Path(); // XXX use the Path object directly.
579                                ArrayList<Node> nodePath = new ArrayList<Node>();
580
581                                nodePath.add(source);
582                                nodePath.add(tpath.target);
583
584                                // Recursively build the path between the source and target node
585                                // by exploring pass-by nodes.
586
587                                expandPath(1, this, tpath, nodePath);
588
589                                // Build a Path object.
590
591                                for (int i = 0; i < nodePath.size() - 1; ++i) {
592                                        // XXX XXX complicated ?
593
594                                        path.add(
595                                                        nodePath.get(i),
596                                                        nodePath.get(i).getEdgeToward(
597                                                                        nodePath.get(i + 1).getId()));
598                                }
599
600                                return path;
601                        }
602
603                        return null;
604                }
605
606                protected int expandPath(int pos, APSPInfo source, TargetPath path,
607                                ArrayList<Node> nodePath) {
608                        // result = will contain the expanded path.
609                        // source = A.
610                        // path.passBy = X.
611                        // path.target = B.
612                        // pos = position of insertion of X inside result.
613
614                        if (path.passBy != null) {
615                                // We want to insert X between A and B.
616
617                                nodePath.add(pos, path.passBy.source);
618
619                                // We build paths between A and X and between X and B.
620
621                                TargetPath path1 = source.targets.get(path.passBy.source
622                                                .getId());      // path from A -> X
623                                TargetPath path2 = path.passBy.targets.get(path.target.getId());
624                                                                        // path from X -> B
625
626                                // Now we recurse the path expansion.
627
628                                int added1 = expandPath(pos, source, path1, nodePath);
629                                int added2 = expandPath(pos + 1 + added1, path.passBy, path2,
630                                                nodePath);
631
632                                // Return the number of elements added at pos.
633
634                                return added1 + added2 + 1;
635                        } else {
636                                // These is no more intermediary node X, stop the recursion.
637
638                                return 0;
639                        }
640                }
641        }
642
643        /**
644         * Description of a path to a target node.
645         * 
646         * <p>
647         * This class is made to be used by the APSPInfo class, which references a
648         * source node. This class describes a target node, the length of the
649         * shortest path to it and, if the path is made of more than only one edge,
650         * an intermediary node (pass-by), used to reconstruct recursively the
651         * shortest path.
652         * </p>
653         * 
654         * <p>
655         * This representation avoids to store each node of each shortest path,
656         * since this would consume a too large memory area. This way, a shortest
657         * path is stored at constant size (this is possible since we computed all
658         * the shortest paths and, knowing that a path of more than one edge is
659         * always made of the sum of two shortest paths, and knowing only one
660         * "pass-by" node in the shortest path, it is possible to rebuild it).
661         * </p>
662         */
663        public static class TargetPath {
664                /**
665                 * A distant other node.
666                 */
667                public Node target;
668
669                /**
670                 * The distance to this other node.
671                 */
672                public double distance;
673
674                /**
675                 * An intermediary other node on the minimum path to the other node.
676                 * Used to reconstruct the path between two nodes.
677                 */
678                public APSPInfo passBy;
679
680                public TargetPath(Node other, double distance, APSPInfo passBy) {
681                        this.target = other;
682                        this.distance = distance;
683                        this.passBy = passBy;
684                }
685        }
686
687        // Sink implementation
688
689        @Override
690        public void nodeAdded(String graphId, long timeId, String nodeId) {
691                graphChanged = true;
692        }
693
694        @Override
695        public void nodeRemoved(String graphId, long timeId, String nodeId) {
696                graphChanged = true;
697        }
698
699        @Override
700        public void edgeAdded(String graphId, long timeId, String edgeId,
701                        String fromNodeId, String toNodeId, boolean directed) {
702                graphChanged = true;
703        }
704
705        @Override
706        public void edgeRemoved(String graphId, long timeId, String edgeId) {
707                graphChanged = true;
708        }
709
710        @Override
711        public void graphCleared(String graphId, long timeId) {
712                graphChanged = true;
713        }
714
715        @Override
716        public void edgeAttributeAdded(String graphId, long timeId, String edgeId,
717                        String attribute, Object value) {
718                if (attribute.equals(weightAttributeName)) {
719                        graphChanged = true;
720                }
721        }
722
723        @Override
724        public void edgeAttributeChanged(String graphId, long timeId,
725                        String edgeId, String attribute, Object oldValue, Object value) {
726                if (attribute.equals(weightAttributeName)) {
727                        graphChanged = true;
728                }
729        }
730
731        /**
732         * Interface allowing to be notified of the algorithm progress.
733         */
734        public interface Progress {
735                /**
736                 * Progress of the algorithm.
737                 * 
738                 * @param percent
739                 *            a value between 0 and 1, 0 meaning 0% and 1 meaning 100%.
740                 */
741                void progress(double percent);
742        }
743}