Package com.jgalgo

Interface TreePathMaxima

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.

Author:

Barak Ugav

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	TreePathMaxima.Builder	A builder for TreePathMaxima objects.
static interface	TreePathMaxima.Queries	Queries container for TreePathMaxima computations.
static interface	TreePathMaxima.Result	A result object for TreePathMaxima algorithm.

Method Summary

Modifier and Type	Method	Description
TreePathMaxima.Result	computeHeaviestEdgeInTreePaths(Graph tree, WeightFunction w, TreePathMaxima.Queries queries)	Compute the heaviest edge in multiple tree paths.
static TreePathMaxima.Builder	newBuilder()	Create a new tree path maxima algorithm builder.
static boolean	verifyMST(Graph g, WeightFunction w, IntCollection mstEdges, TreePathMaxima tpmAlgo)	Verify that the given edges actually form an MST of a graph.

Method Detail

computeHeaviestEdgeInTreePaths

TreePathMaxima.Result computeHeaviestEdgeInTreePaths(Graph tree,
                                                     WeightFunction w,
                                                     TreePathMaxima.Queries 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.

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

newBuilder

static TreePathMaxima.Builder newBuilder()

Create a new tree path maxima algorithm builder.

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

Returns:

a new builder that can build TreePathMaxima objects

verifyMST

static boolean verifyMST(Graph g,
                         WeightFunction w,
                         IntCollection 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.

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