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.List;
020
021/**
022 * Result interface for the single-source shortest path (SSSP) problem.
023 * 
024 * @author Malte Isberner <malte.isberner@gmail.com>
025 *
026 * @param <N> node class
027 * @param <E> edge class
028 */
029public interface SSSPResult<N, E> {
030        
031        
032        /**
033         * Retrieves the node the source was started from.
034         * @return the source node
035         */
036        public N getInitialNode();
037        
038        /**
039         * Retrieves the length of the shortest path from the initial node
040         * to the given one.
041         * @param target the target node
042         * @return the length of the shortest path from the initial node to
043         * the given target node, or {@link GraphAlgorithms#INVALID_DISTANCE} if there exists no
044         * such path.
045         */
046        public float getShortestPathDistance(N target);
047        
048        /**
049         * Retrieves the shortest path from the initial node to the given one (as a sequence of edges),
050         * or <tt>null</tt> if there exists no such path.
051         * <p>
052         * Note that implementations might construct these paths on-the-fly.
053         * 
054         * @param target the target node
055         * @return the path from the initial node to the given target node, or <tt>null</tt> if
056         * there exists no such path.
057         */
058        public List<E> getShortestPath(N target);
059        
060        /**
061         * Retrieves the incoming edge via which the given node is reached on the shortest path.
062         * If the node is not reachable or it is the initial node, <tt>null</tt> is returned.
063         * 
064         * @param target the target node
065         * @return the reaching edge on the shortest path, or <tt>null</tt>.
066         */
067        public E getShortestPathEdge(N target);
068}