enumeration.c File Reference

Detailed Description

includes enumeration algorithms for Steiner tree problems

Author

Daniel Rehfeldt

Methods for enumerating solutions (i.e. trees) to Steiner tree problems.

A list of all interface methods can be found in enumeration.h

Definition in file enumeration.c.

#include <assert.h>
#include "portab.h"
#include "solstp.h"
#include "enumeration.h"

Go to the source code of this file.

Functions
static void	pcmwFindMax2Terms (const GRAPH *g, int *term_max, int *term_max2)
static SCIP_RETCODE	tryPathPcMw (SCIP *scip, const GRAPH *g, int term_start, int term_end, STP_Bool *RESTRICT nodes_inPath)
static SCIP_RETCODE	findSolRPcMw (SCIP *scip, GRAPH *g, int *RESTRICT result)
static void	findSolPcMw1Term (const GRAPH *g, int *RESTRICT result)
static SCIP_RETCODE	findSolPcMw2Term (SCIP *scip, GRAPH *g, int *RESTRICT result)
static SCIP_RETCODE	findSolPcMw (SCIP *scip, GRAPH *g, int *RESTRICT result)
SCIP_RETCODE	enumeration_findSolPcMw (SCIP *scip, GRAPH *g, int *RESTRICT result)
SCIP_Bool	enumeration_isPossible (const GRAPH *g)

Function Documentation

pcmwFindMax2Terms()

static void pcmwFindMax2Terms ( const GRAPH *  g, int *  term_max, int *  term_max2  )

static

Finds maximum two terminals. Terminal for rooted problems is always the maximum.

Parameters

g	graph data structure
term_max	pointer to store maximum-prize terminal
term_max2	pointer to store second-maximum-prize terminal

Definition at line 42 of file enumeration.c.

References graph_get_nNodes(), graph_pc_isRootedPcMw(), Is_term, nnodes, GRAPH::prize, SCIP_Real, GRAPH::source, GRAPH::term, and UNKNOWN.

Referenced by findSolPcMw2Term(), and findSolRPcMw().

tryPathPcMw()

static SCIP_RETCODE tryPathPcMw ( SCIP *  scip, const GRAPH *  g, int  term_start, int  term_end, STP_Bool *RESTRICT  nodes_inPath  )

static

builds path and connect if possible

Parameters

scip	SCIP data structure
g	graph data structure
term_start	start vertex, from which to connect
term_end	vertex to be reached
nodes_inPath	for each node: is in path?

Definition at line 79 of file enumeration.c.

References BMSclearMemoryArray, GRAPH::cost, shortest_path::edge, FSP_MODE, graph_edge_isInRange(), graph_get_nNodes(), graph_path_exec(), LT, nnodes, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, GRAPH::tail, and TRUE.

Referenced by findSolPcMw2Term(), and findSolRPcMw().

findSolRPcMw()

static SCIP_RETCODE findSolRPcMw ( SCIP *  scip, GRAPH *  g, int *RESTRICT  result  )

static

enumeration of rooted PC/MW

Parameters

scip	SCIP data structure
g	graph data structure
result	solution array, indicating whether an edge is in the solution

Definition at line 116 of file enumeration.c.

References GE, graph_get_nNodes(), graph_isMarked(), graph_pc_2org(), graph_pc_2trans(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), nnodes, pcmwFindMax2Terms(), GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, solstp_pruneFromNodes(), GRAPH::source, GRAPH::terms, tryPathPcMw(), and UNKNOWN.

Referenced by enumeration_findSolPcMw().

findSolPcMw1Term()

static void findSolPcMw1Term ( const GRAPH *  g, int *RESTRICT  result  )

static

enumeration of unrooted PC/MW with one terminal other than the root

Parameters

g	graph data structure
result	solution array, indicating whether an edge is in the solution

Definition at line 159 of file enumeration.c.

References a, CONNECT, EAT_LAST, graph_pc_knotIsDummyTerm(), GRAPH::head, GRAPH::oeat, GRAPH::outbeg, GRAPH::source, and GRAPH::terms.

Referenced by findSolPcMw().

findSolPcMw2Term()

static SCIP_RETCODE findSolPcMw2Term ( SCIP *  scip, GRAPH *  g, int *RESTRICT  result  )

static

enumeration of unrooted PC/MW with one terminal other than the root

Parameters

scip	SCIP data structure
g	graph data structure
result	solution array, indicating whether an edge is in the solution

Definition at line 184 of file enumeration.c.

References GRAPH::extended, GE, graph_get_nNodes(), graph_pc_2org(), graph_pc_2trans(), nnodes, pcmwFindMax2Terms(), GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, solstp_pruneFromNodes(), GRAPH::source, GRAPH::terms, tryPathPcMw(), and UNKNOWN.

Referenced by findSolPcMw().

findSolPcMw()

static SCIP_RETCODE findSolPcMw ( SCIP *  scip, GRAPH *  g, int *RESTRICT  result  )

static

enumeration of unrooted PC/MW

Parameters

scip	SCIP data structure
g	graph data structure
result	solution array, indicating whether an edge is in the solution

Definition at line 219 of file enumeration.c.

References findSolPcMw1Term(), findSolPcMw2Term(), graph_isMarked(), graph_pc_isRootedPcMw(), SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, and GRAPH::terms.

Referenced by enumeration_findSolPcMw().

enumeration_findSolPcMw()

SCIP_RETCODE enumeration_findSolPcMw	(	SCIP *	scip,
		GRAPH *	g,
		int *RESTRICT	result
	)

enumeration of PC/MW

Parameters

scip	SCIP data structure
g	graph data structure
result	solution array, indicating whether an edge is in the solution

Definition at line 253 of file enumeration.c.

References enumeration_isPossible(), findSolPcMw(), findSolRPcMw(), graph_get_nEdges(), graph_mark(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), SCIP_CALL, TRUE, and UNKNOWN.

Referenced by pcmwEnumerationTry().

enumeration_isPossible()

SCIP_Bool enumeration_isPossible

(

const GRAPH *

g

)

enumeration possible?

Parameters

g	graph data structure

Definition at line 284 of file enumeration.c.

References FALSE, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), and GRAPH::terms.

Referenced by enumeration_findSolPcMw(), and pcmwEnumerationTry().