match.cpp File Reference

This file defines maximum matching algorithm functions. More...

#include <algorithm>
#include <vector>
#include "match.h"

Go to the source code of this file.

Functions
bool	dfs (const Graph &graph, int rnode, std::vector< bool > &seen, std::vector< int > &match)
	Depth first search recursive function which returns true if a matching for right node / rnode is possible. More...
bool	match_exists (const Graph &graph)
	Check if there exists a matching for all cards. More...
std::vector< int >	match_find (const Graph &graph)
	Find a match of the given graph. More...

Detailed Description

This file defines maximum matching algorithm functions.

Definition in file match.cpp.

Function Documentation

dfs()

bool dfs	(	const Graph &	graph,
		int	rnode,
		std::vector< bool > &	seen,
		std::vector< int > &	match
	)

Depth first search recursive function which returns true if a matching for right node / rnode is possible.

Definition at line 16 of file match.cpp.

{
    for (size_t lnode = 0; lnode < graph.size(); lnode++) {
        if (graph[lnode][rnode] && !seen[lnode]) {
            seen[lnode] = true;
            if (match[lnode] < 0 || dfs(graph, match[lnode], seen, match)) {
                match[lnode] = rnode;
                return true;
            }
        }
    }
    return false;
}

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;
}