RANK_MAX_MATCHING.h

Go to the documentation of this file.

//
// This program can be freely used in an academic environment
// ONLY for research purposes, subject to the following restrictions:
//
// 1. The origin of this software must not be misrepresented; you must not
//    claim that you wrote the original software. If you use this software
//    an acknowledgment in the product documentation is required.
// 2. Altered source versions must be plainly marked as such, and must not be
//    misrepresented as being the original software.
// 3. This notice may not be removed or altered from any source distribution.
//
// Any other use is strictly prohibited by the author, without an explicit
// permission.
//
// Note that this program uses the LEDA library, which is NOT free. For more
// details visit Algorithmic Solutions at http://www.algorithmic-solutions.com/
//
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
// ! Any commercial use of this software is strictly !
// ! prohibited without explicit permission by the   !
// ! author.                                         !
// !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
//
// This software is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
//
// Copyright (C) 2004-2010 Dimitris Michail <michail@hua.gr>

#ifndef RANK_MAX_MATCHING_H
#define RANK_MAX_MATCHING_H

#include <LEP/mosp/config.h>

#ifdef LEDA_GE_V5
#include <LEDA/core/array.h>
#include <LEDA/core/list.h>
#include <LEDA/graph/graph.h>
#include <LEDA/graph/edge_array.h>
#include <LEDA/system/assert.h>
#else
#include <LEDA/array.h>
#include <LEDA/graph.h>
#include <LEDA/list.h>
#include <LEDA/edge_array.h>
#include <LEDA/std/assert.h>
#endif

namespace mosp
{

leda::list<leda::edge> BI_RANK_MAX_MATCHING( leda::graph& G, 
                          const leda::edge_array<int>& rank );

leda::list<leda::edge> BI_RANK_MAX_MATCHING_MWMR( leda::graph& G, 
                const leda::edge_array<int>& rank );

leda::list<leda::edge> DBI_RANK_MAX_MATCHING_MWMR( leda::graph& G, 
                const leda::edge_array<int>& rank );


leda::array<int> BI_RANK_MAX_MATCHING_PROFILE( const leda::graph& G,
                                   const leda::edge_array<int>& rank,
                                   const leda::list<leda::edge>& matching);

// A procedure to check whether a list of edges is 
// a matching, for debugging and testing purposes.
bool DEBUG_is_valid_matching( const leda::graph &G, 
        const leda::list<leda::edge>& matching );

leda::list<leda::edge> BI_RANK_MAX_CAPACITATED_MATCHING( 
            const leda::graph& G, 
            const leda::list<leda::node>& A, 
            const leda::list<leda::node>& B, 
            const leda::node_array<int>& capacity,
            const leda::edge_array<int>& rank 
            );

// A procedure to check whether a list of edges is 
// a matching, for debugging and testing purposes.
bool DEBUG_is_valid_matching( const leda::graph &G, 
            const leda::node_array<int>& capacity,
            const leda::list<leda::edge>& matching );

}  

#endif  // RANK_MAX_MATCHING_H

/* ex: set ts=8 sw=4 sts=4 noet: */