mst.h File Reference

This file contains the declaration of the Minimum Spanning Tree datastructure. More...

#include "mfset.h"
#include "fibonacci_heap.h"

Go to the source code of this file.

Classes
struct	ConstrainedEdge
	A reduced form of an Edge in the Graph, with only the source and destination Nodes. More...
struct	MST
	Minimum Spanning Tree, or MST, and also a 1-Tree. More...

Macros
#define	BRANCHANDBOUND1TREE_MST_H

Typedefs
typedef struct ConstrainedEdge	ConstrainedEdge
	A reduced form of an Edge in the Graph, with only the source and destination Nodes.
typedef struct MST	MST
	Minimum Spanning Tree, or MST, and also a 1-Tree.

Functions
void	create_mst (MST *mst, const Node *nodes, unsigned short num_nodes)
	Create a Minimum Spanning Tree from a set of Nodes.
void	add_edge (MST *tree, const Edge *edge)
	Add an Edge to the MST.
void	print_mst (const MST *mst)
	Print the MST, printing all the information it contains.
void	print_mst_original_weight (const MST *mst, const Graph *graph)
	Print the MST, printing all the information it contains.

Detailed Description

This file contains the declaration of the Minimum Spanning Tree datastructure.

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 mst.h.

Macro Definition Documentation

BRANCHANDBOUND1TREE_MST_H

#define BRANCHANDBOUND1TREE_MST_H

Definition at line 15 of file mst.h.

Typedef Documentation

ConstrainedEdge

typedef struct ConstrainedEdge ConstrainedEdge

A reduced form of an Edge in the Graph, with only the source and destination Nodes.

MST

typedef struct MST MST

Minimum Spanning Tree, or MST, and also a 1-Tree.

Function Documentation

add_edge()

void add_edge	(	MST *	tree,
		const Edge *	edge
	)

Add an Edge to the MST.

Parameters

tree	The Minimum Spanning Tree.
edge	The Edge to add.

Definition at line 38 of file mst.c.

create_mst()

void create_mst	(	MST *	mst,
		const Node *	nodes,
		unsigned short	num_nodes
	)

Create a Minimum Spanning Tree from a set of Nodes.

Parameters

mst	The Minimum Spanning Tree to be initialized.
nodes	The set of Nodes.
num_nodes	The number of Nodes.

Definition at line 17 of file mst.c.

print_mst()

void print_mst

(

const MST *

mst

)

Print the MST, printing all the information it contains.

Parameters

tree	The Minimum Spanning Tree.

Definition at line 70 of file mst.c.

print_mst_original_weight()

void print_mst_original_weight	(	const MST *	mst,
		const Graph *	graph
	)

Print the MST, printing all the information it contains.

This method is used to print a 1Tree with original. Edge weights, since in the branch and bound algorithm, with the dual procedure the Edge weights are changed.

Parameters

tree	The Minimum Spanning Tree.
graph	The Graph from which the MST was created.

Definition at line 92 of file mst.c.