extreduce_util.c File Reference

Detailed Description

utility methods for Steiner tree extended reductions

Author

Daniel Rehfeldt

This file implements utility methods for Steiner tree problem extended reduction techniques.

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

Definition in file extreduce_util.c.

#include "extreduce.h"
#include "misc_stp.h"
#include "portab.h"

Go to the source code of this file.

Functions
Interface methods
void	extreduce_extCompRevert (const GRAPH *graph, const EXTPERMA *extperma, EXTCOMP *extcomp)
SCIP_Bool	extreduce_extCompIsPromising (const GRAPH *graph, const EXTPERMA *extperma, const EXTCOMP *extcomp)
SCIP_Bool	extreduce_extCompFullIsPromising (const GRAPH *graph, const EXTPERMA *extperma, const EXTCOMP *extcomp)

Function Documentation

extreduce_extCompRevert()

void extreduce_extCompRevert	(	const GRAPH *	graph,
		const EXTPERMA *	extperma,
		EXTCOMP *	extcomp
	)

reverts extension component (makes root the only extension leaf)

Parameters

graph	graph data structure
extperma	extension data
extcomp	component to be cleaned for

Definition at line 52 of file extreduce_util.c.

References initial_extension_component::compedges, initial_extension_component::comproot, initial_extension_component::extleaves, flipedge, GRAPH::head, initial_extension_component::ncompedges, initial_extension_component::nextleaves, SCIP_Bool, and GRAPH::tail.

Referenced by extreduce_checkComponent().

extreduce_extCompIsPromising()

SCIP_Bool extreduce_extCompIsPromising	(	const GRAPH *	graph,
		const EXTPERMA *	extperma,
		const EXTCOMP *	extcomp
	)

is extension component promising candidate for extension?

Parameters

graph	graph data structure
extperma	extension data
extcomp	component to be cleaned for

Definition at line 93 of file extreduce_util.c.

References extLeafIsExtendable(), initial_extension_component::extleaves, FALSE, extension_data_permanent::isterm, initial_extension_component::ncompedges, initial_extension_component::nextleaves, SCIP_Bool, and TRUE.

Referenced by extreduce_checkComponent(), and extreduce_extCompFullIsPromising().

extreduce_extCompFullIsPromising()

SCIP_Bool extreduce_extCompFullIsPromising	(	const GRAPH *	graph,
		const EXTPERMA *	extperma,
		const EXTCOMP *	extcomp
	)

is extension component or its reversed version promising candidate for extension?

Parameters

graph	graph data structure
extperma	extension data
extcomp	component to be cleaned for

Definition at line 124 of file extreduce_util.c.

References initial_extension_component::comproot, extLeafIsExtendable(), extreduce_extCompIsPromising(), FALSE, extension_data_permanent::isterm, and TRUE.

Referenced by extreduce_checkComponent().