Package com.jgalgo.alg.tree

Interface TreePathMaxima

All Known Implementing Classes:

TreePathMaximaAbstract, TreePathMaximaHagerup

public interface TreePathMaxima

Tree Path Maxima (TPM) algorithm.

Given a tree \(T\) and a sequence of vertices pairs \((u_1,v_1),(u_2,v_2),\ldots\) called queries, the tree path maxima problem is to find for each pair \((u_i,v_i)\) the heaviest edge on the path between \(u_i\) and \(v_i\) in \(T\).

TPM can be used to validate if a spanning tree is minimum spanning tree (MST) or not, by checking for each edge \((u,v)\) that is not in the tree that it is heavier than the heaviest edge in the path from \(u\) to \(v\) in the tree. If a TPM on \(n\) vertices and \(m\) queries can be answer in \(O(n + m)\) time than an MST can be validated in linear time.

Use newInstance() to get a default implementation of this interface.

Author:

Barak Ugav

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	TreePathMaxima.IQueries	Queries container for TreePathMaxima computations for IntGraph.
static interface	TreePathMaxima.IResult	A result object for TreePathMaxima algorithm for IntGraph.
static interface	TreePathMaxima.Queries<V,E>	Queries container for TreePathMaxima computations.
static interface	TreePathMaxima.Result<V,E>	A result object for TreePathMaxima algorithm.

Method Summary

Modifier and Type	Method	Description
<V,E> TreePathMaxima.Result<V,E>	computeHeaviestEdgeInTreePaths(Graph<V,E> tree, WeightFunction<E> w, TreePathMaxima.Queries<V,E> queries)	Compute the heaviest edge in multiple tree paths.
static TreePathMaxima	newInstance()	Create a new tree path maxima algorithm object.
static <V,E> boolean	verifyMst(Graph<V,E> g, WeightFunction<E> w, Collection<E> mstEdges, TreePathMaxima tpmAlgo)	Verify that the given edges actually form an MST of a graph.

Method Detail

computeHeaviestEdgeInTreePaths

<V,E> TreePathMaxima.Result<V,E> computeHeaviestEdgeInTreePaths(Graph<V,E> tree,
                                                                            WeightFunction<E> w,
                                                                            TreePathMaxima.Queries<V,E> queries)

Compute the heaviest edge in multiple tree paths.

The queries container contains pairs of vertices, each corresponding to a simple path in the given tree. For each of these paths, the heaviest edge in the path will be computed.

If g is an IntGraph, a TreePathMaxima.IResult object is returned. In that case, its better to pass a IWeightFunction as w, and TreePathMaxima.IQueries as queries to avoid boxing/unboxing.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

tree - a tree

w - an edge weight function

queries - a sequence of queries as pairs of vertices, each corresponding to a unique simple path in the tree.

Returns:

a result object, with a corresponding result edge for each query

newInstance

static TreePathMaxima newInstance()

Create a new tree path maxima algorithm object.

This is the recommended way to instantiate a new TreePathMaxima object.

Returns:

a default implementation of TreePathMaxima

verifyMst

static <V,E> boolean verifyMst(Graph<V,E> g,
                                     WeightFunction<E> w,
                                     Collection<E> mstEdges,
                                     TreePathMaxima tpmAlgo)

Verify that the given edges actually form an MST of a graph.

The verification is done by computing for each original edge \((u, v)\) in the graph the heaviest edge on the path from \(u\) to \(v\) in the given spanning tree. If all of the edges which are not in the MST have a greater weight than the maximum one in the path of the MST, the MST is valid.

If g is an IntGraph, its better to pass a IWeightFunction as w, and IntCollection as edges to avoid boxing/unboxing.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - an undirected graph

w - an edge weight function

mstEdges - collection of edges that form an MST

tpmAlgo - tree path maximum algorithm, used for verification

Returns:

true if the collection of edges form an MST of g, else false

Throws:

IllegalArgumentException - if g is a directed graph