BipartiteMatchingProblem (JGraphT : a free Java graph library)

Type Parameters:

V - the graph vertex types

E - the graph edge type

All Known Implementing Classes:

BipartiteMatchingProblem.BipartiteMatchingProblemImpl
```
public interface BipartiteMatchingProblem<V,E>
```
This class represents a bipartite matching problem. The problem can be weighted or unweighted depending on the isWeighted().
The minimum weight (minimum cost) perfect bipartite matching problem is defined as follows: \[ \begin{align} \mbox{minimize}~& \sum_{e \in E}c_e\cdot x_e &\\ \mbox{s.t. }&\sum_{e\in \delta(v)} x_e = 1 & \forall v\in V\\ &x_e \in \{0,1\} & \forall e\in E \end{align} \] Here $\delta(v)$ denotes the set of edges incident to the vertex $v$. The parameters $c_{e}$ define a cost of adding the edge $e$ to the matching. If the problem is unweighted, the values $c_e$ are equal to 1 in the problem formulation.
This class can define bipartite matching problems without the requirement that every edge must be matched, i.e. non-perfect matching problems. These problems are called maximum cardinality bipartite matching problems. The goal of the maximum cardinality matching problem is to find a matching with maximum number of edges. If the cost function is used in this setup, the goal is to find the cheapest matching among all matchings of maximum cardinality.

Author:

Timofey Chudakov

See Also:

MatchingAlgorithm

Nested Class Summary

Nested Classes
Modifier and Type Interface Description

static class BipartiteMatchingProblem.BipartiteMatchingProblemImpl<V,E>
Default implementation of a Bipartite Matching Problem

Method Summary

All Methods Instance Methods Abstract Methods Default Methods
Modifier and Type	Method	Description
`default void`	`dumpCosts()`	Dumps the problem edge costs to the underlying graph.
`Function<E,Double>`	`getCosts()`	Returns a cost function of this problem.
`Graph<V,E>`	`getGraph()`	Returns the graph, which defines the problem
`Set<V>`	`getPartition1()`	Returns one of the 2 partitions of the graph (no 2 vertices in this set share an edge)
`Set<V>`	`getPartition2()`	Returns one of the 2 partitions of the graph (no 2 vertices in this set share an edge)
`boolean`	`isWeighted()`	Determines if this problem is weighted or not.

- Method Detail
  - getGraph
```
Graph<V,E> getGraph()
```
    Returns the graph, which defines the problem
    
    Returns:
    
    the graph, which defines the problem
  - getPartition1
```
Set<V> getPartition1()
```
    Returns one of the 2 partitions of the graph (no 2 vertices in this set share an edge)
    
    Returns:
    
    one of the 2 partitions of the graph
  - getPartition2
```
Set<V> getPartition2()
```
    Returns one of the 2 partitions of the graph (no 2 vertices in this set share an edge)
    
    Returns:
    
    one of the 2 partitions of the graph
  - getCosts
```
Function<E,Double> getCosts()
```
    Returns a cost function of this problem. This function must be defined for all edges of the graph. In the case the problem is unweighted, the function must return any constant value for all edges.
    
    Returns:
    
    a cost function of this problem
  - isWeighted
```
boolean isWeighted()
```
    Determines if this problem is weighted or not.
    
    Returns:
    
    true is the problem is weighted, false otherwise
  - dumpCosts
```
default void dumpCosts()
```
    Dumps the problem edge costs to the underlying graph.