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).

    • Constructor Summary

      Constructors 
      Constructor Description
      UnweightedShortestPath​(edu.uci.ics.jung.graph.Hypergraph<V,​E> g)
      Constructs and initializes algorithm

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      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 which maps each vertex in the graph (including the source vertex) to the last edge on the shortest path from the source vertex.
      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

    • Constructor Detail

      • UnweightedShortestPath

        public UnweightedShortestPath​(edu.uci.ics.jung.graph.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>
        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>
        See Also:
        Distance.getDistanceMap(Object)

      • 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.
        See Also:
        reset()