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}