solhistory.c File Reference

Detailed Description

includes methods working on the (reduction) history of solutions to Steiner tree problems

Author

Daniel Rehfeldt

This file includes methods working on the (reduction) history of solutions to Steiner tree problems

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

Definition in file solhistory.c.

#include "solhistory.h"
#include "probdata_stp.h"
#include "portab.h"
#include "solstp.h"
#include "mst.h"
#include "shortestpath.h"

Go to the source code of this file.

Functions
static void	updateorgsol (const GRAPH *graph, IDX *curr, STP_Bool *RESTRICT orgnodes, STP_Bool *RESTRICT orgedges, int *nsolnodes, int *nsoledges)
static void	cleanHistory (const GRAPH *g, SOLHISTORY *solhistory)
static SCIP_RETCODE	computeHistory (SCIP *scip, SCIP_SOL *scipsol, const GRAPH *graph, SOLHISTORY *solhistory)
static SCIP_RETCODE	computeHistoryPcMw (SCIP *scip, SCIP_SOL *scipsol, const GRAPH *graph, SOLHISTORY *solhistory)
SCIP_RETCODE	solhistory_init (SCIP *scip, const GRAPH *graph, SOLHISTORY **solhistory)
void	solhistory_free (SCIP *scip, SOLHISTORY **solhistory)
SCIP_RETCODE	solhistory_computeHistory (SCIP *scip, SCIP_SOL *scipsol, const GRAPH *g, SOLHISTORY *solhistory)

Function Documentation

updateorgsol()

static void updateorgsol ( const GRAPH *  graph, IDX *  curr, STP_Bool *RESTRICT  orgnodes, STP_Bool *RESTRICT  orgedges, int *  nsolnodes, int *  nsoledges  )

inlinestatic

updates

Parameters

graph	graph data structure
curr	head of solution edge list
orgnodes	array to mark whether a node is part of the original solution
orgedges	array to mark whether an edge is part of the original solution
nsolnodes	pointer to store the number of nodes in the original solution
nsoledges	pointer to store the number of edges in the original solution

Definition at line 46 of file solhistory.c.

References FALSE, Int_List_Node::index, NULL, GRAPH::orghead, GRAPH::orgtail, Int_List_Node::parent, and TRUE.

Referenced by computeHistory().

cleanHistory()

static void cleanHistory ( const GRAPH *  g, SOLHISTORY *  solhistory  )

static

builds history

Parameters

g	graph structure
solhistory	the solution history

Definition at line 91 of file solhistory.c.

References FALSE, solution_history::norgedges, solution_history::norgnodes, GRAPH::orgedges, solution_history::orgedges_isInSol, GRAPH::orgknots, and solution_history::orgnodes_isInSol.

Referenced by solhistory_computeHistory().

computeHistory()

static SCIP_RETCODE computeHistory ( SCIP *  scip, SCIP_SOL *  scipsol, const GRAPH *  graph, SOLHISTORY *  solhistory  )

static

builds history

Parameters

scip	SCIP data structure
scipsol	solution
graph	graph structure
solhistory	the solution history

Definition at line 114 of file solhistory.c.

References GRAPH::ancestors, EAT_LAST, GRAPH::edges, FALSE, flipedge, graph_edge_add(), graph_edge_getAncestors(), graph_free(), graph_getFixedges(), graph_init(), graph_knot_add(), graph_pc_isPcMw(), GRAPH::head, GRAPH::knots, GRAPH::mark, solution_history::norgedges, GRAPH::norgmodelterms, solution_history::norgnodes, solution_history::nsoledges, solution_history::nsolnodes, NULL, GRAPH::oeat, solution_history::orgedges_isInSol, GRAPH::orghead, solution_history::orgnodes_isInSol, GRAPH::orgsource, GRAPH::orgtail, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPisZero(), SCIPprobdataGetVars(), SCIPqueueCreate(), SCIPqueueFree(), SCIPqueueInsert(), SCIPqueueIsEmpty(), SCIPqueueRemove(), GRAPH::source, STP_GSTP, GRAPH::stp_type, GRAPH::terms, TRUE, and updateorgsol().

Referenced by solhistory_computeHistory().

computeHistoryPcMw()

static SCIP_RETCODE computeHistoryPcMw ( SCIP *  scip, SCIP_SOL *  scipsol, const GRAPH *  graph, SOLHISTORY *  solhistory  )

static

builds history

Parameters

scip	SCIP data structure
scipsol	solution
graph	graph structure
solhistory	the solution history

Definition at line 281 of file solhistory.c.

References GRAPH::ancestors, GRAPH::edges, flipedge, graph_edge_getAncestors(), graph_getFixedges(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), Int_List_Node::index, solution_history::norgedges, GRAPH::norgmodelknots, solution_history::norgnodes, solution_history::nsoledges, solution_history::nsolnodes, NULL, solution_history::orgedges_isInSol, GRAPH::orghead, solution_history::orgnodes_isInSol, GRAPH::orgsource, GRAPH::orgtail, Int_List_Node::parent, GRAPH::pcancestors, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPisZero(), SCIPprobdataGetVars(), solstp_markPcancestors(), GRAPH::source, STP_BRMWCSP, STP_MWCSP, STP_RMWCSP, GRAPH::stp_type, and TRUE.

Referenced by solhistory_computeHistory().

solhistory_init()

SCIP_RETCODE solhistory_init	(	SCIP *	scip,
		const GRAPH *	graph,
		SOLHISTORY **	solhistory
	)

initializes

Parameters

scip	SCIP data structure
graph	graph
solhistory	the solution history

Definition at line 389 of file solhistory.c.

References solution_history::norgedges, solution_history::norgnodes, solution_history::nsoledges, solution_history::nsolnodes, GRAPH::orgedges, solution_history::orgedges_isInSol, GRAPH::orgknots, solution_history::orgnodes_isInSol, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, and SCIPallocMemoryArray.

Referenced by SCIPprobdataWriteSolution(), and subscipGetSol().

solhistory_free()

void solhistory_free	(	SCIP *	scip,
		SOLHISTORY **	solhistory
	)

frees

Parameters

scip	SCIP data structure
solhistory	the solution history

Definition at line 419 of file solhistory.c.

References solution_history::orgedges_isInSol, solution_history::orgnodes_isInSol, SCIPfreeMemory, SCIPfreeMemoryArray, and SCIPfreeMemoryArrayNull.

Referenced by SCIPprobdataWriteSolution(), and subscipGetSol().

solhistory_computeHistory()

SCIP_RETCODE solhistory_computeHistory	(	SCIP *	scip,
		SCIP_SOL *	scipsol,
		const GRAPH *	g,
		SOLHISTORY *	solhistory
	)

builds history

Parameters

scip	SCIP data structure
scipsol	solution
g	graph structure
solhistory	the solution history

Definition at line 437 of file solhistory.c.

References cleanHistory(), computeHistory(), computeHistoryPcMw(), graph_pc_isPcMw(), SCIP_CALL, and SCIP_OKAY.

Referenced by SCIPprobdataWriteSolution(), and subscipGetSol().