Class to store a graph with node coloring and related information. More...

#include <qbpp_graph_color.hpp>

Collaboration diagram for qbpp::graph_color::GraphColorMap:

Public Member Functions
	GraphColorMap (uint32_t grid_size=100)
	Constructor to Create an empty map. More...

void	gen_random_map (uint32_t n, bool is_circle=false)
	Generate a random map with n nodes. More...

void	gen_proximity_edges (uint32_t proximity)
	Create an edges between nodes that are close to each other. More...

void	gen_delaunay_edges ()
	Create edges between nodes using the Delaunay triangulation. More...

void	set_color_histogram (const GraphColorQuadModel &model, const qbpp::Sol &sol)
	Set the color histogram of the nodes. More...

uint32_t	node_count () const
	Gets the number of nodes in the map. More...

uint32_t	get_grid_size () const
	Gets the size of the grid. More...

const std::vector< std::pair< uint32_t, uint32_t > >	get_edges () const

void	draw (const std::string &filename)
	Draw the graph in a file. More...

void	print ()
	Displays the histogram of the colors. More...

Private Member Functions
void	add_node (uint32_t x, uint32_t y)
	Add a node to the map. More...

uint32_t	dist (const std::pair< int32_t, int32_t > &p1, const std::pair< int32_t, int32_t > &p2) const
	Compute the Euclidean distance between two nodes. More...

uint32_t	dist (size_t i, size_t j) const
	Compute the Euclidean distance between two nodes. More...

uint32_t	min_dist (uint32_t x, uint32_t y) const
	Compute the minimum distance between a new node and all other nodes. More...

std::pair< int32_t, int32_t > &	operator[] (uint32_t index)
	Get the position of the node at index i. More...

Private Attributes
const uint32_t	grid_size_
	Size of the grid. grid_size x grid_size coordinates are used for the map. More...

std::vector< std::pair< int32_t, int32_t > >	nodes_
	List of nodes with coordinate (x, y) More...

std::vector< std::pair< uint32_t, uint32_t > >	edges_
	List of edges with the distance between the nodes. More...

qbpp::Vector< int32_t >	color_
	List of colors of the nodes. More...

std::vector< uint32_t >	color_hist_
	Histogram of the colors. More...

uint32_t	failure_ = 0
	Number of failure nodes. More...

Detailed Description

Class to store a graph with node coloring and related information.

This class includes nodes with coordinates, edges between the nodes, colors of the nodes, and the histogram of the colors.

Definition at line 31 of file qbpp_graph_color.hpp.

Constructor & Destructor Documentation

◆ GraphColorMap()

qbpp::graph_color::GraphColorMap::GraphColorMap ( uint32_t grid_size = 100 )

inline

Constructor to Create an empty map.

Parameters

grid_size Size of the grid. grid_size x grid_size coordinates are used for the map.

Definition at line 107 of file qbpp_graph_color.hpp.

Member Function Documentation

◆ add_node()

void qbpp::graph_color::GraphColorMap::add_node	(	uint32_t	x,
		uint32_t	y
	)

inlineprivate

Add a node to the map.

Parameters

x	x-coordinate of the node
y	y-coordinate of the node

Definition at line 63 of file qbpp_graph_color.hpp.

Here is the caller graph for this function:

◆ dist() [1/2]

uint32_t qbpp::graph_color::GraphColorMap::dist	(	const std::pair< int32_t, int32_t > &	p1,
		const std::pair< int32_t, int32_t > &	p2
	)		const

inlineprivate

Compute the Euclidean distance between two nodes.

Parameters

p1	First node
p2	Second node

Returns: Euclidean distance between the two nodes

Note: The distance is rounded to the nearest integer

Definition at line 70 of file qbpp_graph_color.hpp.

Here is the caller graph for this function:

◆ dist() [2/2]

uint32_t qbpp::graph_color::GraphColorMap::dist	(	size_t	i,
		size_t	j
	)		const

inlineprivate

Compute the Euclidean distance between two nodes.

Parameters

i	Index of the first node
j	Index of the second node

Returns: Euclidean distance between the two nodes

Definition at line 81 of file qbpp_graph_color.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ min_dist()

uint32_t qbpp::graph_color::GraphColorMap::min_dist	(	uint32_t	x,
		uint32_t	y
	)		const

inlineprivate

Compute the minimum distance between a new node and all other nodes.

Parameters

x	x-coordinate of the node
y	y-coordinate of the node

Returns: Minimum distance between the node and all other nodes

Definition at line 88 of file qbpp_graph_color.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ operator[]()

std::pair<int32_t, int32_t>& qbpp::graph_color::GraphColorMap::operator[] ( uint32_t index )

inlineprivate

Get the position of the node at index i.

Parameters

index Index of the node

Returns: Pair of coordinates (x, y) of the node

Definition at line 99 of file qbpp_graph_color.hpp.

◆ gen_random_map()

void qbpp::graph_color::GraphColorMap::gen_random_map	(	uint32_t	n,
		bool	is_circle = `false`
	)

inline

Generate a random map with n nodes.

Parameters

n	Number of nodes
is_circle	true if all nodes are placed in a circle

Definition at line 198 of file qbpp_graph_color.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ gen_proximity_edges()

void qbpp::graph_color::GraphColorMap::gen_proximity_edges ( uint32_t proximity )

inline

Create an edges between nodes that are close to each other.

Parameters

proximity the maximum distance between two nodes to create an edge

Definition at line 227 of file qbpp_graph_color.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ gen_delaunay_edges()

void qbpp::graph_color::GraphColorMap::gen_delaunay_edges ( )

inline

Create edges between nodes using the Delaunay triangulation.

Definition at line 237 of file qbpp_graph_color.hpp.

Here is the caller graph for this function:

◆ set_color_histogram()

void qbpp::graph_color::GraphColorMap::set_color_histogram	(	const GraphColorQuadModel &	model,
		const qbpp::Sol &	sol
	)

inline

Set the color histogram of the nodes.

Parameters

model	QUBO model for the graph coloring
sol	Solution of the QUBO model

This function sets the color histogram from the QUBO model with the solution.

Definition at line 258 of file qbpp_graph_color.hpp.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ node_count()

uint32_t qbpp::graph_color::GraphColorMap::node_count ( ) const

inline

Gets the number of nodes in the map.

Returns: Number of nodes in the map

Definition at line 131 of file qbpp_graph_color.hpp.

Here is the caller graph for this function:

◆ get_grid_size()

uint32_t qbpp::graph_color::GraphColorMap::get_grid_size ( ) const

inline

Gets the size of the grid.

Returns: Size of the grid

Definition at line 135 of file qbpp_graph_color.hpp.

◆ get_edges()

const std::vector<std::pair<uint32_t, uint32_t> > qbpp::graph_color::GraphColorMap::get_edges ( ) const

inline

Definition at line 137 of file qbpp_graph_color.hpp.

Here is the caller graph for this function:

◆ draw()

void qbpp::graph_color::GraphColorMap::draw ( const std::string & filename )

inline

Draw the graph in a file.

Parameters

filename Name of the file to save the graph

Note: The file format is determined by the extension of the filename; The graph is drawn using the neato program from the Graphviz suite

Definition at line 273 of file qbpp_graph_color.hpp.

Here is the caller graph for this function:

◆ print()

void qbpp::graph_color::GraphColorMap::print ( )

inline

Displays the histogram of the colors.

Note: set_color_histogram must be called before calling this function.

Definition at line 149 of file qbpp_graph_color.hpp.

Here is the caller graph for this function:

Member Data Documentation

◆ grid_size_

const uint32_t qbpp::graph_color::GraphColorMap::grid_size_

private

Size of the grid. grid_size x grid_size coordinates are used for the map.

Definition at line 34 of file qbpp_graph_color.hpp.

◆ nodes_

std::vector<std::pair<int32_t, int32_t> > qbpp::graph_color::GraphColorMap::nodes_

private

List of nodes with coordinate (x, y)

nodes_[i] = (x, y) is the coordinate of the i-th node.

Definition at line 38 of file qbpp_graph_color.hpp.

◆ edges_

std::vector<std::pair<uint32_t, uint32_t> > qbpp::graph_color::GraphColorMap::edges_

private

List of edges with the distance between the nodes.

edges_[i] = (j, k) means that the j-th and k-th nodes are connected.

Note: j < k is always satisfied.

Definition at line 44 of file qbpp_graph_color.hpp.

◆ color_

qbpp::Vector<int32_t> qbpp::graph_color::GraphColorMap::color_

private

List of colors of the nodes.

color_[i] is the color of the i-th node.

Definition at line 49 of file qbpp_graph_color.hpp.

◆ color_hist_

std::vector<uint32_t> qbpp::graph_color::GraphColorMap::color_hist_

private

Histogram of the colors.

color_hist_[i] is the number of nodes with color i.

Definition at line 53 of file qbpp_graph_color.hpp.

◆ failure_

uint32_t qbpp::graph_color::GraphColorMap::failure_ = 0

private

Number of failure nodes.

failure_ is the number of nodes that have no color.

Note: failure means that the resulting one-hot vector is not valid.

Definition at line 58 of file qbpp_graph_color.hpp.

The documentation for this class was generated from the following file:

sample/qbpp_graph_color.hpp

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ GraphColorMap()

Member Function Documentation

◆ add_node()

◆ dist() [1/2]

◆ dist() [2/2]

◆ min_dist()

◆ operator[]()

◆ gen_random_map()

◆ gen_proximity_edges()

◆ gen_delaunay_edges()

◆ set_color_histogram()

◆ node_count()

◆ get_grid_size()

◆ get_edges()

◆ draw()

◆ print()

Member Data Documentation

◆ grid_size_

◆ nodes_

◆ edges_

◆ color_

◆ color_hist_

◆ failure_