graph.h File Reference

This file defines the graph type and a creation function header. More...

#include <vector>
#include "settings.h"
#include "state.h"

Go to the source code of this file.

Typedefs
typedef std::vector< std::vector< bool > >	Graph
	A bipartite graph where true booleans represent edges between a left node denoted as the row and a right node denoted as the column in the grid. More...

Functions
bool	graph_possible (const Settings &settings, const State &state)
	Check if it is possible to create a graph. More...
Graph	graph_copy (const Graph graph)
	Create a copy of the given graph. 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 type and a creation function header.

Definition in file graph.h.

Typedef Documentation

Graph

typedef std::vector<std::vector<bool> > Graph

A bipartite graph where true booleans represent edges between a left node denoted as the row and a right node denoted as the column in the grid.

Definition at line 19 of file graph.h.

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