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

#include "mst.h"
#include "portab.h"

Go to the source code of this file.

Functions
static void	computeOnMarked_init (const GRAPH *g, const STP_Bool *nodes_isMarked, int startnode, MST *mst)
static void	computeOnMarked_exec (const GRAPH *g, const STP_Bool *nodes_isMarked, int startnode, MST *mst)
SCIP_RETCODE	mst_init (SCIP *scip, const GRAPH *g, MST **minspantree)
void	mst_free (SCIP *scip, MST **minspantree)
SCIP_Real	mst_getObj (const GRAPH *g, const MST *mst)
void	mst_getSoledges (const GRAPH *g, const MST *mst, int *RESTRICT soledges)
void	mst_computeOnMarked (const GRAPH *g, const STP_Bool *nodes_isMarked, int startnode, MST *mst)

Function Documentation

computeOnMarked_init()

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

inlinestatic

initializes

Parameters

g	graph data structure
nodes_isMarked	should the node be considered?
startnode	start vertex
mst	MST data

Definition at line 32 of file mst.c.

References minimum_spanning_tree::csr, minimum_spanning_tree::dheap, GRAPH::edges, FARAWAY, graph_get_nNodes(), graph_heap_clean(), graph_heap_correct(), nnodes, csr_storage::nnodes, minimum_spanning_tree::nodes_dist, minimum_spanning_tree::nodes_predEdge, SCIP_Real, csr_storage::start, TRUE, and UNKNOWN.

Referenced by mst_computeOnMarked().

computeOnMarked_exec()

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

inlinestatic

executes

Parameters

g	graph data structure
nodes_isMarked	should the node be considered?
startnode	start vertex
mst	MST data

Definition at line 65 of file mst.c.

References CONNECT, csr_storage::cost, minimum_spanning_tree::csr, minimum_spanning_tree::dheap, graph_heap_correct(), graph_heap_deleteMinReturnNode(), csr_storage::head, LT, minimum_spanning_tree::nodes_dist, minimum_spanning_tree::nodes_predEdge, dijkstra_heap::position, SCIP_Real, SCIPdebugMessage, dijkstra_heap::size, csr_storage::start, and UNKNOWN.

Referenced by mst_computeOnMarked().

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_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 *	g,
		const MST *	mst,
		int *RESTRICT	soledges
	)

gets solution edges

Parameters

g	graph data structure
mst	MST data
soledges	to be filled (CONNECT/UNKNOWN)

Definition at line 196 of file mst.c.

References CONNECT, minimum_spanning_tree::csr, csr_storage::edge_id, graph_get_nEdges(), graph_get_nNodes(), nnodes, minimum_spanning_tree::nodes_predEdge, and UNKNOWN.

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().