projects/GraphConvolutionalBranchandBound/mst_8h_source.html

#pragma once

#ifndef BRANCHANDBOUND1TREE_MST_H

#define BRANCHANDBOUND1TREE_MST_H

#include "mfset.h"

#include "fibonacci_heap.h"


typedef struct ConstrainedEdge{

    unsigned short src;

    unsigned short dest;

}ConstrainedEdge;


typedef struct MST{

    bool isValid;

    double cost;

    double prob;

    unsigned short num_nodes;

    unsigned short num_edges;

    Node nodes [MAX_VERTEX_NUM];

    Edge edges [MAX_VERTEX_NUM];

    short edges_matrix [MAX_VERTEX_NUM][MAX_VERTEX_NUM];

}MST;


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


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


void print_mst(const MST * mst);


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


#endif //BRANCHANDBOUND1TREE_MST_H

fibonacci_heap.h
This file contains the declaration of the Fibonacci Heap datastructure for the Minimum Spanning Tree ...

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

add_edge
void add_edge(MST *tree, const Edge *edge)
Add an Edge to the MST.
Definition: mst.c:38

print_mst
void print_mst(const MST *mst)
Print the MST, printing all the information it contains.
Definition: mst.c:70

create_mst
void create_mst(MST *mst, const Node *nodes, unsigned short num_nodes)
Create a Minimum Spanning Tree from a set of Nodes.
Definition: mst.c:17

print_mst_original_weight
void print_mst_original_weight(const MST *mst, const Graph *graph)
Print the MST, printing all the information it contains.
Definition: mst.c:92

ConstrainedEdge
A reduced form of an Edge in the Graph, with only the source and destination Nodes.
Definition: mst.h:21

ConstrainedEdge::src
unsigned short src
The source Node of the Edge.
Definition: mst.h:22

ConstrainedEdge::dest
unsigned short dest
The destination Node of the Edge.
Definition: mst.h:23

Edge
Structure of an Edge.
Definition: graph.h:40

Graph
Structure of a Graph.
Definition: graph.h:51

MST
Minimum Spanning Tree, or MST, and also a 1-Tree.
Definition: mst.h:28

MST::num_nodes
unsigned short num_nodes
The number of Nodes in the MST.
Definition: mst.h:32

MST::edges_matrix
short edges_matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]
-1 if there is no Edge between the two Nodes, otherwise the index of the Edge in the MST.
Definition: mst.h:36

MST::prob
double prob
The probability of the MST, i.e. the average of the probabilities of its Edges.
Definition: mst.h:31

MST::edges
Edge edges[MAX_VERTEX_NUM]
The set of Edges in the MST, these are |V| because the MST can be a 1-Tree.
Definition: mst.h:35

MST::nodes
Node nodes[MAX_VERTEX_NUM]
The set of Nodes in the MST.
Definition: mst.h:34

MST::num_edges
unsigned short num_edges
The number of Edges in the MST.
Definition: mst.h:33

MST::isValid
bool isValid
True if the MST has the correct number of Edges, false otherwise.
Definition: mst.h:29

MST::cost
double cost
The total cost of the MST, i.e. the sum of the weights of the Edges.
Definition: mst.h:30

Node
Structure of a Node.
Definition: graph.h:30