Package org.jgrapht.alg.shortestpath

Class KShortestPathsIterator<V,​E>

  • All Implemented Interfaces:
    java.util.Iterator<java.util.Set<V>>
    class KShortestPathsIterator<V,​E>
extends java.lang.Object
implements java.util.Iterator<java.util.Set<V>>
    Helper class for KShortestPaths.
    Since:
    July 5, 2007

    • Field Detail

      • endVertex

        private V endVertex
        End vertex.

      • graph

        private Graph<V,​E> graph
        Graph on which shortest paths are searched.

      • k

        private int k
        Number of paths stored at each end vertex.

      • prevImprovedVertices

        private java.util.Set<V> prevImprovedVertices
        Vertices whose ranking shortest paths have been modified during the previous pass.

      • prevSeenDataContainer

        private java.util.Map<V,​RankingPathElementList<V,​E>> prevSeenDataContainer
        Stores the paths that improved the vertex in the previous pass.

      • seenDataContainer

        private java.util.Map<V,​RankingPathElementList<V,​E>> seenDataContainer
        Stores the vertices that have been seen during iteration and (optionally) some additional traversal info regarding each vertex. Key = vertex, value = RankingPathElementList list of calculated paths.

      • pathValidator

        private PathValidator<V,​E> pathValidator
        Performs path validations in addition to the basics (source and target are connected w/o loops)

      • startVertex

        private V startVertex
        Start vertex.

      • startVertexEncountered

        private boolean startVertexEncountered

      • passNumber

        private int passNumber
        Stores the number of the path.

    • Constructor Detail

      • KShortestPathsIterator

        public KShortestPathsIterator​(Graph<V,​E> graph,
                              V startVertex,
                              V endVertex,
                              int maxSize)
        Parameters:
        graph - graph on which shortest paths are searched.
        startVertex - start vertex of the calculated paths.
        endVertex - end vertex of the calculated paths.
        maxSize - number of paths stored at end vertex of the graph.

      • KShortestPathsIterator

        public KShortestPathsIterator​(Graph<V,​E> graph,
                              V startVertex,
                              V endVertex,
                              int maxSize,
                              PathValidator<V,​E> pathValidator)
        Parameters:
        graph - graph on which shortest paths are searched.
        startVertex - start vertex of the calculated paths.
        endVertex - end vertex of the calculated paths.
        maxSize - number of paths stored at end vertex of the graph.
        pathValidator - the path validator to use

    • Method Detail

      • hasNext

        public boolean hasNext()
        Specified by:
        hasNext in interface java.util.Iterator<V>
        Returns:
        true if at least one path has been improved during the previous pass, false otherwise.

      • next

        public java.util.Set<V> next()
        Returns the list of vertices whose path has been improved during the current pass. Complexity =
        • O(m*k*(m+n)) where k is the maximum number of shortest paths to compute, m is the number of edges of the graph and n is the number of vertices of the graph
        Specified by:
        next in interface java.util.Iterator<V>
        See Also:
        Iterator.next()

      • remove

        public void remove()
        Unsupported.
        Specified by:
        remove in interface java.util.Iterator<V>
        See Also:
        Iterator.remove()

      • getPathElements

        RankingPathElementList<V,​E> getPathElements​(V endVertex)
        Returns the path elements of the ranking shortest paths with less than nMaxHops edges between the start vertex and the end vertex.
        Parameters:
        endVertex - end vertex.
        Returns:
        list of RankingPathElement, or null of no path exists between the start vertex and the end vertex.

      • assertKShortestPathsIterator

        private void assertKShortestPathsIterator​(Graph<V,​E> graph,
                                          V startVertex)

      • createSeenData

        private RankingPathElementList<V,​E> createSeenData​(V vertex,
                                                         E edge)
        The first time we see a vertex, make up a new entry for it.
        Parameters:
        vertex - a vertex which has just been encountered.
        edge - the edge via which the vertex was encountered.
        Returns:
        the new entry.

      • edgesOfIterator

        private java.util.Iterator<E> edgesOfIterator​(V vertex)
        Returns an iterator to loop over outgoing edges Edge of the vertex.
        Parameters:
        vertex -
        Returns:
        .

      • encounterStartVertex

        private void encounterStartVertex()
        Initializes the list of paths at the start vertex and adds an empty path.

      • savePassData

        private void savePassData​(java.util.Set<V> improvedVertices)

      • tryToAddFirstPaths

        private boolean tryToAddFirstPaths​(V vertex,
                                   E edge)
        Try to add the first paths to the specified vertex. These paths reached the specified vertex and ended with the specified edge. A new intermediary path is stored in the paths list of the specified vertex provided that the path can be extended to the end-vertex.
        Parameters:
        vertex - vertex reached by a path.
        edge - edge reaching the vertex.

      • tryToAddNewPaths

        private boolean tryToAddNewPaths​(V vertex,
                                 E edge)
        Try to add new paths for the vertex. These new paths reached the specified vertex and ended with the specified edge. A new intermediary path is stored in the paths list of the specified vertex provided that the path can be extended to the end-vertex.
        Parameters:
        vertex - a vertex which has just been encountered.
        edge - the edge via which the vertex was encountered.

      • updateOutgoingVertices

        private void updateOutgoingVertices​(V vertex,
                                    java.util.Set<V> improvedVertices)

        Updates outgoing vertices of the vertex. For each outgoing vertex, the new paths are obtained by concatenating the specified edge to the calculated paths of the specified vertex. If the weight of a new path is greater than the weight of any path stored so far at the outgoing vertex then the path is not added, otherwise it is added to the list of paths in increasing order of weight.

        Complexity =
        • O(d(v)*k*(m+n)) where d(v) is the outgoing degree of the specified vertex, k is the maximum number of shortest paths to compute, m is the number of edges of the graph and n is the number of vertices of the graph
        Parameters:
        vertex -
        improvedVertices -