001/* Copyright (C) 2013 TU Dortmund
002 * This file is part of AutomataLib, http://www.automatalib.net/.
003 * 
004 * AutomataLib is free software; you can redistribute it and/or
005 * modify it under the terms of the GNU Lesser General Public
006 * License version 3.0 as published by the Free Software Foundation.
007 * 
008 * AutomataLib is distributed in the hope that it will be useful,
009 * but WITHOUT ANY WARRANTY; without even the implied warranty of
010 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
011 * Lesser General Public License for more details.
012 * 
013 * You should have received a copy of the GNU Lesser General Public
014 * License along with AutomataLib; if not, see
015 * http://www.gnu.de/documents/lgpl.en.html.
016 */
017package net.automatalib.algorithms.graph.sssp;
018
019import java.util.ArrayList;
020import java.util.Collections;
021import java.util.List;
022
023import net.automatalib.algorithms.graph.GraphAlgorithms;
024import net.automatalib.commons.smartcollections.BinaryHeap;
025import net.automatalib.commons.smartcollections.ElementReference;
026import net.automatalib.commons.smartcollections.SmartDynamicPriorityQueue;
027import net.automatalib.commons.util.mappings.MutableMapping;
028import net.automatalib.graphs.Graph;
029import net.automatalib.graphs.concepts.EdgeWeights;
030
031
032/**
033 * Implementation of Dijkstras algorithm for the single-source shortest path
034 * problem.
035 * 
036 * @author Malte Isberner <malte.isberner@gmail.com>
037 *
038 * @param <N> node class
039 * @param <E> edge class
040 */
041public class DijkstraSSSP<N,E> implements SSSPResult<N,E> {
042        
043        /*
044         * Internal data record
045         */
046        private static final class Record<N,E> implements Comparable<Record<N,E>> {
047                public final N node;
048                public float dist;
049                public ElementReference ref;
050                public E reach;
051                public Record<N,E> parent;
052                int depth;
053                
054                
055                public Record(N node, float dist) {
056                        this(node, dist, null, null);
057                }
058                
059                public Record(N node, float dist, E reach, Record<N,E> parent) {
060                        this.node = node;
061                        this.dist = dist;
062                        this.reach = reach;
063                        this.parent = parent;
064                        this.depth = (parent != null) ? parent.depth + 1 : 0;
065                }
066
067                @Override
068                public int compareTo(Record<N, E> o) {
069                        if(dist < o.dist)
070                                return -1;
071                        return (dist == o.dist) ? 0 : 1;
072                }
073        }
074        
075        /**
076         * Search for the shortest paths from a single source node in a graph.
077         * 
078         * @param graph the graph in which to perform the search
079         * @param init the initial (source) node
080         * @param edgeWeights the edge weights
081         * @return the single-source shortest path results
082         */
083        public static <N,E> SSSPResult<N,E> findSSSP(Graph<N,E> graph, N init, EdgeWeights<E> edgeWeights) {
084                DijkstraSSSP<N, E> dijkstra = new DijkstraSSSP<N, E>(graph, init, edgeWeights);
085                dijkstra.findSSSP();
086                return dijkstra;
087        }
088        
089        private final Graph<N,E> graph;
090        private final N init;
091        private final EdgeWeights<E> edgeWeights;
092        private final MutableMapping<N,Record<N,E>> records;
093        
094        /**
095         * Constructor.
096         * @param graph the graph in which to search for shortest paths
097         * @param init the initial node
098         * @param edgeWeights the edge weights
099         */
100        public DijkstraSSSP(Graph<N,E> graph, N init, EdgeWeights<E> edgeWeights) {
101                this.graph = graph;
102                this.init = init;
103                this.edgeWeights = edgeWeights;
104                this.records = graph.createStaticNodeMapping();
105        }
106        
107        
108        /**
109         * Start the search. This method may only be invoked once.
110         */
111        public void findSSSP() {
112                Record<N,E> initRec = new Record<>(init, 0.0f);
113                if(records.put(init, initRec) != null)
114                        throw new IllegalStateException("Search has already been performed!");
115                
116                SmartDynamicPriorityQueue<Record<N,E>> pq = BinaryHeap.create(graph.size());
117                initRec.ref = pq.referencedAdd(initRec);
118                
119                while(!pq.isEmpty()) {
120                        // Remove node with minimum distance
121                        Record<N,E> rec = pq.extractMin();
122                        float dist = rec.dist;
123                        
124                        N node = rec.node;
125                        
126                        // edge scanning
127                        for(E edge : graph.getOutgoingEdges(node)) {
128                                float w = edgeWeights.getEdgeWeight(edge);
129                                float newDist = dist + w;
130                                
131                                N tgt = graph.getTarget(edge);
132                                Record<N,E> tgtRec = records.get(tgt);
133                                if(tgtRec == null) {
134                                        // node has not been visited before, add a record
135                                        // and add it to the queue
136                                        tgtRec = new Record<>(tgt, newDist, edge, rec);
137                                        tgtRec.ref = pq.referencedAdd(tgtRec);
138                                        records.put(tgt, tgtRec);
139                                }
140                                else if(newDist < tgtRec.dist) {
141                                        // using currently considered edge decreases current distance
142                                        tgtRec.dist = newDist;
143                                        tgtRec.reach = edge;
144                                        tgtRec.depth = rec.depth + 1;
145                                        tgtRec.parent = rec;
146                                        // update it's position in the queue
147                                        pq.keyChanged(tgtRec.ref);
148                                }
149                        }
150                }
151        }
152        
153        /*
154         * (non-Javadoc)
155         * @see net.automatalib.algorithms.graph.sssp.SSSPResult#getShortestPathDistance(java.lang.Object)
156         */
157        @Override
158        public float getShortestPathDistance(N target) {
159                Record<N,E> rec = records.get(target);
160                if(rec == null)
161                        return GraphAlgorithms.INVALID_DISTANCE;
162                return rec.dist;
163        }
164        
165        /*
166         * (non-Javadoc)
167         * @see net.automatalib.algorithms.graph.sssp.SSSPResult#getShortestPath(java.lang.Object)
168         */
169        @Override
170        public List<E> getShortestPath(N target) {
171                Record<N,E> rec = records.get(target);
172                if(rec == null)
173                        return null;
174                
175                if(rec.depth == 0)
176                        return Collections.emptyList();
177                
178                List<E> result = new ArrayList<>(rec.depth);
179                
180                E edge;
181                while((edge = rec.reach) != null) {
182                        result.add(edge);
183                        rec = rec.parent;
184                }
185                
186                Collections.reverse(result);
187                return result;
188        }
189
190        /*
191         * (non-Javadoc)
192         * @see net.automatalib.algorithms.graph.sssp.SSSPResult#getInitialNode()
193         */
194        @Override
195        public N getInitialNode() {
196                return init;
197        }
198        
199        /*
200         * (non-Javadoc)
201         * @see net.automatalib.algorithms.graph.sssp.SSSPResult#getShortestPathEdge(java.lang.Object)
202         */
203        @Override
204        public E getShortestPathEdge(N target) {
205                Record<N,E> rec = records.get(target);
206                if(rec == null)
207                        return null;
208                return rec.reach;
209        }
210}