special_distance_graph Struct Reference

Detailed Description

see reduce.h

Definition at line 46 of file reduce_sdgraph.c.

Data Fields
GRAPH *	distgraph
PATH *	sdmst
SCIP_Real *	mstcosts
SCIP_Real *	mstsdist
int *	nodemapOrgToDist
STP_Bool *	halfedge_isInMst
SCIP_Real	mstmaxcost
int	nnodesorg
int	nedgesorg
SCIP_Bool	mstcostsReady
SCIP_Bool	edgemarkReady
SCIP_Bool	usingRMQ
SCIP_Real *	fullq_dists
int *	fullq_nodeToIdx
int	fullq_size
int	fullq_dimension
int *	rmq_nodeToRmqEntry
SCIP_Real *	rmq_sparseTable
SCIP_Real *	rmq_edgecosts
int	rmq_loglength

Field Documentation

distgraph

GRAPH* special_distance_graph::distgraph

(complete) distance graph

Definition at line 48 of file reduce_sdgraph.c.

Referenced by log2floor(), reduce_sdgraphFree(), reduce_sdgraphInitFromDistGraph(), reduce_sdgraphInsertEdge(), sdgraphBuildDistgraph(), sdgraphBuildDistgraphFromTpaths(), sdgraphGetSd(), sdgraphMstBuild(), sdgraphMstMarkOrgEdges(), sdgraphMstSortCosts(), sdgraphUpdateDistgraphFromTpaths(), sdqueryBuildBinaryTree(), sdqueryBuildNodesToFullMap(), sdqueryBuildNodesToRmqMap(), sdqueryFullBuild(), sdqueryFullInit(), sdqueryGetRmqLength(), sdqueryLcaBuilderInit(), and sdqueryRmqInit().

sdmst

PATH* special_distance_graph::sdmst

MST on sdgraph

Definition at line 49 of file reduce_sdgraph.c.

Referenced by reduce_sdgraphFree(), reduce_sdgraphFreeFromDistGraph(), sdgraphAlloc(), sdgraphAllocRestricted(), sdgraphGetSd(), sdgraphMstBuild(), sdgraphMstMarkOrgEdges(), sdgraphMstSortCosts(), and sdqueryBuildBinaryTree().

mstcosts

SCIP_Real* special_distance_graph::mstcosts

maximum MST edge costs in descending order

Definition at line 50 of file reduce_sdgraph.c.

Referenced by reduce_sdgraphFree(), reduce_sdgraphFreeFromDistGraph(), reduce_sdgraphGetOrderedMstCosts(), reduce_sdgraphGetSd(), reduce_sdgraphHasOrderedMstCosts(), reduce_sdgraphInitOrderedMstCosts(), sdgraphAlloc(), sdgraphAllocRestricted(), sdgraphMstSortCosts(), and sdneighborUpdate().

mstsdist

SCIP_Real* special_distance_graph::mstsdist

helper array; each entry needs to -1.0; of size nnodesorg

Definition at line 51 of file reduce_sdgraph.c.

Referenced by reduce_sdgraphFree(), reduce_sdgraphFreeFromDistGraph(), reduce_sdgraphGetSd(), sdgraphAlloc(), sdgraphAllocRestricted(), sdgraphGetSd(), and sdgraphSetDefaults().

nodemapOrgToDist

int* special_distance_graph::nodemapOrgToDist

node mapping from original graph to distance graph

Definition at line 52 of file reduce_sdgraph.c.

Referenced by reduce_sdgraphFree(), reduce_sdgraphGetOrgnodesToSdMap(), reduce_sdgraphGetSd(), sdgraphAlloc(), sdgraphAllocRestricted(), sdgraphBuildDistgraph(), sdgraphBuildDistgraphFromTpaths(), sdgraphGetSd(), sdgraphUpdateDistgraphFromTpaths(), sdqueryBuildNodesToFullMap(), and sdqueryBuildNodesToRmqMap().

halfedge_isInMst

STP_Bool* special_distance_graph::halfedge_isInMst

signifies whether edge of original graph is part of MST NOTE: operates on edges / 2!

Definition at line 53 of file reduce_sdgraph.c.

Referenced by reduce_sdgraphEdgeIsInMst(), reduce_sdgraphFree(), reduce_sdgraphFreeFromDistGraph(), reduce_sdgraphGetMstHalfMark(), reduce_sdgraphHasMstHalfMark(), sdgraphAlloc(), sdgraphAllocRestricted(), sdgraphMstBuild(), and sdgraphMstMarkOrgEdges().

mstmaxcost

SCIP_Real special_distance_graph::mstmaxcost

maximum edge cost

Definition at line 55 of file reduce_sdgraph.c.

Referenced by reduce_sdgraphGetMaxCost(), reduce_sdgraphGetOrderedMstCosts(), reduce_sdgraphInitOrderedMstCosts(), and sdgraphMstBuild().

nnodesorg

int special_distance_graph::nnodesorg

number of nodes of original graph

Definition at line 56 of file reduce_sdgraph.c.

Referenced by reduce_sdgraphGetSd(), and sdgraphSetDefaults().

nedgesorg

int special_distance_graph::nedgesorg

number of edges of original graph

Definition at line 57 of file reduce_sdgraph.c.

Referenced by sdgraphSetDefaults().

mstcostsReady

SCIP_Bool special_distance_graph::mstcostsReady

are the mstcosts already available?

Definition at line 58 of file reduce_sdgraph.c.

Referenced by reduce_sdgraphHasOrderedMstCosts(), reduce_sdgraphInitOrderedMstCosts(), and sdgraphSetDefaults().

edgemarkReady

SCIP_Bool special_distance_graph::edgemarkReady

edge mark available?

Definition at line 59 of file reduce_sdgraph.c.

Referenced by reduce_sdgraphHasMstHalfMark(), and sdgraphSetDefaults().

usingRMQ

SCIP_Bool special_distance_graph::usingRMQ

is RMQ being used?

Definition at line 60 of file reduce_sdgraph.c.

Referenced by reduce_sdgraphGetSd(), sdgraphSetDefaults(), sdqueryFree(), sdqueryFullInit(), sdqueryInit(), and sdqueryRmqInit().

fullq_dists

SCIP_Real* special_distance_graph::fullq_dists

of size |T| * |T - 1| or NULL

Definition at line 62 of file reduce_sdgraph.c.

Referenced by sdgraphSetDefaults(), sdqueryFree(), sdqueryFullBuild(), sdqueryFullGetSd(), and sdqueryFullInit().

fullq_nodeToIdx

int* special_distance_graph::fullq_nodeToIdx

maps nodes of original graphs to full index; of size |V|

Definition at line 63 of file reduce_sdgraph.c.

Referenced by sdgraphSetDefaults(), sdqueryBuildNodesToFullMap(), sdqueryFree(), sdqueryFullGetSd(), and sdqueryFullInit().

fullq_size

int special_distance_graph::fullq_size

|T - 1| * |T - 1| or |T - 1| * |T - 1| / 2

Definition at line 67 of file reduce_sdgraph.c.

Referenced by sdgraphSetDefaults(), sdqueryFullGetSd(), and sdqueryFullInit().

fullq_dimension

int special_distance_graph::fullq_dimension

|T - 1|

Definition at line 68 of file reduce_sdgraph.c.

Referenced by sdgraphSetDefaults(), sdqueryFullGetSd(), and sdqueryFullInit().

rmq_nodeToRmqEntry

int* special_distance_graph::rmq_nodeToRmqEntry

of size |V|

Definition at line 70 of file reduce_sdgraph.c.

Referenced by sdgraphSetDefaults(), sdqueryBuildNodesToRmqMap(), sdqueryFree(), sdqueryGetSd(), and sdqueryRmqInit().

rmq_sparseTable

SCIP_Real* special_distance_graph::rmq_sparseTable

of size rmq_log * 2 |T|

Definition at line 71 of file reduce_sdgraph.c.

Referenced by sdgraphSetDefaults(), sdqueryBuildRmqSparseTable(), sdqueryFree(), sdqueryGetSd(), and sdqueryRmqInit().

rmq_edgecosts

SCIP_Real* special_distance_graph::rmq_edgecosts

of size 2|T| - 3

Definition at line 72 of file reduce_sdgraph.c.

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

rmq_loglength

int special_distance_graph::rmq_loglength

log2(2|T| - 3)

Definition at line 73 of file reduce_sdgraph.c.

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