Class KShortestPathsIterator<V,​E>

  • All Implemented Interfaces:
    java.util.Iterator<java.util.Set<V>>

    @Deprecated
    class KShortestPathsIterator<V,​E>
    extends java.lang.Object
    implements java.util.Iterator<java.util.Set<V>>
    Deprecated.
    Moved in shortest path package
    Helper class for KShortestPaths.
    Since:
    July 5, 2007
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private V endVertex
      Deprecated.
      End vertex.
      private Graph<V,​E> graph
      Deprecated.
      Graph on which shortest paths are searched.
      private int k
      Deprecated.
      Number of paths stored at each end vertex.
      private int passNumber
      Deprecated.
      Stores the number of the path.
      private PathValidator<V,​E> pathValidator
      Deprecated.
      Performs path validations in addition to the basics (source and target are connected w/o loops)
      private java.util.Set<V> prevImprovedVertices
      Deprecated.
      Vertices whose ranking shortest paths have been modified during the previous pass.
      private java.util.Map<V,​RankingPathElementList<V,​E>> prevSeenDataContainer
      Deprecated.
      Stores the paths that improved the vertex in the previous pass.
      private java.util.Map<V,​RankingPathElementList<V,​E>> seenDataContainer
      Deprecated.
      Stores the vertices that have been seen during iteration and (optionally) some additional traversal info regarding each vertex.
      private V startVertex
      Deprecated.
      Start vertex.
      private boolean startVertexEncountered
      Deprecated.
       
    • Method Summary

      All Methods Instance Methods Concrete Methods Deprecated Methods 
      Modifier and Type Method Description
      private void assertKShortestPathsIterator​(Graph<V,​E> graph, V startVertex)
      Deprecated.
       
      private RankingPathElementList<V,​E> createSeenData​(V vertex, E edge)
      Deprecated.
      The first time we see a vertex, make up a new entry for it.
      private java.util.Iterator<E> edgesOfIterator​(V vertex)
      Deprecated.
      Returns an iterator to loop over outgoing edges Edge of the vertex.
      private void encounterStartVertex()
      Deprecated.
      Initializes the list of paths at the start vertex and adds an empty path.
      (package private) RankingPathElementList<V,​E> getPathElements​(V endVertex)
      Deprecated.
      Returns the path elements of the ranking shortest paths with less than nMaxHops edges between the start vertex and the end vertex.
      boolean hasNext()
      Deprecated.
       
      java.util.Set<V> next()
      Deprecated.
      Returns the list of vertices whose path has been improved during the current pass.
      void remove()
      Deprecated.
      Unsupported.
      private void savePassData​(java.util.Set<V> improvedVertices)
      Deprecated.
       
      private boolean tryToAddFirstPaths​(V vertex, E edge)
      Deprecated.
      Try to add the first paths to the specified vertex.
      private boolean tryToAddNewPaths​(V vertex, E edge)
      Deprecated.
      Try to add new paths for the vertex.
      private void updateOutgoingVertices​(V vertex, java.util.Set<V> improvedVertices)
      Deprecated.
      Updates outgoing vertices of the vertex.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
      • Methods inherited from interface java.util.Iterator

        forEachRemaining
    • Field Detail

      • endVertex

        private V endVertex
        Deprecated.
        End vertex.
      • graph

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

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

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

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

        private java.util.Map<V,​RankingPathElementList<V,​E>> seenDataContainer
        Deprecated.
        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
        Deprecated.
        Performs path validations in addition to the basics (source and target are connected w/o loops)
      • startVertex

        private V startVertex
        Deprecated.
        Start vertex.
      • startVertexEncountered

        private boolean startVertexEncountered
        Deprecated.
      • passNumber

        private int passNumber
        Deprecated.
        Stores the number of the path.
    • Constructor Detail

      • KShortestPathsIterator

        public KShortestPathsIterator​(Graph<V,​E> graph,
                                      V startVertex,
                                      V endVertex,
                                      int maxSize)
        Deprecated.
        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)
        Deprecated.
        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()
        Deprecated.
        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()
        Deprecated.
        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()
        Deprecated.
        Unsupported.
        Specified by:
        remove in interface java.util.Iterator<V>
        See Also:
        Iterator.remove()
      • getPathElements

        RankingPathElementList<V,​E> getPathElements​(V endVertex)
        Deprecated.
        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)
        Deprecated.
      • createSeenData

        private RankingPathElementList<V,​E> createSeenData​(V vertex,
                                                                 E edge)
        Deprecated.
        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)
        Deprecated.
        Returns an iterator to loop over outgoing edges Edge of the vertex.
        Parameters:
        vertex -
        Returns:
        .
      • encounterStartVertex

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

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

        private boolean tryToAddFirstPaths​(V vertex,
                                           E edge)
        Deprecated.
        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)
        Deprecated.
        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)
        Deprecated.

        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 -