Solving Constraint Integer Programs

mst.h File Reference

Detailed Description

minimum spanning tree based algorithms for Steiner problems

Daniel Rehfeldt

This file encompasses various minimum spanning tree based algorithms. Note: This file is supposed to (partly) replace graph_path.c in the long run, as it includes the faster implementations.

Definition in file mst.h.

#include "graph.h"
#include "completegraph.h"

Go to the source code of this file.

Data Structures

struct  minimum_spanning_tree


typedef struct minimum_spanning_tree MST


SCIP_RETCODE mst_init (SCIP *, const GRAPH *, MST **)
void mst_free (SCIP *, MST **)
void mst_computeOnMarked (const GRAPH *, const STP_Bool *, int, MST *)
SCIP_Real mst_getObj (const GRAPH *, const MST *)
void mst_getSoledges (const GRAPH *, const MST *, int *RESTRICT)

Typedef Documentation


typedef struct minimum_spanning_tree MST

information for (sparse) MST computations

Function Documentation

◆ mst_init()

SCIP_RETCODE mst_init ( SCIP scip,
const GRAPH g,
MST **  minspantree 

◆ mst_free()

void mst_free ( SCIP scip,
MST **  minspantree 

◆ mst_computeOnMarked()

void mst_computeOnMarked ( const GRAPH g,
const STP_Bool nodes_isMarked,
int  startnode,
MST mst 

computes MST on marked vertices

ggraph data structure
nodes_isMarkedshould the node be considered?
startnodestart vertex
mstMST data

Definition at line 223 of file mst.c.

References computeOnMarked_exec(), computeOnMarked_init(), minimum_spanning_tree::csr, minimum_spanning_tree::dheap, GRAPH::knots, minimum_spanning_tree::nodes_dist, minimum_spanning_tree::nodes_predEdge, GRAPH::source, STP_MWCSP, STP_PCSPG, and GRAPH::stp_type.

Referenced by enumExec(), and solGetMstEdges_csr().

◆ mst_getObj()

SCIP_Real mst_getObj ( const GRAPH g,
const MST mst 

gets objective value of MST

ggraph data structure
mstMST data

Definition at line 168 of file mst.c.

References csr_storage::cost, minimum_spanning_tree::csr, FARAWAY, GE, graph_get_nNodes(), LE, nnodes, minimum_spanning_tree::nodes_predEdge, SCIP_Real, and UNKNOWN.

Referenced by enumExec().

◆ mst_getSoledges()

void mst_getSoledges ( const GRAPH ,
const MST ,
int *  RESTRICT