mst.h File Reference

Detailed Description

minimum spanning tree based algorithms for Steiner problems

Author

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

Typedefs
typedef struct minimum_spanning_tree	MST

Functions
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

MST

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
	)

initializes

Parameters

scip	SCIP data structure
g	graph data structure
minspantree	MST data

Definition at line 118 of file mst.c.

References GRAPH::cost, minimum_spanning_tree::csr, minimum_spanning_tree::dheap, graph_csr_allocWithEdgeId(), graph_csr_build(), graph_get_nEdges(), graph_get_nNodes(), graph_heap_create(), nnodes, minimum_spanning_tree::nodes_dist, minimum_spanning_tree::nodes_predEdge, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and SCIPallocMemoryArray.

Referenced by enumExec().

mst_free()

void mst_free	(	SCIP *	scip,
		MST **	minspantree
	)

frees

Parameters

scip	SCIP data structure
minspantree	MST data

Definition at line 145 of file mst.c.

References minimum_spanning_tree::csr, minimum_spanning_tree::dheap, graph_csr_free(), graph_heap_free(), minimum_spanning_tree::nodes_dist, minimum_spanning_tree::nodes_predEdge, SCIPfreeMemory, SCIPfreeMemoryArray, and TRUE.

Referenced by enumExec().

mst_computeOnMarked()

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

computes MST on marked vertices

Parameters

g	graph data structure
nodes_isMarked	should the node be considered?
startnode	start vertex
mst	MST 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

Parameters

g	graph data structure
mst	MST 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
	)