mfset.h File Reference

This file contains the declaration of the Merge-Find Set datastructure for the Minimum Spanning Tree problem. More...

#include "graph.h"

Go to the source code of this file.

Classes
struct	Set
	A Set is a node in the Forest. More...
struct	Forest
	A Forest is a list of Sets. More...

Typedefs
typedef struct Set	Set
	A Set is a node in the Forest.
typedef struct Forest	Forest
	A Forest is a list of Sets.

Functions
void	create_forest (Forest *forest, const Node *nodes, unsigned short num_nodes)
	Create a new Forest with n Sets, each Set containing a Node, without constraints.
void	create_forest_constrained (Forest *forest, const Node *nodes, unsigned short num_nodes, unsigned short candidateId)
	Create a new Forest with n Sets, each Set containing a Node, with constraints.
void	merge (Set *set1, Set *set2)
	Merge two Sets in the Forest if they are not already in the same Set.
Set *	find (Set *set)
	Find the root of a Set.
void	print_forest (const Forest *forest)
	Print all the Forest.

Detailed Description

This file contains the declaration of the Merge-Find Set datastructure for the Minimum Spanning Tree problem.

Author

Lorenzo Sciandra

Version

1.0.0 @data 2024-05-1

Copyright

Copyright (c) 2024, license MIT

Repo: https://github.com/LorenzoSciandra/GraphConvolutionalBranchandBound

Definition in file mfset.h.

Typedef Documentation

Forest

typedef struct Forest Forest

A Forest is a list of Sets.

Set

typedef struct Set Set

A Set is a node in the Forest.

Function Documentation

create_forest()

void create_forest	(	Forest *	forest,
		const Node *	nodes,
		unsigned short	num_nodes
	)

Create a new Forest with n Sets, each Set containing a Node, without constraints.

Parameters

nodes	Pointer to the List of Nodes.
num_nodes	Number of Nodes in the List.
forest	Pointer to the Forest to be initialized.

Definition at line 31 of file mfset.c.

create_forest_constrained()

void create_forest_constrained	(	Forest *	forest,
		const Node *	nodes,
		unsigned short	num_nodes,
		unsigned short	candidateId
	)

Create a new Forest with n Sets, each Set containing a Node, with constraints.

The candidateId Node is not added to the Forest because for the 1-tree I need a MST on the remaining Nodes.

Parameters

nodes	Pointer to the List of Nodes.
num_nodes	Number of Nodes in the List.
candidateId	Id of the Node in the List to be excluded from the Forest.
forest	Pointer to the Forest to be initialized.

Definition at line 17 of file mfset.c.

find()

Set * find

(

Set *

set

)

Find the root of a Set.

Complexity: O(log n), only a path in the tree is traversed. The parent Set of all the Nodes in the path are updated to point to the root, to reduce the complexity of the next find operations.

Parameters

set	Pointer to the Set.

Returns

Pointer to the root of the Set.

Definition at line 44 of file mfset.c.

merge()

void merge	(	Set *	set1,
		Set *	set2
	)

Merge two Sets in the Forest if they are not already in the same Set.

The Set with the highest rank is the parent of the other. This is done to let the find operation run in O(log n) time. Complexity: O(log n_1 + log n_2)

Parameters

set1	Pointer to the first Set.
set2	Pointer to the second Set.

Definition at line 53 of file mfset.c.

print_forest()

void print_forest

(

const Forest *

forest

)

Print all the Forest.

Used for debugging purposes.

Parameters

forest

Pointer to the Forest.

Definition at line 72 of file mfset.c.