Class BaseBidirectionalShortestPathAlgorithm<V,​E>

    • Field Detail

      • GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE

        protected static final String GRAPH_CONTAINS_A_NEGATIVE_WEIGHT_CYCLE
        Error message for reporting the existence of a negative-weight cycle.
        See Also:
        Constant Field Values
      • GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX

        protected static final String GRAPH_MUST_CONTAIN_THE_SOURCE_VERTEX
        Error message for reporting that a source vertex is missing.
        See Also:
        Constant Field Values
      • GRAPH_MUST_CONTAIN_THE_SINK_VERTEX

        protected static final String GRAPH_MUST_CONTAIN_THE_SINK_VERTEX
        Error message for reporting that a sink vertex is missing.
        See Also:
        Constant Field Values
      • graph

        protected final Graph<V,​E> graph
        The underlying graph.
    • Constructor Detail

      • BaseBidirectionalShortestPathAlgorithm

        public BaseBidirectionalShortestPathAlgorithm​(Graph<V,​E> graph)
        Constructs a new instance of the algorithm for a given graph.
        Parameters:
        graph - the graph
    • Method Detail

      • createPath

        protected GraphPath<V,​E> createPath​(org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V,​E> forwardFrontier,
                                                  org.jgrapht.alg.shortestpath.BaseBidirectionalShortestPathAlgorithm.BaseSearchFrontier<V,​E> backwardFrontier,
                                                  double weight,
                                                  V source,
                                                  V commonVertex,
                                                  V sink)
        Builds shortest path between source and sink based on the information provided by search frontiers and common vertex.
        Parameters:
        forwardFrontier - forward direction frontier
        backwardFrontier - backward direction frontier
        weight - weight of the shortest path
        source - path source
        commonVertex - path common vertex
        sink - path sink
        Returns:
        shortest path between source and sink
      • getPathWeight

        public double getPathWeight​(V source,
                                    V sink)
        Get the weight of the shortest path from a source vertex to a sink vertex. Returns Double.POSITIVE_INFINITY if no path exists.
        Specified by:
        getPathWeight in interface ShortestPathAlgorithm<V,​E>
        Parameters:
        source - the source vertex
        sink - the sink vertex
        Returns:
        the weight of the shortest path from a source vertex to a sink vertex, or Double.POSITIVE_INFINITY if no path exists
      • createEmptyPath

        protected final GraphPath<V,​E> createEmptyPath​(V source,
                                                             V sink)
        Create an empty path. Returns null if the source vertex is different than the target vertex.
        Parameters:
        source - the source vertex
        sink - the sink vertex
        Returns:
        an empty path or null null if the source vertex is different than the target vertex