Functions
bool	mosp::BI_POPULAR_MATCHING (const leda::graph &G, const leda::list< leda::node > &A, const leda::list< leda::node > &B, const leda::edge_array< int > &rank, leda::list< leda::edge > &L)
	Compute a popular matching. More...

bool	mosp::BI_APPROX_POPULAR_MATCHING (const leda::graph &G, const leda::list< leda::node > &A, const leda::list< leda::node > &B, const leda::edge_array< int > &rank, int maxphase, leda::list< leda::edge > &L, int &phase)
	Compute an approximate popular matching. More...

bool	mosp::BI_APPROX_POPULAR_MATCHING (const leda::graph &G, const leda::list< leda::node > &A, const leda::list< leda::node > &B, const leda::edge_array< int > &rank, leda::list< leda::edge > &L, int &phase)
	Compute an approximate popular matching. More...

bool	mosp::BI_UNPOPULARITY_FACTOR (graph &G, const list< node > &A, const list< node > &B, const edge_array< int > &rank, const list< edge > &M, int &factor)
	Compute the unpopularity factor of a matching. More...

bool	mosp::BI_POPULAR_CAPACITATED_MATCHING (const graph &G, const list< node > &A, const list< node > &B, const edge_array< int > &rank, const node_array< int > &capacity, list< edge > &L)
	Compute a popular matching in a capacitated instance. More...

int	mosp::BI_UNPOPULARITY_MARGIN (graph &G, const list< node > &A, const list< node > &B, const edge_array< int > &rank, const list< edge > &M)
	Compute the unpopularity margin of a matching. More...

Detailed Description

Function Documentation

bool mosp::BI_APPROX_POPULAR_MATCHING	(	const leda::graph &	G,
		const leda::list< leda::node > &	A,
		const leda::list< leda::node > &	B,
		const leda::edge_array< int > &	rank,
		int	maxphase,
		leda::list< leda::edge > &	L,
		int &	phase
	)

Compute an approximate popular matching.

During the algorithm the graph is copied and everything happens on the copy.

Parameters

G	A bipartite graph.
A	The list of nodes on the left side of the bipartite graph.
B	The list of nodes on the right side of the bipartite graph.
rank	An edge array. Each entry corresponds to the rank of an edge.
maxphase	The maximum phase that the algorithm will try to compute a matching. As you increase the phases the matching's popularity will drop but the chance of finding a matching that is approximate popular increases.
L	A list of edges which after the algorithm will contain the computed matching.
phase	A value which contains the number of phases that the algorithm needed to compute the resulting matching. It will be at most the value of the parameter maxphase.

bool mosp::BI_APPROX_POPULAR_MATCHING	(	const leda::graph &	G,
		const leda::list< leda::node > &	A,
		const leda::list< leda::node > &	B,
		const leda::edge_array< int > &	rank,
		leda::list< leda::edge > &	L,
		int &	phase
	)

Compute an approximate popular matching.

During the algorithm the graph is copied and everything happens on the copy.

Parameters

G	A bipartite graph.
A	The list of nodes on the left side of the bipartite graph.
B	The list of nodes on the right side of the bipartite graph.
rank	An edge array. Each entry corresponds to the rank of an edge.
L	A list of edges which after the algorithm will contain the computed matching.
phase	A value which contains the number of phases that the algorithm needed to compute the resulting matching. A value of 2 means that the algorithm found a popular matching.

bool mosp::BI_POPULAR_CAPACITATED_MATCHING	(	const graph &	G,
		const list< node > &	A,
		const list< node > &	B,
		const edge_array< int > &	rank,
		const node_array< int > &	capacity,
		list< edge > &	L
	)

Compute a popular matching in a capacitated instance.

During the algorithm the graph is copied and everything happens on the copy.

Parameters

G	A bipartite graph.
A	The list of nodes on the left side of the bipartite graph.
B	The list of nodes on the right side of the bipartite graph.
rank	An edge array. Each entry corresponds to the rank of an edge.
capacity	Node capacities.
L	A list of edges which after the algorithm will contain the computed matching. Undefined if no popular matching exists.

Precondition: Capacities of the left side of the graph have to be 1, capacities of the right side have to be positive.; The graph must be bipartite

bool mosp::BI_POPULAR_MATCHING	(	const leda::graph &	G,
		const leda::list< leda::node > &	A,
		const leda::list< leda::node > &	B,
		const leda::edge_array< int > &	rank,
		leda::list< leda::edge > &	L
	)

Compute a popular matching.

During the algorithm the graph is copied and everything happens on the copy. The algorithm has a running time of $O(\sqrt{n}m)$ .

Parameters

G	A bipartite graph.
A	The list of nodes on the left side of the bipartite graph.
B	The list of nodes on the right side of the bipartite graph.
rank	An edge array. Each entry corresponds to the rank of an edge.
L	A list of edges which after the algorithm will contain the computed matching.

bool mosp::BI_UNPOPULARITY_FACTOR	(	graph &	G,
		const list< node > &	A,
		const list< node > &	B,
		const edge_array< int > &	rank,
		const list< edge > &	M,
		int &	factor
	)

Compute the unpopularity factor of a matching.

The unpopularity factor is based on the definition with the multiplicities. See McCutchen 2007.

This function might change the order of the graph edges in the adjacency lists.

Parameters

G	A bipartite graph.
A	The list of nodes on the left side of the bipartite graph.
B	The list of nodes on the right side of the bipartite graph.
rank	An edge array. Each entry corresponds to the rank of an edge.
M	The matching to test in the following form. A list of edges.
factor	Contains the unpopularity factor if it is finite. Undefined otherwise.

Precondition: All edges are directed from A to B.; The adjacency lists of the graph must be sorted according to the rank parameter. This means that in LEDA someone has to call G.sort_edges( rank ) before calling this function.

Returns: True if the matching has a finite unpopularity factor, false if infinite.

int mosp::BI_UNPOPULARITY_MARGIN	(	graph &	G,
		const list< node > &	A,
		const list< node > &	B,
		const edge_array< int > &	rank,
		const list< edge > &	M
	)

Compute the unpopularity margin of a matching.

See McCutchen 2007.

This function might change the order of the graph edges in the adjacency lists.

Parameters

G	A bipartite graph.
A	The list of nodes on the left side of the bipartite graph.
B	The list of nodes on the right side of the bipartite graph.
rank	An edge array. Each entry corresponds to the rank of an edge.
M	The matching to test as a list of edges.