POPULAR.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 LEP_POPULAR_H
#define LEP_POPULAR_H

#include <LEP/mosp/config.h>

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

#include <LEP/mosp/graphcopy.h>

namespace mosp
{

    bool 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 );

    bool 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 );

    bool 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 );


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

    bool 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 );

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


}

#endif  // LEP_POPULAR_H

/* ex: set ts=4 sw=4 sts=4 et: */