Detailed Description

extended reductions for Steiner tree problems

Author: Daniel Rehfeldt

This file implements extended reduction techniques for several Steiner problems. Note: Deprecated and is only used for test purposes. Use extreduce.h methods instead.

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

Definition in file reduce_ext.c.

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "graph.h"
#include "reduce.h"

Go to the source code of this file.

Macros
#define	EXT_ANCESTORS_MAX 16

#define	RED_EXT_MAXDFSDEPTH 6

#define	RED_EXT_MINDFSDEPTH 4

#define	RED_EXT_MAXGRAD 8

#define	RED_EXT_MINGRAD 6

#define	RED_EXT_EDGELIMIT 50000

Functions
static void	removeEdge (SCIP scip, int edge, GRAPH graph)

static SCIP_Bool	markAncestorsConflict (const GRAPH graph, int edge, int ancestormark)

static void	markAncestors (const GRAPH graph, int edge, int ancestormark)

static void	unmarkAncestorsConflict (const GRAPH graph, int edge, int ancestormark)

static void	unmarkAncestors (const GRAPH graph, int edge, int ancestormark)

static void	finalizeSubtree (const GRAPH graph, const int edgeends, const int treeedges, int dfsdepth, SCIP_Bool stopped, SCIP_Real localbound, SCIP_Real globalbound, SCIP_Bool ruleout, int nodepos, int *ancestormark)

static SCIP_Bool	truncateSubtree (const GRAPH graph, SCIP_Real extendedcost, int root, int currhead, int maxgrad, int dfsdepth, int maxdfsdepth, SCIP_Real minbound, SCIP_Bool *stopped)

static SCIP_Real	shortenSubtree (SCIP scip, const GRAPH graph, const SCIP_Real redcost, const int treeedges, SCIP_Real treecostold, SCIP_Real treecostoffset, int dfsdepth, int lastnode, int nodepos, int ancestormark, unsigned int *nstallrounds)

static int	extendSubtreeHead (SCIP scip, const GRAPH graph, const SCIP_Real redcost, int curredge, int currhead, int dfsdepth, int nadded_edges, SCIP_Real treecost, SCIP_Real treecosts, int nodepos, int treeedges, int edgestack, int *ancestormark)

static int	extendSubtreeTail (const GRAPH graph, const SCIP_Real redcost, int curredge, int currtail, int dfsdepth, int nadded_edges, SCIP_Real treecost, SCIP_Real treecosts, int nodepos, int treeedges, int edgestack, int ancestormark)

static void	updateEqArrays (int edge, unsigned int eqstack, int eqstack_size, SCIP_Bool *eqmark)

static SCIP_Bool	bottleneckRuleOut (SCIP scip, const GRAPH graph, const SCIP_Real treecosts, const SCIP_Real basebottlenecks, const int nodepos, const int treeedges, SCIP_Real orgedgecost, SCIP_Real extedgecost, int orgedge, int extedge, int dfsdepth, SCIP_Bool allow_eq, unsigned int eqstack, int eqstack_size, SCIP_Bool *eqmark)

static SCIP_Bool	ruleOutSubtree (SCIP scip, const GRAPH graph, const SCIP_Real treecosts, const SCIP_Real basebottlenecks, const int nodepos, const int treeedges, SCIP_Real cutoff, SCIP_Real extendedcost, int dfsdepth, int curredge, SCIP_Bool allowequality, const int ancestormark, unsigned int eqstack, int eqstack_size, SCIP_Bool eqmark)

static SCIP_RETCODE	reduceCheckEdge (SCIP scip, const GRAPH graph, int root, const SCIP_Real redcost, const SCIP_Real pathdist, const PATH vnoi, SCIP_Real cutoff, int edge, SCIP_Bool equality, int edgestack, SCIP_Bool deletable, unsigned int eqstack, int eqstack_size, SCIP_Bool eqmark)

SCIP_RETCODE	reduce_deleteConflictEdges (SCIP scip, GRAPH g)

SCIP_RETCODE	reduce_extendedCheck3Tree (SCIP scip, const GRAPH graph, int root, const SCIP_Real redcost, const SCIP_Real pathdist, const PATH vnoi, const int vbase, SCIP_Real cutoff, const int outedges, int inedge, SCIP_Real treebound, SCIP_Bool ruleout, unsigned int eqstack, int eqstack_size, SCIP_Bool eqmark)

int	reduce_extendedEdge (SCIP scip, GRAPH graph, const PATH vnoi, const SCIP_Real cost, const SCIP_Real pathdist, const int result, SCIP_Real minpathcost, int root, STP_Bool *marked, SCIP_Bool markdirected)

Macro Definition Documentation

◆ EXT_ANCESTORS_MAX

#define EXT_ANCESTORS_MAX 16

Definition at line 36 of file reduce_ext.c.

Referenced by markAncestors(), markAncestorsConflict(), ruleOutSubtree(), unmarkAncestors(), and unmarkAncestorsConflict().

◆ RED_EXT_MAXDFSDEPTH

#define RED_EXT_MAXDFSDEPTH 6

Definition at line 38 of file reduce_ext.c.

Referenced by reduce_extendedCheck3Tree(), and reduceCheckEdge().

◆ RED_EXT_MINDFSDEPTH

#define RED_EXT_MINDFSDEPTH 4

Definition at line 39 of file reduce_ext.c.

Referenced by reduce_extendedCheck3Tree(), and reduceCheckEdge().

◆ RED_EXT_MAXGRAD

#define RED_EXT_MAXGRAD 8

Definition at line 40 of file reduce_ext.c.

Referenced by reduce_extendedCheck3Tree(), reduceCheckEdge(), and ruleOutSubtree().

◆ RED_EXT_MINGRAD

#define RED_EXT_MINGRAD 6

Definition at line 41 of file reduce_ext.c.

Referenced by reduce_extendedCheck3Tree(), and reduceCheckEdge().

◆ RED_EXT_EDGELIMIT

#define RED_EXT_EDGELIMIT 50000

Definition at line 42 of file reduce_ext.c.

Referenced by reduce_extendedCheck3Tree(), and reduceCheckEdge().

Function Documentation

◆ removeEdge()

static void removeEdge	(	SCIP *	scip,
		int	edge,
		GRAPH *	graph
	)

static

deletes an edge and makes corresponding adaptations

Parameters

scip	SCIP
edge	edge to delete
graph	graph data structure

Definition at line 47 of file reduce_ext.c.

References FALSE, GRAPH::grad, graph_edge_del(), graph_pc_isPcMw(), GRAPH::head, Is_term, GRAPH::mark, GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_extendedEdge().

◆ markAncestorsConflict()

static SCIP_Bool markAncestorsConflict	(	const GRAPH *	graph,
		int	edge,
		int *	ancestormark
	)

static

mark ancestors of given edge

Parameters

graph	graph data structure
edge	edge to use
ancestormark	ancestor mark array

Definition at line 84 of file reduce_ext.c.

References GRAPH::edges, EXT_ANCESTORS_MAX, FALSE, graph_edge_getAncestors(), MAX, NULL, GRAPH::orgedges, and TRUE.

Referenced by reduce_deleteConflictEdges(), and reduce_extendedCheck3Tree().

◆ markAncestors()

static void markAncestors	(	const GRAPH *	graph,
		int	edge,
		int *	ancestormark
	)

static

mark ancestors of given edge

Parameters

graph	graph data structure
edge	edge to use
ancestormark	ancestor mark array

Definition at line 110 of file reduce_ext.c.

References GRAPH::edges, EXT_ANCESTORS_MAX, graph_edge_getAncestors(), MAX, NULL, and GRAPH::orgedges.

Referenced by extendSubtreeHead(), extendSubtreeTail(), and reduceCheckEdge().

◆ unmarkAncestorsConflict()

static void unmarkAncestorsConflict	(	const GRAPH *	graph,
		int	edge,
		int *	ancestormark
	)

static

unmark ancestors of given edge

Parameters

graph	graph data structure
edge	edge to use
ancestormark	ancestor mark array

Definition at line 130 of file reduce_ext.c.

References GRAPH::edges, EXT_ANCESTORS_MAX, graph_edge_getAncestors(), MAX, NULL, and GRAPH::orgedges.

Referenced by reduce_deleteConflictEdges(), and reduce_extendedCheck3Tree().

◆ unmarkAncestors()

static void unmarkAncestors	(	const GRAPH *	graph,
		int	edge,
		int *	ancestormark
	)

static

unmark ancestors of given edge

Parameters

graph	graph data structure
edge	edge to use
ancestormark	ancestor mark array

Definition at line 148 of file reduce_ext.c.

References GRAPH::edges, EXT_ANCESTORS_MAX, graph_edge_getAncestors(), MAX, NULL, and GRAPH::orgedges.

Referenced by finalizeSubtree(), reduceCheckEdge(), and shortenSubtree().

◆ finalizeSubtree()

static void finalizeSubtree	(	const GRAPH *	graph,
		const int *	edgeends,
		const int *	treeedges,
		int	dfsdepth,
		SCIP_Bool	stopped,
		SCIP_Real	localbound,
		SCIP_Real *	globalbound,
		SCIP_Bool *	ruleout,
		int *	nodepos,
		int *	ancestormark
	)

static

finalize subtree computations (clean up, update global bound)

Parameters

graph	graph data structure
edgeends	heads or tail of edge
treeedges	tree edges
dfsdepth	dfs depth
stopped	has extension been stopped?
localbound	local bound
globalbound	points to global bound
ruleout	rule out?
nodepos	node position in tree
ancestormark	ancestor mark array

Definition at line 170 of file reduce_ext.c.

References TRUE, and unmarkAncestors().

Referenced by reduce_extendedCheck3Tree(), and reduceCheckEdge().

◆ truncateSubtree()

static SCIP_Bool truncateSubtree	(	const GRAPH *	graph,
		SCIP_Real	extendedcost,
		int	root,
		int	currhead,
		int	maxgrad,
		int	dfsdepth,
		int	maxdfsdepth,
		SCIP_Real *	minbound,
		SCIP_Bool *	stopped
	)

static

should we truncate subtree?

Parameters

graph	graph data structure
extendedcost	cost of subtree
root	DA root
currhead	latest node
maxgrad	maximum allowed degree
dfsdepth	dfs depth
maxdfsdepth	max dfs depth
minbound	bound
stopped	real truncation?

Definition at line 208 of file reduce_ext.c.

References FALSE, GRAPH::grad, Is_term, GRAPH::mark, GRAPH::term, and TRUE.

Referenced by reduce_extendedCheck3Tree(), and reduceCheckEdge().

◆ shortenSubtree()

static SCIP_Real shortenSubtree	(	SCIP *	scip,
		const GRAPH *	graph,
		const SCIP_Real *	redcost,
		const int *	treeedges,
		SCIP_Real	treecostold,
		SCIP_Real	treecostoffset,
		int	dfsdepth,
		int	lastnode,
		int *	nodepos,
		int *	ancestormark,
		unsigned int *	nstallrounds
	)

static

remove latest edge from subtree and returns new tree cost

Parameters

scip	SCIP
graph	graph data structure
redcost	reduced costs
treeedges	edges of tree
treecostold	old tree cost
treecostoffset	tree cost offset
dfsdepth	DFS depth
lastnode	last node
nodepos	array to mark node position
ancestormark	ancestor mark array
nstallrounds	rounds since latest update

Definition at line 238 of file reduce_ext.c.

References SCIP_Real, SCIPisEQ(), SCIPisGE(), and unmarkAncestors().

Referenced by reduce_extendedCheck3Tree(), and reduceCheckEdge().

◆ extendSubtreeHead()

static int extendSubtreeHead	(	SCIP *	scip,
		const GRAPH *	graph,
		const SCIP_Real *	redcost,
		int	curredge,
		int	currhead,
		int	dfsdepth,
		int	nadded_edges,
		SCIP_Real *	treecost,
		SCIP_Real *	treecosts,
		int *	nodepos,
		int *	treeedges,
		int *	edgestack,
		int *	ancestormark
	)

static

extend subtree and return new nadded_edges

Parameters

scip	SCIP
graph	graph data structure
redcost	reduced costs
curredge	added edges
currhead	latest node
dfsdepth	DFS depth
nadded_edges	added edges
treecost	pointer to treecost
treecosts	edge costs of tree
nodepos	node position in tree
treeedges	edges of tree
edgestack	stack
ancestormark	ancestor mark array

Definition at line 278 of file reduce_ext.c.

References GRAPH::cost, EAT_LAST, GRAPH::head, GRAPH::mark, markAncestors(), GRAPH::oeat, and GRAPH::outbeg.

Referenced by reduce_extendedCheck3Tree(), and reduceCheckEdge().

◆ extendSubtreeTail()

static int extendSubtreeTail	(	const GRAPH *	graph,
		const SCIP_Real *	redcost,
		int	curredge,
		int	currtail,
		int	dfsdepth,
		int	nadded_edges,
		SCIP_Real *	treecost,
		SCIP_Real *	treecosts,
		int *	nodepos,
		int *	treeedges,
		int *	edgestack,
		int *	ancestormark
	)

static

extend subtree and return new nadded_edges

Parameters

graph	graph data structure
redcost	reduced costs
curredge	added edges
currtail	latest node
dfsdepth	DFS depth
nadded_edges	added edges
treecost	pointer to treecost
treecosts	edge costs of tree
nodepos	node position in tree
treeedges	edges of tree
edgestack	stack
ancestormark	ancestor mark array

Definition at line 315 of file reduce_ext.c.

References GRAPH::cost, EAT_LAST, GRAPH::ieat, GRAPH::inpbeg, GRAPH::mark, markAncestors(), and GRAPH::tail.

Referenced by reduce_extendedCheck3Tree(), and reduceCheckEdge().

◆ updateEqArrays()

static void updateEqArrays	(	int	edge,
		unsigned int *	eqstack,
		int *	eqstack_size,
		SCIP_Bool *	eqmark
	)

static

small helper

Parameters

edge	the edge
eqstack	stores edges that were used for equality comparison
eqstack_size	pointer to size of eqstack
eqmark	marks edges that were used for equality comparison

Definition at line 352 of file reduce_ext.c.

References TRUE.

Referenced by bottleneckRuleOut().

◆ bottleneckRuleOut()

static SCIP_Bool bottleneckRuleOut	(	SCIP *	scip,
		const GRAPH *	graph,
		const SCIP_Real *	treecosts,
		const SCIP_Real *	basebottlenecks,
		const int *	nodepos,
		const int *	treeedges,
		SCIP_Real	orgedgecost,
		SCIP_Real	extedgecost,
		int	orgedge,
		int	extedge,
		int	dfsdepth,
		SCIP_Bool	allow_eq,
		unsigned int *	eqstack,
		int *	eqstack_size,
		SCIP_Bool *	eqmark
	)

static

compare with tree bottleneck

Parameters

scip	SCIP
graph	graph data structure
treecosts	costs of edges of the tree
basebottlenecks	bottleneck costs for innode and basenode
nodepos	node position in tree
treeedges	edges in tree (corresponding to treecosts)
orgedgecost	cost of original edge
extedgecost	cost of short-cut edge
orgedge	original edge
extedge	short-cut edge
dfsdepth	dfs depth
allow_eq	test for equality?
eqstack	stores edges that were used for equality comparison
eqstack_size	pointer to size of eqstack
eqmark	marks edges that were used for equality comparison

Definition at line 375 of file reduce_ext.c.

References FALSE, GRAPH::knots, NULL, SCIPisEQ(), SCIPisLE(), SCIPisLT(), GRAPH::tail, TRUE, and updateEqArrays().

Referenced by ruleOutSubtree().

◆ ruleOutSubtree()

static SCIP_Bool ruleOutSubtree	(	SCIP *	scip,
		const GRAPH *	graph,
		const SCIP_Real *	treecosts,
		const SCIP_Real *	basebottlenecks,
		const int *	nodepos,
		const int *	treeedges,
		SCIP_Real	cutoff,
		SCIP_Real	extendedcost,
		int	dfsdepth,
		int	curredge,
		SCIP_Bool	allowequality,
		const int *	ancestormark,
		unsigned int *	eqstack,
		int *	eqstack_size,
		SCIP_Bool *	eqmark
	)

static

can subtree be ruled out?

Parameters

scip	SCIP
graph	graph data structure
treecosts	costs of edges of the tree
basebottlenecks	bottleneck costs for innode and basenode
nodepos	node position in tree
treeedges	edges in tree (corresponding to treecosts)
cutoff	cut-off bound
extendedcost	cost of subtree
dfsdepth	dfs depth
curredge	latest edge
allowequality	rule out also in case of equality
ancestormark	ancestor mark array
eqstack	stores edges that were used for equality comparison
eqstack_size	pointer to size of eqstack
eqmark	marks edges that were used for equality comparison

Definition at line 455 of file reduce_ext.c.

References bottleneckRuleOut(), GRAPH::cost, EAT_LAST, GRAPH::edges, EXT_ANCESTORS_MAX, FALSE, flipedge, graph_edge_getAncestors(), graph_pc_isPcMw(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::mark, MAX, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::outbeg, GRAPH::prize, RED_EXT_MAXGRAD, SCIP_Bool, SCIP_Real, SCIPisGT(), GRAPH::tail, GRAPH::term, and TRUE.

Referenced by reduce_extendedCheck3Tree(), and reduceCheckEdge().

◆ reduceCheckEdge()

static SCIP_RETCODE reduceCheckEdge	(	SCIP *	scip,
		const GRAPH *	graph,
		int	root,
		const SCIP_Real *	redcost,
		const SCIP_Real *	pathdist,
		const PATH *	vnoi,
		SCIP_Real	cutoff,
		int	edge,
		SCIP_Bool	equality,
		int *	edgestack,
		SCIP_Bool *	deletable,
		unsigned int *	eqstack,
		int *	eqstack_size,
		SCIP_Bool *	eqmark
	)

static

check (directed) edge

Parameters

scip	SCIP data structure
graph	graph data structure
root	graph root from dual ascent
redcost	reduced costs
pathdist	shortest path distances
vnoi	Voronoi paths
cutoff	cutoff value
edge	(directed) edge to be checked
equality	allow equality?
edgestack	array of size nodes for internal computations
deletable	is edge deletable?
eqstack	stores edges that were used for equality comparison
eqstack_size	pointer to size of eqstack
eqmark	marks edges that were used for equality comparison

Definition at line 564 of file reduce_ext.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, GRAPH::extended, extendSubtreeHead(), extendSubtreeTail(), FALSE, FARAWAY, finalizeSubtree(), flipedge, GRAPH::grad, graph_pc_isPcMw(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::mark, markAncestors(), MAX, nnodes, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::outbeg, RED_EXT_EDGELIMIT, RED_EXT_MAXDFSDEPTH, RED_EXT_MAXGRAD, RED_EXT_MINDFSDEPTH, RED_EXT_MINGRAD, ruleOutSubtree(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, SCIPisEQ(), SCIPisGE(), SCIPisGT(), shortenSubtree(), GRAPH::tail, GRAPH::term, TRUE, truncateSubtree(), and unmarkAncestors().

Referenced by reduce_extendedEdge().

◆ reduce_deleteConflictEdges()

SCIP_RETCODE reduce_deleteConflictEdges	(	SCIP *	scip,
		GRAPH *	g
	)

todo don't use this function, but check for conflicts in misc_stp.c and handle them

Parameters

scip	SCIP data structure
g	the graph

Definition at line 791 of file reduce_ext.c.

References GRAPH::ancestors, GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::extended, FALSE, graph_edge_del(), graph_pc_isPcMw(), GRAPH::head, Is_pseudoTerm, markAncestorsConflict(), MAX, NULL, GRAPH::oeat, GRAPH::orgedges, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::tail, GRAPH::term, TRUE, and unmarkAncestorsConflict().

Referenced by reduce_redLoopPc().

◆ reduce_extendedCheck3Tree()

SCIP_RETCODE reduce_extendedCheck3Tree	(	SCIP *	scip,
		const GRAPH *	graph,
		int	root,
		const SCIP_Real *	redcost,
		const SCIP_Real *	pathdist,
		const PATH *	vnoi,
		const int *	vbase,
		SCIP_Real	cutoff,
		const int *	outedges,
		int	inedge,
		SCIP_Real *	treebound,
		SCIP_Bool *	ruleout,
		unsigned int *	eqstack,
		int *	eqstack_size,
		SCIP_Bool *	eqmark
	)

check 3-tree

Parameters

scip	SCIP data structure
graph	graph data structure
root	graph root from dual ascent
redcost	reduced costs
pathdist	shortest path distances
vnoi	Voronoi paths
vbase	bases to Voronoi paths
cutoff	cutoff value
outedges	two outgoing edge
inedge	incoming edge
treebound	to store a lower bound for the tree
ruleout	could tree be ruled out?
eqstack	stores edges that were used for equality comparison
eqstack_size	pointer to size of eqstack
eqmark	marks edges that were used for equality comparison

Definition at line 842 of file reduce_ext.c.

References GRAPH::cost, shortest_path::dist, EAT_LAST, GRAPH::edges, extendSubtreeHead(), extendSubtreeTail(), FALSE, FARAWAY, finalizeSubtree(), flipedge, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, markAncestorsConflict(), MAX, nnodes, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::outbeg, RED_EXT_EDGELIMIT, RED_EXT_MAXDFSDEPTH, RED_EXT_MAXGRAD, RED_EXT_MINDFSDEPTH, RED_EXT_MINGRAD, ruleOutSubtree(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPisGE(), SCIPisGT(), shortenSubtree(), GRAPH::tail, GRAPH::term, TRUE, truncateSubtree(), and unmarkAncestorsConflict().

Referenced by updateNodeReplaceBounds().

◆ reduce_extendedEdge()

int reduce_extendedEdge	(	SCIP *	scip,
		GRAPH *	graph,
		const PATH *	vnoi,
		const SCIP_Real *	cost,
		const SCIP_Real *	pathdist,
		const int *	result,
		SCIP_Real	minpathcost,
		int	root,
		STP_Bool *	marked,
		SCIP_Bool	markdirected
	)

reduce SPG graph based on reduced cost information and given upper bound todo to be deleted and replaced by reduce_extendedEdge2

Parameters

scip	SCIP data structure
graph	graph data structure
vnoi	Voronoi data structure
cost	dual ascent costs
pathdist	distance array from shortest path calculations
result	sol int array
minpathcost	the required reduced path cost to be surpassed
root	the root
marked	edge array to mark which (directed) edge can be removed
markdirected	try to also mark edge if anti-parallel is not marked

Definition at line 1155 of file reduce_ext.c.

References CONNECT, GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), Is_term, GRAPH::knots, GRAPH::mark, nnodes, NULL, GRAPH::oeat, reduceCheckEdge(), removeEdge(), SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPallocCleanBufferArray, SCIPfreeBufferArray, SCIPfreeCleanBufferArray, SCIPisEQ(), SCIPisZero(), GRAPH::term, and TRUE.

Referenced by fixVarsExtendedRed().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ EXT_ANCESTORS_MAX

◆ RED_EXT_MAXDFSDEPTH

◆ RED_EXT_MINDFSDEPTH

◆ RED_EXT_MAXGRAD

◆ RED_EXT_MINGRAD

◆ RED_EXT_EDGELIMIT

Function Documentation

◆ removeEdge()

◆ markAncestorsConflict()

◆ markAncestors()

◆ unmarkAncestorsConflict()

◆ unmarkAncestors()

◆ finalizeSubtree()

◆ truncateSubtree()

◆ shortenSubtree()

◆ extendSubtreeHead()

◆ extendSubtreeTail()

◆ updateEqArrays()

◆ bottleneckRuleOut()

◆ ruleOutSubtree()

◆ reduceCheckEdge()

◆ reduce_deleteConflictEdges()

◆ reduce_extendedCheck3Tree()

◆ reduce_extendedEdge()