Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

includes several graph statistic methods for Steiner problem graphs

Author: Daniel Rehfeldt

This file contains methods to obtain statistics on the given Steiner problem instance.

Definition in file graph_stats.c.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "portab.h"
#include "graph.h"

Go to the source code of this file.

Macros
#define	STP_UNIFORM_MINRATIO 0.9

#define	STP_UNIFORM_RANGEMIN 0.9

#define	STP_UNIFORM_RANGEMAX 1.1

Functions
Interface methods
SCIP_Bool	graph_typeIsSpgLike (const GRAPH *g)

SCIP_Bool	graph_typeIsUndirected (const GRAPH *g)

SCIP_Bool	graph_typeIsDirected (const GRAPH *g)

SCIP_Bool	graph_edge_isBlocked (const GRAPH *g, int e)

SCIP_Bool	graph_edge_isInRange (const GRAPH *g, int e)

SCIP_Bool	graph_edge_isDeleted (const GRAPH *g, int e)

void	graph_edge_printInfo (const GRAPH *g, int e)

void	graph_knot_printInfo (const GRAPH *g, int k)

SCIP_Bool	graph_hasMultiEdges (SCIP scip, const GRAPH g, SCIP_Bool verbose)

SCIP_Bool	graph_isAlmostUniform (const GRAPH *g)

void	graph_printInfo (const GRAPH *g)

void	graph_printInfoReduced (const GRAPH *g)

SCIP_RETCODE	graph_printEdgeConflicts (SCIP scip, const GRAPH g)

int	graph_get_nNodes (const GRAPH *graph)

int	graph_get_nEdges (const GRAPH *graph)

int	graph_get_nTerms (const GRAPH *graph)

void	graph_get_nVET (const GRAPH graph, int nnodes, int nedges, int nterms)

SCIP_Real	graph_get_avgDeg (const GRAPH *graph)

Macro Definition Documentation

◆ STP_UNIFORM_MINRATIO

#define STP_UNIFORM_MINRATIO 0.9

Definition at line 37 of file graph_stats.c.

Referenced by graph_isAlmostUniform().

◆ STP_UNIFORM_RANGEMIN

#define STP_UNIFORM_RANGEMIN 0.9

Definition at line 38 of file graph_stats.c.

Referenced by graph_isAlmostUniform().

◆ STP_UNIFORM_RANGEMAX

#define STP_UNIFORM_RANGEMAX 1.1

Definition at line 39 of file graph_stats.c.

Referenced by graph_isAlmostUniform().

Function Documentation

◆ graph_typeIsSpgLike()

SCIP_Bool graph_typeIsSpgLike ( const GRAPH * g )

is the given graph a variant that is effectively an STP??

Parameters

g the graph

Definition at line 57 of file graph_stats.c.

References STP_GSTP, STP_OARSMT, STP_RSMT, STP_SPG, and GRAPH::stp_type.

Referenced by abortSlackPruneEarly(), addRedsol(), blockEdgesWithGlobalFixings(), check_inputgraph(), computeReducedProbSolution(), computeSteinerTree_execBiased(), computeSteinerTreeKeyNodesCsr(), createInitialCuts(), daGetNruns(), divideAndConquer(), extractSubgraphBuild(), extreduce_deleteEdges(), fixVarsRedbased(), fixVarsRedbasedIsPromising(), graph_writeReductionRatioStatsLive(), graph_writeStp(), initDecompose(), initPropAtFirstCall(), nodesolUpdate(), probAllowsSolBranching(), probtypeIsValidForSlackPrune(), redcostGraphBuild(), reduce_bidecomposition(), reduce_bidecompositionExact(), reduce_exec(), reduce_getMinNreductions(), reduce_redLoopStp(), runTm(), SCIP_DECL_CONSPROP(), SCIP_DECL_HEUREXEC(), SCIP_DECL_RELAXEXEC(), SCIPprobdataCreateFromGraph(), SCIPStpHeurTMRunLP(), selectBranchingVertexBySol(), sepaspecial_vtimplicationsInit(), setParams(), shortestpath_computeSteinerTree(), shortestpath_computeSteinerTreeBiased(), tmBaseInit(), updateBestSol(), updateSolution(), and useRedcostdata().

◆ graph_typeIsUndirected()

SCIP_Bool graph_typeIsUndirected ( const GRAPH * g )

is the given graph (originally) undirected?

Parameters

g the graph

Definition at line 69 of file graph_stats.c.

References FALSE, STP_DHCSTP, STP_NWPTSPG, STP_SAP, GRAPH::stp_type, and TRUE.

Referenced by computeDualSolutionGuided(), daGetNruns(), daGuidedIsPromising(), daRoundInit(), delPseudoPath(), extractSubgraphAddEdge(), graph_edge_getAncestors(), graph_edge_printInfo(), graph_edge_reinsert(), graph_initAncestors(), graph_knot_contract(), graph_knot_replaceDeg2(), graph_sdPaths(), graph_singletonAncestors_init(), graph_typeIsDirected(), graph_valid_ancestors(), redcostGraphMark(), reduce_rpt(), reduce_sap(), reduce_unconnectedForDirected(), reduceRootedProb(), SCIPStpHeurAscendPruneRun(), and SCIPStpHeurRecRun().

◆ graph_typeIsDirected()

SCIP_Bool graph_typeIsDirected ( const GRAPH * g )

is the given graph (originally) directed?

Parameters

g the graph

Definition at line 83 of file graph_stats.c.

References graph_typeIsUndirected().

Referenced by computeSteinerTree_execDirected(), computeSteinerTreeCsr(), computeSteinerTreeRedCostsDirected(), computeSteinerTreeTM(), createInitialCuts(), daExec(), daOrderRoots(), daRoundExit(), graph_csr_build(), redcostGraphSolRetransform(), reduce_da(), reduceWithEdgeFixingBounds(), shortestpath_computeSteinerTreeDirected(), and solstp_isUnreduced().

◆ graph_edge_isBlocked()

SCIP_Bool graph_edge_isBlocked	(	const GRAPH *	g,
		int	e
	)

is the edge blocked?

Parameters

g	the graph
e	the edge

Definition at line 94 of file graph_stats.c.

References BLOCKED, BLOCKED_MINOR, GRAPH::cost, EQ, FALSE, and TRUE.

Referenced by graph_pc_getOrgCosts(), graph_pc_getOrgCostsCsr(), graph_pc_shiftNonLeafCosts(), graph_pc_transOrgAreConistent(), setCostToOrgPc(), and setCostToOrgPcPreState().

◆ graph_edge_isInRange()

SCIP_Bool graph_edge_isInRange	(	const GRAPH *	g,
		int	e
	)

is edge in range?

Parameters

g	the graph
e	the edge

Definition at line 110 of file graph_stats.c.

Referenced by addComponentUpdateTreeCosts(), bdkTryDegGe4(), bottleneckMarkEqualityEdge(), closeNodesPathIsForbidden(), closeNodesRunCompute(), createPrizeConstraints(), daUpdateRescaps(), decomposeExactFixSol(), delPseudoPathCreatePseudoAncestorTuple(), distDataGetNormalDistForbidden(), distDataGetNormalDistForbiddenEq(), distDataGetNormalDistForbiddenLast(), extPreprocessInitialGenStar(), extractSubgraphAddEdge(), extreduce_bottleneckWithExtedgeIsDominated(), extreduce_bottleneckWithExtedgeIsDominatedBiased(), extreduce_distDataGetSdDoubleForbiddenEq(), extreduce_distDataGetSdDoubleForbiddenLast(), extreduce_distDataGetSdDoubleForbiddenSingle(), extreduce_edgeIsValid(), extreduce_extCompClean(), extreduce_redcostTreeRecompute(), extreduce_spgCheck3ComponentSimple(), extTreeStackTopRootRemove(), extUnhashInitialComponent(), generalStarCheck(), generalStarCheckExit(), generalStarCheckGetNextStar(), generalStarCheckInit(), getCloseNodeDistanceForbiddenLast(), getCloseNodePath(), gmlWriteEdge(), graph_edge_delPseudo(), graph_edge_delPseudoPath(), graph_edge_getAncestors(), graph_edge_redirect(), graph_tpathsGetProfitNodes(), graph_tpathsRepair(), graph_voronoiWithDist(), nsvEdgeIsValid(), nsvExec(), redcostGraphSolRetransform(), reduce_cutEdgeTryPrune(), reduce_impliedProfitBasedRpc(), reduce_sdprofitUpdateFromBLC(), reduce_sdRepair(), reduce_starResetWithEdges(), reduceLurk(), removeEdge(), sdgraphMstBuild(), sdqueryBuildBinaryTree(), sepafullReduceFromSols(), sepaspecial_vtimplicationsSeparate(), setSubBottleneckEdges(), subsolFixOrgEdges(), subSolIsRedundant(), tpathsPrintPath(), and tryPathPcMw().

◆ graph_edge_isDeleted()

SCIP_Bool graph_edge_isDeleted	(	const GRAPH *	g,
		int	e
	)

has edge been deleted?

Parameters

g	the graph
e	the edge

Definition at line 121 of file graph_stats.c.

References EAT_FREE, and GRAPH::oeat.

Referenced by generalStarDeleteEdges(), nsvEdgeIsValid(), reduceLurk(), reinsertSubgraphTransferEdges(), termcompDeleteEdges(), testGeneralStarDeletedEdge1(), testGeneralStarDeletedEdge2(), testGeneralStarDeletedEdge3(), testPathReplaceDeletesEdge(), testPathReplaceDeletesEdge2(), and tpathsPrintPath().

◆ graph_edge_printInfo()

void graph_edge_printInfo	(	const GRAPH *	g,
		int	e
	)

print information on edge

Parameters

g	the graph
e	the edge

Definition at line 133 of file graph_stats.c.

References GRAPH::cost, flipedge, graph_pc_isPcMw(), graph_typeIsUndirected(), h, GRAPH::head, GRAPH::tail, and GRAPH::term.

Referenced by applyEdgestateToProb(), bdkStarLoadNext(), bottleneckMarkEqualityPath(), delPseudoEdgeDeleteEdge(), delPseudoPath(), distCloseNodesPrintLostNodeInfo(), extreduce_printStack(), extStackAddCompsNonExpanded(), extTreeRuleOutEdgeSimple(), fixEdgestate(), generalStarCheck(), generalStarCheckGetNextStar(), generalStarCheckInit(), getBoundaryPathCostPrized(), getKeyPathsStar(), getKeyPathUpper(), graph_pc_transOrgAreConistent(), nsvEdgeContract(), pcsolPrune(), pcsubtreeDelete(), pcsubtreePruneForProfit(), reduce_blctreeGetMstEdgesToCutDist(), reduce_impliedProfitBasedRpc(), reduce_rpt(), reduce_sdBiased(), reduce_sdBiasedNeighbor(), reduce_sdEdgeCliqueStar(), reduce_sdImpLongEdge(), reduce_simple_sap(), reduce_sl(), removeEdge(), replaceEdgeByPath(), SCIPStpHeurLocalExtendPcMw(), sepafullReduceFromSols(), setEdgestate(), setSubBottleneckEdges(), solstp_print(), subgraphBuild(), subsolFixOrgEdges(), supergraphComputeMst(), tbottleneckInit(), termcompDeleteEdges(), testDistRootPathsAreValid(), tpathsPrintPath(), treeGetCounters(), and validateEdgestate().

◆ graph_knot_printInfo()

void graph_knot_printInfo	(	const GRAPH *	g,
		int	k
	)

print information on node

Parameters

g	the graph
k	the node

Definition at line 151 of file graph_stats.c.

References GRAPH::grad, graph_knotIsNWLeaf(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), Is_term, NULL, GRAPH::prize, GRAPH::source, STP_NWPTSPG, GRAPH::stp_type, GRAPH::term, and GRAPH::term2edge.

Referenced by addComponentUpdateLeavesStarts(), ansDeleteVertex(), bidecomposition_markSub(), createPrizeConstraints(), cutNodesGetLastCutnode(), cutNodesTreeDeleteComponents(), cutNodesTreeMakeTerms(), cutNodesTreeMakeTermsIsComplete(), dapathsFixPotTerms(), dapathsSortStarts(), decomposeCsrIsValid(), decomposeExactSubTry(), decomposeGetSubgraph(), distCloseNodesPrintLostNodeInfo(), extreduce_distCloseNodesAreValid(), graph_isMarked(), graph_path_st_dc(), graph_pc_term2edgeIsConsistent(), graph_tpathsPrintForNode(), graph_transRpcGetSpg(), graph_valid(), graphmarkIsClean(), propgraphDeleteNode(), propgraphFixNode(), reduce_applyPseudoDeletions(), reduce_bound(), reduce_compbuilderPrintSeparators(), reduce_rpt(), reduce_simple_sap(), reduce_unconnectedRpcRmwInfeas(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalExtendPcMwImp(), solDegIsValid(), solstp_isValid(), and termcompMarkPseudoDelNodes().

◆ graph_hasMultiEdges()

SCIP_Bool graph_hasMultiEdges	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Bool	verbose
	)

graph with multi-edges?

Parameters

scip	SCIP data structure
g	graph data structure
verbose	be verbose?

Definition at line 185 of file graph_stats.c.

References EAT_LAST, FALSE, graph_get_nNodes(), GRAPH::head, nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPdebugMessage, SCIPerrorMessage, SCIPfreeBufferArray, and TRUE.

Referenced by check_inputgraph(), and graph_load().

◆ graph_isAlmostUniform()

SCIP_Bool graph_isAlmostUniform ( const GRAPH * g )

has the graph almost uniform edge weights?

Parameters

g the graph

Definition at line 237 of file graph_stats.c.

References GRAPH::cost, EAT_FREE, EQ, FARAWAY, graph_get_nEdges(), GRAPH::oeat, SCIP_Real, SCIPdebugMessage, STP_UNIFORM_MINRATIO, STP_UNIFORM_RANGEMAX, STP_UNIFORM_RANGEMIN, and TRUE.

◆ graph_printInfo()

void graph_printInfo ( const GRAPH * g )

print information on graph

Parameters

g the graph

Definition at line 299 of file graph_stats.c.

References GRAPH::budget, GRAPH::edges, GRAPH::extended, graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_nFixedTerms(), graph_pc_nNonLeafTerms(), graph_pc_nProperPotentialTerms(), GRAPH::knots, NULL, GRAPH::source, STP_BRMWCSP, GRAPH::stp_type, and GRAPH::terms.

Referenced by decomposeExactSubDoIt(), pcmwEnumerationTry(), reduce_bound(), reduce_redLoopPc(), SCIPStpHeurAscendPruneRun(), solveSub(), solveWithDpBorder(), and tbottleneckInit().

◆ graph_printInfoReduced()

void graph_printInfoReduced ( const GRAPH * g )

print information on graph that has been subject to reductions

Parameters

g the graph

Definition at line 375 of file graph_stats.c.

References GRAPH::extended, graph_get_nVET(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_nFixedTerms(), graph_pc_nNonLeafTerms(), graph_pc_nProperPotentialTerms(), nnodes, nterms, GRAPH::source, and GRAPH::stp_type.

Referenced by decomposeReduceSubDoIt(), initHelpers(), lurkpruneInit(), mincut_findTerminalSeparators(), nodesolUpdate(), redcostGraphMark(), reduceLurk(), and SCIPStpHeurTMRun().

◆ graph_printEdgeConflicts()

SCIP_RETCODE graph_printEdgeConflicts	(	SCIP *	scip,
		const GRAPH *	g
	)

prints edge conflicts

Parameters

scip	SCIP data structure
g	the graph

Definition at line 408 of file graph_stats.c.

References a, GRAPH::ancestors, GRAPH::edges, GRAPH::extended, FALSE, graph_edge_getPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_getNfixpseudonodes(), graph_knot_getPseudoAncestors(), graph_knot_nPseudoAncestors(), graph_pc_isPcMw(), Is_term, GRAPH::knots, MAX, nnodes, NULL, GRAPH::orgedges, GRAPH::pcancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::term, and TRUE.

◆ graph_get_nNodes()

int graph_get_nNodes ( const GRAPH * graph )

get number of nodes

Parameters

graph the graph

Definition at line 536 of file graph_stats.c.

References GRAPH::knots.

Referenced by allTermsAreVisited(), bidecomposition_cutnodesInit(), bidecomposition_init(), bidecomposition_isPossible(), bidecomposition_markSub(), blctreeBuildMst(), blctreeInitPrimitives(), borderNodesCollect(), buildTmAllSp(), cliquePathsInitData(), collectRoots(), computeOnMarked_init(), computeOrderingFromNode(), computeSteinerTree(), computeSteinerTree_allFixedTermsAreReached(), computeSteinerTree_allPseudoTermsAreReached(), computeSteinerTree_allTermsAreReached(), computeSteinerTree_init(), computeSteinerTreeTM(), createModel(), createPrizeConstraints(), cutEdgeProbe(), cutNodesGetLastCutnode(), cutNodesSetDfsRoot(), cutNodesTreeBuildSteinerTree(), cutNodesTreeDeleteComponents(), cutNodesTreeInit(), cutNodesTreeMakeTermsIsComplete(), dapathsInit(), dapathsSetRunParams(), dapathsSortStarts(), daRedcostsInit(), decomposeBuildCsr(), decomposeGetFirstMarked(), deletenodesDeg1(), dhcstpWarmUp(), distCloseNodesIncluded(), distgraphAddEdges(), distgraphAddEdgesFromTpaths(), distgraphAddNodes(), dpborder_coreSolve(), dpborder_dpbsequenceInit(), dpborderInitHelper(), dpgraphInit(), dpiterInit(), dualascent_allTermsReachable(), dualascent_execDegCons(), enumExec(), enumIsPromising(), extractSubgraphAddEdgesWithHistory(), extractSubgraphGetSizeAndMap(), extreduce_distCloseNodesAreValid(), extreduce_distDataRecomputeDirtyPaths(), extreduce_extdataCleanArraysDbg(), extreduce_extdataIsClean(), extreduce_extPermaInit(), extreduce_extPermaIsClean(), extreduce_pcdataIsClean(), extreduce_treeIsFlawed(), findSolPcMw2Term(), findSolRPcMw(), fixVarsRedbased(), getBiasedMw(), getBiasedPc(), getBoundchanges(), getOrgNodeToNodeMap(), getRedCost2ndNextDistances(), getSd(), graph_add1stTermPaths(), graph_add2ndTermPaths(), graph_add3rdTermPaths(), graph_add4thTermPaths(), graph_buildOrgNodesToReducedMap(), graph_csr_build(), graph_csr_buildCosts(), graph_csr_chgCosts(), graph_csr_costsAreInSync(), graph_dijkLimited_initPcShifts(), graph_findCentralTerminal(), graph_get2nextTermPaths(), graph_get3nextTermPaths(), graph_get4nextTermPaths(), graph_getTerms(), graph_hasMultiEdges(), graph_initContractTracing(), graph_load(), graph_mark(), graph_pack(), graph_path_exec(), graph_path_st_dc(), graph_pc_2org(), graph_pc_getNonLeafTermOffset(), graph_pc_getOrgCostsCsr(), graph_pc_knotHasMaxPrize(), graph_pc_nNonLeafTerms(), graph_pc_solGetObj(), graph_sdCloseNodesBiased(), graph_sdStarBiased(), graph_subinoutInit(), graph_tpathsAdd1st(), graph_tpathsAdd2nd(), graph_tpathsAdd3rd(), graph_tpathsAdd4th(), graph_tpathsGetProfitNodes(), graph_tpathsPrintForNode(), graph_tpathsRepairSetUp(), graph_tpathsSetAll2(), graph_tpathsSetAll3(), graph_tpathsSetAll4(), graph_transMw(), graph_transNw2pc(), graph_transNw2sap(), graph_transRpcGetSpg(), graph_transRpcToSpgIsStable(), graph_validInput(), graph_vnoiCompute(), graph_vnoiComputeImplied(), graph_vnoiInit(), graph_voronoiRepair(), graph_voronoiTerms(), graph_voronoiWithDist(), graph_writeReductionStats(), graph_writeStp(), graphmarkIsClean(), initPropAtFirstCall(), initRedcostdata(), initSolve(), isMaxprizeTerm(), keyNodesResetTerms(), keyNodesSetTerms(), ledgeFromNetgraph(), log2floor(), lurkpruneInit(), mincut_separateLp(), mincutExec(), mincutFree(), mincutInit(), mincutInitForLp(), mincutInitForTermSepa(), mincutPrepareForLp(), mst_getObj(), mst_getSoledges(), mst_init(), mwContract0WeightVertices(), mwContractTerminalsChainWise(), mwContractTerminalsSimple(), nodesolGetEdgeSol(), nodesolSetTrivial(), nodesolUpdate(), nsvInitData(), nwptstpSetRoot(), packNodes(), pcmwAdaptStarts(), pcmwDeleteNonSolEdges(), pcmwFindMax2Terms(), pcmwUpdateBestSol_csrInSync(), pcsolGetMstEdges(), pcsolMarkGraphNodes(), pcsolMarkGraphNodes_csr(), pcsolPrune(), prInit(), propgraphApplyImplicationsPcMw(), propgraphApplyStates(), propgraphMarkFixedTermsPcMw(), pruneSteinerTreeStp(), pseudodeleteBiasedIsPromising(), pseudodeleteDeleteMarkedNodes(), pseudodeleteExecute(), pseudodeleteInit(), redcostGetNTermsMarked(), redcostGraphBuild(), redcostGraphComputeSteinerTreeDirected(), redcostGraphMark(), redcostGraphSolRetransform(), redcosts_forLPget(), redcosts_initializeDistances(), reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_applyPseudoDeletions(), reduce_baseInit(), reduce_bdkWithSd(), reduce_blctreeGetMstBottlenecks(), reduce_blctreeGetMstEdges(), reduce_blctreeGetMstEdgesState(), reduce_blctreeGetMstEdgesToCutDist(), reduce_bound(), reduce_chain2(), reduce_cnsAdv(), reduce_compbuilderInit(), reduce_cutEdgeTryPrune(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_dc(), reduce_getMinNreductions(), reduce_hc(), reduce_identifyNonLeafTerms(), reduce_impliedNodesGet(), reduce_impliedNodesIsValid(), reduce_mw(), reduce_nnp(), reduce_nodesDeg1(), reduce_npv(), reduce_nvAdv(), reduce_removeDeg0NonLeafTerms(), reduce_rpt(), reduce_sap(), reduce_sd(), reduce_sdBiased(), reduce_sdBiasedNeighbor(), reduce_sdEdgeCliqueStar(), reduce_sdImpLongEdge(), reduce_sdneighborGetCloseTerms(), reduce_sdneighborInit(), reduce_sdprofitPrintStats(), reduce_sdsp(), reduce_sdStarBiasedWithProfit(), reduce_simple_dc(), reduce_simple_mw(), reduce_simple_pc(), reduce_simple_sap(), reduce_solGetEdgesol(), reduce_solLevelTopUpdate(), reduce_sollocalInit(), reduce_sollocalUpdateNodesol(), reduce_solPack(), reduce_stp(), reduce_termcompChangeSubgraphToBottleneck(), reduce_unconnectedForDirected(), reduce_unconnectedInfeas(), reduceExact(), reducePcMw(), reinsertSubgraphAdaptSubToOrgMap(), reinsertSubgraphDeleteOldEdges(), reinsertSubgraphTransferTerminals(), reroot(), SCIPStpHeurSlackPruneRun(), SCIPStpHeurTMRunLP(), SCIPStpPropCheckForInfeas(), SCIPStpPropGetGraph(), SCIPStpValidateSol(), sdCliqueInitData(), sdCliqueUpdateGraphWithStarWalks(), sdGetSdsCliqueTermWalks(), sdgraphAlloc(), sdgraphAllocRestricted(), sdgraphMstBuild(), sdgraphMstMarkOrgEdges(), sdgraphMstSortCosts(), sdgraphSetDefaults(), sdgraphUpdateDistgraphFromTpaths(), sdneighborUpdateExec(), sdneighborUpdateInit(), sdprofitAlloc(), sdprofitBuild(), sdprofitBuild1stOnly(), sdqueryAttachBinaryTreeNode(), sdqueryBuildBinaryTree(), sdqueryBuildNodesToFullMap(), sdqueryBuildNodesToRmqMap(), sdqueryFullInit(), sdqueryGetRmqLength(), sdqueryLcaBuilderInit(), sdqueryRmqInit(), sdStarBiasedProcessNode(), sdStarInit(), selectBranchingVertexBySol(), sep_flow(), sepaspecial_pcimplicationsInit(), sepaspecial_vtimplicationsInit(), setNodeSolArray(), shortestpath_pcInit(), solGetMstEdges_csr(), solstp_getObjCsr(), solstp_isValid(), solstp_pcConnectDummies(), solstp_pcGetObjCsr(), solstp_pcGetSolRoot(), solstp_pruneFromEdges(), STP_Vectype(), stPcmwInit(), stpsol_pruningIsPossible(), stpsolPrune_csr(), strongPruneSteinerTreePc(), strongPruneSteinerTreePc_csr(), stRpcmwInit(), tbottleneckInit(), termcompDeleteEdges(), termcompMarkPseudoDelNodes(), termsepaCsrAddEdges(), termsepaCsrAddReverseEdges(), termsepaCsrAddTermCopies(), termsepaCsrGetMaxNedges(), termsepaCsrGetMaxNnodes(), termsepaCutIsCorrect(), termsepaStoreCutFinalize(), termsepaTraverseSinkComp(), tmAllspFree(), tmAllspInit(), tmBaseInit(), tmVnoiFree(), tmVnoiInit(), tpathsAlloc(), tpathsGetDistNew(), tpathsPrintPath(), tpathsRepairExit(), tpathsRepairInitLevel(), tpathsRepairTraverseLevelWithStack(), tpathsRepairTraverseStackAddBelow(), tpathsRepairTraverseStackAddEdge(), tpathsRepairUpdateLevel(), tpathsResetMembers(), tpathsScan2nd(), tpathsScan3rd(), tpathsScan4th(), trailGraphWithStates(), treeDistsAreFlawed(), treeResetCounters(), tryPathPcMw(), updateEdgestateFromRedPcmw(), updateTerminalSource(), vnoiCompute(), vnoiComputeImplied(), and vnoiInit().

◆ graph_get_nEdges()

int graph_get_nEdges ( const GRAPH * graph )

get number of edges

Parameters

graph the graph

Definition at line 548 of file graph_stats.c.

References GRAPH::edges.

Referenced by applyEdgestateToProb(), blockEdgesWithGlobalFixings(), computeSteinerTree(), computeSteinerTreeSingleNode(), computeSteinerTreeTM(), createModel(), createPrizeConstraints(), dapathsDeleteEdges(), dapathsInitRedCosts(), daRedcostsInit(), daRoundInit(), daUpdateRescaps(), dhcstpWarmUp(), distgraphAddEdges(), distgraphGetNedges(), dpgraphInit(), dualascent_execDegCons(), enumeration_findSolPcMw(), extreduce_deleteArcs(), extreduce_deleteEdges(), extreduce_extdataIsClean(), extreduce_treeIsFlawed(), fixVarsRedbased(), getBoundchanges(), getGraphStatesDirected(), getRedCost2ndNextDistances(), graph_copyPseudoAncestors(), graph_csr_build(), graph_csr_buildCosts(), graph_csr_chgCosts(), graph_csr_costsAreInSync(), graph_getEdgeCosts(), graph_getEdgeRevCosts(), graph_initAncestors(), graph_initHistory(), graph_isAlmostUniform(), graph_pack(), graph_path_st_dc(), graph_pc_costsEqualOrgCosts(), graph_pc_getNorgEdges(), graph_pc_getOrgCosts(), graph_pc_getOrgCostsCsr(), graph_pc_solGetObj(), graph_subgraphCompleteNewHistory(), graph_subinoutActivateEdgeMap(), graph_transGstpClean(), graph_transNw2pc(), graph_writeReductionStats(), initRedcostdata(), keyNodesSetTerms(), ledgeFromNetgraph(), lpcutAdd(), lurkpruneFinalize(), lurkpruneInit(), mark0FixedArcs(), mincutInit(), mincutInitForLp(), mincutInitForTermSepa(), mincutPrepareForLp(), mst_getSoledges(), mst_init(), nodesolGetEdgeSol(), packEdges(), packPseudoAncestors(), pacliquesBuildMap(), pathreplaceExec(), pcmwEnumerationTry(), pcmwUpdateBestSol(), pcmwUpdateBestSol_csrInSync(), propgraphApplyStates(), pruneSteinerTreePc(), redcostGraphComputeSteinerTreeDegCons(), redcostGraphComputeSteinerTreeDirected(), redcostGraphMark(), redcostGraphSolRetransform(), redcosts_forLPareReliable(), redcosts_forLPget(), redcosts_increaseOnDeletedArcs(), redcosts_initializeDistances(), redcosts_unifyBlockedEdgeCosts(), reduce_baseInit(), reduce_bound(), reduce_boundHopDa(), reduce_dapaths(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_fixedConflicts(), reduce_getMinNreductions(), reduce_hc(), reduce_sap(), reduce_sd(), reduce_stp(), reduceExact(), reduceFixedVars(), reduceLurk(), reinsertSubgraphTransferEdges(), runTmDhcstp(), SCIPStpHeurSlackPruneRun(), SCIPStpHeurTMRun(), SCIPStpHeurTMRunLP(), SCIPStpPropCheckForInfeas(), SCIPStpPropGetGraph(), sdgraphAlloc(), sdgraphBuildDistgraph(), sdgraphMstBuild(), sdgraphMstMarkOrgEdges(), sdgraphSetDefaults(), sdStarFinalize(), sdStarInit(), selectBranchingVertexBySol(), sepafullBuildSolcands(), sepafullReduceFromSols(), sepaspecial_pacliquesInit(), sepaspecial_pacliquesSeparate(), setNodeSolArray(), solAddTry(), solGetStpSol(), solpool_addSolToScip(), solstp_addSolToProb(), solstp_convertCsrToGraph(), solstp_getNedges(), solstp_getNedgesBounded(), solstp_getStpFromSCIPsol(), solstp_getTrivialSol(), solstp_isUnreduced(), solstp_print(), solstp_prune(), solstp_pruneFromEdges(), solstp_pruneFromTmHeur(), tbottleneckInit(), termcompComputeSubgraphSol(), termsepaCsrAddReverseEdges(), termsepaCsrGetMaxNedges(), termsepaCsrInit(), tmBaseInit(), treeResetCounters(), updateBestSol(), updateEdgestateFromRed(), updateEdgestateFromRedPcmw(), and validateEdgestate().

◆ graph_get_nTerms()

int graph_get_nTerms ( const GRAPH * graph )

get number of terminals

Parameters

graph the graph

Definition at line 560 of file graph_stats.c.

References GRAPH::terms.

Referenced by dpgraphInit(), reduce_mw(), reduce_nvAdv(), reduce_stp(), and termsepaCsrGetMaxNnodes().

◆ graph_get_nVET()

void graph_get_nVET	(	const GRAPH *	graph,
		int *	nnodes,
		int *	nedges,
		int *	nterms
	)

get (real) number of nodes, edges, terminals

Parameters

graph	the graph
nnodes	number of nodes
nedges	number of edges
nterms	number of terminals

Definition at line 571 of file graph_stats.c.

References GRAPH::grad, Is_term, GRAPH::knots, MAX, NULL, and GRAPH::term.

Referenced by blctreeInitPrimitives(), daGetNruns(), dapathsIsPromising(), distDataInitSizes(), dpterms_isPromisingFully(), extreduce_getMaxTreeDepth(), getReductionRatios(), graph_printInfoReduced(), graph_writeReductionStats(), graph_writeStp(), initHelpers(), lurkpruneInit(), mincut_findTerminalSeparatorsIsPromising(), redLoopInnerMw(), reduce_compbuilderInit(), SCIPStpHeurPruneRun(), and SCIPStpHeurSlackPruneRun().

◆ graph_get_avgDeg()

SCIP_Real graph_get_avgDeg ( const GRAPH * graph )

get (real) average degree of graph

Parameters

graph the graph

Definition at line 613 of file graph_stats.c.

References GRAPH::grad, and GRAPH::knots.