hmap::Graph Class Reference

Graph class, to manipulate graphs in 2D. More...

#include <graph.hpp>

Inheritance diagram for hmap::Graph:

Collaboration diagram for hmap::Graph:

Public Member Functions
	Graph ()
	Construct a new Graph object.
	Graph (Cloud cloud)
	Construct a new Graph object based on a cloud of points.
	Graph (std::vector< Point > points)
	Construct a new Graph object based on a list of points.
	Graph (std::vector< float > x, std::vector< float > y)
	Construct a new Graph object based on x and y coordinates.
void	add_edge (std::vector< int > edge, float weight)
	Add an edge to the graph.
void	add_edge (std::vector< int > edge)
	Add an edge to the graph with default weight.
std::vector< int >	dijkstra (int source_point_index, int target_point_index)
	Return the shortest route between two points using Dijkstra's algorithm.
float	get_edge_length (int k)
	Get the length of edge k.
std::vector< float >	get_edge_x_pairs ()
	Return x coordinates of the edges (as pairs).
std::vector< float >	get_edge_y_pairs ()
	Return y coordinates of the edges (as pairs).
std::vector< float >	get_lengths ()
	Get the length of all the edges.
size_t	get_nedges ()
	Get the number of edges in the graph.
Graph	minimum_spanning_tree_prim ()
	Generate a Minimum Spanning Tree (MST) of the graph using Prim's algorithm.
void	print ()
	Print the graph data to the standard output.
Graph	remove_orphan_points ()
	Remove orphan points from the graph.
void	to_array (Array &array, Vec4< float > bbox, bool color_by_edge_weight=true)
	Project the graph to an array and optionally color by edge weight.
void	to_array_fractalize (Array &array, Vec4< float > bbox, int iterations, uint seed, float sigma=0.3f, int orientation=0.f, float persistence=1.f)
	Apply fractalization to graph edges and project to an array.
Array	to_array_sdf (Vec2< int > shape, Vec4< float > bbox, Array *p_noise_x=nullptr, Array *p_noise_y=nullptr, Vec4< float > bbox_array={0.f, 1.f, 0.f, 1.f})
	Generate an array filled with the Signed Distance Function (SDF) to the graph.
void	to_csv (std::string fname_xy, std::string fname_adjacency)
	Export graph data to CSV files.
void	to_png (std::string fname, Vec2< int > shape={512, 512})
	Export the graph as a PNG image file.
void	update_adjacency_matrix ()
	Update the adjacency matrix of the graph.
void	update_connectivity ()
	Update the point connectivity information.
Public Member Functions inherited from hmap::Cloud
	Cloud ()
	Default constructor for the Cloud class.
virtual	~Cloud ()=default
	Cloud (int npoints, uint seed, Vec4< float > bbox={0.f, 1.f, 0.f, 1.f})
	Constructs a new Cloud object with random positions and values.
	Cloud (const std::vector< Point > &points)
	Constructs a new Cloud object based on a list of existing points.
	Cloud (const std::vector< float > &x, const std::vector< float > &y, float default_value=0.f)
	Constructs a new Cloud object from lists of x and y coordinates.
	Cloud (const std::vector< float > &x, const std::vector< float > &y, const std::vector< float > &v)
	Constructs a new Cloud object from lists of x and y coordinates with assigned values.
void	add_point (const Point &p)
	Add a new point to the cloud.
void	clear ()
	Clear all data from the cloud.
bool	from_csv (const std::string &fname)
	Loads point data from a CSV file into the Cloud object.
Vec4< float >	get_bbox () const
	Get the bounding box of the cloud.
Point	get_center () const
	Calculates the centroid of a set of points.
std::vector< int >	get_convex_hull_point_indices () const
	Computes the indices of the points that form the convex hull of a set of points.
size_t	get_npoints () const
	Get the number of points in the cloud.
std::vector< float >	get_values () const
	Get the values assigned to the points in the cloud.
float	get_values_max () const
	Get the maximum value among the points in the cloud.
float	get_values_min () const
	Get the minimum value among the points in the cloud.
virtual std::vector< float >	get_x () const
	Get the x coordinates of the points in the cloud.
virtual std::vector< float >	get_xy () const
	Get the concatenated x and y coordinates of the points in the cloud.
virtual std::vector< float >	get_y () const
	Get the y coordinates of the points in the cloud.
std::vector< float >	interpolate_values_from_array (const Array &array, Vec4< float > bbox)
	Interpolate values from an array at the points' (x, y) locations.
void	print ()
	Print information about the cloud's points.
void	randomize (uint seed, Vec4< float > bbox={0.f, 1.f, 0.f, 1.f})
	Randomize the positions and values of the cloud points.
void	rejection_filter_density (const Array &density_mask, uint seed, const Vec4< float > &bbox={0.f, 1.f, 0.f, 1.f})
	Filter a point cloud using rejection sampling based on a density mask.
void	remap_values (float vmin, float vmax)
	Remap the values of the cloud points to a target range.
void	remove_point (int point_idx)
	Remove a point from the cloud.
void	set_points (const std::vector< float > &x, const std::vector< float > &y)
	Set points of the using x, y coordinates.
void	set_values (const std::vector< float > &new_values)
	Set new values for the cloud points.
void	set_values (float new_value)
	Set a single value for all cloud points.
void	set_values_from_array (const Array &array, const Vec4< float > &bbox={0.f, 1.f, 0.f, 1.f})
	Set the values of the cloud points using values from an underlying array.
void	set_values_from_border_distance (const Vec4< float > &bbox={0.f, 1.f, 0.f, 1.f})
	Sets point values based on their distance to the bounding box border.
void	set_values_from_chull_distance ()
	Set the values of the cloud points based on the distance to the convex hull of the cloud.
void	set_values_from_min_distance ()
	Sets point values based on the distance to their nearest neighbor.
void	to_array (Array &array, Vec4< float > bbox={0.f, 1.f, 0.f, 1.f}) const
	Project the cloud points onto an array.
Array	to_array_sdf (Vec2< int > shape, Vec4< float > bbox, Array *p_noise_x=nullptr, Array *p_noise_y=nullptr, Vec4< float > bbox_array={0.f, 1.f, 0.f, 1.f}) const
	Generate an array filled with the signed distance function (SDF) to the cloud points.
void	to_array_interp (Array &array, Vec4< float > bbox={0.f, 1.f, 0.f, 1.f}, InterpolationMethod2D interpolation_method=InterpolationMethod2D::DELAUNAY, Array *p_noise_x=nullptr, Array *p_noise_y=nullptr, Vec4< float > bbox_array={0.f, 1.f, 0.f, 1.f}) const
	Interpolate the values of an array using the cloud points.
void	to_csv (const std::string &fname) const
	Export the cloud data to a CSV file.
Graph	to_graph_delaunay ()
	Convert the cloud to a graph using Delaunay triangulation.
void	to_png (const std::string &fname, int cmap, Vec4< float > bbox={0.f, 1.f, 0.f, 1.f}, int depth=CV_8U, Vec2< int > shape={512, 512})
	Saves the current data as a PNG image file.

Public Attributes
std::vector< std::vector< int > >	edges = {}
	Edges of the graph.
std::vector< float >	weights = {}
	Edge weights.
std::vector< std::vector< int > >	connectivity = {}
	Store point connectivity.
std::map< std::pair< int, int >, float >	adjacency_matrix
	Adjacency matrix.
Public Attributes inherited from hmap::Cloud
std::vector< Point >	points = {}
	Points of the cloud.

Detailed Description

Graph class, to manipulate graphs in 2D.

This class represents a 2D graph, allowing the creation, manipulation, and analysis of graphs derived from point clouds. It supports operations such as graph construction, traversal, and various geometric analyses. This class inherits from the Cloud class, leveraging the functionalities of point clouds while adding graph-specific methods.

Example

#include "highmap.hpp"
 
int main(void)
{
  int seed = 1;
 
  hmap::Vec4<float> bbox = {-1.f, 2.f, 0.f, 5.f};
 
  // create a cloud of points and convert it to a graph using Delaunay
  // triangulation
  int         npoints = 10;
  hmap::Cloud cloud = hmap::Cloud(npoints, seed, bbox);
  hmap::Graph graph = cloud.to_graph_delaunay();
 
  graph.print();
  graph.to_png("ex_graph0.png");
 
  graph.update_adjacency_matrix();
  graph.to_csv("ex_graph_nodes.csv", "ex_graph_adj.csv");
}

Result

Constructor & Destructor Documentation

Graph() [1/4]

hmap::Graph::Graph ( )

inline

Construct a new Graph object.

The default constructor initializes a new Graph object. It calls the base class constructor Cloud() to set up any inherited functionality from the Cloud class. This constructor sets up an empty graph with no edges, weights, connectivity, or adjacency matrix.

Graph() [2/4]

hmap::Graph::Graph ( Cloud  cloud )

inline

Construct a new Graph object based on a cloud of points.

This constructor initializes a Graph object using a Cloud object. The Cloud object provides the points which will be used to construct the graph. This constructor is useful when you have a Cloud object and want to create a Graph representation from it.

Parameters

cloud

The cloud of points used to initialize the graph.

Graph() [3/4]

hmap::Graph::Graph ( std::vector< Point >  points )

inline

Construct a new Graph object based on a list of points.

This constructor initializes a Graph object using a vector of Point objects. The Point objects are used to populate the vertices of the graph. This constructor is useful when you have a list of Point objects and want to create a Graph representation from them.

Parameters

points

The list of points used to initialize the graph.

Graph() [4/4]

hmap::Graph::Graph ( std::vector< float >  x, std::vector< float >  y  )

inline

Construct a new Graph object based on x and y coordinates.

This constructor initializes a Graph object using separate vectors for x and y coordinates. The points are created from these coordinates and used to populate the vertices of the graph. This constructor is useful when you have x and y coordinates and want to create a Graph representation from them.

Parameters

x	Vector of x coordinates for the points.
y	Vector of y coordinates for the points.

Member Function Documentation

add_edge() [1/2]

void hmap::Graph::add_edge	(	std::vector< int >	edge,
		float	weight
	)

Add an edge to the graph.

This method adds a new edge to the graph. The edge is specified by a vector of two indices representing the points connected by the edge. The weight of the edge can be provided explicitly; if not provided, the Euclidean distance between the connected points is used as the default weight.

Parameters

edge	A vector of two integers representing the indices of the points connected by the edge.
weight	The weight of the edge. If not provided, the default weight is calculated as the Euclidean distance between the points.

add_edge() [2/2]

void hmap::Graph::add_edge

(

std::vector< int >

edge

)

Add an edge to the graph with default weight.

This method adds a new edge to the graph. The edge is specified by a vector of two indices representing the points connected by the edge. The weight of the edge is calculated as the Euclidean distance between the connected points.

Parameters

edge	A vector of two integers representing the indices of the points connected by the edge.

dijkstra()

std::vector< int > hmap::Graph::dijkstra	(	int	source_point_index,
		int	target_point_index
	)

Return the shortest route between two points using Dijkstra's algorithm.

This method computes the shortest path from a specified source point to a target point in the graph using Dijkstra's algorithm. It returns a vector of point indices representing the route from the source to the target point.

Parameters

source_point_index	The index of the starting point in the graph.
target_point_index	The index of the ending point in the graph.

Returns

std::vector<int> A vector of point indices representing the shortest path from the source to the target.

Example

#include <iostream>
 
#include "highmap.hpp"
 
int main(void)
{
  int               seed = 1;
  hmap::Vec4<float> bbox = {-1.f, 2.f, 0.f, 5.f};
 
  // create a cloud of points and convert it to a graph using Delaunay
  // triangulation
  int         npoints = 15;
  hmap::Cloud cloud = hmap::Cloud(npoints, seed, bbox);
  hmap::Graph graph = cloud.to_graph_delaunay();
 
  graph.print();
 
  graph.update_adjacency_matrix();
  graph.update_connectivity();
 
  int              i_point_start = 0;
  int              i_point_end = 4;
  std::vector<int> route = graph.dijkstra(i_point_start, i_point_end);
 
  std::cout << "Route (point indices):\n";
  for (auto &p : route)
    std::cout << p << "\n";
}

get_edge_length()

float hmap::Graph::get_edge_length

(

int

k

)

Get the length of edge k.

This method calculates the Euclidean length of a specific edge in the graph. The edge is identified by the index k, and its length is determined by the distance between the two vertices connected by the edge.

Parameters

k	Index of the edge for which the length is to be computed.

Returns

float The Euclidean length of the edge.

get_edge_x_pairs()

std::vector< float > hmap::Graph::get_edge_x_pairs

(

)

Return x coordinates of the edges (as pairs).

This method returns the x coordinates of the endpoints of each edge in the graph. The coordinates are returned as a vector of floats, where each pair of floats represents the x coordinates of an edge's endpoints.

Returns

std::vector<float> The x coordinates of the edges.

get_edge_y_pairs()

std::vector< float > hmap::Graph::get_edge_y_pairs

(

)

Return y coordinates of the edges (as pairs).

This method returns the y coordinates of the endpoints of each edge in the graph. The coordinates are returned as a vector of floats, where each pair of floats represents the y coordinates of an edge's endpoints.

Returns

std::vector<float> The y coordinates of the edges.

get_lengths()

std::vector< float > hmap::Graph::get_lengths

(

)

Get the length of all the edges.

This method returns the lengths of all the edges in the graph. The lengths are computed using the Euclidean distance formula, and the result is returned as a vector of floats.

Returns

std::vector<float> The lengths of all the edges in the graph.

get_nedges()

size_t hmap::Graph::get_nedges

(

)

Get the number of edges in the graph.

This method returns the total number of edges present in the graph. The edges are stored in a vector, and this method returns the size of that vector, which represents the number of edges.

Returns

size_t The number of edges in the graph.

minimum_spanning_tree_prim()

Graph hmap::Graph::minimum_spanning_tree_prim

(

)

Generate a Minimum Spanning Tree (MST) of the graph using Prim's algorithm.

This method creates a Minimum Spanning Tree from the graph using Prim's algorithm. It returns a new Graph object that represents the MST, which connects all the points in the graph with the minimum total edge weight.

Returns

Graph The Minimum Spanning Tree (MST) of the original graph.

Example

#include "highmap.hpp"
 
int main(void)
{
  int seed = 1;
 
  hmap::Vec4<float> bbox = {-1.f, 2.f, 0.f, 5.f};
 
  // create a cloud of points and convert it to a graph using Delaunay
  // triangulation
  int         npoints = 10;
  hmap::Cloud cloud = hmap::Cloud(npoints, seed, bbox);
  hmap::Graph graph_delaunay = cloud.to_graph_delaunay();
 
  graph_delaunay.update_adjacency_matrix();
  hmap::Graph graph_mst = graph_delaunay.minimum_spanning_tree_prim();
 
  graph_delaunay.to_png("ex_graph_minimum_spanning_tree_prim0.png");
  graph_mst.to_png("ex_graph_minimum_spanning_tree_prim1.png");
}

Result**

print()

void hmap::Graph::print

(

)

Print the graph data to the standard output.

This method prints the current state of the graph, including point coordinates, edges, and edge weights.

remove_orphan_points()

Graph hmap::Graph::remove_orphan_points

(

)

Remove orphan points from the graph.

Orphan points are points that are not connected to any edges. This method removes such points from the graph and returns a new Graph object that excludes these orphan points.

Returns

Graph A new graph object with orphan points removed.

to_array()

void hmap::Graph::to_array	(	Array &	array,
		Vec4< float >	bbox,
		bool	color_by_edge_weight = true
	)

Project the graph to an array and optionally color by edge weight.

This method projects the graph onto a 2D array. The array's elements are filled based on the graph's structure, and optionally, the color can represent edge weights. This allows visual representation of the graph in array form.

Parameters

array	The input array to project the graph onto.
bbox	The bounding box for the array.
color_by_edge_weight	If true, colors the array based on edge weights; otherwise, colors by node values.

to_array_fractalize()

void hmap::Graph::to_array_fractalize	(	Array &	array,
		Vec4< float >	bbox,
		int	iterations,
		uint	seed,
		float	sigma = 0.3f,
		int	orientation = 0.f,
		float	persistence = 1.f
	)

Apply fractalization to graph edges and project to an array.

This method applies a fractalization process to the graph edges, creating a more complex structure, and then projects the result onto an array. The fractalization includes multiple iterations and random Gaussian displacement to generate a fractal effect. The parameters control the number of iterations, randomness, and how the graph path is altered.

Parameters

array	The input array to project the fractalized graph onto.
bbox	The bounding box for the array.
iterations	Number of fractalization iterations to perform.
seed	Random seed number for stochastic processes.
sigma	Half-width of the Gaussian displacement normalized by the distance between points.
orientation	Displacement orientation: 0 for random inward/outward, 1 to inflate, -1 to deflate.
persistence	Noise persistence factor with respect to iteration number.

to_array_sdf()

Array hmap::Graph::to_array_sdf	(	Vec2< int >	shape,
		Vec4< float >	bbox,
		Array *	p_noise_x = nullptr,
		Array *	p_noise_y = nullptr,
		Vec4< float >	bbox_array = {0.f, 1.f, 0.f, 1.f}
	)

Generate an array filled with the Signed Distance Function (SDF) to the graph.

This method computes the signed distance function for the graph, which measures the distance of each point in the array to the nearest edge of the graph. The result is projected onto an output array. The optional noise arrays can be used for domain warping.

Parameters

shape	The shape of the output array.
bbox	The bounding box defining the area over which the SDF is computed.
p_noise_x	Reference to the input noise array for domain warping in the x-direction (optional).
p_noise_y	Reference to the input noise array for domain warping in the y-direction (optional).
bbox_array	The bounding box of the destination array.

Returns

Array The resulting array with the signed distance function values.

Example

#include "highmap.hpp"
 
int main(void)
{
  hmap::Vec2<int> shape = {256, 256};
  uint            seed = 1;
 
  auto noise = hmap::noise_fbm(hmap::NoiseType::PERLIN, shape, {2, 2}, seed);
  hmap::remap(noise, 0.f, 0.2f);
 
  hmap::Vec4<float> bbox = {0.2f, 0.8f, 0.2f, 0.8f};
  hmap::Cloud       cloud = hmap::Cloud(5, seed, bbox);
 
  hmap::Vec4<float> bbox_array = {0.f, 1.f, 0.f, 1.f};
 
  hmap::Array z_sdf1 = cloud.to_array_sdf(shape, bbox_array);
  hmap::Array z_sdf2 = cloud.to_array_sdf(shape, bbox_array, &noise, &noise);
 
  hmap::export_banner_png("ex_cloud_sdf.png",
                          {z_sdf1, z_sdf2},
                          hmap::Cmap::JET);
}

Result**

to_csv()

void hmap::Graph::to_csv	(	std::string	fname_xy,
		std::string	fname_adjacency
	)

Export graph data to CSV files.

This method exports the graph data to two separate CSV files: one for node coordinates and one for the adjacency matrix. The node coordinates file contains the (x, y) coordinates of the graph's nodes, and the adjacency matrix file contains the graph's connectivity information.

Parameters

fname_xy	Filename for the CSV file containing node (x, y) coordinates.
fname_adjacency	Filename for the CSV file containing the adjacency matrix.

to_png()

void hmap::Graph::to_png	(	std::string	fname,
		Vec2< int >	shape = {512, 512}
	)

Export the graph as a PNG image file.

This method exports a visual representation of the graph as a PNG image file. The resolution of the image can be specified using the shape parameter.

Parameters

fname	The file name for the PNG image.
shape	The resolution of the image in pixels (width, height).

update_adjacency_matrix()

void hmap::Graph::update_adjacency_matrix

(

)

Update the adjacency matrix of the graph.

This method updates the adjacency matrix based on the current graph edges and weights. The adjacency matrix represents the connectivity between nodes in the graph.

update_connectivity()

void hmap::Graph::update_connectivity

(

)

Update the point connectivity information.

This method updates the point connectivity data, which describes the relationships between nodes in the graph based on the current edges.

Member Data Documentation

edges

std::vector<std::vector<int> > hmap::Graph::edges = {}

Edges of the graph.

This member variable stores the edges of the graph. Each edge is represented as a pair of indices referring to the vertices in the graph. The edges are stored as a vector of vectors, where each inner vector contains the indices of vertices connected by that edge.

weights

std::vector<float> hmap::Graph::weights = {}

Edge weights.

This member variable stores the weights associated with the edges of the graph. Each weight corresponds to an edge and is stored in a vector. The weights are used to represent the cost or distance associated with traveling along an edge in the graph.

connectivity

std::vector<std::vector<int> > hmap::Graph::connectivity = {}

Store point connectivity.

This member variable stores the connectivity information of the points in the graph. It is represented as a vector of vectors, where each inner vector contains the indices of neighboring vertices connected to the corresponding point.

adjacency_matrix

std::map<std::pair<int, int>, float> hmap::Graph::adjacency_matrix

Adjacency matrix.

This member variable represents the adjacency matrix of the graph. It is a map where each key is a pair of vertex indices and the value is the weight of the edge connecting those vertices. The adjacency matrix provides a way to quickly access the weight of an edge between any two vertices.

---

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

• HighMap/include/highmap/geometry/graph.hpp
• HighMap/src/geometry/graph.cpp