Package edu.uci.ics.jung.algorithms.shortestpath

Class UnweightedShortestPath<V,​E>

  • All Implemented Interfaces:
    Distance<V>, ShortestPath<V,​E>
    public class UnweightedShortestPath<V,​E>
extends java.lang.Object
implements ShortestPath<V,​E>, Distance<V>
    Computes the shortest path distances for graphs whose edges are not weighted (using BFS).

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private void computeShortestPathsFromSource​(V source)
      Computes the shortest path distances from a given node to all other nodes.
      java.lang.Number getDistance​(V source, V target)
      Returns the distance from the source vertex to the target vertex.
      java.util.Map<V,​java.lang.Number> getDistanceMap​(V source)
      Returns a Map which maps each vertex in the graph (including the source vertex) to its distance (represented as a Number) from source.
      java.util.Map<V,​E> getIncomingEdgeMap​(V source)
      Returns a map from vertices to the last edge on the shortest path to that vertex starting from source.
      void reset()
      Clears all stored distances for this instance.
      void reset​(V v)
      Clears all stored distances for the specified source vertex source.

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • mDistanceMap

        private java.util.Map<V,​java.util.Map<V,​java.lang.Number>> mDistanceMap

      • mIncomingEdgeMap

        private java.util.Map<V,​java.util.Map<V,​E>> mIncomingEdgeMap

      • distances

        private java.util.Map<V,​java.lang.Number> distances

    • Constructor Detail

      • UnweightedShortestPath

        public UnweightedShortestPath​(Hypergraph<V,​E> g)
        Constructs and initializes algorithm
        Parameters:
        g - the graph

    • Method Detail

      • getDistance

        public java.lang.Number getDistance​(V source,
                                    V target)
        Description copied from interface: Distance
        Returns the distance from the source vertex to the target vertex. If target is not reachable from source, returns null.
        Specified by:
        getDistance in interface Distance<V>
        Parameters:
        source - the vertex from which distance is to be measured
        target - the vertex to which distance is to be measured
        Returns:
        the distance from source to target
        See Also:
        Distance.getDistance(Object, Object)

      • getDistanceMap

        public java.util.Map<V,​java.lang.Number> getDistanceMap​(V source)
        Description copied from interface: Distance
        Returns a Map which maps each vertex in the graph (including the source vertex) to its distance (represented as a Number) from source. If any vertex is not reachable from source, no distance is stored for that vertex.
        Specified by:
        getDistanceMap in interface Distance<V>
        Parameters:
        source - the vertex from which distances are to be measured
        Returns:
        a Map of the distances from source to other vertices in the graph
        See Also:
        Distance.getDistanceMap(Object)

      • getIncomingEdgeMap

        public java.util.Map<V,​E> getIncomingEdgeMap​(V source)
        Description copied from interface: ShortestPath
        Returns a map from vertices to the last edge on the shortest path to that vertex starting from source.
        Specified by:
        getIncomingEdgeMap in interface ShortestPath<V,​E>
        Parameters:
        source - the starting point for the shortest paths
        Returns:
        a map from vertices to the last edge on the shortest path to that vertex starting from source
        See Also:
        ShortestPath.getIncomingEdgeMap(Object)

      • computeShortestPathsFromSource

        private void computeShortestPathsFromSource​(V source)
        Computes the shortest path distances from a given node to all other nodes.
        Parameters:
        source - the source node

      • reset

        public void reset()
        Clears all stored distances for this instance. Should be called whenever the graph is modified (edge weights changed or edges added/removed). If the user knows that some currently calculated distances are unaffected by a change, reset(V) may be appropriate instead.
        See Also:
        reset(Object)

      • reset

        public void reset​(V v)
        Clears all stored distances for the specified source vertex source. Should be called whenever the stored distances from this vertex are invalidated by changes to the graph.
        Parameters:
        v - the vertex for which distances should be cleared
        See Also:
        reset()