Package org.jgrapht.alg.shortestpath

Class BellmanFordIterator<V,​E>

  • All Implemented Interfaces:
    java.util.Iterator<java.util.List<V>>
    class BellmanFordIterator<V,​E>
extends java.lang.Object
implements java.util.Iterator<java.util.List<V>>
    Helper class for BellmanFordShortestPath; not intended for general use.

    • Field Detail

      • NEGATIVE_UNDIRECTED_EDGE

        protected static final java.lang.String NEGATIVE_UNDIRECTED_EDGE
        Error message.
        See Also:
        Constant Field Values

      • graph

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

      • startVertex

        protected V startVertex
        Start vertex.

      • prevImprovedVertices

        private java.util.List<V> prevImprovedVertices
        Vertices whose shortest path cost have been improved during the previous pass.

      • startVertexEncountered

        private boolean startVertexEncountered

      • vertexData

        private java.util.Map<V,​BellmanFordPathElement<V,​E>> vertexData
        Stores the vertices that have been seen during iteration and (optionally) some additional traversal info regarding each vertex.

      • epsilon

        private double epsilon

    • Constructor Detail

      • BellmanFordIterator

        protected BellmanFordIterator​(Graph<V,​E> graph,
                              V startVertex,
                              double epsilon)
        Parameters:
        graph -
        startVertex - start vertex.
        epsilon - tolerance factor.

    • Method Detail

      • getPathElement

        public BellmanFordPathElement<V,​E> getPathElement​(V endVertex)
        Returns the path element of the shortest path with less than nMaxHops edges between the start vertex and the end vertex.
        Parameters:
        endVertex - end vertex.
        Returns:
        .

      • 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.List<V> next()
        Returns the list Collection of vertices whose path has been improved during the current pass.
        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()

      • assertValidEdge

        protected void assertValidEdge​(E edge)
        Parameters:
        edge -
        Throws:
        java.lang.IllegalArgumentException - if the graph is undirected and the edge-weight is negative.

      • calculatePathCost

        protected double calculatePathCost​(V vertex,
                                   E edge)
        Costs taken into account are the weights stored in Edge objects.
        Parameters:
        vertex - a vertex which has just been encountered.
        edge - the edge via which the vertex was encountered.
        Returns:
        the cost obtained by concatenation.
        See Also:
        Graph#getEdgeWeight(E)

      • edgesOfIterator

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

      • getPrevSeenData

        protected BellmanFordPathElement<V,​E> getPrevSeenData​(V vertex)
        Access the data stored for a seen vertex in the previous pass.
        Parameters:
        vertex - a vertex which has already been seen.
        Returns:
        data associated with the seen vertex or null if no data was associated with the vertex.

      • getSeenData

        protected BellmanFordPathElement<V,​E> getSeenData​(V vertex)
        Access the data stored for a seen vertex in the current pass.
        Parameters:
        vertex - a vertex which has already been seen.
        Returns:
        data associated with the seen vertex or null if no data was associated with the vertex.

      • isSeenVertex

        protected boolean isSeenVertex​(V vertex)
        Determines whether a vertex has been seen yet by this traversal.
        Parameters:
        vertex - vertex in question.
        Returns:
        true if vertex has already been seen.

      • putSeenData

        protected BellmanFordPathElement<V,​E> putSeenData​(V vertex,
                                                        BellmanFordPathElement<V,​E> data)
        Stores iterator-dependent data for a vertex that has been seen during the current pass.
        Parameters:
        vertex - a vertex which has been seen.
        data - data to be associated with the seen vertex.
        Returns:
        previous value associated with specified vertex or null if no data was associated with the vertex.

      • assertBellmanFordIterator

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

      • createSeenData

        private BellmanFordPathElement<V,​E> createSeenData​(V vertex,
                                                         E edge,
                                                         double cost)
        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.
        cost - cost of the created path element.
        Returns:
        the new entry.

      • encounterStartVertex

        private void encounterStartVertex()

      • relaxVertex

        private void relaxVertex​(V vertex,
                         E edge)
        Upates data first time a vertex is reached by a path.
        Parameters:
        vertex - a vertex which has just been encountered.
        edge - the edge via which the vertex was encountered.

      • relaxVertexAgain

        private boolean relaxVertexAgain​(V vertex,
                                 E edge)
        Check if the cost of the best path so far reaching the specified vertex could be improved if the vertex is reached through the specified edge.
        Parameters:
        vertex - a vertex which has just been encountered.
        edge - the edge via which the vertex was encountered.
        Returns:
        true if the cost has been improved, false otherwise.

      • savePassData

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