Interface MinimumSpanningTree


  • public interface MinimumSpanningTree
    Minimum spanning tree algorithm.

    A spanning tree is an edge sub set of the graph edges which form a tree and connect (span) all the vertices of the graph. A minimum spanning tree (MST) is a spanning tree with the minimum edge weights sum over all spanning trees.

    If a maximum spanning tree is needed, the edge weights can be negated and the MST algorithm can be used to compute the maximum spanning tree.

    Use newInstance() to get a default implementation of this interface. A builder obtained via builder() may support different options to obtain different implementations.

    Author:
    Barak Ugav
    See Also:
    Wikipedia, MinimumDirectedSpanningTree
    • Method Detail

      • computeMinimumSpanningTree

        <V,​E> MinimumSpanningTree.Result<V,​E> computeMinimumSpanningTree​(Graph<V,​E> g,
                                                                                     WeightFunction<E> w)
        Compute the minimum spanning tree (MST) of a given graph.

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

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - a graph
        w - an edge weight function
        Returns:
        a result object containing all the edges of the computed spanning tree, which there are \(n-1\) of them (or less, forming a forest if the graph is not connected)
      • isSpanningTree

        static <V,​E> boolean isSpanningTree​(Graph<V,​E> g,
                                                  Collection<E> edges)
        Check whether a given set of edges is a spanning tree of a given graph.

        A set of edges is spanning tree if it is a tree and connects all the vertices of the graph. Specifically, if the graph is not empty, the number of edges must be \(n-1\) where \(n\) denote the number of vertices in the graph. The edge set should not contain any duplicate edges.

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

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - a graph
        edges - a set of edges that should form a spanning tree
        Returns:
        true if the given set of edges is a spanning tree of the given graph, false otherwise
      • isSpanningForest

        static <V,​E> boolean isSpanningForest​(Graph<V,​E> g,
                                                    Collection<E> edges)
        Check whether a given set of edges is a spanning forest of a given graph.

        A set of edges is spanning forest if it is a forest (do not contains cycles) which connected any pair of vertices that are connected in the original graph, namely its connected components are identical to the connected components of the original graph. Specifically, the number of edges must be \(n-c\) where \(n\) denote the number of vertices in the graph and \(c\) denote the number of connected components in the graph. The edge set should not contain any duplicate edges.

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - a graph
        edges - a set of edges that should form a spanning forest
        Returns:
        true if the given set of edges is a spanning forest of the given graph, false otherwise