graph.cpp File Reference

This file defines the graph creation functions. More...

#include <algorithm>
#include <cassert>
#include <numeric>
#include <vector>
#include "graph.h"
#include "settings.h"
#include "state.h"

Go to the source code of this file.

Functions
Graph	graph_copy (const Graph graph)
	Create a copy of the given graph. More...
bool	graph_possible (const Settings &settings, const State &state)
	Check if it is possible to create a graph. More...
void	graph_set (const Settings &settings, const State &state, Graph &graph, int player, int set, int hand_offset, int hand_entry)
	Add all the edges representing the set constraints for a player. More...
void	graph_player (const Settings &settings, const State &state, Graph &graph, int player, int hand_offset)
	Add all the edges representing the given player. More...
Graph	graph_create (const Settings &settings, const State &state)
	Create a biparite graph which has a matching if the state is valid. More...

Detailed Description

This file defines the graph creation functions.

Definition in file graph.cpp.

Function Documentation

graph_copy()

Graph graph_copy

(

const Graph

graph

)

Create a copy of the given graph.

Definition at line 19 of file graph.cpp.

{
    Graph graph_clone(graph.size(), std::vector<bool>(graph.size()));
    for (size_t i = 0; i < graph.size(); i++)
        for (size_t j = 0; j < graph[i].size(); j++)
            graph_clone[i][j] = graph[i][j];
    return graph_clone;
}

graph_create()

Graph graph_create	(	const Settings &	settings,
		const State &	state
	)

Create a biparite graph which has a matching if the state is valid.

The graph is represented as a 2d array where every cell is an edge between the left node (row number) and the right node (column number). We go through all the players and add the constraints corresponding to that player's possible hands.

See also

graph_player

Definition at line 101 of file graph.cpp.

{
    assert(graph_possible(settings, state));  // make sure we can create a graph
 
    // create the graph array and initialize all values to false
    const int NUM_CARDS = settings.NUM_SETS * settings.SET_SIZE;
    Graph graph(NUM_CARDS, std::vector<bool>(NUM_CARDS, false));
 
    // set the corresponding edges for all players
    int hand_offset = 0;
    for (int player = 0; player < settings.NUM_PLAYERS; player++) {
        graph_player(settings, state, graph, player, hand_offset);
        hand_offset += state.players[player].num_cards;
    }
 
    return graph;
}

graph_player()

void graph_player	(	const Settings &	settings,
		const State &	state,
		Graph &	graph,
		int	player,
		int	hand_offset
	)

Add all the edges representing the given player.

First we add all the edges for our set constraints.

After this we assign edges to the leftover cards the player has going to all possible cards the player could have.

See also

graph_set

Definition at line 73 of file graph.cpp.

{
    // go through all set constraints and make edges for them
    int hand_entry = 0;
    for (int set = 0; set < settings.NUM_SETS; set++) {
        graph_set(settings, state, graph, player, set, hand_offset, hand_entry);
        hand_entry += state.players[player].sets[set];
    }
 
    // after all set constraints are set we can have any card
    while (hand_entry < state.players[player].num_cards) {
        for (int card = 0; card < settings.NUM_SETS * settings.SET_SIZE; card++)
            if (state.cards[card].players[player])
                graph[hand_offset + hand_entry][card] = true;
        hand_entry++;
    }
}

graph_possible()

bool graph_possible	(	const Settings &	settings,
		const State &	state
	)

Check if it is possible to create a graph.

More specifically, check that no player's total number of set constraints is bigger than the number of cards that player has.

Returns

true if possible

Definition at line 36 of file graph.cpp.

{
    for (Player player: state.players)
        if (player.num_cards < accumulate(player.sets.begin(), player.sets.end(), 0))
            return false;
    return true;
}

graph_set()

void graph_set	(	const Settings &	settings,
		const State &	state,
		Graph &	graph,
		int	player,
		int	set,
		int	hand_offset,
		int	hand_entry
	)

Add all the edges representing the set constraints for a player.

For every set constraint corresponding to the given set and player, add edges to the current player card (hand_offset + hand_entry) to all cards the player can have from the given set.

Definition at line 51 of file graph.cpp.

{
    int minimum = state.players[player].sets[set];
    while (minimum-- > 0) {
        int card_start = set * settings.SET_SIZE;
        for (int card = card_start; card < card_start + settings.SET_SIZE; card++)
            if (state.cards[card].players[player])
                graph[hand_offset + hand_entry][card] = true;
        hand_entry++;
    }
}