/*
 * (C) Copyright 2016-2017, by Joris Kinable and Contributors.
 *
 * JGraphT : a free Java graph-theory library
 *
 * This program and the accompanying materials are dual-licensed under
 * either
 *
 * (a) the terms of the GNU Lesser General Public License version 2.1
 * as published by the Free Software Foundation, or (at your option) any
 * later version.
 *
 * or (per the licensee's choosing)
 *
 * (b) the terms of the Eclipse Public License v1.0 as published by
 * the Eclipse Foundation.
 */
package org.jgrapht.alg.interfaces;

import java.util.*;

/**
 * Given a weighted graph G(V,E) (directed or undirected). This class computes a minimum s-t cut. A
 * cut is a partitioning of the vertices into two disjoint sets S, T such that s ∈ S, t ∈ T, and
 * that S ∪ T = V. The capacity of a cut is defined as the sum of the weights of the edges
 * from S to T. In case of a directed graph, only the edges with their tail in S and their head in T
 * are counted. In cased of a undirected graph, all edges with one endpoint in S and one endpoint in
 * T are counted. For a given s and t, this class computes two partitions S and T such that the
 * capacity of the cut is minimized. When each edge has equal weight, by definition this class
 * minimizes the number of edges from S to T.
 *
 * Note: it is not recommended to use this class to calculate the overall minimum cut in a graph by
 * iteratively invoking this class for all source-sink pairs. This is computationally expensive.
 * Instead, use the StoerWagnerMinimumCut implementation.
 *
 * @param  the graph vertex type
 * @param  the graph edge type
 *
 * @author Joris Kinable
 */
public interface MinimumSTCutAlgorithm
{

    /**
     * Computes a minimum capacity s-t cut.
     * 
     * @param source s
     * @param sink t
     * @return capacity of the cut
     */
    double calculateMinCut(V source, V sink);

    /**
     * Returns the capacity of the cut obtained after the last invocation of
     * {@link #calculateMinCut(Object, Object)}
     * 
     * @return capacity of the cut
     */
    double getCutCapacity();

    /**
     * Returns the source partition S, s ∈ S, of the cut obtained after the last invocation of
     * {@link #calculateMinCut(Object, Object)}
     * 
     * @return source partition S
     */
    Set getSourcePartition();

    /**
     * Returns the sink partition T, t ∈ T, of the cut obtained after the last invocation of
     * {@link #calculateMinCut(Object, Object)}
     * 
     * @return source partition T
     */
    Set getSinkPartition();

    /**
     * Returns the set of edges which run from S to T, in the s-t cut obtained after the last
     * invocation of {@link #calculateMinCut(Object, Object)} In case of a directed graph, only the
     * edges with their tail in S and their head in T are returned. In cased of a undirected graph,
     * all edges with one endpoint in S and one endpoint in T are returned.
     * 
     * @return set of edges which run from S to T
     */
    Set getCutEdges();

}

 

Ads help maintain this website.