Detailed Description

bottleneck distance graph methods for Steiner tree reductions

Author: Daniel Rehfeldt

This file implements methods for Steiner tree problem special distance (bottleneck Steiner distance) graph. This graph is the (complete) distance graph on the terminal vertex set. Note that the complete graph is in general not built.

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

Definition in file reduce_sdgraph.c.

#include "reduce.h"
#include "misc_stp.h"
#include "portab.h"

Go to the source code of this file.

Data Structures
struct	special_distance_graph

struct	binary_tree_node

struct	lowest_common_ancestor_tree_builder

Macros
#define	STP_SDQUERYFULL_MAXTERMS 200

Typedefs
typedef struct binary_tree_node	BINARYNODE

typedef struct lowest_common_ancestor_tree_builder	LCABUILDER

Functions
static int	log2floor (uint32_t number)

static SCIP_Real	sdgraphGetSd (int term1, int term2, SDGRAPH *sdgraph)

static int	sdqueryGetRmqLength (const SDGRAPH *sdgraph)

static SCIP_RETCODE	sdqueryLcaBuilderInit (SCIP scip, const SDGRAPH sdgraph, LCABUILDER **lcabuilder)

static void	sdqueryLcaBuilderFree (SCIP scip, LCABUILDER *lcabuilder)

static void	sdqueryAttachBinaryTreeNode (const GRAPH distgraph, int parentposition, int graphnode, LCABUILDER lcabuilder, UF *uf)

static SCIP_RETCODE	sdqueryBuildBinaryTree (SCIP scip, SDGRAPH sdgraph, LCABUILDER *lcabuilder)

static void	sdqueryRmqDfs (int root, const BINARYNODE lcatree, const SCIP_Real lcatree_costs, SCIP_Real rmq_edgecosts, int lcatreeNodeToRmq, int *rmq_count)

static void	sdqueryBuildRmqSparseTable (SDGRAPH *sdgraph)

static void	sdqueryBuildRmq (SDGRAPH sdgraph, LCABUILDER lcabuilder)

static void	sdqueryBuildNodesToRmqMap (const GRAPH g, const LCABUILDER lcabuilder, SDGRAPH *sdgraph)

static SCIP_RETCODE	sdqueryRmqInit (SCIP scip, const GRAPH g, SDGRAPH *sdgraph)

static void	sdqueryBuildNodesToFullMap (const GRAPH g, const LCABUILDER lcabuilder, SDGRAPH *sdgraph)

static SCIP_Real	sdqueryGetSd (int term1, int term2, const SDGRAPH *sdgraph)

static SCIP_Real	sdqueryFullGetSd (int term1, int term2, const SDGRAPH *sdgraph)

static void	sdqueryFullDfs (int root, const BINARYNODE lcatree, int nlcanodes, const SCIP_Real lcatree_costs, SCIP_Bool RESTRICT nodes_isVisited, UF uf, SCIP_Real *RESTRICT fullq_dists)

static SCIP_RETCODE	sdqueryFullBuild (SCIP scip, SDGRAPH sdgraph, LCABUILDER *lcabuilder)

static SCIP_RETCODE	sdqueryFullInit (SCIP scip, const GRAPH g, SDGRAPH *sdgraph)

static SCIP_RETCODE	sdqueryInit (SCIP scip, const GRAPH g, SDGRAPH *sdgraph)

static void	sdqueryFree (SCIP scip, SDGRAPH sdgraph)

static int	distgraphGetNedges (const GRAPH *g)

static void	distgraphAddNodes (const GRAPH g, int RESTRICT distnodes_id, GRAPH *distgraph)

static SCIP_Real	distgraphGetBoundaryEdgeDist (int tail, int head, int vbase_tail, int vbase_head, SCIP_Real edgecost, const SCIP_Real nodes_vdist, const SDPROFIT sdprofit)

static SCIP_Real	distgraphGetBoundaryEdgeDist2 (int tail, int head, int vbase_tail, int vbase_head, SCIP_Real edgecost, SCIP_Real dist_tail, SCIP_Real dist_head, const SDPROFIT *sdprofit)

static SCIP_Real	distgraphGetBoundaryEdgeDistBest (const GRAPH g, const TPATHS tpaths, int tail, int head, SCIP_Real edgecost, const SDPROFIT sdprofit, int base_tail, int *base_head)

static void	distgraphInsertEdge (SCIP scip, int sdnode1, int sdnode2, SCIP_Real edgecost, int edgeid, int RESTRICT edgeorg, GRAPH distgraph, SCIP_Bool success)

static void	distgraphAddEdges (SCIP scip, const GRAPH g, const int distnodes_id, const VNOI vnoi, const SDPROFIT sdprofit, int RESTRICT edgeorg, GRAPH *distgraph)

static void	sdgraphSetDefaults (const GRAPH g, SDGRAPH g_sd)

static SCIP_RETCODE	sdgraphAlloc (SCIP scip, const GRAPH g, SDGRAPH **sdgraph)

static SCIP_RETCODE	sdgraphAllocRestricted (SCIP scip, const GRAPH g, SDGRAPH **sdgraph)

static void	distgraphAddEdgesFromTpaths (SCIP scip, const GRAPH g, const int distnodes_id, const SDPROFIT sdprofit, const TPATHS tpaths, GRAPH distgraph)

static SCIP_RETCODE	sdgraphBuildDistgraph (SCIP scip, const GRAPH g, const SDPROFIT sdprofit, SDGRAPH g_sd, VNOI vnoi, int distedge2org)

static SCIP_RETCODE	sdgraphBuildDistgraphFromTpaths (SCIP scip, const GRAPH g, const SDPROFIT sdprofit, const TPATHS tpaths, SDGRAPH *g_sd)

static SCIP_RETCODE	sdgraphUpdateDistgraphFromTpaths (SCIP scip, const GRAPH g, const SDPROFIT sdprofit, const TPATHS tpaths, SDGRAPH *g_sd)

static void	sdgraphMstSortCosts (SDGRAPH *g_sd)

static void	sdgraphMstMarkOrgEdges (const GRAPH g, const VNOI vnoi, const int distedge2org, SDGRAPH g_sd)

static SCIP_RETCODE	sdgraphMstBuild (SCIP scip, const GRAPH g, SDGRAPH *g_sd)

static void	sdgraphFinalize (SCIP scip, VNOI vnoi, int *edgeorg)

SCIP_RETCODE	reduce_sdgraphInit (SCIP scip, const GRAPH g, SDGRAPH **sdgraph)

SCIP_RETCODE	reduce_sdgraphInitFromDistGraph (SCIP scip, const GRAPH g, GRAPH distgraph, int node2dist, SDGRAPH **sdgraph)

SCIP_RETCODE	reduce_sdgraphInitBiased (SCIP scip, const GRAPH g, const SDPROFIT sdprofit, SDGRAPH *sdgraph)

SCIP_RETCODE	reduce_sdgraphInitBiasedFromTpaths (SCIP scip, GRAPH g, const SDPROFIT sdprofit, const TPATHS tpaths, SDGRAPH **sdgraph)

SCIP_Real	reduce_sdgraphGetMaxCost (const SDGRAPH *sdgraph)

const STP_Bool *	reduce_sdgraphGetMstHalfMark (const SDGRAPH *sdgraph)

SCIP_Bool	reduce_sdgraphHasMstHalfMark (const SDGRAPH *sdgraph)

SCIP_Bool	reduce_sdgraphEdgeIsInMst (const SDGRAPH *sdgraph, int edge)

SCIP_Bool	reduce_sdgraphHasOrderedMstCosts (const SDGRAPH *sdgraph)

void	reduce_sdgraphInitOrderedMstCosts (SDGRAPH *sdgraph)

SCIP_Real	reduce_sdgraphGetSd (int term1, int term2, SDGRAPH *sdgraph)

const SCIP_Real *	reduce_sdgraphGetOrderedMstCosts (const SDGRAPH *sdgraph)

const int *	reduce_sdgraphGetOrgnodesToSdMap (const SDGRAPH *sdgraph)

void	reduce_sdgraphInsertEdge (SCIP scip, int sdnode1, int sdnode2, SCIP_Real edgecost, int edgeid, int RESTRICT edgeorg, SDGRAPH sdgraph, SCIP_Bool success)

SCIP_RETCODE	reduce_sdgraphMstBuild (SCIP scip, const GRAPH g, SDGRAPH *g_sd)

void	reduce_sdgraphMstSortCosts (SDGRAPH *g_sd)

void	reduce_sdgraphFree (SCIP scip, SDGRAPH *sdgraph)

void	reduce_sdgraphFreeFromDistGraph (SCIP scip, SDGRAPH *sdgraph)

Variables
static const int	deBruijnBits [32]

Macro Definition Documentation

◆ STP_SDQUERYFULL_MAXTERMS

#define STP_SDQUERYFULL_MAXTERMS 200

Definition at line 35 of file reduce_sdgraph.c.

Referenced by sdqueryInit().

Typedef Documentation

◆ BINARYNODE

typedef struct binary_tree_node BINARYNODE

Simple binary tree node. Value of UNKNOWN signifies that child does not exist.

◆ LCABUILDER

typedef struct lowest_common_ancestor_tree_builder LCABUILDER

data needed for building the RMQ based SD query structures

Function Documentation

◆ log2floor()

static int log2floor ( uint32_t number )

inlinestatic

returns the floor of log2(number)

Parameters

number number

Definition at line 109 of file reduce_sdgraph.c.

References deBruijnBits, special_distance_graph::distgraph, graph_get_nNodes(), lowest_common_ancestor_tree_builder::lcatree, lowest_common_ancestor_tree_builder::lcatree_costs, nterms, number, SCIP_Real, and lowest_common_ancestor_tree_builder::termToLcatreeNode.

Referenced by sdqueryGetSd().

◆ sdgraphGetSd()

static SCIP_Real sdgraphGetSd	(	int	term1,
		int	term2,
		SDGRAPH *	sdgraph
	)

inlinestatic

Gets special distance (i.e. bottleneck distance) from graph. Corresponds to bottleneck length of path between term1 and term2 on distance graph

Parameters

term1	terminal 1
term2	terminal 2
sdgraph	the SD graph

Definition at line 165 of file reduce_sdgraph.c.

References GRAPH::cost, special_distance_graph::distgraph, shortest_path::edge, EQ, GE, GRAPH::head, special_distance_graph::mstsdist, special_distance_graph::nodemapOrgToDist, SCIP_Real, special_distance_graph::sdmst, GRAPH::source, and GRAPH::tail.

Referenced by sdgraphUpdateDistgraphFromTpaths(), and sdqueryGetSd().

◆ sdqueryGetRmqLength()

static int sdqueryGetRmqLength ( const SDGRAPH * sdgraph )

inlinestatic

gets length of RMQ array

Parameters

sdgraph the SD graph

Definition at line 259 of file reduce_sdgraph.c.

References special_distance_graph::distgraph, graph_get_nNodes(), and nterms.

Referenced by sdqueryBuildRmq(), sdqueryBuildRmqSparseTable(), sdqueryGetSd(), and sdqueryRmqInit().

◆ sdqueryLcaBuilderInit()

static SCIP_RETCODE sdqueryLcaBuilderInit	(	SCIP *	scip,
		const SDGRAPH *	sdgraph,
		LCABUILDER **	lcabuilder
	)

static

initializes LCA builder

Parameters

scip	SCIP
sdgraph	the SD graph
lcabuilder	the builder

Definition at line 272 of file reduce_sdgraph.c.

References binary_tree_node::child1, binary_tree_node::child2, special_distance_graph::distgraph, graph_get_nNodes(), lowest_common_ancestor_tree_builder::lcatree, lowest_common_ancestor_tree_builder::lcatree_costs, lowest_common_ancestor_tree_builder::lcatreeNodeToInds, nterms, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, lowest_common_ancestor_tree_builder::termToLcatreeNode, and UNKNOWN.

Referenced by sdqueryFullInit(), and sdqueryRmqInit().

◆ sdqueryLcaBuilderFree()

static void sdqueryLcaBuilderFree	(	SCIP *	scip,
		LCABUILDER **	lcabuilder
	)

static

frees LCA builder

Parameters

scip	SCIP
lcabuilder	the builder

Definition at line 315 of file reduce_sdgraph.c.

References lowest_common_ancestor_tree_builder::lcatree, lowest_common_ancestor_tree_builder::lcatree_costs, lowest_common_ancestor_tree_builder::lcatreeNodeToInds, SCIPfreeMemory, SCIPfreeMemoryArray, and lowest_common_ancestor_tree_builder::termToLcatreeNode.

Referenced by sdqueryFullInit(), and sdqueryRmqInit().

◆ sdqueryAttachBinaryTreeNode()

static void sdqueryAttachBinaryTreeNode	(	const GRAPH *	distgraph,
		int	parentposition,
		int	graphnode,
		LCABUILDER *	lcabuilder,
		UF *	uf
	)

inlinestatic

Parameters

distgraph	SD distance graph
parentposition	position of parent (edge) in binary tree array
graphnode	graph node to attach
lcabuilder	the builder
uf	union-find data structure

Definition at line 333 of file reduce_sdgraph.c.

References FALSE, graph_get_nNodes(), graph_knot_isInRange(), lowest_common_ancestor_tree_builder::lcatree, nterms, SCIPStpunionfindFind(), SCIPStpunionfindUnion(), lowest_common_ancestor_tree_builder::termToLcatreeNode, and UNKNOWN.

Referenced by sdqueryBuildBinaryTree().

◆ sdqueryBuildBinaryTree()

static SCIP_RETCODE sdqueryBuildBinaryTree	(	SCIP *	scip,
		SDGRAPH *	sdgraph,
		LCABUILDER *	lcabuilder
	)

static

builds binary tree for LCA computation

Parameters

scip	SCIP
sdgraph	the SD graph
lcabuilder	the builder

Definition at line 379 of file reduce_sdgraph.c.

References GRAPH::cost, shortest_path::dist, special_distance_graph::distgraph, shortest_path::edge, EQ, graph_edge_isInRange(), graph_get_nNodes(), GRAPH::head, lowest_common_ancestor_tree_builder::lcatree_costs, nterms, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPsortDownRealInt(), SCIPStpunionfindFreeMembers(), SCIPStpunionfindInit(), special_distance_graph::sdmst, sdqueryAttachBinaryTreeNode(), and GRAPH::tail.

Referenced by sdqueryFullInit(), and sdqueryRmqInit().

◆ sdqueryRmqDfs()

static void sdqueryRmqDfs	(	int	root,
		const BINARYNODE *	lcatree,
		const SCIP_Real *	lcatree_costs,
		SCIP_Real *	rmq_edgecosts,
		int *	lcatreeNodeToRmq,
		int *	rmq_count
	)

static

Builds RMQ by DFS. NOTE: recursive method.

Parameters

root	root node (LCA tree position)
lcatree	tree
lcatree_costs	LCA tree costs
rmq_edgecosts	edge costs for RMQ
lcatreeNodeToRmq	mapping from binary LCA tree nodes to RMQ indices
rmq_count	current position

Definition at line 444 of file reduce_sdgraph.c.

References binary_tree_node::child1, binary_tree_node::child2, SCIPdebugMessage, and UNKNOWN.

Referenced by sdqueryBuildRmq().

◆ sdqueryBuildRmqSparseTable()

static void sdqueryBuildRmqSparseTable ( SDGRAPH * sdgraph )

static

builds RMQ sparse table

Parameters

sdgraph the SD graph

Definition at line 482 of file reduce_sdgraph.c.

References FARAWAY, MAX, special_distance_graph::rmq_edgecosts, special_distance_graph::rmq_loglength, special_distance_graph::rmq_sparseTable, SCIP_Real, SCIPdebugMessage, and sdqueryGetRmqLength().

Referenced by sdqueryBuildRmq().

◆ sdqueryBuildRmq()

static void sdqueryBuildRmq	(	SDGRAPH *	sdgraph,
		LCABUILDER *	lcabuilder
	)

static

builds RMQ, including sparse table representation

Parameters

sdgraph	the SD graph
lcabuilder	the builder

Definition at line 539 of file reduce_sdgraph.c.

References lowest_common_ancestor_tree_builder::lcatree, lowest_common_ancestor_tree_builder::lcatree_costs, lowest_common_ancestor_tree_builder::lcatreeNodeToInds, special_distance_graph::rmq_edgecosts, SCIP_Real, sdqueryBuildRmqSparseTable(), sdqueryGetRmqLength(), and sdqueryRmqDfs().

Referenced by sdqueryRmqInit().

◆ sdqueryBuildNodesToRmqMap()

static void sdqueryBuildNodesToRmqMap	(	const GRAPH *	g,
		const LCABUILDER *	lcabuilder,
		SDGRAPH *	sdgraph
	)

static

builds RMQ map

Parameters

g	graph
lcabuilder	the builder
sdgraph	the SD graph

Definition at line 568 of file reduce_sdgraph.c.

References special_distance_graph::distgraph, graph_get_nNodes(), graph_knot_isInRange(), Is_term, lowest_common_ancestor_tree_builder::lcatreeNodeToInds, nnodes, special_distance_graph::nodemapOrgToDist, special_distance_graph::rmq_nodeToRmqEntry, SCIPdebugMessage, GRAPH::term, lowest_common_ancestor_tree_builder::termToLcatreeNode, and UNKNOWN.

Referenced by sdqueryRmqInit().

◆ sdqueryRmqInit()

static SCIP_RETCODE sdqueryRmqInit	(	SCIP *	scip,
		const GRAPH *	g,
		SDGRAPH *	sdgraph
	)

static

initializes SD constant time query data

Parameters

scip	SCIP
g	graph to initialize from
sdgraph	the SD graph

Definition at line 604 of file reduce_sdgraph.c.

References special_distance_graph::distgraph, graph_get_nNodes(), nnodes, nterms, special_distance_graph::rmq_edgecosts, special_distance_graph::rmq_loglength, special_distance_graph::rmq_nodeToRmqEntry, special_distance_graph::rmq_sparseTable, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, sdqueryBuildBinaryTree(), sdqueryBuildNodesToRmqMap(), sdqueryBuildRmq(), sdqueryGetRmqLength(), sdqueryLcaBuilderFree(), sdqueryLcaBuilderInit(), GRAPH::terms, UNKNOWN, and special_distance_graph::usingRMQ.

Referenced by sdqueryInit().

◆ sdqueryBuildNodesToFullMap()

static void sdqueryBuildNodesToFullMap	(	const GRAPH *	g,
		const LCABUILDER *	lcabuilder,
		SDGRAPH *	sdgraph
	)

static

builds map

Parameters

g	graph
lcabuilder	the builder
sdgraph	the SD graph

Definition at line 650 of file reduce_sdgraph.c.

References special_distance_graph::distgraph, special_distance_graph::fullq_nodeToIdx, graph_get_nNodes(), graph_knot_isInRange(), Is_term, nnodes, special_distance_graph::nodemapOrgToDist, SCIPdebugMessage, GRAPH::term, lowest_common_ancestor_tree_builder::termToLcatreeNode, and UNKNOWN.

Referenced by sdqueryFullInit().

◆ sdqueryGetSd()

static SCIP_Real sdqueryGetSd	(	int	term1,
		int	term2,
		const SDGRAPH *	sdgraph
	)

inlinestatic

Gets special distance (i.e. bottleneck distance) from graph. Corresponds to bottleneck length of path between term1 and term2 on distance graph

Parameters

term1	terminal 1
term2	terminal 2
sdgraph	the SD graph

Definition at line 686 of file reduce_sdgraph.c.

References EQ, FARAWAY, log2floor(), LT, MAX, special_distance_graph::rmq_edgecosts, special_distance_graph::rmq_loglength, special_distance_graph::rmq_nodeToRmqEntry, special_distance_graph::rmq_sparseTable, SCIP_Real, SCIPdebugMessage, sdgraphGetSd(), and sdqueryGetRmqLength().

Referenced by reduce_sdgraphGetSd().

◆ sdqueryFullGetSd()

static SCIP_Real sdqueryFullGetSd	(	int	term1,
		int	term2,
		const SDGRAPH *	sdgraph
	)

inlinestatic

Gets special distance (i.e. bottleneck distance) from graph. Corresponds to bottleneck length of path between term1 and term2 on distance graph

Parameters

term1	terminal 1
term2	terminal 2
sdgraph	the SD graph

Definition at line 749 of file reduce_sdgraph.c.

References special_distance_graph::fullq_dimension, special_distance_graph::fullq_dists, special_distance_graph::fullq_nodeToIdx, special_distance_graph::fullq_size, and SCIPdebugMessage.

Referenced by reduce_sdgraphGetSd().

◆ sdqueryFullDfs()

static void sdqueryFullDfs	(	int	root,
		const BINARYNODE *	lcatree,
		int	nlcanodes,
		const SCIP_Real *	lcatree_costs,
		SCIP_Bool *RESTRICT	nodes_isVisited,
		UF *	uf,
		SCIP_Real *RESTRICT	fullq_dists
	)

static

initializes full SD query data structure by DFS

Parameters

root	root node (LCA tree position)
lcatree	tree
nlcanodes	number of nodes
lcatree_costs	LCA tree costs
nodes_isVisited	per node: is visited?
uf	union-find data structure
fullq_dists	distances to be computed

Definition at line 787 of file reduce_sdgraph.c.

References binary_tree_node::child1, binary_tree_node::child2, FALSE, SCIPdebugMessage, SCIPStpunionfindFind(), SCIPStpunionfindUnion(), TRUE, and UNKNOWN.

Referenced by sdqueryFullBuild().

◆ sdqueryFullBuild()

static SCIP_RETCODE sdqueryFullBuild	(	SCIP *	scip,
		SDGRAPH *	sdgraph,
		LCABUILDER *	lcabuilder
	)

static

builds full representation

Parameters

scip	SCIP
sdgraph	the SD graph
lcabuilder	the builder

Definition at line 876 of file reduce_sdgraph.c.

References special_distance_graph::distgraph, FALSE, special_distance_graph::fullq_dists, GRAPH::knots, lowest_common_ancestor_tree_builder::lcatree, lowest_common_ancestor_tree_builder::lcatree_costs, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPStpunionfindFreeMembers(), SCIPStpunionfindInit(), and sdqueryFullDfs().

Referenced by sdqueryFullInit().

◆ sdqueryFullInit()

static SCIP_RETCODE sdqueryFullInit	(	SCIP *	scip,
		const GRAPH *	g,
		SDGRAPH *	sdgraph
	)

static

initializes full SD constant time query data

Parameters

scip	SCIP
g	graph to initialize from
sdgraph	the SD graph

Definition at line 919 of file reduce_sdgraph.c.

References special_distance_graph::distgraph, special_distance_graph::fullq_dimension, special_distance_graph::fullq_dists, special_distance_graph::fullq_nodeToIdx, special_distance_graph::fullq_size, graph_get_nNodes(), GRAPH::knots, nterms, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPdebugMessage, sdqueryBuildBinaryTree(), sdqueryBuildNodesToFullMap(), sdqueryFullBuild(), sdqueryLcaBuilderFree(), sdqueryLcaBuilderInit(), GRAPH::terms, and special_distance_graph::usingRMQ.

Referenced by sdqueryInit().

◆ sdqueryInit()

static SCIP_RETCODE sdqueryInit	(	SCIP *	scip,
		const GRAPH *	g,
		SDGRAPH *	sdgraph
	)

static

initializes SD constant time query data

Parameters

scip	SCIP
g	graph to initialize from
sdgraph	the SD graph

Definition at line 962 of file reduce_sdgraph.c.

References FALSE, SCIP_CALL, SCIP_OKAY, sdqueryFullInit(), sdqueryRmqInit(), STP_SDQUERYFULL_MAXTERMS, GRAPH::terms, TRUE, and special_distance_graph::usingRMQ.

Referenced by reduce_sdgraphInit(), reduce_sdgraphInitBiased(), reduce_sdgraphInitBiasedFromTpaths(), and reduce_sdgraphInitFromDistGraph().

◆ sdqueryFree()

static void sdqueryFree	(	SCIP *	scip,
		SDGRAPH *	sdgraph
	)

static

frees SD constant time query data

Parameters

scip	SCIP
sdgraph	the SD graph

Definition at line 985 of file reduce_sdgraph.c.

References special_distance_graph::fullq_dists, special_distance_graph::fullq_nodeToIdx, special_distance_graph::rmq_edgecosts, special_distance_graph::rmq_nodeToRmqEntry, special_distance_graph::rmq_sparseTable, SCIPfreeMemoryArray, and special_distance_graph::usingRMQ.

Referenced by reduce_sdgraphFree(), and reduce_sdgraphFreeFromDistGraph().

◆ distgraphGetNedges()

static int distgraphGetNedges ( const GRAPH * g )

static

gets number of edges

Parameters

g	graph to initialize from

Definition at line 1014 of file reduce_sdgraph.c.

References graph_get_nEdges(), nterms, SCIP_Longint, and GRAPH::terms.

Referenced by sdgraphBuildDistgraph(), and sdgraphBuildDistgraphFromTpaths().

◆ distgraphAddNodes()

static void distgraphAddNodes	(	const GRAPH *	g,
		int *RESTRICT	distnodes_id,
		GRAPH *	distgraph
	)

static

adds nodes to distance graph

Parameters

g	graph to initialize from
distnodes_id	IDs of nodes
distgraph	distance graph

Definition at line 1039 of file reduce_sdgraph.c.

References graph_get_nNodes(), graph_knot_add(), graph_knot_chg(), Is_term, GRAPH::knots, nnodes, GRAPH::source, STP_TERM, STP_TERM_NONE, GRAPH::term, GRAPH::terms, and UNKNOWN.

Referenced by sdgraphBuildDistgraph(), and sdgraphBuildDistgraphFromTpaths().

◆ distgraphGetBoundaryEdgeDist()

static SCIP_Real distgraphGetBoundaryEdgeDist	(	int	tail,
		int	head,
		int	vbase_tail,
		int	vbase_head,
		SCIP_Real	edgecost,
		const SCIP_Real *	nodes_vdist,
		const SDPROFIT *	sdprofit
	)

inlinestatic

gets SD for boundary edge

Parameters

tail	tail
head	head
vbase_tail	base
vbase_head	base
edgecost	cost
nodes_vdist	distance
sdprofit	profit

Definition at line 1072 of file reduce_sdgraph.c.

References miscstp_maxReal(), reduce_sdprofitGetProfit(), and SCIP_Real.

Referenced by distgraphAddEdges().

◆ distgraphGetBoundaryEdgeDist2()

static SCIP_Real distgraphGetBoundaryEdgeDist2	(	int	tail,
		int	head,
		int	vbase_tail,
		int	vbase_head,
		SCIP_Real	edgecost,
		SCIP_Real	dist_tail,
		SCIP_Real	dist_head,
		const SDPROFIT *	sdprofit
	)

inlinestatic

gets SD for boundary edge

Parameters

tail	tail
head	head
vbase_tail	base
vbase_head	base
edgecost	cost
dist_tail	distance
dist_head	distance
sdprofit	profit

Definition at line 1099 of file reduce_sdgraph.c.

References miscstp_maxReal(), reduce_sdprofitGetProfit(), and SCIP_Real.

Referenced by distgraphAddEdgesFromTpaths(), and distgraphGetBoundaryEdgeDistBest().

◆ distgraphGetBoundaryEdgeDistBest()

static SCIP_Real distgraphGetBoundaryEdgeDistBest	(	const GRAPH *	g,
		const TPATHS *	tpaths,
		int	tail,
		int	head,
		SCIP_Real	edgecost,
		const SDPROFIT *	sdprofit,
		int *	base_tail,
		int *	base_head
	)

inlinestatic

gets SD for boundary edge ... choose among nearest terminals (w.r.t. implied SD)

Parameters

g	graph
tpaths	terminal paths
tail	tail
head	head
edgecost	cost
sdprofit	profit
base_tail	base of tail
base_head	base of head

Definition at line 1127 of file reduce_sdgraph.c.

References distgraphGetBoundaryEdgeDist2(), FARAWAY, graph_tpathsGet3CloseTerms(), NULL, and SCIP_Real.

Referenced by sdgraphUpdateDistgraphFromTpaths().

◆ distgraphInsertEdge()

static void distgraphInsertEdge	(	SCIP *	scip,
		int	sdnode1,
		int	sdnode2,
		SCIP_Real	edgecost,
		int	edgeid,
		int *RESTRICT	edgeorg,
		GRAPH *	distgraph,
		SCIP_Bool *	success
	)

inlinestatic

inserts new edge

Parameters

scip	SCIP data structure
sdnode1	end node 1
sdnode2	end node 2
edgecost	cost
edgeid	ID or -1
edgeorg	IDs of edges or NULL
distgraph	the SD graph
success	could the edge be added?

Definition at line 1179 of file reduce_sdgraph.c.

References GRAPH::cost, EAT_LAST, Edge_anti, GRAPH::edges, GRAPH::esize, FALSE, GE, graph_edge_add(), GRAPH::head, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::tail, and TRUE.

Referenced by distgraphAddEdges(), distgraphAddEdgesFromTpaths(), reduce_sdgraphInsertEdge(), and sdgraphUpdateDistgraphFromTpaths().

◆ distgraphAddEdges()

static void distgraphAddEdges	(	SCIP *	scip,
		const GRAPH *	g,
		const int *	distnodes_id,
		const VNOI *	vnoi,
		const SDPROFIT *	sdprofit,
		int *RESTRICT	edgeorg,
		GRAPH *	distgraph
	)

static

adds edges to distance graph, given a Voronoi diagram

Parameters

scip	SCIP data structure
g	graph to initialize from
distnodes_id	IDs of nodes
vnoi	Voronoi
sdprofit	profit or NULL
edgeorg	IDs of edges
distgraph	distance graph

Definition at line 1246 of file reduce_sdgraph.c.

References GRAPH::cost, distgraphGetBoundaryEdgeDist(), distgraphInsertEdge(), EAT_LAST, graph_get_nEdges(), graph_get_nNodes(), GRAPH::head, Is_term, LE, nnodes, voronoi_storage::nodes_base, voronoi_storage::nodes_dist, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, GRAPH::tail, GRAPH::term, and UNKNOWN.

Referenced by sdgraphBuildDistgraph().

◆ sdgraphSetDefaults()

static void sdgraphSetDefaults	(	const GRAPH *	g,
		SDGRAPH *	g_sd
	)

static

helper

Parameters

g	graph to initialize from
g_sd	the SD graph

Definition at line 1304 of file reduce_sdgraph.c.

Referenced by sdgraphAlloc(), and sdgraphAllocRestricted().

◆ sdgraphAlloc()

static SCIP_RETCODE sdgraphAlloc	(	SCIP *	scip,
		const GRAPH *	g,
		SDGRAPH **	sdgraph
	)

static

allocates memory

Parameters

scip	SCIP
g	graph to initialize from
sdgraph	the SD graph

Definition at line 1336 of file reduce_sdgraph.c.

References graph_get_nEdges(), graph_get_nNodes(), special_distance_graph::halfedge_isInMst, special_distance_graph::mstcosts, special_distance_graph::mstsdist, nnodes, special_distance_graph::nodemapOrgToDist, nterms, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, sdgraphSetDefaults(), special_distance_graph::sdmst, and GRAPH::terms.

Referenced by reduce_sdgraphInit(), reduce_sdgraphInitBiased(), and reduce_sdgraphInitBiasedFromTpaths().

◆ sdgraphAllocRestricted()

static SCIP_RETCODE sdgraphAllocRestricted	(	SCIP *	scip,
		const GRAPH *	g,
		SDGRAPH **	sdgraph
	)

static

allocates memory

Parameters

scip	SCIP
g	graph to initialize from
sdgraph	the SD graph

Definition at line 1365 of file reduce_sdgraph.c.

References graph_get_nNodes(), special_distance_graph::halfedge_isInMst, special_distance_graph::mstcosts, special_distance_graph::mstsdist, nnodes, special_distance_graph::nodemapOrgToDist, nterms, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, sdgraphSetDefaults(), special_distance_graph::sdmst, and GRAPH::terms.

Referenced by reduce_sdgraphInitFromDistGraph().

◆ distgraphAddEdgesFromTpaths()

static void distgraphAddEdgesFromTpaths	(	SCIP *	scip,
		const GRAPH *	g,
		const int *	distnodes_id,
		const SDPROFIT *	sdprofit,
		const TPATHS *	tpaths,
		GRAPH *	distgraph
	)

static

adds edges to distance graph, given terminal paths

Parameters

scip	SCIP data structure
g	graph to initialize from
distnodes_id	IDs of nodes
sdprofit	profit or NULL
tpaths	terminal paths
distgraph	distance graph

Definition at line 1392 of file reduce_sdgraph.c.

References GRAPH::cost, distgraphGetBoundaryEdgeDist2(), distgraphInsertEdge(), EAT_LAST, graph_get_nNodes(), graph_tpathsGetClosestTerm(), GRAPH::head, Is_term, LE, nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, and GRAPH::term.

Referenced by sdgraphBuildDistgraphFromTpaths().

◆ sdgraphBuildDistgraph()

static SCIP_RETCODE sdgraphBuildDistgraph	(	SCIP *	scip,
		const GRAPH *	g,
		const SDPROFIT *	sdprofit,
		SDGRAPH *	g_sd,
		VNOI **	vnoi,
		int **	distedge2org
	)

static

builds distance graph

Parameters

scip	SCIP
g	graph to initialize from
sdprofit	profit or NULL
g_sd	the SD graph
vnoi	Voronoi
distedge2org	array of size nedges / 2

Definition at line 1439 of file reduce_sdgraph.c.

References special_distance_graph::distgraph, distgraphAddEdges(), distgraphAddNodes(), distgraphGetNedges(), graph_get_nEdges(), graph_init(), graph_valid(), graph_vnoiCompute(), graph_vnoiComputeImplied(), graph_vnoiInit(), special_distance_graph::nodemapOrgToDist, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, GRAPH::terms, and TRUE.

Referenced by reduce_sdgraphInit(), and reduce_sdgraphInitBiased().

◆ sdgraphBuildDistgraphFromTpaths()

static SCIP_RETCODE sdgraphBuildDistgraphFromTpaths	(	SCIP *	scip,
		const GRAPH *	g,
		const SDPROFIT *	sdprofit,
		const TPATHS *	tpaths,
		SDGRAPH *	g_sd
	)

static

builds distance graph

Parameters

scip	SCIP
g	graph to initialize from
sdprofit	profit or NULL
tpaths	terminal paths
g_sd	the SD graph

Definition at line 1479 of file reduce_sdgraph.c.

References special_distance_graph::distgraph, distgraphAddEdgesFromTpaths(), distgraphAddNodes(), distgraphGetNedges(), graph_init(), graph_valid(), special_distance_graph::nodemapOrgToDist, SCIP_CALL, SCIP_OKAY, and GRAPH::terms.

Referenced by reduce_sdgraphInitBiasedFromTpaths().

◆ sdgraphUpdateDistgraphFromTpaths()

static SCIP_RETCODE sdgraphUpdateDistgraphFromTpaths	(	SCIP *	scip,
		const GRAPH *	g,
		const SDPROFIT *	sdprofit,
		const TPATHS *	tpaths,
		SDGRAPH *	g_sd
	)

static

updates distance graph

Parameters

scip	SCIP
g	graph to initialize from
sdprofit	profit or NULL
tpaths	terminal paths
g_sd	the SD graph

Definition at line 1506 of file reduce_sdgraph.c.

References GRAPH::cost, special_distance_graph::distgraph, distgraphGetBoundaryEdgeDistBest(), distgraphInsertEdge(), EAT_LAST, FALSE, FARAWAY, graph_get_nNodes(), graph_tpathsGetProfitNodes(), GRAPH::head, LE, LT, nnodes, special_distance_graph::nodemapOrgToDist, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, sdgraphGetSd(), STP_Vectype, StpVecFree, StpVecGetSize, StpVecReserve, and TRUE.

Referenced by reduce_sdgraphInitBiasedFromTpaths().

◆ sdgraphMstSortCosts()

static void sdgraphMstSortCosts ( SDGRAPH * g_sd )

static

builds MST costs (ordered) for distance graph

Parameters

g_sd	the SD graph

Definition at line 1604 of file reduce_sdgraph.c.

References GRAPH::cost, shortest_path::dist, special_distance_graph::distgraph, shortest_path::edge, EQ, FARAWAY, GE, graph_get_nNodes(), special_distance_graph::mstcosts, SCIP_Real, SCIPsortDownReal(), special_distance_graph::sdmst, and UNKNOWN.

Referenced by reduce_sdgraphInitOrderedMstCosts(), and reduce_sdgraphMstSortCosts().

◆ sdgraphMstMarkOrgEdges()

static void sdgraphMstMarkOrgEdges	(	const GRAPH *	g,
		const VNOI *	vnoi,
		const int *	distedge2org,
		SDGRAPH *	g_sd
	)

static

marks original edges corresponding to MST

Parameters

g	graph to initialize from
vnoi	Voronoi
distedge2org	array of size nedges / 2
g_sd	the SD graph

Definition at line 1644 of file reduce_sdgraph.c.

References special_distance_graph::distgraph, EAT_LAST, graph_get_nEdges(), graph_get_nNodes(), special_distance_graph::halfedge_isInMst, GRAPH::head, voronoi_storage::nodes_base, voronoi_storage::nodes_predEdge, special_distance_graph::sdmst, GRAPH::tail, and TRUE.

Referenced by reduce_sdgraphInit(), and reduce_sdgraphInitBiased().

◆ sdgraphMstBuild()

static SCIP_RETCODE sdgraphMstBuild	(	SCIP *	scip,
		const GRAPH *	g,
		SDGRAPH *	g_sd
	)

static

builds MST on distance graph

Parameters

scip	SCIP
g	graph to initialize from
g_sd	the SD graph

Definition at line 1691 of file reduce_sdgraph.c.

References GRAPH::cost, special_distance_graph::distgraph, FALSE, graph_edge_isInRange(), graph_get_nEdges(), graph_get_nNodes(), graph_path_exec(), graph_path_exit(), graph_path_init(), special_distance_graph::halfedge_isInMst, GRAPH::mark, MST_MODE, special_distance_graph::mstmaxcost, NULL, GRAPH::path_heap, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, special_distance_graph::sdmst, GRAPH::source, and TRUE.

Referenced by reduce_sdgraphInit(), reduce_sdgraphInitBiased(), reduce_sdgraphInitBiasedFromTpaths(), reduce_sdgraphInitFromDistGraph(), and reduce_sdgraphMstBuild().

◆ sdgraphFinalize()

static void sdgraphFinalize	(	SCIP *	scip,
		VNOI **	vnoi,
		int **	edgeorg
	)

static

finalizes distance graph

Parameters

scip	SCIP data structure
vnoi	Voronoi data structure
edgeorg	array of size nedges / 2

Definition at line 1747 of file reduce_sdgraph.c.

References graph_vnoiFree(), and SCIPfreeBufferArray.

Referenced by reduce_sdgraphInit(), and reduce_sdgraphInitBiased().

◆ reduce_sdgraphInit()

SCIP_RETCODE reduce_sdgraphInit	(	SCIP *	scip,
		const GRAPH *	g,
		SDGRAPH **	sdgraph
	)

initializes SD graph

Parameters

scip	SCIP
g	graph to initialize from
sdgraph	the SD graph

Definition at line 1764 of file reduce_sdgraph.c.

References NULL, SCIP_CALL, SCIP_OKAY, sdgraphAlloc(), sdgraphBuildDistgraph(), sdgraphFinalize(), sdgraphMstBuild(), sdgraphMstMarkOrgEdges(), and sdqueryInit().

Referenced by reduce_sdInit(), and reduce_sdRepair().

◆ reduce_sdgraphInitFromDistGraph()

SCIP_RETCODE reduce_sdgraphInitFromDistGraph	(	SCIP *	scip,
		const GRAPH *	g,
		GRAPH *	distgraph,
		int *	node2dist,
		SDGRAPH **	sdgraph
	)

initializes SD graph

Parameters

scip	SCIP
g	graph to initialize from
distgraph	distance graph
node2dist	map
sdgraph	the SD graph

Definition at line 1788 of file reduce_sdgraph.c.

References special_distance_graph::distgraph, SCIP_CALL, SCIP_OKAY, sdgraphAllocRestricted(), sdgraphMstBuild(), and sdqueryInit().

Referenced by reduce_sd().

◆ reduce_sdgraphInitBiased()

SCIP_RETCODE reduce_sdgraphInitBiased	(	SCIP *	scip,
		const GRAPH *	g,
		const SDPROFIT *	sdprofit,
		SDGRAPH **	sdgraph
	)

initializes biased SD graph

Parameters

scip	SCIP
g	graph to initialize from
sdprofit	SD profit
sdgraph	the SD graph

Definition at line 1811 of file reduce_sdgraph.c.

References SCIP_CALL, SCIP_OKAY, sdgraphAlloc(), sdgraphBuildDistgraph(), sdgraphFinalize(), sdgraphMstBuild(), sdgraphMstMarkOrgEdges(), and sdqueryInit().

Referenced by reduce_sdInitBiased().

◆ reduce_sdgraphInitBiasedFromTpaths()

SCIP_RETCODE reduce_sdgraphInitBiasedFromTpaths	(	SCIP *	scip,
		GRAPH *	g,
		const SDPROFIT *	sdprofit,
		const TPATHS *	tpaths,
		SDGRAPH **	sdgraph
	)

initializes biased SD graph from given terminal paths

Parameters

scip	SCIP
g	graph to initialize from
sdprofit	SD profit
tpaths	terminal paths
sdgraph	the SD graph

Definition at line 1836 of file reduce_sdgraph.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPfreeMemoryArray, sdgraphAlloc(), sdgraphBuildDistgraphFromTpaths(), sdgraphMstBuild(), sdgraphUpdateDistgraphFromTpaths(), and sdqueryInit().

Referenced by reduce_sdInitBiasedBottleneck(), and testSdGraphStrongBiasedDistsAreValid().

◆ reduce_sdgraphGetMaxCost()

SCIP_Real reduce_sdgraphGetMaxCost ( const SDGRAPH * sdgraph )

return maximum MST edge cost

Parameters

sdgraph the SD graph

Definition at line 1867 of file reduce_sdgraph.c.

References GE, and special_distance_graph::mstmaxcost.

Referenced by generalStarSetUp(), reduce_sdBiased(), reduce_sdBiasedNeighbor(), reduce_sdImpLongEdge(), and sdGetSdsCliqueTermWalks().

◆ reduce_sdgraphGetMstHalfMark()

const STP_Bool* reduce_sdgraphGetMstHalfMark ( const SDGRAPH * sdgraph )

returns edge mark

Parameters

sdgraph the SD graph

Definition at line 1879 of file reduce_sdgraph.c.

References special_distance_graph::halfedge_isInMst, and reduce_sdgraphHasMstHalfMark().

Referenced by bdkInit(), generalStarSetUp(), and reduce_sdImpLongEdge().

◆ reduce_sdgraphHasMstHalfMark()

SCIP_Bool reduce_sdgraphHasMstHalfMark ( const SDGRAPH * sdgraph )

has edge mark?

Parameters

sdgraph the SD graph

Definition at line 1891 of file reduce_sdgraph.c.

References special_distance_graph::edgemarkReady, FALSE, special_distance_graph::halfedge_isInMst, and TRUE.

Referenced by bdkInit(), reduce_sdBiasedNeighbor(), reduce_sdgraphEdgeIsInMst(), reduce_sdgraphGetMstHalfMark(), and reduce_sdImpLongEdge().

◆ reduce_sdgraphEdgeIsInMst()

SCIP_Bool reduce_sdgraphEdgeIsInMst	(	const SDGRAPH *	sdgraph,
		int	edge
	)

is edge in current SD MST?

Parameters

sdgraph	the SD graph
edge	edge

Definition at line 1909 of file reduce_sdgraph.c.

References special_distance_graph::halfedge_isInMst, and reduce_sdgraphHasMstHalfMark().

Referenced by extreduce_deleteEdges(), generalStarSetUp(), pathreplaceExec(), and reduce_sdRepair().

◆ reduce_sdgraphHasOrderedMstCosts()

SCIP_Bool reduce_sdgraphHasOrderedMstCosts ( const SDGRAPH * sdgraph )

MST costs in descending order available?

Parameters

sdgraph the SD graph

Definition at line 1924 of file reduce_sdgraph.c.

References special_distance_graph::mstcosts, and special_distance_graph::mstcostsReady.

Referenced by reduce_sdgraphGetOrderedMstCosts(), and reduce_sdgraphInitOrderedMstCosts().

◆ reduce_sdgraphInitOrderedMstCosts()

void reduce_sdgraphInitOrderedMstCosts ( SDGRAPH * sdgraph )

initializes all MST costs in descending order

Parameters

sdgraph the SD graph

Definition at line 1938 of file reduce_sdgraph.c.

References special_distance_graph::mstcosts, special_distance_graph::mstcostsReady, special_distance_graph::mstmaxcost, reduce_sdgraphHasOrderedMstCosts(), sdgraphMstSortCosts(), and TRUE.

Referenced by reduce_sdInit(), reduce_sdInitBiased(), reduce_sdInitBiasedBottleneck(), reduce_sdRepair(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), testSdGraphQueriesAreValid(), and testSdGraphStrongBiasedDistsAreValid().

◆ reduce_sdgraphGetSd()

SCIP_Real reduce_sdgraphGetSd	(	int	term1,
		int	term2,
		SDGRAPH *	sdgraph
	)

Gets special distance (e.g. bottleneck distance) from distance graph. Only works if both nodes are terminals!

Parameters

term1	node 1
term2	node 2
sdgraph	the SD graph

Definition at line 1958 of file reduce_sdgraph.c.

References EQ, special_distance_graph::mstcosts, special_distance_graph::mstsdist, special_distance_graph::nnodesorg, special_distance_graph::nodemapOrgToDist, sdqueryFullGetSd(), sdqueryGetSd(), UNKNOWN, and special_distance_graph::usingRMQ.

Referenced by getSd(), reduce_sd(), sdGetSd(), sdGetSdNeighbor(), sdneighborUpdateNode(), and testSdGraphQueriesAreValid().

◆ reduce_sdgraphGetOrderedMstCosts()

const SCIP_Real* reduce_sdgraphGetOrderedMstCosts ( const SDGRAPH * sdgraph )

returns all MST costs in descending order

Parameters

sdgraph the SD graph

Definition at line 1989 of file reduce_sdgraph.c.

References special_distance_graph::mstcosts, special_distance_graph::mstmaxcost, and reduce_sdgraphHasOrderedMstCosts().

Referenced by bdkStarGetCombinedSdCost(), bdkStarIsReplacableDeg3(), bdkStarIsSdTreeReplacable(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), and testSdGraphStrongBiasedDistsAreValid().

◆ reduce_sdgraphGetOrgnodesToSdMap()

const int* reduce_sdgraphGetOrgnodesToSdMap ( const SDGRAPH * sdgraph )

returns mapping from original nodes to distance graph nodes

Parameters

sdgraph the SD graph

Definition at line 2001 of file reduce_sdgraph.c.

References special_distance_graph::nodemapOrgToDist.

Referenced by sdgraphInsertEdge().

◆ reduce_sdgraphInsertEdge()

void reduce_sdgraphInsertEdge	(	SCIP *	scip,
		int	sdnode1,
		int	sdnode2,
		SCIP_Real	edgecost,
		int	edgeid,
		int *RESTRICT	edgeorg,
		SDGRAPH *	sdgraph,
		SCIP_Bool *	success
	)

Inserts new edge. NOTE: just a wrapper, should only be used by other reduce_sd* methods

Parameters

scip	SCIP data structure
sdnode1	end node 1
sdnode2	end node 2
edgecost	cost
edgeid	ID or -1
edgeorg	IDs of edges or NULL
sdgraph	the SD graph
success	could the edge be added?

Definition at line 2015 of file reduce_sdgraph.c.

References special_distance_graph::distgraph, and distgraphInsertEdge().

◆ reduce_sdgraphMstBuild()

SCIP_RETCODE reduce_sdgraphMstBuild	(	SCIP *	scip,
		const GRAPH *	g,
		SDGRAPH *	g_sd
	)

Builds MST on distance graph. NOTE: just a wrapper, should only be used by other reduce_sd* methods

Parameters

scip	SCIP
g	graph to initialize from
g_sd	the SD graph

Definition at line 2032 of file reduce_sdgraph.c.

References SCIP_CALL, SCIP_OKAY, and sdgraphMstBuild().

Referenced by sdneighborUpdate().

◆ reduce_sdgraphMstSortCosts()

void reduce_sdgraphMstSortCosts ( SDGRAPH * g_sd )

Builds MST costs (ordered) for distance graph NOTE: just a wrapper, should only be used by other reduce_sd* methods

Parameters

g_sd	the SD graph

Definition at line 2046 of file reduce_sdgraph.c.

References sdgraphMstSortCosts().

Referenced by sdneighborUpdate().

◆ reduce_sdgraphFree()

void reduce_sdgraphFree	(	SCIP *	scip,
		SDGRAPH **	sdgraph
	)

frees SD graph

Parameters

scip	SCIP
sdgraph	the SD graph

Definition at line 2055 of file reduce_sdgraph.c.

References special_distance_graph::distgraph, graph_free(), special_distance_graph::halfedge_isInMst, special_distance_graph::mstcosts, special_distance_graph::mstsdist, special_distance_graph::nodemapOrgToDist, SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, special_distance_graph::sdmst, sdqueryFree(), and TRUE.

Referenced by reduce_sdFree(), reduce_sdRepair(), and testSdGraphStrongBiasedDistsAreValid().

◆ reduce_sdgraphFreeFromDistGraph()

void reduce_sdgraphFreeFromDistGraph	(	SCIP *	scip,
		SDGRAPH **	sdgraph
	)

frees SD graph, but does not free actual graph and node-map (assumed to be non-owned)

Parameters

scip	SCIP
sdgraph	the SD graph

Definition at line 2080 of file reduce_sdgraph.c.

References special_distance_graph::halfedge_isInMst, special_distance_graph::mstcosts, special_distance_graph::mstsdist, SCIPfreeMemory, SCIPfreeMemoryArray, special_distance_graph::sdmst, and sdqueryFree().

Referenced by reduce_sd().

Variable Documentation

◆ deBruijnBits

const int deBruijnBits[32]

static

Initial value:

=
{
   0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
   8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
}

Definition at line 101 of file reduce_sdgraph.c.

Referenced by log2floor().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Variables

Macro Definition Documentation

◆ STP_SDQUERYFULL_MAXTERMS

Typedef Documentation

◆ BINARYNODE

◆ LCABUILDER

Function Documentation

◆ log2floor()

◆ sdgraphGetSd()

◆ sdqueryGetRmqLength()

◆ sdqueryLcaBuilderInit()

◆ sdqueryLcaBuilderFree()

◆ sdqueryAttachBinaryTreeNode()

◆ sdqueryBuildBinaryTree()

◆ sdqueryRmqDfs()

◆ sdqueryBuildRmqSparseTable()

◆ sdqueryBuildRmq()

◆ sdqueryBuildNodesToRmqMap()

◆ sdqueryRmqInit()

◆ sdqueryBuildNodesToFullMap()

◆ sdqueryGetSd()

◆ sdqueryFullGetSd()

◆ sdqueryFullDfs()

◆ sdqueryFullBuild()

◆ sdqueryFullInit()

◆ sdqueryInit()

◆ sdqueryFree()

◆ distgraphGetNedges()

◆ distgraphAddNodes()

◆ distgraphGetBoundaryEdgeDist()

◆ distgraphGetBoundaryEdgeDist2()

◆ distgraphGetBoundaryEdgeDistBest()

◆ distgraphInsertEdge()

◆ distgraphAddEdges()

◆ sdgraphSetDefaults()

◆ sdgraphAlloc()

◆ sdgraphAllocRestricted()

◆ distgraphAddEdgesFromTpaths()

◆ sdgraphBuildDistgraph()

◆ sdgraphBuildDistgraphFromTpaths()

◆ sdgraphUpdateDistgraphFromTpaths()

◆ sdgraphMstSortCosts()

◆ sdgraphMstMarkOrgEdges()

◆ sdgraphMstBuild()

◆ sdgraphFinalize()

◆ reduce_sdgraphInit()

◆ reduce_sdgraphInitFromDistGraph()

◆ reduce_sdgraphInitBiased()

◆ reduce_sdgraphInitBiasedFromTpaths()

◆ reduce_sdgraphGetMaxCost()

◆ reduce_sdgraphGetMstHalfMark()

◆ reduce_sdgraphHasMstHalfMark()

◆ reduce_sdgraphEdgeIsInMst()

◆ reduce_sdgraphHasOrderedMstCosts()

◆ reduce_sdgraphInitOrderedMstCosts()

◆ reduce_sdgraphGetSd()

◆ reduce_sdgraphGetOrderedMstCosts()

◆ reduce_sdgraphGetOrgnodesToSdMap()

◆ reduce_sdgraphInsertEdge()

◆ reduce_sdgraphMstBuild()

◆ reduce_sdgraphMstSortCosts()

◆ reduce_sdgraphFree()

◆ reduce_sdgraphFreeFromDistGraph()

Variable Documentation

◆ deBruijnBits