Package com.jgalgo.alg.shortestpath

Class ShortestPathAllPairsAbstract

java.lang.Object

com.jgalgo.alg.shortestpath.ShortestPathAllPairsAbstract

All Implemented Interfaces:

ShortestPathAllPairs

Direct Known Subclasses:

ShortestPathAllPairsCardinality, ShortestPathAllPairsFloydWarshall, ShortestPathAllPairsJohnson

public abstract class ShortestPathAllPairsAbstract
extends Object
implements ShortestPathAllPairs

Abstract class for computing shortest path between all pairs in a graph.

The class implements the interface by solving the problem on the index graph and then maps the results back to the original graph. The implementation for index graphs is abstract and left to the subclasses.

Author:

Barak Ugav

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.shortestpath.ShortestPathAllPairs

ShortestPathAllPairs.Builder, ShortestPathAllPairs.IResult, ShortestPathAllPairs.Result<V,E>

Constructor Summary

Constructors

Constructor	Description
ShortestPathAllPairsAbstract()	Default constructor.

Method Summary

Modifier and Type	Method	Description
<V,E> ShortestPathAllPairs.Result<V,E>	computeAllShortestPaths(Graph<V,E> g, WeightFunction<E> w)	Compute the shortest path between each pair of vertices in a graph.
<V,E> ShortestPathAllPairs.Result<V,E>	computeSubsetShortestPaths(Graph<V,E> g, Collection<V> verticesSubset, WeightFunction<E> w)	Compute the shortest path between each pair of vertices in a given subset of the vertices of the graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

ShortestPathAllPairsAbstract

public ShortestPathAllPairsAbstract()

Default constructor.

Method Detail

computeAllShortestPaths

public <V,E> ShortestPathAllPairs.Result<V,E> computeAllShortestPaths(Graph<V,E> g,
                                                                                  WeightFunction<E> w)

Description copied from interface: ShortestPathAllPairs

Compute the shortest path between each pair of vertices in a graph.

Given an edge weight function, the length of a path is the weight sum of all edges of the path. The shortest path from a source vertex to some other vertex is the path with the minimum weight.

To compute the shortest cardinality (non weighted) paths, pass null instead of the weight function w.

If g is an IntGraph, a ShortestPathAllPairs.IResult object will be returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.

Specified by:

computeAllShortestPaths in interface ShortestPathAllPairs

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

w - an edge weight function

Returns:

a result object containing information on the shortest path between each pair of vertices

computeSubsetShortestPaths

public <V,E> ShortestPathAllPairs.Result<V,E> computeSubsetShortestPaths(Graph<V,E> g,
                                                                                     Collection<V> verticesSubset,
                                                                                     WeightFunction<E> w)

Description copied from interface: ShortestPathAllPairs

Compute the shortest path between each pair of vertices in a given subset of the vertices of the graph.

To compute the shortest cardinality (non weighted) paths, pass null instead of the weight function w.

If g is an IntGraph, a ShortestPathAllPairs.IResult object will be returned. In that case, its better to pass a IWeightFunction as w and IntCollection as verticesSubset to avoid boxing/unboxing.

Specified by:

computeSubsetShortestPaths in interface ShortestPathAllPairs

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

verticesSubset - a subset of vertices of the graph. All shortest paths will be computed between each pair of vertices from the subset

w - as edge weight function

Returns:

a result object containing information on the shortest path between each pair of vertices in the subset