match.h File Reference

This file defines maximum matching algorithm function headers. More...

#include <vector>
#include "graph.h"

Go to the source code of this file.

Functions
std::vector< int >	match_find (const Graph &graph)
	Find a match of the given graph. More...
bool	match_exists (const Graph &graph)
	Check if there exists a matching for all cards. More...

Detailed Description

This file defines maximum matching algorithm function headers.

Definition in file match.h.

Function Documentation

match_exists()

bool match_exists

(

const Graph &

graph

)

Check if there exists a matching for all cards.

See also

match_find

Definition at line 35 of file match.cpp.

{
    std::vector<int> match = match_find(graph);
    return std::find(match.begin(), match.end(), -1) == match.end();
}

match_find()

std::vector<int> match_find

(

const Graph &

graph

)

Find a match of the given graph.

Returns

A vector list with integers representing to which rnode the lnode at the given index is connected, -1 indicates a connection to none.

Definition at line 47 of file match.cpp.

{
    std::vector<int> match(graph.size(), -1);  // FIXME Make match for left node, not for right.
    for (int rnode = 0; rnode < (int)graph.size(); rnode++) {
        std::vector<bool> seen(graph.size(), false);
        dfs(graph, rnode, seen, match);
    }
    return match;
}