Detailed Description

includes various files containing graph methods used for Steiner tree problems

Author: Gerald Gamrath; Thorsten Koch; Daniel Rehfeldt

Definition in file graph.h.

#include "scip/scip.h"
#include "misc_stp.h"
#include "graphdefs.h"
#include "redcosts.h"
#include "reducedefs.h"
#include "portab.h"
#include "stpvector.h"

Go to the source code of this file.

Functions
SCIP_RETCODE	graph_initContractTracing (SCIP , GRAPH )

int	graph_contractTrace (int, const GRAPH *)

SCIP_Bool	graph_knot_hasContractTrace (int, const GRAPH *)

void	graph_fixed_resetMoved (GRAPH *)

SCIP_RETCODE	graph_singletonAncestors_init (SCIP , const GRAPH , int, SINGLETONANS *)

void	graph_singletonAncestors_freeMembers (SCIP , SINGLETONANS )

SCIP_Bool	graph_valid_ancestors (SCIP , const GRAPH )

SCIP_RETCODE	graph_initAncestors (SCIP , GRAPH )

SCIP_RETCODE	graph_initPseudoAncestors (SCIP , GRAPH )

SCIP_RETCODE	graph_initPseudoAncestorsSized (SCIP , int, GRAPH )

void	graph_freePseudoAncestors (SCIP , GRAPH )

void	graph_edge_delPseudoAncestors (SCIP , int, GRAPH )

void	graph_knot_delPseudoAncestors (SCIP , int, GRAPH )

void	graph_edge_printPseudoAncestors (const GRAPH *, int)

void	graph_knot_printPseudoAncestors (const GRAPH *, int)

int	graph_edge_nPseudoAncestors (const GRAPH *, int)

int	graph_knot_nPseudoAncestors (const GRAPH *, int)

const int *	graph_edge_getPseudoAncestors (const GRAPH *, int)

IDX *	graph_edge_getAncestors (const GRAPH *, int)

const int *	graph_knot_getPseudoAncestors (const GRAPH *, int)

int	graph_getNpseudoAncestors (const GRAPH *)

void	graph_addPseudoAncestor (GRAPH , int )

void	graph_addPseudoAncestors (int, GRAPH *)

SCIP_RETCODE	graph_pseudoAncestors_appendCopyEdge (SCIP , int, int, SCIP_Bool, GRAPH , SCIP_Bool *)

SCIP_RETCODE	graph_pseudoAncestors_appendCopyNode (SCIP , int, int, SCIP_Bool, GRAPH , SCIP_Bool *)

SCIP_RETCODE	graph_pseudoAncestors_appendCopyNodeToEdge (SCIP , int, int, SCIP_Bool, GRAPH , SCIP_Bool *)

SCIP_RETCODE	graph_pseudoAncestors_appendCopyEdgeToNode (SCIP , int, int, SCIP_Bool, GRAPH , SCIP_Bool *)

SCIP_RETCODE	graph_pseudoAncestors_appendCopySingToEdge (SCIP , int, const SINGLETONANS , SCIP_Bool, GRAPH , SCIP_Bool )

SCIP_RETCODE	graph_pseudoAncestors_appendCopyArrayToEdge (SCIP , int, const int , int, GRAPH , SCIP_Bool )

SCIP_RETCODE	graph_pseudoAncestors_appendMoveEdge (SCIP , int, int, SCIP_Bool, GRAPH , SCIP_Bool *)

SCIP_RETCODE	graph_pseudoAncestors_appendMoveNode (SCIP , int, int, SCIP_Bool, GRAPH , SCIP_Bool *)

SCIP_RETCODE	graph_pseudoAncestors_addToEdge (SCIP , int, int, GRAPH )

SCIP_RETCODE	graph_pseudoAncestors_addToNode (SCIP , int, int, GRAPH )

SCIP_RETCODE	graph_free_pseudoAncestorsBlock (SCIP , int, GRAPH )

int	graph_pseudoAncestorsGetHashArraySize (const PSEUDOANS *)

void	graph_pseudoAncestors_hashNode (const PSEUDOANS , int, int )

void	graph_pseudoAncestors_hashEdge (const PSEUDOANS , int, int )

void	graph_pseudoAncestors_unhashNode (const PSEUDOANS , int, int )

void	graph_pseudoAncestors_unhashEdge (const PSEUDOANS , int, int )

void	graph_pseudoAncestors_hashNodeDirty (const PSEUDOANS , int, SCIP_Bool, SCIP_Bool , int *)

void	graph_pseudoAncestors_hashEdgeDirty (const PSEUDOANS , int, SCIP_Bool, SCIP_Bool , int *)

void	graph_pseudoAncestors_unhashNodeDirty (const PSEUDOANS , int, int )

void	graph_pseudoAncestors_unhashEdgeDirty (const PSEUDOANS , int, int )

SCIP_Bool	graph_pseudoAncestors_edgeIsHashed (const PSEUDOANS , int, const int )

SCIP_Bool	graph_pseudoAncestors_nodeIsHashed (const PSEUDOANS , int, const int )

SCIP_Bool	graph_pseudoAncestors_edgesInConflict (SCIP , const GRAPH , const int *, int)

SCIP_Bool	graph_valid_pseudoAncestors (SCIP , const GRAPH )

SCIP_RETCODE	graph_init_fixed (SCIP , GRAPH )

void	graph_free_fixed (SCIP , GRAPH )

void	graph_free_fixedEdgesOnly (SCIP , GRAPH )

SCIP_RETCODE	graph_fixed_add (SCIP , IDX , const int , int, GRAPH )

SCIP_RETCODE	graph_fixed_addEdge (SCIP , int, GRAPH )

SCIP_RETCODE	graph_fixed_addNodePc (SCIP , int, GRAPH )

SCIP_RETCODE	graph_fixed_moveNodePc (SCIP , int, GRAPH )

SCIP_RETCODE	graph_copyFixed (SCIP , GRAPH , SCIP_Bool, GRAPH *)

IDX *	graph_getFixedges (const GRAPH *)

const int *	graph_getFixpseudonodes (SCIP , const GRAPH )

int	graph_getNfixpseudonodes (const GRAPH *)

SCIP_RETCODE	graph_termsReachable (SCIP , const GRAPH , SCIP_Bool *)

SCIP_RETCODE	graph_findCentralTerminal (SCIP , const GRAPH , int, int *)

SCIP_RETCODE	graph_trail_arr (SCIP , const GRAPH , int, SCIP_Bool *)

SCIP_RETCODE	graph_trail_costAware (SCIP , const GRAPH , int, SCIP_Bool *)

SCIP_RETCODE	graph_heap_create (SCIP , int, int , DENTRY , DHEAP *)

void	graph_heap_free (SCIP , SCIP_Bool, SCIP_Bool, DHEAP *)

void	graph_heap_deleteMin (int , SCIP_Real , DHEAP *)

void	graph_heap_deleteMinGetNode (int , DHEAP )

int	graph_heap_deleteMinReturnNode (DHEAP *)

void	graph_heap_clean (SCIP_Bool, DHEAP *)

void	graph_heap_correct (int, SCIP_Real, DHEAP *)

SCIP_Bool	graph_heap_isClean (const DHEAP *)

SCIP_RETCODE	graph_init_csr (SCIP , GRAPH )

SCIP_RETCODE	graph_init_csrWithEdgeId (SCIP , GRAPH )

void	graph_free_csr (SCIP , GRAPH )

SCIP_RETCODE	graph_csr_alloc (SCIP , int, int, CSR *)

SCIP_RETCODE	graph_csr_allocWithEdgeId (SCIP , int, int, CSR *)

void	graph_csr_copy (const CSR , CSR )

void	graph_csr_build (const GRAPH , const SCIP_Real , CSR *)

void	graph_csr_buildCosts (const GRAPH , const CSR , const SCIP_Real , SCIP_Real RESTRICT)

void	graph_csr_chgCosts (const GRAPH , const SCIP_Real , CSR *)

void	graph_csr_print (const CSR *)

int	graph_csr_getNedges (const CSR *)

void	graph_csr_free (SCIP , CSR *)

SCIP_Bool	graph_csr_costsAreInSync (const GRAPH , const CSR , const SCIP_Real *)

SCIP_Bool	graph_csr_isValid (const CSR *, SCIP_Bool verbose)

SCIP_Bool	graph_valid_csr (const GRAPH *, SCIP_Bool verbose)

void	graph_buildOrgNodesToReducedMap (const GRAPH , int )

SCIP_RETCODE	graph_csrdepo_init (SCIP , int, int, CSRDEPO *)

void	graph_csrdepo_free (SCIP , CSRDEPO *)

void	graph_csrdepo_print (const CSRDEPO *)

void	graph_csrdepo_getCSR (const CSRDEPO , int, CSR )

void	graph_csrdepo_getTopCSR (const CSRDEPO , CSR )

int	graph_csrdepo_getNcsrs (const CSRDEPO *)

int	graph_csrdepo_getDataSize (const CSRDEPO *)

void	graph_csrdepo_clean (CSRDEPO *)

void	graph_csrdepo_removeTop (CSRDEPO *)

void	graph_csrdepo_addEmptyTop (CSRDEPO *, int, int)

void	graph_csrdepo_addEmptyTopTree (CSRDEPO *, int)

SCIP_Bool	graph_csrdepo_isEmpty (const CSRDEPO *)

SCIP_Bool	graph_csrdepo_hasEmptyTop (const CSRDEPO *)

void	graph_csrdepo_getEmptyTop (const CSRDEPO , CSR )

void	graph_csrdepo_emptyTopSetMarked (CSRDEPO *)

SCIP_RETCODE	graph_init_dcsr (SCIP , GRAPH )

void	graph_update_dcsr (SCIP , GRAPH )

void	graph_dcsr_deleteEdge (DCSR *, int, int)

void	graph_dcsr_deleteEdgeBi (SCIP , DCSR , int)

void	graph_free_dcsr (SCIP , GRAPH )

SCIP_Bool	graph_valid_dcsr (const GRAPH *, SCIP_Bool verbose)

SCIP_RETCODE	graph_dijkLimited_init (SCIP , const GRAPH , DIJK **)

SCIP_RETCODE	graph_dijkLimited_initPcShifts (SCIP , const GRAPH , DIJK *)

void	graph_dijkLimited_reset (const GRAPH , DIJK )

void	graph_dijkLimited_clean (const GRAPH , DIJK )

void	graph_dijkLimited_free (SCIP , DIJK *)

void	graph_mark (GRAPH *)

void	graph_show (const GRAPH *)

void	graph_uncover (GRAPH *)

void	graph_free (SCIP , GRAPH *, SCIP_Bool)

void	graph_freeHistory (SCIP , GRAPH )

void	graph_freeHistoryDeep (SCIP , GRAPH )

void	graph_getIsTermArray (const GRAPH , SCIP_Bool )

void	graph_getTerms (const GRAPH , int )

SCIP_RETCODE	graph_getTermsRandom (SCIP , const GRAPH , int *)

void	graph_getEdgeCosts (const GRAPH , SCIP_Real RESTRICT, SCIP_Real *RESTRICT)

void	graph_getEdgeRevCosts (const GRAPH , SCIP_Real RESTRICT)

void	graph_getCsr (const GRAPH , int RESTRICT, int RESTRICT, int RESTRICT, int *)

SCIP_RETCODE	graph_resize (SCIP , GRAPH , int, int, int)

SCIP_RETCODE	graph_copy (SCIP , const GRAPH , GRAPH **)

SCIP_RETCODE	graph_copyPseudoAncestors (SCIP , const GRAPH , GRAPH *)

SCIP_RETCODE	graph_copyData (SCIP , const GRAPH , GRAPH *)

SCIP_RETCODE	graph_pack (SCIP , GRAPH , GRAPH *, REDSOL , SCIP_Bool)

SCIP_RETCODE	graph_init (SCIP , GRAPH *, int, int, int)

SCIP_RETCODE	graph_initHistory (SCIP , GRAPH )

SCIP_Bool	graph_isMarked (const GRAPH *)

SCIP_Bool	graph_isSetUp (const GRAPH *)

SCIP_RETCODE	graph_buildCompleteGraph (SCIP , GRAPH *, int)

SCIP_Bool	graph_valid (SCIP , const GRAPH )

SCIP_Bool	graph_validInput (SCIP , const GRAPH )

SCIP_Bool	graph_knotIsNWLeaf (const GRAPH *, int)

SCIP_RETCODE	graph_subgraphExtract (SCIP , GRAPH , SUBINOUT , GRAPH *)

SCIP_RETCODE	graph_subinoutInit (SCIP , const GRAPH , SUBINOUT **)

void	graph_subinoutFree (SCIP , SUBINOUT *)

void	graph_subinoutClean (SCIP , SUBINOUT )

SCIP_Bool	graph_subinoutUsesNewHistory (const SUBINOUT *)

SCIP_RETCODE	graph_subinoutActivateEdgeMap (const GRAPH , SUBINOUT )

void	graph_subinoutActivateNewHistory (SUBINOUT *)

const int *	graph_subinoutGetSubToOrgEdgeMap (const SUBINOUT *)

const int *	graph_subinoutGetSubToOrgNodeMap (const SUBINOUT *)

const int *	graph_subinoutGetOrgToSubNodeMap (const SUBINOUT *)

const int *	graph_subinoutGetContractionRecord (const SUBINOUT *)

int	graph_knot_getContractionRecordAncestor (int, const SUBINOUT *)

SCIP_RETCODE	graph_subgraphCompleteNewHistory (SCIP , const int , GRAPH , GRAPH )

SCIP_RETCODE	graph_subgraphReinsert (SCIP , SUBINOUT , GRAPH , GRAPH *)

void	graph_subgraphFree (SCIP , GRAPH *)

SCIP_RETCODE	graph_grid_create (SCIP , GRAPH , int *, int, int, int)

SCIP_RETCODE	graph_obstgrid_create (SCIP , GRAPH , int , int *, int, int, int, int)

SCIP_RETCODE	graph_grid_coordinates (SCIP , int , int , int , int, int)

void	graph_edge_add (SCIP , GRAPH , int, int, double, double)

void	graph_edge_addBi (SCIP , GRAPH , int, int, double)

void	graph_edge_addSubgraph (SCIP , const GRAPH , const int , int, GRAPH )

void	graph_edge_del (SCIP , GRAPH , int, SCIP_Bool)

void	graph_edge_delFull (SCIP , GRAPH , int, SCIP_Bool)

void	graph_edge_delBlocked (SCIP , GRAPH , const SCIP_Bool *, SCIP_Bool)

void	graph_edge_delHistory (SCIP , GRAPH , int)

void	graph_edge_hide (GRAPH *, int)

int	graph_edge_redirect (SCIP , GRAPH , int, int, int, SCIP_Real, SCIP_Bool, SCIP_Bool)

SCIP_RETCODE	graph_knot_contract (SCIP , GRAPH , int *, int, int)

SCIP_RETCODE	graph_knot_contractFixed (SCIP , GRAPH , int *, int, int, int)

SCIP_RETCODE	graph_knot_contractLowdeg2High (SCIP , GRAPH , int *, int, int)

SCIP_RETCODE	graph_knot_replaceDeg2 (SCIP , int, SCIP_Real, int, GRAPH , SCIP_Bool *)

SCIP_RETCODE	graph_edge_reinsert (SCIP , GRAPH , int, int, int, SCIP_Real, int, SINGLETONANS , SINGLETONANS , int , SCIP_Bool )

SCIP_Bool	graph_knot_isInRange (const GRAPH *, int)

void	graph_knot_add (GRAPH *, int)

void	graph_knot_chg (GRAPH *, int, int)

void	graph_knot_del (SCIP , GRAPH , int, SCIP_Bool)

void	graph_knot_delFull (SCIP , GRAPH , int, SCIP_Bool)

void	graph_knot_contract_dir (GRAPH *, int, int)

SCIP_RETCODE	graph_edge_delPseudo (SCIP , GRAPH , const SCIP_Real , const SCIP_Real , const SCIP_Real , int, SCIP_Real , SCIP_Bool *)

SCIP_RETCODE	graph_edge_delPseudoPath (SCIP , GRAPH , int, int, int, SCIP_Real *)

SCIP_RETCODE	graph_knot_delPseudo (SCIP , GRAPH , const SCIP_Real , const SCIP_Real , const SCIP_Real , int, REDCOST , SCIP_Bool *)

SCIP_RETCODE	graph_knot_delPseudoCheckIfPossible (SCIP , const GRAPH , const SCIP_Real , const SCIP_Real , const SCIP_Real , int, SCIP_Bool )

SCIP_RETCODE	graph_printEdgeConflicts (SCIP , const GRAPH )

void	graph_edge_printInfo (const GRAPH *, int)

SCIP_Bool	graph_edge_isBlocked (const GRAPH *, int)

SCIP_Bool	graph_edge_isDeleted (const GRAPH *, int)

SCIP_Bool	graph_edge_isInRange (const GRAPH *, int)

SCIP_Bool	graph_hasMultiEdges (SCIP , const GRAPH , SCIP_Bool)

SCIP_Bool	graph_isAlmostUniform (const GRAPH *)

void	graph_knot_printInfo (const GRAPH *, int)

void	graph_printInfo (const GRAPH *)

void	graph_printInfoReduced (const GRAPH *)

int	graph_get_nNodes (const GRAPH *)

int	graph_get_nEdges (const GRAPH *)

int	graph_get_nTerms (const GRAPH *)

void	graph_get_nVET (const GRAPH , int , int , int )

SCIP_Real	graph_get_avgDeg (const GRAPH *)

SCIP_Bool	graph_typeIsSpgLike (const GRAPH *)

SCIP_Bool	graph_typeIsUndirected (const GRAPH *)

SCIP_Bool	graph_typeIsDirected (const GRAPH *)

SCIP_RETCODE	graph_transNw (SCIP , PRESOL , GRAPH *)

SCIP_RETCODE	graph_transNw2sap (SCIP , PRESOL , GRAPH *)

SCIP_RETCODE	graph_transNw2pc (SCIP , PRESOL , GRAPH *)

void	graph_transGstpClean (PRESOL , GRAPH )

SCIP_RETCODE	graph_transPc (SCIP , GRAPH )

SCIP_RETCODE	graph_transPc2Spg (SCIP , PRESOL , GRAPH *)

SCIP_RETCODE	graph_transRpc (SCIP , GRAPH )

SCIP_RETCODE	graph_transRpc2SpgTrivial (SCIP , GRAPH )

SCIP_RETCODE	graph_transRpc2FixedProper (SCIP , PRESOL , GRAPH *)

SCIP_RETCODE	graph_transMw (SCIP , GRAPH )

SCIP_RETCODE	graph_transRmw (SCIP , GRAPH )

SCIP_RETCODE	graph_transPcmw2rooted (SCIP , GRAPH , SCIP_Real, SCIP_Bool)

SCIP_RETCODE	graph_transPcGetSap (SCIP , GRAPH , GRAPH *, SCIP_Real )

SCIP_RETCODE	graph_transPcGetRsap (SCIP , GRAPH , GRAPH *, const int , int, int)

SCIP_RETCODE	graph_transRpcGetSpg (SCIP , const GRAPH , SCIP_Real, SCIP_Real , int , GRAPH *)

SCIP_Bool	graph_transRpcToSpgIsStable (const GRAPH *, SCIP_Real)

void	graph_pc_knotToNonTermProperty (GRAPH *, int)

void	graph_pc_knotToFixedTermProperty (GRAPH *, int)

void	graph_pc_termToNonLeafTerm (SCIP , GRAPH , int, SCIP_Bool)

void	graph_pc_termToNonTerm (SCIP , GRAPH , int)

void	graph_pc_fixedTermToNonTerm (SCIP , GRAPH , int)

void	graph_pc_knotToFixedTerm (SCIP , GRAPH , int, SCIP_Real *)

void	graph_pc_nonTermToFixedTerm (GRAPH , int, SCIP_Real )

void	graph_pc_updateSubgraphEdge (const GRAPH , const int , int, GRAPH *)

void	graph_pc_enforcePseudoTerm (SCIP , GRAPH , int)

void	graph_pc_enforceNonLeafTerm (SCIP , GRAPH , int)

SCIP_Bool	graph_pc_nonLeafTermIsEnforced (SCIP , const GRAPH , int)

void	graph_pc_enforceNode (SCIP , GRAPH , int, SCIP_Real *)

void	graph_pc_subtractPrize (SCIP , GRAPH , SCIP_Real, int)

void	graph_pc_knotChgPrize (GRAPH *, SCIP_Real, int)

void	graph_pc_2org (SCIP , GRAPH )

void	graph_pc_2trans (SCIP , GRAPH )

void	graph_pc_2orgcheck (SCIP , GRAPH )

void	graph_pc_2transcheck (SCIP , GRAPH )

int	graph_pc_getNorgEdges (const GRAPH *)

void	graph_pc_getReductionRatios (const GRAPH , SCIP_Real , SCIP_Real *)

void	graph_pc_getOrgCosts (SCIP , const GRAPH , SCIP_Real *)

void	graph_pc_getOrgCostsCsr (SCIP , const GRAPH , CSR *)

void	graph_pc_markOrgGraph (GRAPH *)

void	graph_pc_adaptSap (SCIP_Real, GRAPH , SCIP_Real )

void	graph_pc_presolExit (SCIP , GRAPH )

void	graph_pc_getBiased (const GRAPH , SCIP_Real RESTRICT, SCIP_Real *RESTRICT)

void	graph_pc_termMarkProper (const GRAPH , int )

void	graph_pc_shiftNonLeafCosts (SCIP , GRAPH )

SCIP_Real	graph_pc_getNonLeafTermOffset (SCIP , const GRAPH )

SCIP_RETCODE	graph_pc_presolInit (SCIP , GRAPH )

SCIP_RETCODE	graph_pc_initSubgraph (SCIP , GRAPH )

SCIP_RETCODE	graph_pc_finalizeSubgraph (SCIP , GRAPH )

SCIP_RETCODE	graph_pc_initPrizes (SCIP , GRAPH , int)

SCIP_RETCODE	graph_pc_initTerm2Edge (SCIP , GRAPH , int)

SCIP_RETCODE	graph_pc_contractNodeAncestors (SCIP , GRAPH , int, int, int)

SCIP_RETCODE	graph_pc_contractEdge (SCIP , GRAPH , int *, int, int, int)

SCIP_RETCODE	graph_pc_contractEdgeUnordered (SCIP , GRAPH , int *, int, int)

int	graph_pc_deleteTerm (SCIP , GRAPH , int, SCIP_Real *)

int	graph_pc_realDegree (const GRAPH *, int, SCIP_Bool)

int	graph_pc_getRoot2PtermEdge (const GRAPH *, int)

int	graph_pc_nFixedTerms (const GRAPH *)

int	graph_pc_nNonFixedTerms (const GRAPH *)

int	graph_pc_nProperPotentialTerms (const GRAPH *)

int	graph_pc_nNonLeafTerms (const GRAPH *)

int	graph_pc_getTwinTerm (const GRAPH *, int)

SCIP_Bool	graph_pc_costsEqualOrgCosts (SCIP , const GRAPH , const SCIP_Real *)

SCIP_Bool	graph_pc_edgeIsExtended (const GRAPH *, int)

SCIP_Bool	graph_pc_knotIsFixedTerm (const GRAPH *, int)

SCIP_Bool	graph_pc_knotIsPropPotTerm (const GRAPH *, int)

SCIP_Bool	graph_pc_knotHasMaxPrize (const GRAPH *, int)

SCIP_Bool	graph_pc_knotIsDummyTerm (const GRAPH *, int)

SCIP_Bool	graph_pc_termIsNonLeafTerm (const GRAPH *, int)

SCIP_Bool	graph_pc_knotIsNonLeafTerm (const GRAPH *, int)

SCIP_Bool	graph_pc_evalTermIsNonLeaf (SCIP , const GRAPH , int)

SCIP_Bool	graph_pc_term2edgeIsConsistent (SCIP , const GRAPH )

SCIP_Bool	graph_pc_transOrgAreConistent (SCIP , const GRAPH , SCIP_Bool)

SCIP_Real	graph_pc_getPosPrizeSum (SCIP , const GRAPH )

SCIP_Bool	graph_pc_isPc (const GRAPH *)

SCIP_Bool	graph_pc_isMw (const GRAPH *)

SCIP_Bool	graph_pc_isPcMw (const GRAPH *)

SCIP_Bool	graph_pc_isRootedPcMw (const GRAPH *)

SCIP_Bool	graph_pc_isUnrootedPcMw (const GRAPH *)

SCIP_Real	graph_pc_solGetObj (SCIP , const GRAPH , const int *, SCIP_Real)

void	graph_path_exit (SCIP , GRAPH )

void	graph_path_exec (SCIP , const GRAPH , int, int, const SCIP_Real , PATH )

void	graph_pathInLimitedExec (const GRAPH , const SCIP_Real , const SCIP_Bool , int, DIJK , SCIP_Real *)

void	graph_path_execX (SCIP , const GRAPH , int, const SCIP_Real , SCIP_Real , int *)

void	graph_path_invroot (SCIP , const GRAPH , int, const SCIP_Real , SCIP_Real , int *)

void	graph_path_st (const GRAPH , const SCIP_Real , SCIP_Real , int , int, STP_Bool *)

SCIP_RETCODE	graph_path_st_dc (SCIP , const GRAPH , const SCIP_Real , SCIP_Real , int , int, STP_Bool , int , STP_Bool )

void	graph_path_st_rpcmw (GRAPH , SCIP_Real , int , const SCIP_Real , const SCIP_Real , SCIP_Real , int , int, STP_Bool )

SCIP_RETCODE	graph_path_st_brmwcs (SCIP , GRAPH , const SCIP_Real , SCIP_Real , int , int, STP_Bool , SCIP_Bool *)

void	graph_path_st_pcmw (GRAPH , SCIP_Real , int , const SCIP_Real , const SCIP_Real , SCIP_Bool, SCIP_Real , int , int, STP_Bool )

void	graph_path_st_pcmw_full (GRAPH , const SCIP_Real , SCIP_Real , int , int, STP_Bool *)

void	graph_path_st_pcmw_reduce (SCIP , const GRAPH , const SCIP_Real , SCIP_Real , int , int, STP_Bool )

void	graph_path_st_pcmw_extend (SCIP , const GRAPH , const SCIP_Real , SCIP_Bool, PATH , STP_Bool , SCIP_Bool )

void	graph_path_st_pcmw_extendBiased (SCIP , GRAPH , const SCIP_Real , const SCIP_Real , PATH , STP_Bool , SCIP_Bool *)

void	graph_path_st_pcmw_extendOut (SCIP , const GRAPH , int, STP_Bool , SCIP_Real , int , STP_Bool , DHEAP , SCIP_Bool )

void	graph_pathHeapAdd (const PATH , int, int RESTRICT, int RESTRICT, int )

void	graph_path_PcMwSd (SCIP , const GRAPH , PATH , SCIP_Real , SCIP_Real, int , int , int , int , int , int , int, int, int)

SCIP_RETCODE	graph_path_init (SCIP , GRAPH )

SCIP_Bool	graph_path_exists (const GRAPH *)

void	graph_sdPaths (const GRAPH , PATH , const SCIP_Real , SCIP_Real, int , int , int , int *, int, int, int)

void	graph_add2ndTermPaths (const GRAPH , const SCIP_Real , const SCIP_Real , PATH , int , int )

void	graph_add3rdTermPaths (const GRAPH , const SCIP_Real , const SCIP_Real , PATH , int , int )

void	graph_add4thTermPaths (const GRAPH , const SCIP_Real , const SCIP_Real , PATH , int , int )

void	graph_get2nextTermPaths (GRAPH , const SCIP_Real , const SCIP_Real , PATH , int , int )

void	graph_get3nextTermPaths (GRAPH , const SCIP_Real , const SCIP_Real , PATH , int , int )

void	graph_get4nextTermPaths (GRAPH , const SCIP_Real , const SCIP_Real , PATH , int , int )

SCIP_RETCODE	graph_get4nextTTerms (SCIP , GRAPH , const SCIP_Real , PATH , int , int , int *)

SCIP_RETCODE	graph_tpathsInit (SCIP , GRAPH , TPATHS **)

SCIP_RETCODE	graph_tpathsInitBiased (SCIP , const SDPROFIT , GRAPH , TPATHS *)

SCIP_RETCODE	graph_tpathsRecomputeBiased (const SDPROFIT , GRAPH , TPATHS *)

SCIP_RETCODE	graph_tpathsRepair (SCIP , int, SCIP_Bool, const GRAPH , TPATHS *)

SCIP_RETCODE	graph_tpathsRepairSetUp (const GRAPH , TPATHS )

void	graph_tpathsFree (SCIP , TPATHS *)

void	graph_tpathsPrintForNode (const GRAPH , const SDPROFIT , const TPATHS *, int)

void	graph_tpathsGetProfitNodes (SCIP , const GRAPH , const TPATHS , const SDPROFIT , int, int, STP_Vectype(int))

void	graph_tpathsAdd1st (const GRAPH , const SCIP_Real , const SDPROFIT , TPATHS )

void	graph_tpathsAdd2nd (const GRAPH , const SCIP_Real , const SCIP_Real , const SDPROFIT , TPATHS *)

void	graph_tpathsAdd3rd (const GRAPH , const SCIP_Real , const SCIP_Real , const SDPROFIT , TPATHS *)

void	graph_tpathsAdd4th (const GRAPH , const SCIP_Real , const SCIP_Real , const SDPROFIT , TPATHS *)

void	graph_tpathsSetAll2 (GRAPH , const SCIP_Real , const SCIP_Real , const SDPROFIT , TPATHS *)

void	graph_tpathsSetAll3 (GRAPH , const SCIP_Real , const SCIP_Real , const SDPROFIT , TPATHS *)

void	graph_tpathsSetAll4 (GRAPH , const SCIP_Real , const SCIP_Real , const SDPROFIT , TPATHS *)

void	graph_tpathsGetClosestTerm (const GRAPH , const TPATHS , int, int RESTRICT, int RESTRICT, SCIP_Real *RESTRICT)

void	graph_tpathsGet3CloseTerms (const GRAPH , const TPATHS , int, SCIP_Real, int RESTRICT, int RESTRICT, SCIP_Real RESTRICT, int RESTRICT)

void	graph_tpathsGet4CloseTerms (const GRAPH , const TPATHS , int, SCIP_Real, int RESTRICT, int RESTRICT, SCIP_Real RESTRICT, int RESTRICT)

void	graph_tpathsGet4CloseTermsLE (const GRAPH , const TPATHS , int, SCIP_Real, int RESTRICT, int RESTRICT, SCIP_Real RESTRICT, int RESTRICT)

void	graph_sdStar (SCIP , const GRAPH , SCIP_Bool, int, int, int , SCIP_Real , int , int , DHEAP , STP_Bool , SCIP_Bool *)

SCIP_RETCODE	graph_sdStarBiased (SCIP , const GRAPH , const SDPROFIT , int, int , DIJK , SCIP_Bool )

SCIP_RETCODE	graph_sdCloseNodesBiased (SCIP , const GRAPH , const SDPROFIT , int, DIJK )

SCIP_Bool	graph_sdWalksConnected (SCIP , const GRAPH , const int , const SCIP_Real , const STP_Bool , int, int, SCIP_Real , int , int , STP_Bool *, SCIP_Bool)

SCIP_Bool	graph_sdWalks (SCIP , const GRAPH , const SCIP_Real , const int , SCIP_Real, int, int, int, SCIP_Real , int , int , int , int , STP_Bool )

SCIP_Bool	graph_sdWalks_csr (SCIP , const GRAPH , const int , SCIP_Real, int, int, int, SCIP_Real , int , int , DHEAP , STP_Bool )

SCIP_Bool	graph_sdWalksTriangle (SCIP , const GRAPH , const int , const int , SCIP_Real, int, int, int, SCIP_Real , SCIP_Real , int , int , DHEAP , STP_Bool )

SCIP_Bool	graph_sdWalksExt (SCIP , const GRAPH , const SCIP_Real , SCIP_Real, int, int, int, int, SCIP_Real , int , int , int , int , int , int , STP_Bool *)

SCIP_Bool	graph_sdWalksExt2 (SCIP , const GRAPH , const SCIP_Real , const int , SCIP_Real, int, int, int, int, SCIP_Real , int , int , int , int , int , int , int , int , int , int , STP_Bool )

SCIP_RETCODE	graph_sdComputeCliqueStar (SCIP , const GRAPH , const SDPROFIT , SDCLIQUE )

SCIP_RETCODE	graph_vnoiInit (SCIP , const GRAPH , SCIP_Bool, VNOI **)

void	graph_vnoiFree (SCIP , VNOI *)

SCIP_RETCODE	graph_vnoiCompute (SCIP , const GRAPH , VNOI *)

SCIP_RETCODE	graph_vnoiComputeImplied (SCIP , const GRAPH , const SDPROFIT , VNOI )

void	graph_voronoi (const GRAPH , const SCIP_Real , const SCIP_Real , const STP_Bool , int , PATH )

void	graph_voronoiTerms (const GRAPH , const SCIP_Bool , int RESTRICT, PATH RESTRICT)

void	graph_voronoiRepair (SCIP , const GRAPH , const SCIP_Real , const SCIP_Real , int , int , PATH , int , int, UF *)

void	graph_voronoiRepairMult (SCIP , const GRAPH , const SCIP_Real , const STP_Bool , int RESTRICT, int RESTRICT, int RESTRICT, int RESTRICT, UF RESTRICT, PATH RESTRICT)

void	graph_voronoiWithRadiusMw (SCIP , const GRAPH , PATH , const SCIP_Real , SCIP_Real , int , int , int )

void	graph_voronoiMw (SCIP , const GRAPH , const SCIP_Real , PATH , int , int , int *)

void	graph_add1stTermPaths (const GRAPH , const SCIP_Real , PATH , int , int *)

void	voronoiSteinerTreeExt (SCIP , const GRAPH , SCIP_Real , int , STP_Bool , PATH )

SCIP_RETCODE	graph_voronoiExtend (SCIP , const GRAPH , const SCIP_Real , PATH , SCIP_Real , int , int *, STP_Bool , int , int , int *, int, int, int)

SCIP_RETCODE	graph_voronoiWithDist (SCIP , const GRAPH , const SCIP_Bool , const SCIP_Real , double , int , int , int , int , PATH )

SCIP_RETCODE	graph_voronoiWithRadius (SCIP , const GRAPH , GRAPH , PATH , SCIP_Real , SCIP_Real , SCIP_Real , int , int , int )

void	graph_mincut_exit (SCIP , GRAPH )

void	graph_mincut_exec (const GRAPH , const int, const int, const int, const int, const int, const int , const int , int RESTRICT, const int , const int , const int *, const SCIP_Bool)

SCIP_RETCODE	graph_mincut_init (SCIP , GRAPH )

SCIP_RETCODE	graph_mincut_reInit (SCIP , int, int, GRAPH )

SCIP_Bool	graph_mincut_isInitialized (const GRAPH *)

void	graph_mincut_setDefaultVals (GRAPH *)

SCIP_RETCODE	graph_load (SCIP , GRAPH , const char , PRESOL *)

void	graph_save (SCIP , const GRAPH , const char *, FILETYPE)

void	graph_writeReductionStats (const GRAPH , const char , const char *)

void	graph_writeReductionRatioStats (const GRAPH , const char , const char *)

SCIP_RETCODE	graph_writeReductionRatioStatsLive (SCIP , GRAPH , const char *)

SCIP_RETCODE	graph_writeGml (const GRAPH , const char , const SCIP_Bool *)

SCIP_RETCODE	graph_writeGmlSub (const GRAPH , const char , const SCIP_Bool *)

void	graph_writeStp (SCIP , const GRAPH , FILE *, SCIP_Real)

void	graph_writeStpByName (SCIP , const GRAPH , const char *, SCIP_Real)

void	graph_writeStpOrg (SCIP , const GRAPH , const char *)

SCIP_RETCODE	SCIPStpValidateSol (SCIP , const GRAPH , const double , SCIP_Bool, SCIP_Bool )

Function Documentation

◆ graph_initContractTracing()

SCIP_RETCODE graph_initContractTracing	(	SCIP *	scip,
		GRAPH *	graph
	)

initializes

Parameters

scip	SCIP data structure
graph	graph

Definition at line 1836 of file graph_history.c.

References GRAPH::contracttrace, graph_get_nNodes(), nnodes, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by extractSubgraphBuild().

◆ graph_contractTrace()

int graph_contractTrace	(	int	node,
		const GRAPH *	graph
	)

traces contraction back; returns traced node

Parameters

node	node to trace back from
graph	graph

Definition at line 1872 of file graph_history.c.

References GRAPH::contracttrace, GRAPH::grad, and graph_knot_isInRange().

Referenced by borderNodesContract(), and reinsertSubgraphTransferTerminals().

◆ graph_knot_hasContractTrace()

SCIP_Bool graph_knot_hasContractTrace	(	int	node,
		const GRAPH *	graph
	)

has the node a contract trace?

Parameters

node	node to trace back from
graph	graph

Definition at line 1859 of file graph_history.c.

References GRAPH::contracttrace, and graph_knot_isInRange().

Referenced by borderNodesContract(), and reinsertSubgraphTransferTerminals().

◆ graph_fixed_resetMoved()

void graph_fixed_resetMoved ( GRAPH * g )

resets

Parameters

g the graph

Definition at line 1821 of file graph_history.c.

References FALSE, GRAPH::fixedcomponents, fixed_graph_components::movedFrom, and NULL.

Referenced by reinsertSubgraphTransferFixedHistory().

◆ graph_singletonAncestors_init()

SCIP_RETCODE graph_singletonAncestors_init	(	SCIP *	scip,
		const GRAPH *	g,
		int	edge,
		SINGLETONANS *	singletonans
	)

initializes singleton edge ancestors

Parameters

scip	SCIP data structure
g	the graph
edge	edge to initialize from
singletonans	singleton edge ancestors

Definition at line 684 of file graph_history.c.

References singleton_ancestors_edge::ancestors, GRAPH::ancestors, BMScopyMemoryArray, singleton_ancestors_edge::edge, FALSE, flipedge, graph_edge_getAncestors(), graph_edge_getPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_typeIsUndirected(), singleton_ancestors_edge::npseudoancestors, NULL, singleton_ancestors_edge::pseudoancestors, singleton_ancestors_edge::revancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, and SCIPintListNodeAppendCopy().

Referenced by delPseudoDeleteVertex(), delPseudoEdgeDeleteEdge(), graph_knot_contract(), and pcReduceTermDeg2().

◆ graph_singletonAncestors_freeMembers()

void graph_singletonAncestors_freeMembers	(	SCIP *	scip,
		SINGLETONANS *	singletonans
	)

initializes singleton edge ancestors

Parameters

scip	SCIP data structure
singletonans	singleton edge ancestors

Definition at line 734 of file graph_history.c.

References singleton_ancestors_edge::ancestors, singleton_ancestors_edge::npseudoancestors, singleton_ancestors_edge::pseudoancestors, singleton_ancestors_edge::revancestors, SCIPfreeMemoryArray, and SCIPintListNodeFree().

Referenced by delPseudoDeleteVertex(), delPseudoEdgeDeleteEdge(), graph_knot_contract(), and pcReduceTermDeg2().

◆ graph_valid_ancestors()

SCIP_Bool graph_valid_ancestors	(	SCIP *	scip,
		const GRAPH *	g
	)

valid ancestors (no conflicts)?

Parameters

scip	SCIP data structure
g	the graph

Definition at line 753 of file graph_history.c.

References GRAPH::ancestors, ancestorsMarkConflict(), ancestorsUnmarkConflict(), GRAPH::cost, EAT_FREE, GRAPH::edges, FALSE, fixedPseudoAncestorsAreValid(), graph_pc_isPcMw(), graph_typeIsUndirected(), MAX, NULL, GRAPH::oeat, GRAPH::orgedges, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), TRUE, and GRAPH::withInexactReductions.

Referenced by reduce_da(), and reduce_redLoopStp().

◆ graph_initAncestors()

SCIP_RETCODE graph_initAncestors	(	SCIP *	scip,
		GRAPH *	g
	)

initializes edge ancestors

Parameters

scip	SCIP data structure
g	the graph

Definition at line 975 of file graph_history.c.

References GRAPH::ancestors, graph_get_nEdges(), graph_typeIsUndirected(), Int_List_Node::index, NULL, Int_List_Node::parent, SCIP_CALL, SCIP_OKAY, and SCIPallocBlockMemory().

Referenced by graph_initHistory(), and graph_subgraphCompleteNewHistory().

◆ graph_initPseudoAncestors()

SCIP_RETCODE graph_initPseudoAncestors	(	SCIP *	scip,
		GRAPH *	g
	)

initializes pseudo ancestors

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1049 of file graph_history.c.

References GRAPH::edges, graph_initPseudoAncestorsSized(), NULL, GRAPH::pseudoancestors, SCIP_CALL, and SCIP_OKAY.

Referenced by graph_initHistory(), packPseudoAncestors(), SCIP_DECL_PROBCOPY(), and SCIPprobdataCreateFromGraph().

◆ graph_initPseudoAncestorsSized()

SCIP_RETCODE graph_initPseudoAncestorsSized	(	SCIP *	scip,
		int	nedges,
		GRAPH *	g
	)

initializes pseudo ancestors with given size

Parameters

scip	SCIP data structure
nedges	number of edges to use
g	the graph

Definition at line 1064 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, pseudo_ancestors::ans_nodes, blockedAncestors_init(), graph_pc_isPcMw(), pseudo_ancestors::halfnedges, GRAPH::knots, pseudo_ancestors::nAllPseudoancestors, pseudo_ancestors::nnodes, NULL, GRAPH::pseudoancestors, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by extractSubgraphInitHistory(), and graph_initPseudoAncestors().

◆ graph_freePseudoAncestors()

void graph_freePseudoAncestors	(	SCIP *	scip,
		GRAPH *	g
	)

frees pseudo ancestors

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1101 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, pseudo_ancestors::ans_nodes, blockedAncestors_free(), pseudo_ancestors::nAllPseudoancestors, NULL, GRAPH::pseudoancestors, and SCIPfreeMemoryArray.

Referenced by graph_freeHistory().

◆ graph_edge_delPseudoAncestors()

void graph_edge_delPseudoAncestors	(	SCIP *	scip,
		int	edge_free,
		GRAPH *	g
	)

frees pseudo ancestor block for given edge

Parameters

scip	SCIP data structure
edge_free	edge for which to free pseudo ancestors
g	the graph

Definition at line 1128 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, blockedAncestors_freeBlock(), and GRAPH::pseudoancestors.

Referenced by graph_edge_delHistory(), graph_knot_contract(), graph_pseudoAncestors_appendMoveEdge(), and pseudoAncestorsCreation().

◆ graph_knot_delPseudoAncestors()

void graph_knot_delPseudoAncestors	(	SCIP *	scip,
		int	node_free,
		GRAPH *	g
	)

frees pseudo ancestor block for given node

Parameters

scip	SCIP data structure
node_free	node for which to free pseudo ancestors
g	the graph

Definition at line 1144 of file graph_history.c.

References pseudo_ancestors::ans_nodes, blockedAncestors_freeBlock(), graph_pc_isPcMw(), and GRAPH::pseudoancestors.

Referenced by graph_fixed_moveNodePc(), and graph_pseudoAncestors_appendMoveNode().

◆ graph_edge_printPseudoAncestors()

void graph_edge_printPseudoAncestors	(	const GRAPH *	g,
		int	edge
	)

prints pseudo ancestors for given edge

Parameters

g	the graph
edge	edge for which to return pseudo ancestors

Definition at line 1248 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, blocked_pseudo_ancestor::blocks, GRAPH::pseudoancestors, and blocked_pseudo_ancestor::sizes.

◆ graph_knot_printPseudoAncestors()

void graph_knot_printPseudoAncestors	(	const GRAPH *	g,
		int	node
	)

prints pseudo ancestors for given node

Parameters

g	the graph
node	node for which to return pseudo ancestors

Definition at line 1226 of file graph_history.c.

References pseudo_ancestors::ans_nodes, blocked_pseudo_ancestor::blocks, GRAPH::pseudoancestors, and blocked_pseudo_ancestor::sizes.

◆ graph_edge_nPseudoAncestors()

int graph_edge_nPseudoAncestors	(	const GRAPH *	g,
		int	edge
	)

returns number of pseudo ancestors for given edge

Parameters

g	the graph
edge	edge for which to return number of pseudo ancestors

Definition at line 1159 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, GRAPH::pseudoancestors, and blocked_pseudo_ancestor::sizes.

Referenced by extractSubgraphAddEdge(), extreduce_stackTopIsHashed(), extreduce_treeIsHashed(), graph_copyPseudoAncestors(), graph_fixed_addEdge(), graph_knot_contract(), graph_knot_replaceDeg2(), graph_printEdgeConflicts(), graph_singletonAncestors_init(), graph_subgraphCompleteNewHistory(), packPseudoAncestors(), pacliquesBuildMap(), pseudoAncestorsCreation(), pseudoAncestorsMerge(), pseudoDelDouble(), pseudoDelSingle(), and reduce_fixedConflicts().

◆ graph_knot_nPseudoAncestors()

int graph_knot_nPseudoAncestors	(	const GRAPH *	g,
		int	node
	)

returns number of pseudo ancestors for given node

Parameters

g	the graph
node	node for which to return number of pseudo ancestors

Definition at line 1174 of file graph_history.c.

References pseudo_ancestors::ans_nodes, GRAPH::pseudoancestors, and blocked_pseudo_ancestor::sizes.

Referenced by graph_fixed_addNodePc(), graph_printEdgeConflicts(), and pseudoAncestorsMergePc().

◆ graph_edge_getPseudoAncestors()

const int* graph_edge_getPseudoAncestors	(	const GRAPH *	g,
		int	edge
	)

returns pseudo ancestors for given edge

Parameters

g	the graph
edge	edge for which to return pseudo ancestors

Definition at line 1187 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, blocked_pseudo_ancestor::blocks, and GRAPH::pseudoancestors.

Referenced by extractSubgraphAddEdge(), graph_copyPseudoAncestors(), graph_fixed_addEdge(), graph_knot_replaceDeg2(), graph_printEdgeConflicts(), graph_singletonAncestors_init(), graph_subgraphCompleteNewHistory(), packPseudoAncestors(), pacliquesBuildMap(), pseudoDelSingle(), and reduce_fixedConflicts().

◆ graph_edge_getAncestors()

IDX* graph_edge_getAncestors	(	const GRAPH *	g,
		int	edge
	)

returns pseudo ancestors for given edge

Parameters

g	the graph
edge	edge for which to return ancestors

Definition at line 1202 of file graph_history.c.

References GRAPH::ancestors, flipedge, graph_edge_isInRange(), graph_typeIsUndirected(), and NULL.

Referenced by computeHistory(), computeHistoryPcMw(), computeReducedProbSolutionBiased(), delPseudoPath(), extractSubgraphAddEdge(), graph_fixed_addEdge(), graph_knot_replaceDeg2(), graph_pc_contractNodeAncestors(), graph_singletonAncestors_init(), markAncestors(), markAncestorsConflict(), mwTraverseChain(), reduce_contract0Edges(), retransformReducedProbSolution(), ruleOutSubtree(), SCIPStpHeurRecExclude(), solstp_getOrg(), unmarkAncestors(), and unmarkAncestorsConflict().

◆ graph_knot_getPseudoAncestors()

const int* graph_knot_getPseudoAncestors	(	const GRAPH *	g,
		int	node
	)

returns pseudo ancestors for given node

Parameters

g	the graph
node	node for which to return pseudo ancestors

Definition at line 1269 of file graph_history.c.

References pseudo_ancestors::ans_nodes, blocked_pseudo_ancestor::blocks, and GRAPH::pseudoancestors.

Referenced by graph_fixed_addNodePc(), and graph_printEdgeConflicts().

◆ graph_getNpseudoAncestors()

int graph_getNpseudoAncestors ( const GRAPH * g )

returns number of pseudo-ancestors

Parameters

g the graph

Definition at line 1282 of file graph_history.c.

References pseudo_ancestors::nAllPseudoancestors, and GRAPH::pseudoancestors.

Referenced by extractSubgraphInitHistory(), graph_copyPseudoAncestors(), packPseudoAncestors(), reinsertSubgraphTransferFixedHistory(), and sepaspecial_pacliquesInit().

◆ graph_addPseudoAncestor()

void graph_addPseudoAncestor	(	GRAPH *	g,
		int *	pseudoancestor
	)

adds new pseudo ancestor and provides index

Parameters

g	the graph (in/out)
pseudoancestor	gives the new pseudo ancestor index (out)

Definition at line 1293 of file graph_history.c.

References pseudo_ancestors::nAllPseudoancestors, and GRAPH::pseudoancestors.

Referenced by delPseudoDeleteVertex(), delPseudoPathCreatePseudoAncestorTuple(), pseudoAncestorsCreation(), pseudoAncestorsHash(), pseudoAncestorsMerge(), and testEdgeDeletion2_deprecated().

◆ graph_addPseudoAncestors()

void graph_addPseudoAncestors	(	int	nadd,
		GRAPH *	g
	)

adds n new pseudo ancestor

Parameters

nadd	number of ancestors to add
g	the graph (in/out)

Definition at line 1307 of file graph_history.c.

References pseudo_ancestors::nAllPseudoancestors, and GRAPH::pseudoancestors.

Referenced by extractSubgraphInitHistory(), graph_copyPseudoAncestors(), packPseudoAncestors(), and reinsertSubgraphTransferFixedHistory().

◆ graph_pseudoAncestors_appendCopyEdge()

SCIP_RETCODE graph_pseudoAncestors_appendCopyEdge	(	SCIP *	scip,
		int	edge_target,
		int	edge_source,
		SCIP_Bool	revertIfConflict,
		GRAPH *	g,
		SCIP_Bool *	conflict
	)

appends copy of pseudo ancestors of edge_source to edge_target

Parameters

scip	SCIP data structure
edge_target	edge target
edge_source	edge source
revertIfConflict	break on conflict
g	the graph
conflict	conflict?

Definition at line 1334 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, blockedAncestors_appendCopy(), graph_pseudoAncestorsGetHashArraySize(), GRAPH::pseudoancestors, SCIP_CALL, and SCIP_OKAY.

Referenced by delPseudoPath(), and graph_pseudoAncestors_appendMoveEdge().

◆ graph_pseudoAncestors_appendCopyNode()

SCIP_RETCODE graph_pseudoAncestors_appendCopyNode	(	SCIP *	scip,
		int	node_target,
		int	node_source,
		SCIP_Bool	revertIfConflict,
		GRAPH *	g,
		SCIP_Bool *	conflict
	)

appends copy of pseudo ancestors of node source to node target

Parameters

scip	SCIP data structure
node_target	node target
node_source	node source
revertIfConflict	break on conflict
g	the graph
conflict	conflict?

Definition at line 1358 of file graph_history.c.

References pseudo_ancestors::ans_nodes, blockedAncestors_appendCopy(), graph_pseudoAncestorsGetHashArraySize(), GRAPH::pseudoancestors, SCIP_CALL, and SCIP_OKAY.

Referenced by graph_pseudoAncestors_appendMoveNode().

◆ graph_pseudoAncestors_appendCopyNodeToEdge()

SCIP_RETCODE graph_pseudoAncestors_appendCopyNodeToEdge	(	SCIP *	scip,
		int	edge_target,
		int	node_source,
		SCIP_Bool	revertIfConflict,
		GRAPH *	g,
		SCIP_Bool *	conflict
	)

appends copy of pseudo ancestors of node source to edge target

Parameters

scip	SCIP data structure
edge_target	edge target
node_source	node source
revertIfConflict	break on conflict
g	the graph
conflict	conflict?

Definition at line 1380 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, pseudo_ancestors::ans_nodes, blockedAncestors_appendCopy(), graph_pseudoAncestorsGetHashArraySize(), GRAPH::pseudoancestors, SCIP_CALL, and SCIP_OKAY.

Referenced by graph_edge_reinsert(), and graph_knot_replaceDeg2().

◆ graph_pseudoAncestors_appendCopyEdgeToNode()

SCIP_RETCODE graph_pseudoAncestors_appendCopyEdgeToNode	(	SCIP *	scip,
		int	node_target,
		int	edge_source,
		SCIP_Bool	revertIfConflict,
		GRAPH *	g,
		SCIP_Bool *	conflict
	)

appends copy of pseudo ancestors of edge source to node target

Parameters

scip	SCIP data structure
node_target	node target
edge_source	edge source
revertIfConflict	break on conflict
g	the graph
conflict	conflict?

Definition at line 1403 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, pseudo_ancestors::ans_nodes, blockedAncestors_appendCopy(), graph_pseudoAncestorsGetHashArraySize(), GRAPH::pseudoancestors, SCIP_CALL, and SCIP_OKAY.

◆ graph_pseudoAncestors_appendCopySingToEdge()

SCIP_RETCODE graph_pseudoAncestors_appendCopySingToEdge	(	SCIP *	scip,
		int	edge_target,
		const SINGLETONANS *	source,
		SCIP_Bool	revertIfConflict,
		GRAPH *	g,
		SCIP_Bool *	conflict
	)

appends given of pseudo ancestors to edge target

Parameters

scip	SCIP data structure
edge_target	edge target
source	source
revertIfConflict	break on conflict
g	the graph
conflict	conflict?

Definition at line 1426 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, blockedAncestors_appendArray(), FALSE, graph_pseudoAncestorsGetHashArraySize(), singleton_ancestors_edge::npseudoancestors, singleton_ancestors_edge::pseudoancestors, GRAPH::pseudoancestors, SCIP_CALL, and SCIP_OKAY.

Referenced by graph_edge_reinsert(), and graph_knot_contract().

◆ graph_pseudoAncestors_appendCopyArrayToEdge()

SCIP_RETCODE graph_pseudoAncestors_appendCopyArrayToEdge	(	SCIP *	scip,
		int	edge_target,
		const int *	ancestors,
		int	nancestors,
		GRAPH *	g,
		SCIP_Bool *	conflict
	)

appends copy of pseudo ancestors in array form to edge target

Parameters

scip	SCIP data structure
edge_target	edge target
ancestors	pseudo ancestors array
nancestors	number of ancestors
g	the graph
conflict	conflict?

Definition at line 1458 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, blockedAncestors_appendArray(), FALSE, graph_pseudoAncestorsGetHashArraySize(), GRAPH::pseudoancestors, SCIP_Bool, SCIP_CALL, and SCIP_OKAY.

Referenced by extractSubgraphAddEdge(), graph_copyPseudoAncestors(), graph_knot_replaceDeg2(), graph_subgraphCompleteNewHistory(), and packPseudoAncestors().

◆ graph_pseudoAncestors_appendMoveEdge()

SCIP_RETCODE graph_pseudoAncestors_appendMoveEdge	(	SCIP *	scip,
		int	edge_target,
		int	edge_source,
		SCIP_Bool	revertIfConflict,
		GRAPH *	g,
		SCIP_Bool *	conflict
	)

appends pseudo ancestors of edge_source to edge_target, ancestors for edge_source are deleted

Parameters

scip	SCIP data structure
edge_target	target edge
edge_source	source edge
revertIfConflict	break on conflict
g	the graph
conflict	conflict?

Definition at line 1489 of file graph_history.c.

References graph_edge_delPseudoAncestors(), graph_pseudoAncestors_appendCopyEdge(), SCIP_CALL, and SCIP_OKAY.

Referenced by pseudoAncestorsMerge().

◆ graph_pseudoAncestors_appendMoveNode()

SCIP_RETCODE graph_pseudoAncestors_appendMoveNode	(	SCIP *	scip,
		int	node_target,
		int	node_source,
		SCIP_Bool	revertIfConflict,
		GRAPH *	g,
		SCIP_Bool *	conflict
	)

appends pseudo ancestors of node source to node target, ancestors for source are deleted

Parameters

scip	SCIP data structure
node_target	target node
node_source	source node
revertIfConflict	break on conflict
g	the graph
conflict	conflict?

Definition at line 1506 of file graph_history.c.

References graph_knot_delPseudoAncestors(), graph_pseudoAncestors_appendCopyNode(), SCIP_CALL, and SCIP_OKAY.

Referenced by pseudoAncestorsMergePc().

◆ graph_pseudoAncestors_addToEdge()

SCIP_RETCODE graph_pseudoAncestors_addToEdge	(	SCIP *	scip,
		int	edge_target,
		int	ancestor,
		GRAPH *	g
	)

adds pseudo ancestor to ancestor list of given edge

Parameters

scip	SCIP data structure
edge_target	edge for which to add pseudo ancestor
ancestor	(index of) pseudo ancestor
g	the graph

Definition at line 1523 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, blockedAncestors_addAncestor(), graph_pseudoAncestorsGetHashArraySize(), pseudo_ancestors::halfnedges, pseudo_ancestors::nAllPseudoancestors, GRAPH::pseudoancestors, SCIP_CALL, and SCIP_OKAY.

Referenced by delPseudoDeleteVertex(), delPseudoPathCreatePseudoAncestorTuple(), pseudoAncestorsCreation(), pseudoAncestorsHash(), pseudoAncestorsMerge(), and testEdgeDeletion2_deprecated().

◆ graph_pseudoAncestors_addToNode()

SCIP_RETCODE graph_pseudoAncestors_addToNode	(	SCIP *	scip,
		int	node_target,
		int	ancestor,
		GRAPH *	g
	)

adds pseudo ancestor to ancestor list of given node

Parameters

scip	SCIP data structure
node_target	node for which to add pseudo ancestor
ancestor	(index of) pseudo ancestor
g	the graph

Definition at line 1545 of file graph_history.c.

References pseudo_ancestors::ans_nodes, blockedAncestors_addAncestor(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), graph_pseudoAncestorsGetHashArraySize(), pseudo_ancestors::nAllPseudoancestors, pseudo_ancestors::nnodes, GRAPH::pseudoancestors, SCIP_CALL, and SCIP_OKAY.

Referenced by pseudoAncestorsHashPc(), and pseudoAncestorsMergePc().

◆ graph_free_pseudoAncestorsBlock()

SCIP_RETCODE graph_free_pseudoAncestorsBlock	(	SCIP *	,
		int	,
		GRAPH *
	)

◆ graph_pseudoAncestorsGetHashArraySize()

int graph_pseudoAncestorsGetHashArraySize ( const PSEUDOANS * pseudoancestors )

returns minimum required number for hash array

Parameters

pseudoancestors pseudo-ancestors

Definition at line 1321 of file graph_history.c.

References getNextPow2(), and pseudo_ancestors::nAllPseudoancestors.

◆ graph_pseudoAncestors_hashNode()

void graph_pseudoAncestors_hashNode	(	const PSEUDOANS *	pseudoancestors,
		int	node,
		int *	hasharr
	)

hash ancestors of given node

Parameters

pseudoancestors	pseudo-ancestors
node	node for which to hash
hasharr	hash array

Definition at line 840 of file graph_history.c.

References pseudo_ancestors::ans_nodes, blockedAncestors_hash(), and nnodes.

Referenced by pseudoAncestorsHashPc().

◆ graph_pseudoAncestors_hashEdge()

void graph_pseudoAncestors_hashEdge	(	const PSEUDOANS *	pseudoancestors,
		int	edge,
		int *	hasharr
	)

hash ancestors of given edge

Parameters

pseudoancestors	pseudo-ancestors
edge	edge for which to hash
hasharr	hash array

Definition at line 824 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, and blockedAncestors_hash().

Referenced by delPseudoCheckReplacement(), delPseudoEdgeGetReplaceEdges(), delPseudoGetReplaceEdges(), generalStarSetUp(), and pseudoAncestorsHash().

◆ graph_pseudoAncestors_unhashNode()

void graph_pseudoAncestors_unhashNode	(	const PSEUDOANS *	pseudoancestors,
		int	node,
		int *	hasharr
	)

hash ancestors of given node

Parameters

pseudoancestors	pseudo-ancestors
node	node for which to unhash
hasharr	hash array

Definition at line 870 of file graph_history.c.

References pseudo_ancestors::ans_nodes, blockedAncestors_unhashPartial(), and nnodes.

Referenced by pseudoAncestorsHashPc().

◆ graph_pseudoAncestors_unhashEdge()

void graph_pseudoAncestors_unhashEdge	(	const PSEUDOANS *	pseudoancestors,
		int	edge,
		int *	hasharr
	)

unhash ancestors of given edge

Parameters

pseudoancestors	pseudo-ancestors
edge	edge for which to unhash
hasharr	hash array

Definition at line 854 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, and blockedAncestors_unhashPartial().

Referenced by delPseudoCheckReplacement(), delPseudoEdgeGetReplaceEdges(), delPseudoGetReplaceEdges(), extreduce_extCompClean(), extTreeStackTopAdd(), extTreeStackTopRemove(), extUnhashInitialComponent(), generalStarSetUp(), graph_pseudoAncestors_edgesInConflict(), and pseudoAncestorsHash().

◆ graph_pseudoAncestors_hashNodeDirty()

void graph_pseudoAncestors_hashNodeDirty	(	const PSEUDOANS *	pseudoancestors,
		int	node,
		SCIP_Bool	revertIfConflict,
		SCIP_Bool *	conflict,
		int *	hasharr
	)

hash ancestors of given node with possible conflicts

Parameters

pseudoancestors	pseudo-ancestors
node	node for which to hash
revertIfConflict	revert on conflict?
conflict	conflict?
hasharr	hash array

Definition at line 902 of file graph_history.c.

References pseudo_ancestors::ans_nodes, blockedAncestors_hashDirty(), and nnodes.

Referenced by pseudoAncestorsHashPc().

◆ graph_pseudoAncestors_hashEdgeDirty()

void graph_pseudoAncestors_hashEdgeDirty	(	const PSEUDOANS *	pseudoancestors,
		int	edge,
		SCIP_Bool	revertIfConflict,
		SCIP_Bool *	conflict,
		int *	hasharr
	)

hash ancestors of given edge with possible conflicts

Parameters

pseudoancestors	pseudo-ancestors
edge	edge for which to hash
revertIfConflict	revert on conflict?
conflict	conflict?
hasharr	hash array

Definition at line 884 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, and blockedAncestors_hashDirty().

Referenced by extTreeStackTopAdd(), generalStarSetUp(), graph_pseudoAncestors_edgesInConflict(), and pseudoAncestorsHash().

◆ graph_pseudoAncestors_unhashNodeDirty()

void graph_pseudoAncestors_unhashNodeDirty	(	const PSEUDOANS *	pseudoancestors,
		int	node,
		int *	hasharr
	)

hash ancestors of given node with possible conflicts

Parameters

pseudoancestors	pseudo-ancestors
node	node for which to unhash
hasharr	hash array

Definition at line 934 of file graph_history.c.

References pseudo_ancestors::ans_nodes, blockedAncestors_unhashDirty(), and nnodes.

◆ graph_pseudoAncestors_unhashEdgeDirty()

void graph_pseudoAncestors_unhashEdgeDirty	(	const PSEUDOANS *	pseudoancestors,
		int	edge,
		int *	hasharr
	)

unhash ancestors of given edge with possible conflicts

Parameters

pseudoancestors	pseudo-ancestors
edge	edge for which to unhash
hasharr	hash array

Definition at line 918 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, and blockedAncestors_unhashDirty().

◆ graph_pseudoAncestors_edgeIsHashed()

SCIP_Bool graph_pseudoAncestors_edgeIsHashed	(	const PSEUDOANS *	pseudoancestors,
		int	edge,
		const int *	hasharr
	)

any ancestors of given edge already hashed?

Parameters

pseudoancestors	pseudo-ancestors
edge	edge for which to check
hasharr	hash array

Definition at line 948 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, and blockedAncestors_hashIsHitBlock().

Referenced by delPseudoCheckReplacement(), delPseudoEdgeGetReplaceEdges(), delPseudoGetReplaceEdges(), extreduce_stackTopIsHashed(), extreduce_treeIsHashed(), and extTreeRuleOutEdgeSimple().

◆ graph_pseudoAncestors_nodeIsHashed()

SCIP_Bool graph_pseudoAncestors_nodeIsHashed	(	const PSEUDOANS *	pseudoancestors,
		int	node,
		const int *	hasharr
	)

any ancestors of given node already hashed?

Parameters

pseudoancestors	pseudo-ancestors
node	node for which to check
hasharr	hash array

Definition at line 962 of file graph_history.c.

References pseudo_ancestors::ans_nodes, and blockedAncestors_hashIsHitBlock().

◆ graph_pseudoAncestors_edgesInConflict()

SCIP_Bool graph_pseudoAncestors_edgesInConflict	(	SCIP *	scip,
		const GRAPH *	g,
		const int *	edges,
		int	nedges
	)

any ancestors of given edges in conflict?

Parameters

scip	SCIP data structure
g	the graph
edges	edges to check
nedges	number of edges to check

Definition at line 1010 of file graph_history.c.

References FALSE, graph_pseudoAncestors_hashEdgeDirty(), graph_pseudoAncestors_unhashEdge(), graph_pseudoAncestorsGetHashArraySize(), GRAPH::knots, GRAPH::pseudoancestors, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocCleanBufferArray, SCIPfreeCleanBufferArray, and TRUE.

Referenced by bdkStarIsReplacableDeg3(), bdkStarIsReplacableDegGe4(), isPseudoDeletable(), and isPseudoDeletableDeg3().

◆ graph_valid_pseudoAncestors()

SCIP_Bool graph_valid_pseudoAncestors	(	SCIP *	scip,
		const GRAPH *	g
	)

valid pseudo-ancestors (no conflicts)?

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1569 of file graph_history.c.

References pseudo_ancestors::ans_halfedges, pseudo_ancestors::ans_nodes, blockedAncestors_isValid(), FALSE, graph_pc_isPcMw(), graph_pseudoAncestorsGetHashArraySize(), GRAPH::pseudoancestors, SCIP_Bool, SCIP_OKAY, and TRUE.

Referenced by graph_knot_replaceDeg2().

◆ graph_init_fixed()

SCIP_RETCODE graph_init_fixed	(	SCIP *	scip,
		GRAPH *	g
	)

initializes fixed

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1618 of file graph_history.c.

References FALSE, GRAPH::fixedcomponents, fixed_graph_components::fixedges, fixed_graph_components::fixpseudonodes, fixed_graph_components::movedFrom, fixed_graph_components::nfixnodes, NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemory.

Referenced by graph_copyFixed(), and graph_fixed_add().

◆ graph_free_fixed()

void graph_free_fixed	(	SCIP *	scip,
		GRAPH *	g
	)

frees fixed

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1642 of file graph_history.c.

References GRAPH::fixedcomponents, fixed_graph_components::fixedges, fixed_graph_components::fixpseudonodes, fixed_graph_components::nfixnodes, NULL, Int_List_Node::parent, SCIPfreeBlockMemory, SCIPfreeBlockMemoryArray, and SCIPfreeMemory.

Referenced by graph_freeHistoryDeep(), and reinsertSubgraphTransferFixedHistory().

◆ graph_free_fixedEdgesOnly()

void graph_free_fixedEdgesOnly	(	SCIP *	scip,
		GRAPH *	g
	)

frees fixed edges

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1671 of file graph_history.c.

References GRAPH::fixedcomponents, fixed_graph_components::fixedges, fixed_graph_components::nfixnodes, NULL, Int_List_Node::parent, and SCIPfreeBlockMemory.

Referenced by graph_subgraphCompleteNewHistory().

◆ graph_fixed_add()

SCIP_RETCODE graph_fixed_add	(	SCIP *	scip,
		IDX *	edges,
		const int *	pseudonodes,
		int	npseudonodes,
		GRAPH *	g
	)

adds new fixed components

Parameters

scip	SCIP data structure
edges	edge to add or NULL
pseudonodes	nodes to add
npseudonodes	number of nodes to add
g	the graph

Definition at line 1698 of file graph_history.c.

References FALSE, GRAPH::fixedcomponents, fixed_graph_components::fixedges, fixedPseudoAncestorsAreValid(), fixed_graph_components::fixpseudonodes, graph_init_fixed(), fixed_graph_components::movedFrom, fixed_graph_components::nfixnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPintListNodeAppendCopy(), SCIPreallocBlockMemoryArray, and GRAPH::withInexactReductions.

Referenced by graph_fixed_addEdge(), and graph_fixed_addNodePc().

◆ graph_fixed_addEdge()

SCIP_RETCODE graph_fixed_addEdge	(	SCIP *	scip,
		int	edge,
		GRAPH *	g
	)

adds ancestors from given edges

Parameters

scip	SCIP data structure
edge	edge
g	the graph

Definition at line 1760 of file graph_history.c.

References GRAPH::ancestors, graph_edge_getAncestors(), graph_edge_getPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_fixed_add(), SCIP_CALL, and SCIP_OKAY.

Referenced by contractEdgeWithFixedEnd(), graph_knot_contractFixed(), reduce_contract0Edges(), and reduce_simple().

◆ graph_fixed_addNodePc()

SCIP_RETCODE graph_fixed_addNodePc	(	SCIP *	scip,
		int	node,
		GRAPH *	g
	)

adds ancestors from given edges

Parameters

scip	SCIP data structure
node	node
g	the graph

Definition at line 1778 of file graph_history.c.

References GRAPH::ancestors, graph_fixed_add(), graph_knot_getPseudoAncestors(), graph_knot_nPseudoAncestors(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::pcancestors, SCIP_CALL, and SCIP_OKAY.

Referenced by graph_fixed_moveNodePc(), and packPcMwVanished().

◆ graph_fixed_moveNodePc()

SCIP_RETCODE graph_fixed_moveNodePc	(	SCIP *	scip,
		int	node,
		GRAPH *	g
	)

moves ancestors from given edges

Parameters

scip	SCIP data structure
node	node
g	the graph

Definition at line 1798 of file graph_history.c.

References graph_fixed_addNodePc(), graph_knot_delPseudoAncestors(), graph_pc_isPcMw(), GRAPH::pcancestors, SCIP_CALL, SCIP_OKAY, and SCIPintListNodeFree().

Referenced by contractEdgeWithFixedEnd().

◆ graph_copyFixed()

SCIP_RETCODE graph_copyFixed	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Bool	moveFixedEdges,
		GRAPH *	g_copy
	)

copies and potentially moves fixed components

Parameters

scip	SCIP data structure
g	the original graph
moveFixedEdges	move fixed edges? If false, nothing is done!
g_copy	the copied graph

Definition at line 1895 of file graph_history.c.

References BMScopyMemoryArray, GRAPH::fixedcomponents, fixed_graph_components::fixedges, fixed_graph_components::fixpseudonodes, graph_init_fixed(), fixed_graph_components::movedFrom, fixed_graph_components::nfixnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, and TRUE.

Referenced by extractSubgraphInitHistory().

◆ graph_getFixedges()

IDX* graph_getFixedges ( const GRAPH * g )

gets fixed edges

Parameters

g the graph

Definition at line 1944 of file graph_history.c.

References GRAPH::fixedcomponents, fixed_graph_components::fixedges, and NULL.

Referenced by computeHistory(), computeHistoryPcMw(), reduce_exec(), retransformReducedProbSolution(), SCIPStpHeurRecExclude(), solstp_getOrg(), updateEdgestateFromRed(), and updateEdgestateFromRedPcmw().

◆ graph_getFixpseudonodes()

const int* graph_getFixpseudonodes	(	SCIP *	scip,
		const GRAPH *	g
	)

gets fixed pseudo eliminated nodes

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1957 of file graph_history.c.

References GRAPH::fixedcomponents, fixed_graph_components::fixpseudonodes, and NULL.

Referenced by fixedPseudoAncestorsAreValid(), and reduce_fixedConflicts().

◆ graph_getNfixpseudonodes()

int graph_getNfixpseudonodes ( const GRAPH * g )

gets number of fixed pseudo eliminated nodes

Parameters

g the graph

Definition at line 1971 of file graph_history.c.

References GRAPH::fixedcomponents, and fixed_graph_components::nfixnodes.

Referenced by fixedPseudoAncestorsAreValid(), graph_printEdgeConflicts(), reduce_fixedConflicts(), and reinsertSubgraphTransferFixedHistory().

◆ graph_termsReachable()

SCIP_RETCODE graph_termsReachable	(	SCIP *	scip,
		const GRAPH *	g,
		SCIP_Bool *	reachable
	)

checks whether all terminals are reachable from root

Parameters

scip	scip struct
g	the new graph
reachable	are they reachable?

Definition at line 370 of file graph_util.c.

References FALSE, graph_trail_arr(), Is_term, GRAPH::knots, nnodes, NULL, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, GRAPH::term, and TRUE.

◆ graph_findCentralTerminal()

SCIP_RETCODE graph_findCentralTerminal	(	SCIP *	,
		const GRAPH *	,
		int	,
		int *
	)

Definition at line 410 of file graph_util.c.

References shortest_path::dist, GRAPH::edges, FARAWAY, FSP_MODE, GRAPH::grad, graph_get_nNodes(), graph_knotIsNWLeaf(), graph_path_exec(), Is_term, GRAPH::layers, GRAPH::mark, nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIP_VERBLEVEL_HIGH, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisEQ(), SCIPisLT(), SCIPverbMessage(), GRAPH::source, STP_CENTER_ALL, STP_CENTER_DEG, STP_CENTER_MIN, STP_CENTER_OK, STP_CENTER_SUM, STP_NWPTSPG, GRAPH::stp_type, GRAPH::term, and TRUE.

Referenced by SCIPprobdataCreateFromGraph().

◆ graph_trail_arr()

SCIP_RETCODE graph_trail_arr	(	SCIP *	scip,
		const GRAPH *	g,
		int	start,
		SCIP_Bool *	nodevisited
	)

traverses the graph from vertex 'start' and marks all reached nodes

Parameters

scip	SCIP
g	the new graph
start	node to start from
nodevisited	marks which node has been visited

Definition at line 336 of file graph_util.c.

References FALSE, SCIP_OKAY, and trail().

Referenced by graph_termsReachable(), graph_valid(), graph_validInput(), reduce_unconnected(), and reduce_unconnectedInfeas().

◆ graph_trail_costAware()

SCIP_RETCODE graph_trail_costAware	(	SCIP *	scip,
		const GRAPH *	g,
		int	start,
		SCIP_Bool *	nodevisited
	)

traverses the graph and marks all reached nodes, does not take edge of cost >= FARAWAY

Parameters

scip	SCIP
g	the new graph
start	node to start from
nodevisited	marks which node has been visited

Definition at line 353 of file graph_util.c.

References SCIP_OKAY, trail(), and TRUE.

Referenced by graphisValidPcMw(), pcmwUpdate(), and reduce_unconnectedForDirected().

◆ graph_heap_create()

SCIP_RETCODE graph_heap_create	(	SCIP *	scip,
		int	capacity,
		int *	position,
		DENTRY *	entries,
		DHEAP **	heap
	)

creates new heap. If entries array is provided, it must be of size capacity + 2

Parameters

scip	SCIP
capacity	heap capacity
position	heap position array or NULL
entries	entries array or NULL
heap	the heap

Definition at line 992 of file graph_util.c.

References DHEAP_MAX_KEY, DHEAP_MIN_KEY, graph_heap_clean(), dijkstra_heap_entry::key, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, and TRUE.

Referenced by checkSdWalk(), cmst_init(), distCloseNodesCompute(), distGetRestricted(), dpsolverInitData(), extreduce_distDataInit(), graph_dijkLimited_init(), graph_vnoiCompute(), graph_vnoiComputeImplied(), mst_init(), reduce_redLoopPc(), SCIPStpHeurLocalExtendPcMwOut(), stptest_dheap(), and tmBaseInit().

◆ graph_heap_free()

void graph_heap_free	(	SCIP *	scip,
		SCIP_Bool	freePositions,
		SCIP_Bool	freeEntries,
		DHEAP **	heap
	)

frees the heap

Parameters

scip	SCIP
freePositions	free positions array?
freeEntries	free entries array?
heap	the heap

Definition at line 1034 of file graph_util.c.

References SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by checkSdWalk(), cmst_free(), distCloseNodesCompute(), distGetRestricted(), dpsolverFreeData(), extreduce_distDataFree(), graph_dijkLimited_free(), graph_vnoiCompute(), graph_vnoiComputeImplied(), mst_free(), reduce_redLoopPc(), SCIPStpHeurLocalExtendPcMwOut(), stptest_dheap(), and tmBaseFree().

◆ graph_heap_deleteMin()

void graph_heap_deleteMin	(	int *	node,
		SCIP_Real *	key,
		DHEAP *	heap
	)

deletes heap minimum

Parameters

node	pointer to value of minimum
key	pointer to key of minimum
heap	the heap

Definition at line 1053 of file graph_util.c.

References dijkstra_heap::entries, graph_heap_deleteMinGetNode(), and dijkstra_heap_entry::key.

Referenced by propagateUBs(), subtreesExtend(), and subtreesRemoveNonValids().

◆ graph_heap_deleteMinGetNode()

void graph_heap_deleteMinGetNode	(	int *	node,
		DHEAP *	heap
	)

deletes heap minimum

Parameters

node	pointer to node stored in minimum (set by method)
heap	the heap

Definition at line 1065 of file graph_util.c.

References graph_heap_deleteMinReturnNode().

Referenced by graph_heap_deleteMin(), and stptest_dheap().

◆ graph_heap_deleteMinReturnNode()

int graph_heap_deleteMinReturnNode ( DHEAP * heap )

deletes heap minimum and returns corresponding node

Parameters

heap the heap

Definition at line 1076 of file graph_util.c.

References CONNECT, DHEAP_MAX_KEY, dijkstra_heap::entries, dijkstra_heap::position, SCIP_Real, and dijkstra_heap::size.

Referenced by closeNodesRunCompute(), cmst_computeMst(), computeOnMarked_exec(), computeSteinerTree_exec(), computeSteinerTree_execBiased(), computeSteinerTree_execDirected(), computeSteinerTree_execPcMw(), computeSteinerTree_execPcMwFull(), computeSteinerTree_execRpcMw(), distCloseNodesCompute(), distGetRestricted(), graph_heap_deleteMinGetNode(), graph_path_st_pcmw_extendOut(), graph_pathInLimitedExec(), graph_sdCloseNodesBiased(), graph_sdStar(), graph_sdStarBiased(), graph_sdWalks_csr(), graph_sdWalksTriangle(), sdCliqueStarComputeSds(), vnoiCompute(), and vnoiComputeImplied().

◆ graph_heap_clean()

void graph_heap_clean	(	SCIP_Bool	cleanposition,
		DHEAP *	heap
	)

clean the heap

Parameters

cleanposition	clean position array?
heap	the heap

Definition at line 938 of file graph_util.c.

References dijkstra_heap::capacity, graph_heap_isClean(), dijkstra_heap::position, SCIP_Bool, dijkstra_heap::size, and UNKNOWN.

Referenced by computeOnMarked_init(), computeSteinerTree_init(), graph_dijkLimited_clean(), graph_dijkLimited_reset(), graph_heap_create(), graph_path_st_pcmw_extendOut(), propagateUBs(), reduce_sdStar(), reduce_sdStarPc(), reduce_sdStarPc2(), reduce_sdWalk_csr(), reduce_sdWalkTriangle(), sdStarReset(), stptest_dheap(), subtreesExtend(), and subtreesRemoveNonValids().

◆ graph_heap_correct()

void graph_heap_correct	(	int	node,
		SCIP_Real	newkey,
		DHEAP *	heap
	)

corrects node position in heap according to new key (or newly inserts the node)

Parameters

node	the node
newkey	the new key (needs to be smaller than current one)
heap	the heap

Definition at line 1166 of file graph_util.c.

References dijkstra_heap::capacity, CONNECT, DHEAP_MAX_KEY, DHEAP_MIN_KEY, dijkstra_heap::entries, GE, dijkstra_heap::position, SCIP_Real, dijkstra_heap::size, and UNKNOWN.

◆ graph_heap_isClean()

SCIP_Bool graph_heap_isClean ( const DHEAP * heap )

is the heap clean?

Parameters

heap the heap

Definition at line 962 of file graph_util.c.

References dijkstra_heap::capacity, FALSE, dijkstra_heap::position, SCIPdebugMessage, dijkstra_heap::size, TRUE, and UNKNOWN.

Referenced by cmst_computeMst(), graph_heap_clean(), sdCliqueStarInit(), sdStarInit(), and vnoiInit().

◆ graph_init_csr()

SCIP_RETCODE graph_init_csr	(	SCIP *	scip,
		GRAPH *	g
	)

initializes CSR storage of graph

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1581 of file graph_util.c.

References GRAPH::cost, GRAPH::csr_storage, GRAPH::edges, graph_csr_alloc(), graph_csr_build(), graph_valid_csr(), GRAPH::knots, NULL, SCIP_CALL, SCIP_OKAY, and TRUE.

Referenced by dpborder_solve(), and SCIPStpHeurLocalExtendPcMwOut().

◆ graph_init_csrWithEdgeId()

SCIP_RETCODE graph_init_csrWithEdgeId	(	SCIP *	scip,
		GRAPH *	g
	)

initializes CSR storage of graph

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1603 of file graph_util.c.

References GRAPH::cost, GRAPH::csr_storage, GRAPH::edges, graph_csr_allocWithEdgeId(), graph_csr_build(), graph_valid_csr(), GRAPH::knots, NULL, SCIP_CALL, SCIP_OKAY, and TRUE.

Referenced by dpborder_probePotential(), and dpterms_solve().

◆ graph_free_csr()

void graph_free_csr	(	SCIP *	scip,
		GRAPH *	g
	)

frees dynamic CSR storage of graph

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1623 of file graph_util.c.

References GRAPH::csr_storage, graph_csr_free(), and NULL.

Referenced by dpborder_probePotential(), dpborder_solve(), dpterms_solve(), graph_free(), and SCIPStpHeurLocalExtendPcMwOut().

◆ graph_csr_alloc()

SCIP_RETCODE graph_csr_alloc	(	SCIP *	scip,
		int	nnodes,
		int	nedges,
		CSR **	csr
	)

allocates empty (and invalid!) CSR storage

Parameters

scip	SCIP data structure
nnodes	nodes
nedges	edges
csr	CSR

Definition at line 1231 of file graph_util.c.

References csr_storage::cost, csr_storage::edge_id, csr_storage::head, csr_storage::nedges_max, nnodes, csr_storage::nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, and csr_storage::start.

Referenced by csrdepoTest2(), dcmstTest1(), dcmstTest2(), dcmstTest2b(), dcmstTest3(), extreduce_contractionInit(), graph_csr_allocWithEdgeId(), and graph_init_csr().

◆ graph_csr_allocWithEdgeId()

SCIP_RETCODE graph_csr_allocWithEdgeId	(	SCIP *	scip,
		int	nnodes,
		int	nedges,
		CSR **	csr
	)

allocates empty (and invalid!) CSR storage

Parameters

scip	SCIP data structure
nnodes	nodes
nedges	edges
csr	CSR

Definition at line 1270 of file graph_util.c.

References csr_storage::edge_id, graph_csr_alloc(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by graph_init_csrWithEdgeId(), mst_init(), and tmBaseInit().

◆ graph_csr_copy()

void graph_csr_copy	(	const CSR *	csr_in,
		CSR *	csr_out
	)

copies CSR storage

Parameters

csr_in	CSR source
csr_out	CSR target

Definition at line 1483 of file graph_util.c.

References BMScopyMemoryArray, csr_storage::cost, csr_storage::edge_id, FALSE, graph_csr_isValid(), csr_storage::head, csr_storage::nedges_max, csr_storage::nnodes, NULL, and csr_storage::start.

Referenced by baseMstBuildNew(), dcmstTest1(), dcmstTest2(), dcmstTest2b(), and dcmstTest3().

◆ graph_csr_build()

void graph_csr_build	(	const GRAPH *	g,
		const SCIP_Real *	edgecosts,
		CSR *	csr
	)

Builds CSR storage from graph and cost array. NOTE: for PC/MW no dummy nodes are considered!

Parameters

g	the graph
edgecosts	edge costs (w.r.t graph 'g')
csr	CSR

Definition at line 1351 of file graph_util.c.

References csr_storage::cost, csr_storage::edge_id, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_csr_isValid(), graph_get_nEdges(), graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), graph_typeIsDirected(), csr_storage::head, GRAPH::head, csr_storage::nedges_max, nnodes, csr_storage::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, csr_storage::start, STP_DCSTP, GRAPH::stp_type, and TRUE.

Referenced by graph_init_csr(), graph_init_csrWithEdgeId(), mst_init(), and tmBaseInit().

◆ graph_csr_buildCosts()

void graph_csr_buildCosts	(	const GRAPH *	,
		const CSR *	,
		const SCIP_Real *	,
		SCIP_Real *	RESTRICT
	)

Referenced by tmBaseInit().

◆ graph_csr_chgCosts()

void graph_csr_chgCosts	(	const GRAPH *	g,
		const SCIP_Real *	edgecosts,
		CSR *	csr
	)

Changes edge costs. NOTE: for PC/MW no dummy nodes are considered!

Parameters

g	the graph
edgecosts	edge costs (w.r.t graph 'g')
csr	CSR

Definition at line 1298 of file graph_util.c.

References csr_storage::cost, csr_storage::edge_id, GRAPH::edges, FARAWAY, flipedge, GRAPH::grad, graph_csr_isValid(), graph_get_nEdges(), graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), csr_storage::head, GRAPH::head, csr_storage::nedges_max, nnodes, csr_storage::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_Real, csr_storage::start, and TRUE.

Referenced by pcmwSetEdgeCosts().

◆ graph_csr_print()

void graph_csr_print ( const CSR * csr )

prints CSR storage

Parameters

csr	CSR to print

Definition at line 1514 of file graph_util.c.

References csr_storage::cost, FALSE, graph_csr_isValid(), csr_storage::head, csr_storage::nedges_max, csr_storage::nnodes, SCIP_Real, and csr_storage::start.

Referenced by baseMstFinalizeNew(), and compMstFinalizeNew().

◆ graph_csr_getNedges()

int graph_csr_getNedges ( const CSR * csr )

gets currently used CSR edges

Parameters

csr	CSR to print

Definition at line 1536 of file graph_util.c.

References csr_storage::nedges_max, nnodes, csr_storage::nnodes, and csr_storage::start.

Referenced by pruneSteinerTreePc_csr(), pruneSteinerTreeStp_csr(), solstp_convertCsrToGraph(), solstp_getObjCsr(), solstp_pcGetObjCsr(), and strongPruneSteinerTreePc_csr().

◆ graph_csr_free()

void graph_csr_free	(	SCIP *	scip,
		CSR **	csr
	)

frees dynamic CSR storage

Parameters

scip	SCIP data structure
csr	CSR

Definition at line 1554 of file graph_util.c.

References csr_storage::cost, csr_storage::edge_id, csr_storage::head, csr_storage::nnodes, SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, and csr_storage::start.

Referenced by csrdepoTest2(), dcmstTest1(), dcmstTest2(), dcmstTest2b(), dcmstTest3(), extreduce_contractionFree(), graph_free_csr(), mst_free(), and tmBaseFree().

◆ graph_csr_costsAreInSync()

SCIP_Bool graph_csr_costsAreInSync	(	const GRAPH *	g,
		const CSR *	csr,
		const SCIP_Real *	edgecosts_g
	)

are CSR and graph costs corresponding?

Parameters

g	the graph
csr	CSR
edgecosts_g	edge costs w.r.t graph 'g'

Definition at line 1448 of file graph_util.c.

References csr_storage::cost, csr_storage::edge_id, EQ, FALSE, graph_get_nEdges(), graph_get_nNodes(), nnodes, csr_storage::nnodes, SCIP_Real, csr_storage::start, and TRUE.

Referenced by runTmPcMW_mode(), and solstp_pruneFromTmHeur_csr().

◆ graph_csr_isValid()

SCIP_Bool graph_csr_isValid	(	const CSR *	csr,
		SCIP_Bool	verbose
	)

is CSR storage valid?

Parameters

csr	the CSR graph
verbose	be verbose?

Definition at line 1637 of file graph_util.c.

References FALSE, csr_storage::head, csr_storage::nedges_max, nnodes, csr_storage::nnodes, csr_storage::start, and TRUE.

Referenced by graph_csr_build(), graph_csr_chgCosts(), graph_csr_copy(), graph_csr_print(), graph_valid_csr(), and reduce_dcmstMstIsValid().

◆ graph_valid_csr()

SCIP_Bool graph_valid_csr	(	const GRAPH *	g,
		SCIP_Bool	verbose
	)

is CSR storage of graph valid?

Parameters

g	the graph
verbose	be verbose?

Definition at line 1694 of file graph_util.c.

References csr_storage::cost, GRAPH::csr_storage, GRAPH::edges, FALSE, graph_csr_isValid(), csr_storage::head, GRAPH::knots, csr_storage::nedges_max, and csr_storage::nnodes.

Referenced by graph_init_csr(), and graph_init_csrWithEdgeId().

◆ graph_buildOrgNodesToReducedMap()

void graph_buildOrgNodesToReducedMap	(	const GRAPH *	g,
		int *	map
	)

builds mapping from original vertices to non-zero degree ones

Parameters

g	the graph
map	map

Definition at line 560 of file graph_util.c.

References GRAPH::grad, graph_get_nNodes(), nnodes, and UNKNOWN.

◆ graph_csrdepo_init()

SCIP_RETCODE graph_csrdepo_init	(	SCIP *	scip,
		int	ncsrs_max,
		int	datasize_max,
		CSRDEPO **	depository
	)

initializes CSR depository

Parameters

scip	SCIP data structure
ncsrs_max	maximum number of CSRs
datasize_max	the maximum capacity
depository	the depository

Definition at line 590 of file graph_util.c.

Referenced by csrdepoTest1(), csrdepoTest2(), and extreduce_extPermaInit().

◆ graph_csrdepo_free()

void graph_csrdepo_free	(	SCIP *	scip,
		CSRDEPO **	depository
	)

frees CSR depository

Parameters

scip	SCIP data structure
depository	the depository

Definition at line 637 of file graph_util.c.

Referenced by csrdepoTest1(), csrdepoTest2(), and extreduce_extPermaFree().

◆ graph_csrdepo_print()

void graph_csrdepo_print ( const CSRDEPO * depository )

Prints depository.

Parameters

depository the depository

Definition at line 908 of file graph_util.c.

References compressed_sparse_storages_depository::csr_weight, graph_csrdepo_getCSR(), graph_csrdepo_getNcsrs(), csr_storage::nedges_max, and csr_storage::nnodes.

Referenced by baseMstFinalizeNew(), and compMstFinalizeNew().

◆ graph_csrdepo_getCSR()

void graph_csrdepo_getCSR	(	const CSRDEPO *	depository,
		int	index,
		CSR *	csr
	)

gets CSR from depository

Parameters

depository	the depository
index	the index of the CSR to get
csr	pointer to CSR struct to fill

Definition at line 667 of file graph_util.c.

References compressed_sparse_storages_depository::csr_isEmpty, csrdepoFillCSR(), compressed_sparse_storages_depository::ncsrs_curr, and csr_storage::start.

Referenced by csrdepoGetTopWeight(), csrdepoTest2(), graph_csrdepo_getTopCSR(), graph_csrdepo_print(), and ruledOut().

◆ graph_csrdepo_getTopCSR()

void graph_csrdepo_getTopCSR	(	const CSRDEPO *	depository,
		CSR *	csr
	)

gets top (last added) CSR from depository

Parameters

depository	the depository
csr	pointer to CSR struct to fill

Definition at line 684 of file graph_util.c.

References compressed_sparse_storages_depository::csr_weight, csrdepoCsrIsSet(), csrdepoCsrWeight(), csrdepoGetTopIndex(), EQ, FALSE, graph_csrdepo_getCSR(), graph_csrdepo_hasEmptyTop(), compressed_sparse_storages_depository::ncsrs_curr, and SCIP_Real.

Referenced by baseMstInitMsts(), compMstInitMsts(), extreduce_mstTopCompInSync(), extreduce_mstTopLevelBaseObjValid(), mstCompRuleOut(), and mstLevelLeafTryExtMst().

◆ graph_csrdepo_getNcsrs()

int graph_csrdepo_getNcsrs ( const CSRDEPO * depository )

gets number of CSRs in depository

Parameters

depository the depository

Definition at line 741 of file graph_util.c.

References compressed_sparse_storages_depository::ncsrs_curr.

Referenced by compMstInitMsts(), extreduce_mstCompRemove(), extreduce_mstInternalsInSync(), extreduce_mstLevelRemove(), graph_csrdepo_print(), mstLevelBuildBaseMstRoot(), and postCleanMSTs().

◆ graph_csrdepo_getDataSize()

int graph_csrdepo_getDataSize ( const CSRDEPO * depository )

gets current size of data (from all CSRs) in depository

Parameters

depository the depository

Definition at line 709 of file graph_util.c.

References compressed_sparse_storages_depository::csr_ptrsData, compressed_sparse_storages_depository::csr_ptrsStart, csrdepoGetNedges(), csrdepoGetNnodes(), csrdepoGetTopIndex(), compressed_sparse_storages_depository::datasize_max, MAX, and compressed_sparse_storages_depository::ncsrs_curr.

Referenced by graph_csrdepo_addEmptyTop().

◆ graph_csrdepo_clean()

void graph_csrdepo_clean ( CSRDEPO * depository )

cleans CSR depository

Parameters

depository the depository

Definition at line 781 of file graph_util.c.

References csrdepoCleanDebug(), graph_csrdepo_isEmpty(), graph_csrdepo_removeTop(), and compressed_sparse_storages_depository::ncsrs_curr.

Referenced by postCleanMSTs().

◆ graph_csrdepo_removeTop()

void graph_csrdepo_removeTop ( CSRDEPO * depository )

removes top of CSR depository

Parameters

depository the depository

Definition at line 753 of file graph_util.c.

References compressed_sparse_storages_depository::csr_nedges, compressed_sparse_storages_depository::csr_nnodes, compressed_sparse_storages_depository::csr_weight, csrdepoCsrUnsetDebug(), csrdepoFillCSR(), csrdepoGetTopIndex(), graph_csrdepo_hasEmptyTop(), graph_csrdepo_isEmpty(), and compressed_sparse_storages_depository::ncsrs_curr.

Referenced by compMstFinalizeNew(), csrdepoTest1(), csrdepoTest2(), extreduce_mstCompRemove(), extreduce_mstLevelRemove(), and graph_csrdepo_clean().

◆ graph_csrdepo_addEmptyTop()

void graph_csrdepo_addEmptyTop	(	CSRDEPO *	depository,
		int	nnodes,
		int	nedges
	)

adds empty top to CSR depository

Parameters

depository	the depository
nnodes	nodes of new top
nedges	number of (directed!) edges of new top

Definition at line 800 of file graph_util.c.

Referenced by add1NodeMst(), csrdepoTest1(), csrdepoTest2(), and graph_csrdepo_addEmptyTopTree().

◆ graph_csrdepo_addEmptyTopTree()

void graph_csrdepo_addEmptyTopTree	(	CSRDEPO *	depository,
		int	nnodes
	)

adds empty top for tree to CSR depository

Parameters

depository	the depository
nnodes	nodes of new top

Definition at line 836 of file graph_util.c.

References graph_csrdepo_addEmptyTop().

Referenced by baseMstInitMsts(), and compMstInitMsts().

◆ graph_csrdepo_isEmpty()

SCIP_Bool graph_csrdepo_isEmpty ( const CSRDEPO * depository )

is the CSR depository empty?

Parameters

depository the depository

Definition at line 851 of file graph_util.c.

References compressed_sparse_storages_depository::ncsrs_curr.

Referenced by csrdepoTest1(), csrdepoTest2(), extreduce_extPermaIsClean(), graph_csrdepo_addEmptyTop(), graph_csrdepo_clean(), graph_csrdepo_init(), graph_csrdepo_removeTop(), mstAddRootLevelMsts(), and mstLevelBuildBaseMstRoot().

◆ graph_csrdepo_hasEmptyTop()

SCIP_Bool graph_csrdepo_hasEmptyTop ( const CSRDEPO * depository )

is top of CSR depository empty?

Parameters

depository the depository

Definition at line 863 of file graph_util.c.

References compressed_sparse_storages_depository::csr_isEmpty, and csrdepoGetTopIndex().

Referenced by graph_csrdepo_addEmptyTop(), graph_csrdepo_getTopCSR(), and graph_csrdepo_removeTop().

◆ graph_csrdepo_getEmptyTop()

void graph_csrdepo_getEmptyTop	(	const CSRDEPO *	depository,
		CSR *	csr
	)

Gets empty top of current depository.

Parameters

depository	the depository
csr	pointer to csr struct to fill

Definition at line 874 of file graph_util.c.

References compressed_sparse_storages_depository::csr_isEmpty, csrdepoFillCSR(), csrdepoGetTopIndex(), and compressed_sparse_storages_depository::ncsrs_max.

Referenced by add1NodeMst(), baseMstInitMsts(), compMstInitMsts(), csrdepoTest1(), and csrdepoTest2().

◆ graph_csrdepo_emptyTopSetMarked()

void graph_csrdepo_emptyTopSetMarked ( CSRDEPO * depository )

Sets formerly empty top to marked.

Parameters

depository the depository

Definition at line 890 of file graph_util.c.

References compressed_sparse_storages_depository::csr_isEmpty, compressed_sparse_storages_depository::csr_weight, csrdepoGetTopIndex(), csrdepoGetTopWeight(), EQ, and FALSE.

Referenced by add1NodeMst(), baseMstFinalizeNew(), compMstFinalizeNew(), csrdepoTest1(), and csrdepoTest2().

◆ graph_init_dcsr()

SCIP_RETCODE graph_init_dcsr	(	SCIP *	scip,
		GRAPH *	g
	)

initializes dynamic CSR storage

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1721 of file graph_util.c.

Referenced by extCheckArc(), extCheckEdge(), extCheckNode(), extDeleteNodes(), extInit(), extreduce_init(), fixVarsRedbased(), reduce_pathreplace(), reduce_pathreplaceExt(), reduce_sdStar(), reduce_sdStarBiasedWithProfit(), reduce_sdStarPc(), reduce_sdStarPc2(), reduce_sdWalk_csr(), reduce_sdWalkTriangle(), reduce_termsepaDa(), sdneighborUpdateInit(), sepafullInitDistdata(), testDistCloseNodesAreValid(), testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), testDistDistancesAreValid(), testDistRootPathsAreValid(), and testNode3PseudoDeletedBySdBiasedSimple().

◆ graph_update_dcsr()

void graph_update_dcsr	(	SCIP *	scip,
		GRAPH *	g
	)

updates dynamic CSR storage

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1829 of file graph_util.c.

◆ graph_dcsr_deleteEdge()

void graph_dcsr_deleteEdge	(	DCSR *	dcsr,
		int	tail,
		int	e_csr
	)

deletes CSR indexed edge

Parameters

dcsr	DCSR container
tail	tail of edge
e_csr	CSR indexed edge

Definition at line 1840 of file graph_util.c.

References dynamic_csr_storage::cost, dynamic_csr_storage::cost2, dynamic_csr_storage::cost3, dynamic_csr_storage::edgeid, csr_range::end, FARAWAY, dynamic_csr_storage::head, dynamic_csr_storage::id2csredge, nnodes, dynamic_csr_storage::range, and SCIP_Real.

Referenced by graph_dcsr_deleteEdgeBi().

◆ graph_dcsr_deleteEdgeBi()

void graph_dcsr_deleteEdgeBi	(	SCIP *	scip,
		DCSR *	dcsr,
		int	e_csr
	)

deletes CSR indexed edge and anti-parallel one

Parameters

scip	SCIP data structure
dcsr	DCSR container
e_csr	CSR indexed edge

Definition at line 1894 of file graph_util.c.

References dynamic_csr_storage::cost, dynamic_csr_storage::edgeid, flipedge, graph_dcsr_deleteEdge(), dynamic_csr_storage::head, dynamic_csr_storage::id2csredge, SCIPdebugMessage, and SCIPisEQ().

Referenced by graph_edge_delFull(), reduce_sdStar(), reduce_sdStarPc(), reduce_sdStarPc2(), reduce_sdWalk_csr(), reduce_sdWalkTriangle(), replaceEdgeByPath(), and sdStarBiasedProcessNode().

◆ graph_free_dcsr()

void graph_free_dcsr	(	SCIP *	scip,
		GRAPH *	g
	)

frees dynamic CSR storage

Parameters

scip	SCIP data structure
g	the graph

Definition at line 1807 of file graph_util.c.

References dynamic_csr_storage::cost, GRAPH::dcsr_storage, dynamic_csr_storage::edgeid, dynamic_csr_storage::head, dynamic_csr_storage::id2csredge, dynamic_csr_storage::nnodes, NULL, dynamic_csr_storage::range, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by extCheckArc(), extCheckEdge(), extCheckNode(), extDeleteNodes(), extFree(), extreduce_exit(), fixVarsRedbased(), graph_free(), reduce_pathreplace(), reduce_pathreplaceExt(), reduce_sdStar(), reduce_sdStarBiasedWithProfit(), reduce_sdStarPc(), reduce_sdStarPc2(), reduce_sdWalk_csr(), reduce_sdWalkTriangle(), sdneighborUpdateFree(), sepafullInitDistdata(), testDistCloseNodesAreValid(), testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), testDistDistancesAreValid(), testDistRootPathsAreValid(), and testNode3PseudoDeletedBySdBiasedSimple().

◆ graph_valid_dcsr()

SCIP_Bool graph_valid_dcsr	(	const GRAPH *	g,
		SCIP_Bool	verbose
	)

is DCSR storage of graph valid?

Parameters

g	the graph
verbose	be verbose?

Definition at line 1919 of file graph_util.c.

References GRAPH::dcsr_storage, dynamic_csr_storage::edgeid, GRAPH::edges, csr_range::end, FALSE, dynamic_csr_storage::head, GRAPH::head, dynamic_csr_storage::id2csredge, GRAPH::knots, dynamic_csr_storage::nedges, nnodes, dynamic_csr_storage::nnodes, dynamic_csr_storage::range, csr_range::start, GRAPH::tail, and TRUE.

Referenced by extreduce_distDataInit(), graph_edge_delFull(), graph_init_dcsr(), and replaceEdgeByPath().

◆ graph_dijkLimited_init()

SCIP_RETCODE graph_dijkLimited_init	(	SCIP *	scip,
		const GRAPH *	g,
		DIJK **	dijkdata
	)

initializes (allocates and fills) limited Dijkstra structure members

Parameters

scip	SCIP
g	the graph
dijkdata	data for limited Dijkstra

Definition at line 1989 of file graph_util.c.

References dijkstra_data::dheap, dijkstra_data::edgelimit, FALSE, FARAWAY, graph_heap_create(), GRAPH::knots, nnodes, dijkstra_data::node_bias, dijkstra_data::node_distance, dijkstra_data::node_visited, NULL, dijkstra_data::nvisits, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemory, SCIPallocMemoryArray, and dijkstra_data::visitlist.

Referenced by dapathsInit(), extreduce_distDataInit(), reduce_bdkWithSd(), reduce_sdEdgeCliqueStar(), sdneighborUpdateInit(), sdStarInit(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), testSdGetterReturnsCorrectSds(), and testSdStarPcKillsEdge().

◆ graph_dijkLimited_initPcShifts()

SCIP_RETCODE graph_dijkLimited_initPcShifts	(	SCIP *	scip,
		const GRAPH *	g,
		DIJK *	dijkdata
	)

initializes PC shifts per node

Parameters

scip	SCIP
g	the graph
dijkdata	data for limited Dijkstra

Definition at line 2031 of file graph_util.c.

References GRAPH::cost, EAT_LAST, EQ, GRAPH::extended, FARAWAY, graph_get_nNodes(), graph_pc_isPc(), graph_pc_isRootedPcMw(), GT, GRAPH::ieat, GRAPH::inpbeg, Is_term, nnodes, dijkstra_data::node_bias, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, GRAPH::source, GRAPH::tail, and GRAPH::term.

Referenced by extreduce_distDataInit().

◆ graph_dijkLimited_reset()

void graph_dijkLimited_reset	(	const GRAPH *	g,
		DIJK *	dijkdata
	)

reset data of limited Dijkstra structure

Parameters

g	the graph
dijkdata	data for limited Dijkstra

Definition at line 2105 of file graph_util.c.

References dijkstra_data::dheap, FALSE, FARAWAY, graph_heap_clean(), GRAPH::knots, dijkstra_data::node_distance, dijkstra_data::node_visited, dijkstra_data::nvisits, dijkstra_heap::position, SCIP_Real, UNKNOWN, and dijkstra_data::visitlist.

Referenced by dapathsRunShortestPaths(), distDataRecomputeNormalDist(), extreduce_distDataInit(), reduce_bdkWithSd(), reduce_sdEdgeCliqueStar(), and sdneighborMarkCloseNodes().

◆ graph_dijkLimited_clean()

void graph_dijkLimited_clean	(	const GRAPH *	g,
		DIJK *	dijkdata
	)

cleans limited Dijkstra structure members

Parameters

g	the graph
dijkdata	data for limited Dijkstra

Definition at line 2083 of file graph_util.c.

References dijkstra_data::dheap, dijkstra_data::edgelimit, FALSE, FARAWAY, graph_heap_clean(), GRAPH::knots, nnodes, dijkstra_data::node_distance, dijkstra_data::node_visited, dijkstra_data::nvisits, SCIP_Real, and TRUE.

Referenced by reduce_bdkWithSd(), reduce_sdEdgeCliqueStar(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), and testSdGetterReturnsCorrectSds().

◆ graph_dijkLimited_free()

void graph_dijkLimited_free	(	SCIP *	scip,
		DIJK **	dijkdata
	)

frees limited Dijkstra structure member

Parameters

scip	SCIP
dijkdata	data for limited Dijkstra

Definition at line 2143 of file graph_util.c.

References dijkstra_data::dheap, graph_heap_free(), dijkstra_data::node_bias, dijkstra_data::node_distance, dijkstra_data::node_visited, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, TRUE, and dijkstra_data::visitlist.

Referenced by dapathsFreeMembers(), extreduce_distDataFree(), reduce_bdkWithSd(), reduce_sdEdgeCliqueStar(), sdneighborUpdateFree(), sdStarFinalize(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), testSdGetterReturnsCorrectSds(), and testSdStarPcKillsEdge().

◆ graph_mark()

void graph_mark ( GRAPH * g )

marks the current graph

Parameters

g the graph

Definition at line 1130 of file graph_base.c.

References GRAPH::extended, FALSE, GRAPH::grad, graph_get_nNodes(), graph_isMarked(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), Is_pseudoTerm, Is_term, GRAPH::mark, nnodes, GRAPH::source, GRAPH::term, and TRUE.

Referenced by checkSdWalk(), computeSteinerTreeDijk(), daRoundExit(), daRoundInit(), divideAndConquer(), enumeration_findSolPcMw(), extInit(), extreduce_deleteEdges(), extreduce_init(), extreduce_pseudoDeleteNodes(), fixVarsDualcost(), fixVarsExtendedRed(), graph_get4nextTTerms(), graph_init_dcsr(), graph_pc_2org(), graph_pc_2trans(), graph_tpathsSetAll2(), graph_tpathsSetAll3(), graph_tpathsSetAll4(), initDecompose(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), pcmwDeleteNonSolEdges(), prunegraphInit(), redcosts_initializeDistances(), reduce_ans(), reduce_articulations(), reduce_bd34(), reduce_bd34WithSd(), reduce_bdkWithSd(), reduce_bidecomposition(), reduce_bidecompositionExact(), reduce_blctreeInit(), reduce_bound(), reduce_da(), reduce_dapaths(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_impliedProfitBasedRpc(), reduce_npv(), reduce_nvAdv(), reduce_sdBiased(), reduce_sdBiasedNeighbor(), reduce_sdEdgeCliqueStar(), reduce_sdStarPc2(), reduce_simple_mw(), reduce_sl(), reduce_termcompChangeSubgraphToBottleneck(), reduceWithNodeFixingBounds(), SCIPStpHeurPruneUpdateSols(), stptest_graphSetUp(), termcompReduceWithParams(), testDistCloseNodesAreValid(), testDistDistancesAreValid(), testDistRootPathsAreValid(), testEdgeDeletion1_deprecated(), testEdgeDeletion2_deprecated(), testEdgeDeletion3_deprecated(), and testEdgeDeletion4_deprecated().

◆ graph_show()

void graph_show ( const GRAPH * )

Definition at line 1251 of file graph_base.c.

References GRAPH::cost, EAT_FREE, GRAPH::edges, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::tail, and GRAPH::term.

◆ graph_uncover()

void graph_uncover ( GRAPH * g )

reinsert all hidden edges

Parameters

g the graph

Definition at line 1276 of file graph_base.c.

References EAT_HIDE, GRAPH::edges, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, and GRAPH::tail.

◆ graph_free()

void graph_free	(	SCIP *	scip,
		GRAPH **	graph,
		SCIP_Bool	final
	)

free the graph

Parameters

scip	SCIP data structure
graph	graph to be freed
final	delete ancestor data structures?

Definition at line 796 of file graph_base.c.

References GRAPH::cost, GRAPH::cost_org_pc, GRAPH::costbudget, GRAPH::csr_storage, GRAPH::dcsr_storage, GRAPH::grad, graph_free_csr(), graph_free_dcsr(), graph_freeHistory(), graph_freeHistoryDeep(), graph_mincut_exit(), graph_mincut_isInitialized(), graph_path_exists(), graph_path_exit(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::mark, GRAPH::maxdeg, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::rootedgeprevs, SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, STP_DCSTP, STP_RSMT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and GRAPH::term2edge.

Referenced by bdkFree(), boundPruneHeur(), buildsolgraph(), checkSdWalk(), computeHistory(), dualascent_execPcMw(), graph_pack(), graph_subgraphFree(), graph_subgraphReinsert(), initReceivedSubproblem(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), lurkpruneFinalize(), pseudoAncestorsCreation(), pseudoAncestorsHash(), pseudoAncestorsHashPc(), pseudoAncestorsMerge(), pseudoAncestorsMergePc(), pseudoDelDouble(), pseudoDelSingle(), redcostGraphFree(), reduce_bd34(), reduce_bd34WithSd(), reduce_bound(), reduce_boundHop(), reduce_daPcMw(), reduce_impliedProfitBasedRpc(), reduce_npv(), reduce_sd(), reduce_sdgraphFree(), reduce_sdPc(), reduce_termcompFree(), SCIP_DECL_PROBDELORIG(), SCIP_DECL_PROPEXITSOL(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), stptest_graphTearDown(), substpsolver_solve(), supergraphComputeMst(), testDaPathsPcMw3EdgesWorks(), testDistCloseNodesAreValid(), testDistDistancesAreValid(), and testDistRootPathsAreValid().

◆ graph_freeHistory()

void graph_freeHistory	(	SCIP *	scip,
		GRAPH *	p
	)

frees the history

Parameters

scip	SCIP data
p	graph data

Definition at line 868 of file graph_base.c.

References GRAPH::ancestors, GRAPH::contracttrace, GRAPH::edges, graph_freePseudoAncestors(), NULL, Int_List_Node::parent, GRAPH::pseudoancestors, SCIPfreeBlockMemory, SCIPfreeMemoryArray, and SCIPfreeMemoryArrayNull.

Referenced by graph_free(), and updatePropgraph().

◆ graph_freeHistoryDeep()

void graph_freeHistoryDeep	(	SCIP *	scip,
		GRAPH *	p
	)

frees the deep history

Parameters

scip	SCIP data
p	graph data

Definition at line 900 of file graph_base.c.

References GRAPH::fixedcomponents, graph_free_fixed(), GRAPH::norgmodelknots, NULL, GRAPH::orghead, GRAPH::orgtail, Int_List_Node::parent, GRAPH::path_heap, GRAPH::path_state, GRAPH::pcancestors, SCIPfreeBlockMemory, and SCIPfreeMemoryArray.

Referenced by graph_free(), and updatePropgraph().

◆ graph_getIsTermArray()

void graph_getIsTermArray	(	const GRAPH *	,
		SCIP_Bool *
	)

Definition at line 540 of file graph_base.c.

References GRAPH::extended, FALSE, graph_pc_isPcMw(), graph_pc_termIsNonLeafTerm(), Is_term, GRAPH::knots, nnodes, SCIP_Bool, GRAPH::term, and TRUE.

Referenced by checkSdWalk(), extreduce_extPermaInit(), prInit(), reduce_nvAdv(), and reduce_sl().

◆ graph_getTerms()

void graph_getTerms	(	const GRAPH *	g,
		int *	terms
	)

gets terminals

Parameters

g	the graph
terms	array of size g->terms

Definition at line 567 of file graph_base.c.

References graph_get_nNodes(), Is_term, nnodes, nterms, GRAPH::term, and GRAPH::terms.

Referenced by graph_getTermsRandom(), and termsepaFindTerminalSource().

◆ graph_getTermsRandom()

SCIP_RETCODE graph_getTermsRandom	(	SCIP *	scip,
		const GRAPH *	g,
		int *	terms
	)

gets randomly permuted terminals

Parameters

scip	SCIP data structure
g	the graph
terms	array of size g->terms

Definition at line 588 of file graph_base.c.

References graph_getTerms(), SCIP_CALL, SCIP_OKAY, SCIPcreateRandom(), SCIPfreeRandom(), SCIPrandomPermuteIntArray(), GRAPH::terms, and TRUE.

Referenced by dpborder_coreUpdateOrdering().

◆ graph_getEdgeCosts()

void graph_getEdgeCosts	(	const GRAPH *	,
		SCIP_Real *	RESTRICT,
		SCIP_Real *	RESTRICT
	)

Referenced by boundPruneHeur(), boundPruneHeurMw(), computeSteinerTree(), computeSteinerTreeTM(), redcostGraphComputeSteinerTreeDegCons(), redcostGraphComputeSteinerTreeDirected(), and reduce_bound().

◆ graph_getEdgeRevCosts()

void graph_getEdgeRevCosts	(	const GRAPH *	,
		SCIP_Real *	RESTRICT
	)

◆ graph_getCsr()

void graph_getCsr	(	const GRAPH *	,
		int *	RESTRICT,
		int *	RESTRICT,
		int *	RESTRICT,
		int *
	)

Referenced by daExec().

◆ graph_resize()

SCIP_RETCODE graph_resize	(	SCIP *	scip,
		GRAPH *	g,
		int	ksize,
		int	esize,
		int	layers
	)

enlarge given graph

Parameters

scip	SCIP data structure
g	graph to be resized
ksize	new node slots
esize	new edge slots
layers	layers (set to -1 by default)

Definition at line 744 of file graph_base.c.

References GRAPH::cost, GRAPH::costbudget, GRAPH::edges, GRAPH::esize, GRAPH::grad, GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::ksize, GRAPH::layers, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPreallocMemoryArray, GRAPH::tail, GRAPH::term, and GRAPH::term2edge.

Referenced by getBiasedMw(), graph_transPc(), graph_transPc2Spg(), graph_transPcGetSap(), graph_transRmw(), graph_transRpc(), and graph_transRpc2FixedProper().

◆ graph_copy()

SCIP_RETCODE graph_copy	(	SCIP *	scip,
		const GRAPH *	orggraph,
		GRAPH **	copygraph
	)

copy the graph

Parameters

scip	SCIP data structure
orggraph	original graph
copygraph	graph to be created

Definition at line 939 of file graph_base.c.

References GRAPH::esize, graph_copyData(), graph_init(), GRAPH::ksize, GRAPH::layers, NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by graph_transPcGetRsap(), graph_transPcGetSap(), initPropgraph(), initReceivedSubproblem(), prunegraphInit(), SCIP_DECL_PROBCOPY(), SCIPprobdataCreateFromGraph(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), solveSub(), and substpsolver_getObjFromGraph().

◆ graph_copyPseudoAncestors()

SCIP_RETCODE graph_copyPseudoAncestors	(	SCIP *	scip,
		const GRAPH *	orggraph,
		GRAPH *	copygraph
	)

copies the pseudo-ancestors

Parameters

scip	SCIP data structure
orggraph	original graph
copygraph	graph to be created

Definition at line 1088 of file graph_base.c.

References EAT_FREE, GRAPH::edges, FALSE, graph_addPseudoAncestors(), graph_edge_getPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_get_nEdges(), graph_getNpseudoAncestors(), graph_pseudoAncestors_appendCopyArrayToEdge(), GRAPH::ieat, SCIP_Bool, SCIP_CALL, and SCIP_OKAY.

Referenced by initPropgraph(), SCIP_DECL_PROBCOPY(), and SCIPprobdataCreateFromGraph().

◆ graph_copyData()

SCIP_RETCODE graph_copyData	(	SCIP *	scip,
		const GRAPH *	orgraph,
		GRAPH *	copygraph
	)

copy the data of the graph

Parameters

scip	SCIP data structure
orgraph	original graph
copygraph	graph to be copied to

Definition at line 957 of file graph_base.c.

References BMScopyMemoryArray, GRAPH::budget, GRAPH::cost, GRAPH::cost_org_pc, GRAPH::costbudget, GRAPH::csr_storage, GRAPH::dcsr_storage, GRAPH::edges, EQ, GRAPH::esize, GRAPH::extended, GRAPH::grad, graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_valid(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, GRAPH::inpbeg, GRAPH::is_packed, Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::mark, GRAPH::maxdeg, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::norgmodelterms, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::orgknots, GRAPH::orgsource, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, GRAPH::source, STP_BRMWCSP, STP_DCSTP, STP_RSMT, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and GRAPH::withInexactReductions.

Referenced by graph_copy(), and updatePropgraph().

◆ graph_pack()

SCIP_RETCODE graph_pack	(	SCIP *	scip,
		GRAPH *	graph,
		GRAPH **	newgraph,
		REDSOL *	redsol,
		SCIP_Bool	verbose
	)

Packs the graph, i.e. builds a new graph that discards deleted edges and nodes. The original graph is deleted.

Parameters

scip	SCIP data structure
graph	the graph
newgraph	the new graph
redsol	reduce solution or NULL
verbose	verbose?

Definition at line 1324 of file graph_base.c.

References GRAPH::ancestors, GRAPH::budget, EAT_FREE, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, GRAPH::fixedcomponents, GRAPH::grad, graph_free(), graph_get_nEdges(), graph_get_nNodes(), graph_init(), graph_knot_add(), graph_path_exit(), graph_pc_finalizeSubgraph(), graph_pc_getNonLeafTermOffset(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_valid(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::hoplimit, GRAPH::ieat, GRAPH::is_packed, Is_term, GRAPH::knots, GRAPH::layers, GRAPH::maxdeg, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::norgmodelterms, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgsource, GRAPH::orgtail, packEdges(), packNodes(), packPcMwInit(), packPcMwVanished(), GRAPH::path_heap, GRAPH::pcancestors, GRAPH::prize, reduce_solGetOffsetPointer(), reduce_solPack(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::source, STP_RSMT, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by graph_obstgrid_create(), presolveStp(), and SCIPStpHeurRecRun().

◆ graph_init()

SCIP_RETCODE graph_init	(	SCIP *	scip,
		GRAPH **	g,
		int	ksize,
		int	esize,
		int	layers
	)

initialize graph

Parameters

scip	SCIP data structure
g	new graph
ksize	slots for nodes
esize	slots for edges
layers	number of layers (only needed for packing, otherwise 1)

Definition at line 607 of file graph_base.c.

References GRAPH::ancestors, GRAPH::budget, GRAPH::contracttrace, GRAPH::cost, GRAPH::cost_org_pc, GRAPH::costbudget, GRAPH::csr_storage, GRAPH::dcsr_storage, GRAPH::edges, GRAPH::esize, GRAPH::extended, FALSE, GRAPH::fixedcomponents, GRAPH::grad, GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, GRAPH::head, GRAPH::hoplimit, GRAPH::ieat, GRAPH::inpbeg, GRAPH::is_packed, GRAPH::knots, GRAPH::ksize, GRAPH::layers, GRAPH::mark, GRAPH::maxdeg, GRAPH::mincut_dist, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_nedges, GRAPH::mincut_next, GRAPH::mincut_nnodes, GRAPH::mincut_numb, GRAPH::mincut_prev, GRAPH::mincut_r, GRAPH::mincut_temp, GRAPH::mincut_x, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::norgmodelterms, NULL, GRAPH::oeat, GRAPH::orgedges, GRAPH::orghead, GRAPH::orgknots, GRAPH::orgsource, GRAPH::orgtail, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::pcancestors, GRAPH::prize, GRAPH::pseudoancestors, GRAPH::rootedgeprevs, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, GRAPH::source, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, GRAPH::terms, UNKNOWN, and GRAPH::withInexactReductions.

Referenced by boundPruneHeur(), buildsolgraph(), computeHistory(), extractSubgraphBuild(), graph_buildCompleteGraph(), graph_copy(), graph_grid_create(), graph_load(), graph_obstgrid_create(), graph_pack(), graph_transRpcGetSpg(), graphBuildV5E5(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), pseudoDelDouble(), pseudoDelSingle(), redcostGraphBuild(), reduce_bound(), reduce_boundHop(), reduce_npv(), reduce_sd(), reduce_sdPc(), SCIPStpHeurRecExclude(), sdgraphBuildDistgraph(), sdgraphBuildDistgraphFromTpaths(), subgraphBuild(), supergraphComputeMst(), testBdkSdMstDeletesNodeDeg3(), testBdkSdMstDeletesNodeDeg4(), testBdkSdMstStarDeletesNodeDeg4(), testBdkTreeDistDeletesNodeDeg4(), testBiasedTerminalPathsTo4NextFound(), testBiconnectedComponentsAreFound(), testBiconnectedComponentsAreFound2(), testBiconnectedComponentsAreFound3(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), testBiconnectedDecomposition3(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), testBLCworksFor5Tree(), testDaPathsPcMw3EdgesWorks(), testDistCloseNodesAreValid(), testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), testDistDistancesAreValid(), testDistRootPathsAreValid(), testEdgeDeletedBy3LeafSpg(), testEdgeDeletedByCommonRedCostsTargets(), testEdgeDeletedByEqBottleneck(), testEdgeDeletedByEqBottleneck2(), testEdgeDeletedByMst1(), testEdgeDeletedByMst2(), testEdgeDeletedByMultiRedCosts(), testEdgeDeletion1_deprecated(), testEdgeDeletion2_deprecated(), testEdgeDeletion3_deprecated(), testEdgeDeletion4_deprecated(), testEdgeDeletion5_deprecated(), testEdgeNotDeleted1(), testGeneralStarDeletedEdge1(), testGeneralStarDeletedEdge2(), testGeneralStarDeletedEdge3(), testNode3PseudoDeletedByContraction(), testNode3PseudoDeletedByRedCosts1(), testNode3PseudoDeletedBySd1(), testNode3PseudoDeletedBySd2(), testNode3PseudoDeletedBySd3(), testNode3PseudoDeletedBySdBiased(), testNode3PseudoDeletedBySdBiasedSimple(), testNode4PseudoDeletedBySd1(), testNode4PseudoNotDeletedBySd1(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), testNsvImpliedContractsImpliedToTermEdge(), testPathReplaceDeletesEdge(), testPathReplaceDeletesEdge2(), testPcEdgeDeletedByMst1(), testPcEdgeNotDeleted(), testPcNode3PseudoDeletedBySd1(), testPcNode4PseudoDeletedBySd1(), testPrunedSolIsImprovedPc1(), testPrunedSolIsImprovedPc2(), testRmwAnsDeletesOneEdge(), testRmwAnsDeletesOneNode(), testRmwAnsDeletesTwoNodes(), testRmwChain2DeletesNode(), testRmwNpv3DeletesNode(), testRmwTerminalContraction(), testRmwTerminalDeg1Contraction1(), testRmwTerminalDeg1Contraction2(), testRmwTerminalDeg1Contraction3(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), testSdBiasedDeletesEdge(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), testSdCliqueStarDeletesEdge(), testSdGetterReturnsCorrectSds(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), testSdGraphQueriesAreValid(), testSdGraphStrongBiasedDistsAreValid(), testSdPcKillsEdge1(), testSdPcKillsEdge2(), testSdPcKillsTwoEdges(), testSdRepair(), testSdStarBiasedDeletesEdge(), testSdStarBiasedDeletesEdge2(), testSdStarBiasedDeletesEdge3(), testSdStarPcKillsEdge(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), testStar5IsCorrect(), testTerminalPathsRepair(), testTerminalPathsRepair2(), testTerminalPathsRepair3(), testTerminalPathsTo3NextFound(), testTerminalSeparatorsAreFound(), testTerminalSeparatorsAreFound2(), testTerminalSeparatorsAreFound3(), testTmGivesExpectedTreePcFull1(), testTmGivesExpectedTreePcFull2(), and testTmGivesExpectedTreePcFull3().

◆ graph_initHistory()

SCIP_RETCODE graph_initHistory	(	SCIP *	scip,
		GRAPH *	graph
	)

initialize data structures required to keep track of reductions

Parameters

scip	SCIP data structure
graph	graph

Definition at line 695 of file graph_base.c.

References GRAPH::ancestors, BMScopyMemoryArray, graph_get_nEdges(), graph_initAncestors(), graph_initPseudoAncestors(), graph_pc_isPcMw(), GRAPH::head, GRAPH::knots, nnodes, NULL, GRAPH::orghead, GRAPH::orgtail, GRAPH::pcancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, and GRAPH::tail.

Referenced by checkSdWalk(), graphBuildV5E5(), initPropgraph(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), prunegraphInit(), pseudoDelDouble(), pseudoDelSingle(), redcostGraphBuild(), reduce_exec(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), stptest_graphSetUp(), substpsolver_initHistory(), testDistCloseNodesAreValid(), testDistDistancesAreValid(), testDistRootPathsAreValid(), testEdgeDeletion1_deprecated(), testEdgeDeletion2_deprecated(), testEdgeDeletion3_deprecated(), testEdgeDeletion4_deprecated(), and updatePropgraph().

◆ graph_isMarked()

SCIP_Bool graph_isMarked ( const GRAPH * g )

is the current graph properly marked?

Parameters

g the graph

Definition at line 1165 of file graph_base.c.

References GRAPH::extended, FALSE, GRAPH::grad, graph_knot_printInfo(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, GRAPH::source, GRAPH::term, and TRUE.

Referenced by bidecomposition_isPossible(), blctreeComputeBottlenecks(), blctreeComputeEdgesState(), extCheckArc(), extreduce_checkArc(), extreduce_checkEdge(), extreduce_deleteEdges(), extreduce_distDataRecomputeDirtyPaths(), findSolPcMw(), findSolRPcMw(), getRedCost2ndNextDistances(), graph_mark(), graph_tpathsRepair(), graph_transRpcGetSpg(), isPseudoDeletable(), pseudodeleteExecute(), redcosts_initializeDistances(), reduce_dapaths(), and termcompDeleteEdges().

◆ graph_isSetUp()

SCIP_Bool graph_isSetUp ( const GRAPH * g )

is the current graph already set up? (with history and path)

Parameters

g the graph

Definition at line 1240 of file graph_base.c.

References GRAPH::ancestors, NULL, and GRAPH::orgtail.

Referenced by reduce_exec().

◆ graph_buildCompleteGraph()

SCIP_RETCODE graph_buildCompleteGraph	(	SCIP *	scip,
		GRAPH **	g,
		int	nnodes
	)

builds complete graph (Kn) with unit edge weights and no terminals

Parameters

scip	SCIP data structure
g	new graph
nnodes	number of nodes

Definition at line 440 of file graph_base.c.

References graph_edge_add(), graph_init(), graph_knot_add(), nnodes, SCIP_CALL, and SCIP_OKAY.

Referenced by bdkInit(), reduce_bd34(), reduce_bd34WithSd(), and testSdGetterReturnsCorrectSds().

◆ graph_valid()

SCIP_Bool graph_valid	(	SCIP *	scip,
		const GRAPH *	g
	)

is the given graph valid?

Parameters

scip	scip struct
g	the graph

Definition at line 1480 of file graph_base.c.

References EAT_FREE, EAT_LAST, GRAPH::edges, FALSE, GRAPH::grad, graph_knot_printInfo(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_trail_arr(), graphisValidPcMw(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArrayNull, GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by boundPruneHeur(), boundPruneHeurMw(), buildsolgraph(), computeNewSols(), computePertubedSol(), computeReducedProbSolution(), computeSteinerTree(), daRoundExit(), decomposeExec(), decomposeExecExact(), decomposeGetSubgraph(), decomposeReduceSubDoIt(), execNvSl(), fixVarsRedbased(), graph_copyData(), graph_load(), graph_pack(), graph_save(), graph_subgraphReinsert(), graph_transPc(), graph_transPcmw2rooted(), graph_transRmw(), ledgeFromNetgraph(), localRun(), nsvExec(), redcostGraphBuild(), redcostGraphComputeSteinerTree(), redcostGraphComputeSteinerTreeDegCons(), redcostGraphComputeSteinerTreeDirected(), reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_applyPseudoDeletions(), reduce_bd34(), reduce_bd34WithSd(), reduce_bound(), reduce_boundHop(), reduce_boundHopDa(), reduce_boundHopR(), reduce_boundHopRc(), reduce_boundPruneHeur(), reduce_da(), reduce_dapaths(), reduce_daPcMw(), reduce_exec(), reduce_identifyNonLeafTerms(), reduce_impliedProfitBasedRpc(), reduce_nnp(), reduce_pathreplace(), reduce_pathreplaceExt(), reduce_redLoopStp(), reduce_sd(), reduce_sdBiased(), reduce_sdBiasedNeighbor(), reduce_sdPc(), reduce_sdsp(), reduce_simple(), reduce_simple_mw(), reduce_simple_pc(), reduce_simple_sap(), reduceLurk(), runTmPcMW_mode(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurRecRun(), SCIPStpHeurSlackPruneRun(), SCIPStpPropGetGraph(), SCIPStpValidateSol(), sdgraphBuildDistgraph(), sdgraphBuildDistgraphFromTpaths(), selectBranchingVertexBySol(), and termcompDeleteEdges().

◆ graph_validInput()

SCIP_Bool graph_validInput	(	SCIP *	scip,
		const GRAPH *	g
	)

is the given input graph valid?

Parameters

scip	scip struct
g	the graph

Definition at line 1619 of file graph_base.c.

References EAT_LAST, FALSE, GRAPH::grad, graph_get_nNodes(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_trail_arr(), graphisValidPcMw(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL_ABORT, SCIPallocBufferArray, SCIPerrorMessage, SCIPfreeBufferArrayNull, GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by check_inputgraph().

◆ graph_knotIsNWLeaf()

SCIP_Bool graph_knotIsNWLeaf	(	const GRAPH *	,
		int
	)

Definition at line 35 of file graph_node.c.

References GRAPH::cost, EAT_LAST, FARAWAY, LT, NULL, GRAPH::oeat, GRAPH::outbeg, STP_NWPTSPG, and GRAPH::stp_type.

Referenced by computeStarts(), graph_findCentralTerminal(), graph_knot_printInfo(), nwptstpSetRoot(), reduce_rpt(), and runTm().

◆ graph_subgraphExtract()

SCIP_RETCODE graph_subgraphExtract	(	SCIP *	scip,
		GRAPH *	orggraph,
		SUBINOUT *	subinout,
		GRAPH **	subgraph
	)

Obtains a new subgraph corresponding to marked nodes. Also fills a node map from the new to the original nodes. Creates a shallow copy and moves parts wrt ancestor information: ancestors and pseudo-ancestors are kept/moved and will be modified also for original graph!

Parameters

scip	SCIP data structure
orggraph	original graph
subinout	data structure for inserting/extracting sub-problem
subgraph	graph to be created

Definition at line 712 of file graph_sub.c.

References borderNodesCollect(), extractSubgraphBuild(), graph_pc_isPcMw(), GRAPH::knots, SCIP_CALL, SCIP_OKAY, and GRAPH::withInexactReductions.

Referenced by decomposeExactSubTry(), decomposeGetSubgraph(), and decomposeReduceSubDoIt().

◆ graph_subinoutInit()

SCIP_RETCODE graph_subinoutInit	(	SCIP *	scip,
		const GRAPH *	orggraph,
		SUBINOUT **	subinout
	)

initializes

Parameters

scip	SCIP data structure
orggraph	original graph
subinout	data structure for handling inclusion/exclusion of sub-problems

Definition at line 733 of file graph_sub.c.

References FALSE, graph_get_nNodes(), nnodes, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, and sub.

Referenced by bidecomposition_initSubInOut().

◆ graph_subinoutFree()

void graph_subinoutFree	(	SCIP *	scip,
		SUBINOUT **	subinout
	)

frees

Parameters

scip	SCIP data structure
subinout	data structure for handling inclusion/exclusion of sub-problems

Definition at line 859 of file graph_sub.c.

References SCIPfreeMemory, SCIPfreeMemoryArray, SCIPfreeMemoryArrayNull, StpVecFree, and sub.

Referenced by bidecomposition_free().

◆ graph_subinoutClean()

void graph_subinoutClean	(	SCIP *	scip,
		SUBINOUT *	subinout
	)

cleans

Parameters

scip	SCIP data structure
subinout	data structure for handling inclusion/exclusion of sub-problems

Definition at line 882 of file graph_sub.c.

References StpVecClear.

Referenced by decomposeExactSubDoIt(), and decomposeSolveSub().

◆ graph_subinoutUsesNewHistory()

SCIP_Bool graph_subinoutUsesNewHistory ( const SUBINOUT * subinout )

new history per subproblem is being used?

Parameters

subinout data structure for handling inclusion/exclusion of sub-problems

Definition at line 848 of file graph_sub.c.

Referenced by decomposeSolveSub().

◆ graph_subinoutActivateEdgeMap()

SCIP_RETCODE graph_subinoutActivateEdgeMap	(	const GRAPH *	orggraph,
		SUBINOUT *	subinout
	)

activates

Parameters

orggraph	original graph
subinout	data structure for handling inclusion/exclusion of sub-problems

Definition at line 769 of file graph_sub.c.

References graph_get_nEdges(), SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, and TRUE.

Referenced by decomposeExec(), and decomposePartialExact().

◆ graph_subinoutActivateNewHistory()

void graph_subinoutActivateNewHistory ( SUBINOUT * subinout )

activates

Parameters

subinout data structure for handling inclusion/exclusion of sub-problems

Definition at line 788 of file graph_sub.c.

References TRUE.

Referenced by decomposeExec(), and decomposePartialExact().

◆ graph_subinoutGetSubToOrgEdgeMap()

const int* graph_subinoutGetSubToOrgEdgeMap ( const SUBINOUT * subinout )

gets edge map

Parameters

subinout data structure for handling inclusion/exclusion of sub-problems

Definition at line 812 of file graph_sub.c.

Referenced by decomposeExactFixSol(), decomposeExactSubDoIt(), decomposeSolveSub(), and subsolFixOrgEdges().

◆ graph_subinoutGetSubToOrgNodeMap()

const int* graph_subinoutGetSubToOrgNodeMap ( const SUBINOUT * subinout )

gets nodes map

Parameters

subinout data structure for handling inclusion/exclusion of sub-problems

Definition at line 799 of file graph_sub.c.

Referenced by decomposeReduceSubDoIt().

◆ graph_subinoutGetOrgToSubNodeMap()

const int* graph_subinoutGetOrgToSubNodeMap ( const SUBINOUT * subinout )

gets nodes map

Parameters

subinout data structure for handling inclusion/exclusion of sub-problems

Definition at line 825 of file graph_sub.c.

Referenced by bidecomposition_getMarkedSubRoot(), and decomposeReduceSubDoIt().

◆ graph_subinoutGetContractionRecord()

const int* graph_subinoutGetContractionRecord ( const SUBINOUT * subinout )

get contraction record for cut nodes (-1 if no contraction)

Parameters

subinout data structure for handling inclusion/exclusion of sub-problems

Definition at line 837 of file graph_sub.c.

Referenced by bidecomposition_markSub().

◆ graph_knot_getContractionRecordAncestor()

int graph_knot_getContractionRecordAncestor	(	int	node,
		const SUBINOUT *	subinout
	)

gets ancestor

Parameters

node	node to get ancestors for
subinout	data structure for handling inclusion/exclusion of sub-problems

Definition at line 895 of file graph_sub.c.

Referenced by bidecomposition_markSub().

◆ graph_subgraphCompleteNewHistory()

SCIP_RETCODE graph_subgraphCompleteNewHistory	(	SCIP *	scip,
		const int *	edgemap_subToOrg,
		GRAPH *	orggraph,
		GRAPH *	subgraph
	)

completes history NOTE: necessary to allocate block memory on subscip

Parameters

scip	SCIP data structure
edgemap_subToOrg	maps edges of subgraph to original graph
orggraph	original graph
subgraph	graph to fill

Definition at line 920 of file graph_sub.c.

References BMScopyMemoryArray, GRAPH::cost, EQ, extractSubgraphInitHistory(), FALSE, GRAPH::fixedcomponents, graph_edge_getPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_free_fixedEdgesOnly(), graph_get_nEdges(), graph_initAncestors(), graph_pseudoAncestors_appendCopyArrayToEdge(), GRAPH::head, GRAPH::orghead, GRAPH::orgtail, GRAPH::pseudoancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, and GRAPH::tail.

Referenced by substpsolver_transferHistory().

◆ graph_subgraphReinsert()

SCIP_RETCODE graph_subgraphReinsert	(	SCIP *	scip,
		SUBINOUT *	subinout,
		GRAPH *	orggraph,
		GRAPH **	subgraph
	)

reinserts extracted (and modified) subgraph; also deletes subgraph. Dual to "graph_subgraphExtract"

Parameters

scip	SCIP data structure
subinout	data structure for handling inclusion/exclusion of sub-problems
orggraph	original graph
subgraph	graph to be reinserted (and freed)

Definition at line 983 of file graph_sub.c.

References FALSE, GRAPH::fixedcomponents, graph_free(), graph_path_exit(), graph_pc_isPcMw(), graph_valid(), NULL, GRAPH::orghead, GRAPH::orgtail, reinsertSubgraph(), SCIP_CALL, SCIP_OKAY, and SCIPfreeMemoryArray.

Referenced by decomposeReduceSubDoIt().

◆ graph_subgraphFree()

void graph_subgraphFree	(	SCIP *	scip,
		GRAPH **	subgraph
	)

frees extracted subgraph. NOTE: fixed history components are not deleted

Parameters

scip	SCIP data structure
subgraph	graph to be freed

Definition at line 1022 of file graph_sub.c.

References FALSE, graph_free(), and graph_path_exit().

◆ graph_grid_create()

SCIP_RETCODE graph_grid_create	(	SCIP *	scip,
		GRAPH **	gridgraph,
		int **	coords,
		int	nterms,
		int	grid_dim,
		int	scale_order
	)

creates a graph out of a given grid

Parameters

scip	SCIP data structure
gridgraph	the grid graph to be constructed
coords	coordinates
nterms	number of terminals
grid_dim	problem dimension
scale_order	scale order

Definition at line 338 of file graph_grid.c.

References compEdges(), getNodeNumber(), graph_edge_add(), graph_init(), graph_knot_add(), graph_knot_chg(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, nnodes, nterms, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPfreeBufferArray, SCIPsortInt(), STP_RSMT, and GRAPH::stp_type.

Referenced by graph_load().

◆ graph_obstgrid_create()

SCIP_RETCODE graph_obstgrid_create	(	SCIP *	scip,
		GRAPH **	gridgraph,
		int **	coords,
		int **	obst_coords,
		int	nterms,
		int	grid_dim,
		int	nobstacles,
		int	scale_order
	)

creates a graph out of a given grid

Parameters

scip	SCIP data structure
gridgraph	the (obstacle) grid graph to be constructed
coords	coordinates of all points
obst_coords	coordinates of obstacles
nterms	number of terminals
grid_dim	dimension of the problem
nobstacles	number of obstacles
scale_order	scale factor

Definition at line 175 of file graph_grid.c.

References compEdgesObst(), FALSE, getNodeNumber(), graph_edge_add(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_pack(), GRAPH::grid_coordinates, GRAPH::grid_dim, GRAPH::grid_ncoords, nnodes, nterms, NULL, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPfreeBufferArray, SCIPsortInt(), GRAPH::source, STP_OARSMT, GRAPH::stp_type, and TRUE.

Referenced by graph_load().

◆ graph_grid_coordinates()

SCIP_RETCODE graph_grid_coordinates	(	SCIP *	scip,
		int **	coords,
		int **	nodecoords,
		int *	ncoords,
		int	node,
		int	grid_dim
	)

computes coordinates of node 'node'

Parameters

scip	SCIP data structure
coords	coordinates
nodecoords	coordinates of the node (to be computed)
ncoords	array with number of coordinate
node	the node
grid_dim	problem dimension

Definition at line 486 of file graph_grid.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by SCIPprobdataWriteSolution().

◆ graph_edge_add()

void graph_edge_add	(	SCIP *	,
		GRAPH *	,
		int	,
		int	,
		double	,
		double
	)

◆ graph_edge_addBi()

void graph_edge_addBi	(	SCIP *	,
		GRAPH *	,
		int	,
		int	,
		double
	)

Referenced by graph_transPc2Spg(), graph_transRpc2FixedProper(), graph_transRpcGetSpg(), subgraphBuild(), testBdkSdMstDeletesNodeDeg3(), testBdkSdMstDeletesNodeDeg4(), testBdkSdMstStarDeletesNodeDeg4(), testBdkTreeDistDeletesNodeDeg4(), testBiasedTerminalPathsTo4NextFound(), testBiconnectedComponentsAreFound(), testBiconnectedComponentsAreFound2(), testBiconnectedComponentsAreFound3(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), testBiconnectedDecomposition3(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), testBLCworksFor5Tree(), testDaPathsPcMw3EdgesWorks(), testDistCloseNodesAreValid(), testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), testDistDistancesAreValid(), testDistRootPathsAreValid(), testEdgeDeletedBy3LeafSpg(), testEdgeDeletedByCommonRedCostsTargets(), testEdgeDeletedByEqBottleneck(), testEdgeDeletedByEqBottleneck2(), testEdgeDeletedByMst1(), testEdgeDeletedByMst2(), testEdgeDeletedByMultiRedCosts(), testEdgeDeletion1_deprecated(), testEdgeDeletion2_deprecated(), testEdgeDeletion3_deprecated(), testEdgeDeletion4_deprecated(), testEdgeDeletion5_deprecated(), testEdgeNotDeleted1(), testGeneralStarDeletedEdge1(), testGeneralStarDeletedEdge2(), testGeneralStarDeletedEdge3(), testNode3PseudoDeletedByContraction(), testNode3PseudoDeletedByRedCosts1(), testNode3PseudoDeletedBySd1(), testNode3PseudoDeletedBySd2(), testNode3PseudoDeletedBySd3(), testNode3PseudoDeletedBySdBiased(), testNode3PseudoDeletedBySdBiasedSimple(), testNode4PseudoDeletedBySd1(), testNode4PseudoNotDeletedBySd1(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), testNsvImpliedContractsImpliedToTermEdge(), testPathReplaceDeletesEdge(), testPathReplaceDeletesEdge2(), testPcEdgeDeletedByMst1(), testPcEdgeNotDeleted(), testPcNode3PseudoDeletedBySd1(), testPcNode4PseudoDeletedBySd1(), testPrunedSolIsImprovedPc1(), testPrunedSolIsImprovedPc2(), testRmwAnsDeletesOneEdge(), testRmwAnsDeletesOneNode(), testRmwAnsDeletesTwoNodes(), testRmwChain2DeletesNode(), testRmwNpv3DeletesNode(), testRmwTerminalContraction(), testRmwTerminalDeg1Contraction1(), testRmwTerminalDeg1Contraction2(), testRmwTerminalDeg1Contraction3(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), testSdBiasedDeletesEdge(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), testSdCliqueStarDeletesEdge(), testSdGetterReturnsCorrectSds(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), testSdGraphQueriesAreValid(), testSdGraphStrongBiasedDistsAreValid(), testSdRepair(), testSdStarBiasedDeletesEdge(), testSdStarBiasedDeletesEdge2(), testSdStarBiasedDeletesEdge3(), testSdStarPcKillsEdge(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), testStar5IsCorrect(), testTerminalPathsRepair(), testTerminalPathsRepair2(), testTerminalPathsRepair3(), testTerminalPathsTo3NextFound(), testTerminalSeparatorsAreFound(), testTerminalSeparatorsAreFound2(), testTerminalSeparatorsAreFound3(), testTmGivesExpectedTreePcFull1(), testTmGivesExpectedTreePcFull2(), and testTmGivesExpectedTreePcFull3().

◆ graph_edge_addSubgraph()

void graph_edge_addSubgraph	(	SCIP *	scip,
		const GRAPH *	orggraph,
		const int *	nodemapOrg2sub,
		int	orgedge,
		GRAPH *	subgraph
	)

add a new edge to a subgraph

Parameters

scip	SCIP data structure
orggraph	original graph
nodemapOrg2sub	node mapping from original to subgraph
orgedge	original edge
subgraph	the subgraph

Definition at line 341 of file graph_edge.c.

References GRAPH::cost, GRAPH::extended, flipedge, graph_edge_add(), graph_pc_isPcMw(), graph_pc_updateSubgraphEdge(), GRAPH::head, and GRAPH::tail.

Referenced by buildsolgraph(), packEdges(), redcostGraphBuild(), and SCIPStpHeurRecExclude().

◆ graph_edge_del()

void graph_edge_del	(	SCIP *	scip,
		GRAPH *	g,
		int	e,
		SCIP_Bool	freeancestors
	)

delete an edge from standard data structure

Parameters

scip	SCIP data structure
g	the graph
e	the edge
freeancestors	free edge ancestors?

Definition at line 368 of file graph_edge.c.

References GRAPH::ancestors, EAT_FREE, EAT_HIDE, GRAPH::grad, graph_edge_delHistory(), GRAPH::head, GRAPH::ieat, GRAPH::knots, GRAPH::oeat, removeEdge(), and GRAPH::tail.

Referenced by ansProcessCandidateWithBridge(), boundPruneHeur(), boundPruneHeurMw(), cutEdgePrune(), daRpcmwDeleteTermIncidents(), decomposeExactFixSol(), delPseudoEdgeDeleteEdge(), graph_edge_delBlocked(), graph_edge_delFull(), graph_edge_redirect(), graph_knot_contract(), graph_knot_del(), graph_knot_delFull(), graph_knot_replaceDeg2(), graph_pc_deleteTerm(), graph_transPcGetRsap(), ledgeFromNetgraph(), mwContractNonPositiveChain(), mwTraverseChain(), pcmwDeleteNonSolEdges(), pcmwReduceKnotDeg1(), pcmwReduceTerm0Prize(), pcReduceTermDeg2(), propgraphDeleteEdge(), pseudoDelDouble(), reduce_bound(), reduce_boundHop(), reduce_boundHopR(), reduce_boundHopRc(), reduce_boundMw(), reduce_chain2(), reduce_cnsAdv(), reduce_daSlackPrune(), reduce_deleteConflictEdges(), reduce_deleteMultiedges(), reduce_fixedConflicts(), reduce_impliedProfitBasedRpc(), reduce_nnp(), reduce_npv(), reduce_nvAdv(), reduce_sd(), reduce_sdBiased(), reduce_sdBiasedNeighbor(), reduce_sdEdgeCliqueStar(), reduce_sdImpLongEdge(), reduce_sdPc(), reduce_sdsp(), reduce_sdspSap(), reduce_sdWalk(), reduce_sdWalkExt(), reduce_sdWalkExt2(), reduce_simple(), reduce_simple_dc(), reduce_simple_hc(), reduce_simple_sap(), reduce_unconnectedInfeas(), reduce_unconnectedRpcRmwInfeas(), reduceFixedVars(), reduceLurk(), reducePcMw(), reduceRootedProb(), reduceWithEdgeFixingBounds(), reinsertSubgraphDeleteOldEdges(), removeEdge(), SCIPStpHeurPruneRun(), SCIPStpHeurSlackPruneRun(), sepafullReduceFromSols(), termcompDeleteEdges(), termDeleteExtension(), testBLCworksFor3StarAfterReduction(), testSdRepair(), testTerminalPathsRepair2(), and testTerminalPathsRepair3().

◆ graph_edge_delFull()

void graph_edge_delFull	(	SCIP *	scip,
		GRAPH *	g,
		int	e,
		SCIP_Bool	freeancestors
	)

delete an edge from standard, DCSR (if existent) and CSR (if existent) data structures

Parameters

scip	SCIP data structure
g	the graph
e	the edge
freeancestors	free edge ancestors?

Definition at line 418 of file graph_edge.c.

References GRAPH::csr_storage, GRAPH::dcsr_storage, FALSE, graph_dcsr_deleteEdgeBi(), graph_edge_del(), graph_valid_dcsr(), and dynamic_csr_storage::id2csredge.

Referenced by deleteEdge(), graph_knot_delFull(), removeEdge(), and testDistDistancesAreValid().

◆ graph_edge_delBlocked()

void graph_edge_delBlocked	(	SCIP *	scip,
		GRAPH *	g,
		const SCIP_Bool *	edge_deletable,
		SCIP_Bool	freeancestors
	)

deletes edges marked by given array

Parameters

scip	SCIP data structure
g	the graph
edge_deletable	marks edges to delete (of size nedges / 2)
freeancestors	free edge ancestors?

Definition at line 448 of file graph_edge.c.

References GRAPH::edges, and graph_edge_del().

Referenced by reduce_sdStar(), reduce_sdStarPc(), reduce_sdStarPc2(), reduce_sdWalk_csr(), reduce_sdWalkTriangle(), and sdStarFinalize().

◆ graph_edge_delHistory()

void graph_edge_delHistory	(	SCIP *	scip,
		GRAPH *	g,
		int	edge
	)

free the history of an edge

Parameters

scip	SCIP data
g	graph data
edge	edge for which to free the history

Definition at line 466 of file graph_edge.c.

References GRAPH::ancestors, flipedge_Uint, graph_edge_delPseudoAncestors(), and SCIPintListNodeFree().

Referenced by graph_edge_del(), graph_edge_reinsert(), graph_knot_replaceDeg2(), mwTraverseChain(), and packEdges().

◆ graph_edge_hide()

void graph_edge_hide	(	GRAPH *	g,
		int	e
	)

hide edge

Parameters

g	the graph
e	the edge

Definition at line 483 of file graph_edge.c.

References EAT_FREE, EAT_HIDE, GRAPH::grad, GRAPH::head, GRAPH::ieat, NULL, GRAPH::oeat, removeEdge(), and GRAPH::tail.

◆ graph_edge_redirect()

int graph_edge_redirect	(	SCIP *	scip,
		GRAPH *	g,
		int	eki,
		int	k,
		int	j,
		SCIP_Real	cost,
		SCIP_Bool	forcedelete,
		SCIP_Bool	checkexist
	)

redirects given edge eki

Parameters

scip	SCIP data structure
g	the graph
eki	the edge
k	new tail
j	new head
cost	new cost
forcedelete	delete edge eki if it is not used?
checkexist	check if there is already an edge kj

Definition at line 103 of file graph_edge.c.

References GRAPH::cost, EAT_FREE, EAT_LAST, Edge_anti, FALSE, GRAPH::grad, graph_edge_del(), graph_edge_isInRange(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPisGE(), SCIPisGT(), and GRAPH::tail.

Referenced by delPseudoPath(), extractSubgraphAddEdge(), graph_edge_reinsert(), graph_knot_replaceDeg2(), graph_transPcGetRsap(), graph_transPcGetSap(), graph_transPcmw2rooted(), and mwTraverseChain().

◆ graph_knot_contract()

SCIP_RETCODE graph_knot_contract	(	SCIP *	scip,
		GRAPH *	g,
		int *	solnode,
		int	t,
		int	s
	)

contracts node s into node t

Parameters

scip	SCIP data structure
g	graph data structure
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
t	tail node to be contracted (surviving node)
s	head node to be contracted

Definition at line 264 of file graph_node.c.

References singleton_ancestors_edge::ancestors, GRAPH::ancestors, CONNECT, GRAPH::contracttrace, GRAPH::cost, EAT_LAST, Edge_anti, Edge_even, FALSE, flipedge, flipedge_Uint, GRAPH::grad, graph_edge_del(), graph_edge_delPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_knot_chg(), graph_knot_del(), graph_knot_isInRange(), graph_pseudoAncestors_appendCopySingToEdge(), graph_singletonAncestors_freeMembers(), graph_singletonAncestors_init(), graph_typeIsUndirected(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, section::mark, NULL, GRAPH::oeat, GRAPH::outbeg, singleton_ancestors_edge::revancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBlockMemoryArray, SCIPdebugMessage, SCIPfreeBlockMemoryArray, SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisGT(), SCIPisLE(), GRAPH::source, GRAPH::tail, GRAPH::term, and TRUE.

Referenced by borderNodesContract(), contractEdgeNoFixedEnd(), contractEdgeWithFixedEnd(), graph_knot_contractFixed(), graph_knot_contractLowdeg2High(), mwContract0WeightVertices(), reduce_contract0Edges(), reduce_simple(), and reduce_simple_sap().

◆ graph_knot_contractFixed()

SCIP_RETCODE graph_knot_contractFixed	(	SCIP *	scip,
		GRAPH *	g,
		int *	solnode,
		int	edge,
		int	t,
		int	s
	)

contract an edge, given index and by its endpoints, which is to be fixed

Parameters

scip	SCIP data structure
g	graph data structure
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
edge	the edge
t	tail node to be contracted (surviving node)
s	head node to be contracted

Definition at line 521 of file graph_node.c.

References graph_fixed_addEdge(), graph_knot_contract(), SCIP_CALL, and SCIP_OKAY.

Referenced by nsvEdgeContract(), reduce_nv(), reduce_nvAdv(), reduce_rpt(), reduce_simple_sap(), and reduce_sl().

◆ graph_knot_contractLowdeg2High()

SCIP_RETCODE graph_knot_contractLowdeg2High	(	SCIP *	scip,
		GRAPH *	g,
		int *	solnode,
		int	t,
		int	s
	)

contract endpoint of lower degree into endpoint of higher degree

Parameters

scip	SCIP data structure
g	graph data structure
solnode	node array to mark whether an node is part of a given solution (CONNECT), or NULL
t	tail node to be contracted
s	head node to be contracted

Definition at line 539 of file graph_node.c.

References GRAPH::grad, graph_knot_contract(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by reduce_simple().

◆ graph_knot_replaceDeg2()

SCIP_RETCODE graph_knot_replaceDeg2	(	SCIP *	scip,
		int	vertex,
		SCIP_Real	edgecost,
		int	ancestornode,
		GRAPH *	g,
		SCIP_Bool *	edgeEliminated
	)

pseudo deletes non-terminal of degree 2

Parameters

scip	SCIP data structure
vertex	the vertex to replace
edgecost	new edge cost
ancestornode	node to copy ancestors from or -1
g	the graph
edgeEliminated	edge eliminated? (due to conflict)

Definition at line 158 of file graph_node.c.

References GRAPH::ancestors, BMScopyMemoryArray, GRAPH::cost, Edge_even, FALSE, flipedge, GRAPH::grad, graph_edge_del(), graph_edge_delHistory(), graph_edge_getAncestors(), graph_edge_getPseudoAncestors(), graph_edge_nPseudoAncestors(), graph_edge_redirect(), graph_knot_del(), graph_pc_isPcMw(), graph_pseudoAncestors_appendCopyArrayToEdge(), graph_pseudoAncestors_appendCopyNodeToEdge(), graph_typeIsUndirected(), graph_valid_pseudoAncestors(), GRAPH::head, Is_term, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBlockMemoryArray, SCIPdebugMessage, SCIPfreeBlockMemoryArrayNull, SCIPintListNodeAppend(), SCIPintListNodeAppendCopy(), SCIPintListNodeFree(), SCIPisEQ(), GRAPH::term, and TRUE.

Referenced by pcReduceKnotDeg2(), and reduce_simple().

◆ graph_edge_reinsert()

SCIP_RETCODE graph_edge_reinsert	(	SCIP *	scip,
		GRAPH *	g,
		int	edge,
		int	tail,
		int	head,
		SCIP_Real	cost,
		int	ancestornode,
		SINGLETONANS *	ancestorsBackward,
		SINGLETONANS *	ancestorsForward,
		int *	insertedge,
		SCIP_Bool *	conflict
	)

reinsert an edge to replace two other edges

Parameters

scip	SCIP data structure
g	the graph
edge	edge to reinsert
tail	new tail
head	new head
cost	new edge cost
ancestornode	node to copy ancestors from or -1
ancestorsBackward	backwards (edge) ancestors
ancestorsForward	forward (edge) ancestors
insertedge	pointer to inserted edge or -1
conflict	does the newly edge contain conflicts? (i.e. is redundant)

Definition at line 200 of file graph_edge.c.

References singleton_ancestors_edge::ancestors, GRAPH::ancestors, Edge_anti, Edge_even, FALSE, flipedge, graph_edge_delHistory(), graph_edge_redirect(), graph_pc_isPcMw(), graph_pseudoAncestors_appendCopyNodeToEdge(), graph_pseudoAncestors_appendCopySingToEdge(), graph_typeIsUndirected(), NULL, GRAPH::pcancestors, singleton_ancestors_edge::revancestors, SCIP_CALL, SCIP_OKAY, SCIPintListNodeAppendCopy(), and TRUE.

Referenced by delPseudoDeleteVertex(), delPseudoEdgeDeleteEdge(), and pcReduceTermDeg2().

◆ graph_knot_isInRange()

SCIP_Bool graph_knot_isInRange	(	const GRAPH *	g,
		int	k
	)

is node in range?

Parameters

g	the graph
k	the node

Definition at line 52 of file graph_node.c.

Referenced by addLevel(), bidecomposition_getMarkedSubRoot(), bidecomposition_markSub(), blctreeBuildMst(), blctreeComputeBottlenecks(), blctreeComputeEdgesState(), borderNodesCollect(), borderNodesContract(), bottleneckMarkEqualityPath(), closeNodesRunInit(), computeOrderingFromNode(), computeSteinerTree_execBiased(), cutNodesCompute(), cutNodesTreeBuildSteinerTree(), cutNodesTreeMakeTerms(), cutNodesTreeMakeTermsIsComplete(), dapathsRunShortestPaths(), dapathsUpdate(), decomposeCsrIsValid(), decomposeGetFirstMarked(), decomposeGetSubgraph(), dpborder_coreUpdateOrdering(), dpgraphInit(), dpsolverGetSolution(), dualascent_allTermsReachable(), dualascent_execDegCons(), extensionHasImplicationConflict(), extractSubgraphAddEdge(), extractSubgraphAddEdgesWithHistory(), extractSubgraphAddNodes(), extreduce_bottleneckCheckNonLeaves(), extreduce_bottleneckIsDominated(), extreduce_bottleneckIsDominatedBiased(), extreduce_distComputeRestrictedDist(), extreduce_distDataGetSp(), extreduce_mstbiasedCheck3NodeSimple(), extreduce_spgCheck3ComponentSimple(), extreduce_spgCheck3NodeSimple(), extStackTopProcessInitialEdges(), extTreeGetDirectedRedcost(), extTreeGetDirectedRedcostProper(), extTreeStackTopRootRemove(), getTreeRedcosts_dbg(), gmlWriteEdge(), graph_contractTrace(), graph_knot_contract(), graph_knot_del(), graph_knot_delFull(), graph_knot_hasContractTrace(), graph_path_st_dc(), graph_pathInLimitedExec(), graph_tpathsGetClosestTerm(), graph_tpathsGetProfitNodes(), graph_tpathsPrintForNode(), graph_transRpcGetSpg(), graphmarkIsClean(), impliedNodesRemoveTerm(), initSolve(), mincutFree(), redcostGraphBuild(), redcostGraphMark(), reduce_compbuilderPrintSeparators(), reduce_impliedNodesIsValid(), reduce_impliedNodesRepair(), reduce_nodesDeg1(), reduce_sdneighborGetCloseTerms(), reduce_termcompChangeSubgraphToBottleneck(), reduce_termsepaGetNextComp(), reinsertSubgraphAdaptSubToOrgMap(), reinsertSubgraphDeleteOldEdges(), reinsertSubgraphTransferEdges(), reinsertSubgraphTransferTerminals(), sdneighborUpdateExec(), sdqueryAttachBinaryTreeNode(), sdqueryBuildNodesToFullMap(), sdqueryBuildNodesToRmqMap(), subgraphBuild(), subgraphIdentify(), subtreesRemoveNonValids(), termcompMarkPseudoDelNodes(), termcompReduce(), termsepaCsrGetMaxNedges(), termsepaCutIsCorrect(), termsepaStoreCutTry(), termsepaTraverseSinkComp(), tpathsGetKCloseTerms(), tpathsPrintPath(), tpathsRepairExit(), tpathsRepairExitLevel(), tpathsRepairTraverse1st(), tpathsRepairTraverseLevelWithStack(), tpathsRepairTraverseStackAddBelow(), tpathsRepairUpdate1st(), tpathsRepairUpdateLevel(), tpathsScan2nd(), updateBorder(), updateTerminalSource(), and vnoiDataRepairPreprocess().

◆ graph_knot_add()

void graph_knot_add	(	GRAPH *	p,
		int	term
	)

add a vertex

Parameters

p	the graph
term	terminal property

Definition at line 64 of file graph_node.c.

References EAT_LAST, GRAPH::grad, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::mark, NULL, GRAPH::outbeg, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by buildsolgraph(), computeHistory(), distgraphAddNodes(), extractSubgraphAddNodes(), getBiasedMw(), graph_buildCompleteGraph(), graph_grid_create(), graph_load(), graph_obstgrid_create(), graph_pack(), graph_transPc(), graph_transPc2Spg(), graph_transPcGetSap(), graph_transRmw(), graph_transRpc(), graph_transRpc2FixedProper(), graph_transRpcGetSpg(), graph_voronoiWithRadius(), graphBuildV5E5(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangeMw(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), packNodes(), pseudoDelDouble(), pseudoDelSingle(), redcostGraphBuild(), reduce_npv(), reduce_sd(), reduce_sdPc(), SCIPStpHeurRecExclude(), subgraphBuild(), supergraphComputeMst(), testBdkSdMstDeletesNodeDeg3(), testBdkSdMstDeletesNodeDeg4(), testBdkSdMstStarDeletesNodeDeg4(), testBdkTreeDistDeletesNodeDeg4(), testBiasedTerminalPathsTo4NextFound(), testBiconnectedComponentsAreFound(), testBiconnectedComponentsAreFound2(), testBiconnectedComponentsAreFound3(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), testBiconnectedDecomposition3(), testBLCworksFor3Star(), testBLCworksFor3StarAfterReduction(), testBLCworksFor5Tree(), testDaPathsPcMw3EdgesWorks(), testDistCloseNodesAreValid(), testDistCloseNodesPcAreValid1(), testDistCloseNodesPcAreValid2(), testDistCloseNodesPcAreValidAfterDeletion(), testDistDistancesAreValid(), testDistRootPathsAreValid(), testEdgeDeletedBy3LeafSpg(), testEdgeDeletedByCommonRedCostsTargets(), testEdgeDeletedByEqBottleneck(), testEdgeDeletedByEqBottleneck2(), testEdgeDeletedByMst1(), testEdgeDeletedByMst2(), testEdgeDeletedByMultiRedCosts(), testEdgeDeletion1_deprecated(), testEdgeDeletion2_deprecated(), testEdgeDeletion3_deprecated(), testEdgeDeletion4_deprecated(), testEdgeDeletion5_deprecated(), testEdgeNotDeleted1(), testGeneralStarDeletedEdge1(), testGeneralStarDeletedEdge2(), testGeneralStarDeletedEdge3(), testNode3PseudoDeletedByContraction(), testNode3PseudoDeletedByRedCosts1(), testNode3PseudoDeletedBySd1(), testNode3PseudoDeletedBySd2(), testNode3PseudoDeletedBySd3(), testNode3PseudoDeletedBySdBiased(), testNode3PseudoDeletedBySdBiasedSimple(), testNode4PseudoDeletedBySd1(), testNode4PseudoNotDeletedBySd1(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), testNsvImpliedContractsImpliedToTermEdge(), testPathReplaceDeletesEdge(), testPathReplaceDeletesEdge2(), testPcEdgeDeletedByMst1(), testPcEdgeNotDeleted(), testPcNode3PseudoDeletedBySd1(), testPcNode4PseudoDeletedBySd1(), testPrunedSolIsImprovedPc1(), testPrunedSolIsImprovedPc2(), testRmwAnsDeletesOneEdge(), testRmwAnsDeletesOneNode(), testRmwAnsDeletesTwoNodes(), testRmwChain2DeletesNode(), testRmwNpv3DeletesNode(), testRmwTerminalContraction(), testRmwTerminalDeg1Contraction1(), testRmwTerminalDeg1Contraction2(), testRmwTerminalDeg1Contraction3(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), testSdBiasedDeletesEdge(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), testSdCliqueStarDeletesEdge(), testSdGetterReturnsCorrectSds(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), testSdGraphQueriesAreValid(), testSdGraphStrongBiasedDistsAreValid(), testSdPcKillsEdge1(), testSdPcKillsEdge2(), testSdPcKillsTwoEdges(), testSdRepair(), testSdStarBiasedDeletesEdge(), testSdStarBiasedDeletesEdge2(), testSdStarBiasedDeletesEdge3(), testSdStarPcKillsEdge(), testStar3IsCorrect(), testStar4EdgeIsCorrect(), testStar4IsCorrect(), testStar5IsCorrect(), testTerminalPathsRepair(), testTerminalPathsRepair2(), testTerminalPathsRepair3(), testTerminalPathsTo3NextFound(), testTerminalSeparatorsAreFound(), testTerminalSeparatorsAreFound2(), testTerminalSeparatorsAreFound3(), testTmGivesExpectedTreePcFull1(), testTmGivesExpectedTreePcFull2(), and testTmGivesExpectedTreePcFull3().

◆ graph_knot_chg()

void graph_knot_chg	(	GRAPH *	p,
		int	node,
		int	term
	)

change terminal property of a vertex

Parameters

p	the graph
node	node to be changed
term	terminal property

Definition at line 86 of file graph_node.c.

References Is_term, NULL, STP_TERM, STP_TERM_NONE, STP_TERM_NONLEAF, STP_TERM_PSEUDO, GRAPH::term, and GRAPH::terms.

Referenced by applyBranchHistoryToGraph(), boundPruneHeur(), cutNodesTreeMakeTerms(), decomposeExactFixSol(), distgraphAddNodes(), fixVarsDualcost(), getBiasedMw(), graph_grid_create(), graph_knot_contract(), graph_load(), graph_obstgrid_create(), graph_pc_2org(), graph_pc_2trans(), graph_pc_fixedTermToNonTerm(), graph_pc_knotToFixedTerm(), graph_pc_knotToFixedTermProperty(), graph_pc_knotToNonTermProperty(), graph_pc_nonTermToFixedTerm(), graph_transMw(), graph_transNw2pc(), graph_transPc(), graph_transPc2Spg(), graph_transPcGetRsap(), graph_transPcmw2rooted(), graph_transRmw(), graph_transRpc(), graph_transRpc2FixedProper(), initReceivedSubproblem(), keyNodesResetTerms(), keyNodesSetTerms(), localExtendPc(), localInsertion(), localInsertion2(), localInsertion2pc(), localKeyPathExchange(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertex(), localKeyVertexPc(), localKeyVertexPc2(), markNonLeafTerms_2trans(), markNonLeafTerms_pretransPc(), nsvEdgeContract(), propgraphFixNode(), reduce_bound(), reduce_boundHop(), reduce_sd(), reduce_sl(), reinsertSubgraphTransferTerminals(), SCIP_DECL_CONSSEPALP(), SCIPStpHeurTMRunLP(), selectBranchingVertexBySol(), sepafullReduceFromSols(), termDeleteExtension(), testBdkSdMstDeletesNodeDeg3(), testBdkSdMstDeletesNodeDeg4(), testBdkSdMstStarDeletesNodeDeg4(), testBdkTreeDistDeletesNodeDeg4(), testBiasedTerminalPathsTo4NextFound(), testBiconnectedComponentsAreFound(), testBiconnectedComponentsAreFound2(), testBiconnectedComponentsAreFound3(), testBiconnectedDecomposition(), testBiconnectedDecomposition2(), testBiconnectedDecomposition3(), testBLCworksFor5Tree(), testDaPathsPcMw3EdgesWorks(), testEdgeDeletion3_deprecated(), testEdgeDeletion4_deprecated(), testEdgeDeletion5_deprecated(), testNsvImpliedContractsCutDistEdge(), testNsvImpliedContractsCutDistMiddleEdge(), testNsvImpliedContractsEdge(), testNsvImpliedContractsEdge2(), testNsvImpliedContractsImpliedToTermEdge(), testRmwAnsDeletesOneEdge(), testRmwAnsDeletesOneNode(), testRmwAnsDeletesTwoNodes(), testRmwChain2DeletesNode(), testRmwNpv3DeletesNode(), testRmwTerminalContraction(), testRmwTerminalDeg1Contraction1(), testRmwTerminalDeg1Contraction2(), testRmwTerminalDeg1Contraction3(), testSdBiasedBottleneckDeletesEdge(), testSdBiasedBottleneckTermPathDeletesEdge(), testSdBiasedDeletesEdge(), testSdCliqueStarDeg3AdjacencyIsCorrect(), testSdCliqueStarDeg3IsCorrect(), testSdCliqueStarDeg3IsCorrect2(), testSdCliqueStarDeg4IsCorrect(), testSdCliqueStarDeletesEdge(), testSdGetterReturnsCorrectSds(), testSdGraphDistsAreValid(), testSdGraphDistsAreValid2(), testSdGraphStrongBiasedDistsAreValid(), testSdPcKillsEdge2(), testSdPcKillsTwoEdges(), testSdRepair(), testSdStarBiasedDeletesEdge(), testSdStarBiasedDeletesEdge2(), testSdStarBiasedDeletesEdge3(), testTerminalPathsRepair(), testTerminalPathsRepair2(), testTerminalPathsRepair3(), testTerminalPathsTo3NextFound(), testTerminalSeparatorsAreFound(), testTerminalSeparatorsAreFound2(), testTerminalSeparatorsAreFound3(), testTmGivesExpectedTreePcFull2(), and testTmGivesExpectedTreePcFull3().

◆ graph_knot_del()

void graph_knot_del	(	SCIP *	scip,
		GRAPH *	g,
		int	k,
		SCIP_Bool	freeancestors
	)

deletes node

Parameters

scip	SCIP data structure
g	the graph
k	the node
freeancestors	free edge ancestors?

Definition at line 111 of file graph_node.c.

References EAT_LAST, GRAPH::grad, graph_edge_del(), graph_knot_isInRange(), GRAPH::inpbeg, and GRAPH::outbeg.

Referenced by ansDeleteVertex(), cutNodesTreeDeleteComponents(), delPseudoDeleteVertex(), graph_knot_contract(), graph_knot_replaceDeg2(), graph_pc_deleteTerm(), graph_transPcGetRsap(), graph_transPcmw2rooted(), pcmwReduceTerm0Prize(), propgraphApplyImplicationsPcMw(), propgraphDeleteNode(), pseudodeleteExecute(), reduce_daSlackPrune(), reduce_nodesDeg1(), reduce_npv(), reduce_simple_sap(), reduce_unconnected(), reduce_unconnectedForDirected(), reduce_unconnectedRpcRmwInfeas(), reduceRootedProb(), reduceWithNodeFixingBounds(), and rpcTryFullReduce().

◆ graph_knot_delFull()

void graph_knot_delFull	(	SCIP *	scip,
		GRAPH *	g,
		int	k,
		SCIP_Bool	freeancestors
	)

deletes node, and also adapts DCSR storage

Parameters

scip	SCIP data structure
g	the graph
k	the node
freeancestors	free edge ancestors?

Definition at line 131 of file graph_node.c.

References GRAPH::dcsr_storage, EAT_LAST, GRAPH::grad, graph_edge_del(), graph_edge_delFull(), graph_knot_isInRange(), GRAPH::inpbeg, and GRAPH::outbeg.

◆ graph_knot_contract_dir()

void graph_knot_contract_dir	(	GRAPH *	,
		int	,
		int
	)

◆ graph_edge_delPseudo()

SCIP_RETCODE graph_edge_delPseudo	(	SCIP *	scip,
		GRAPH *	g,
		const SCIP_Real *	cutoffcosts,
		const SCIP_Real *	cutoffs,
		const SCIP_Real *	cutoffsrev,
		int	edge,
		SCIP_Real *	edgecosts_adapt,
		SCIP_Bool *	success
	)

Pseudo deletes edge, i.e. reconnects tail of edge with neighbors of head; maximum degree of STP_DELPSEUDO_MAXGRAD! The orientation of the edge is important!

Parameters

scip	SCIP data structure
g	the graph
cutoffcosts	edge costs for cutoff
cutoffs	cutoff values for each incident edge (or NULL)
cutoffsrev	reverse edge cutoff values (or NULL if undirected or non-existent)
edge	the edge, mind the orientation!
edgecosts_adapt	costs to adapt or NULL
success	has node been pseudo-eliminated?

Definition at line 1097 of file graph_delpseudo.c.

References delPseudoEdgeDeleteEdge(), delPseudoEdgeGetReplaceEdges(), delPseudoEdgeInit(), delPseudoFreeData(), delPseudoIsEdgeDeletionMode(), GRAPH::grad, graph_edge_isInRange(), GRAPH::head, NULL, SCIP_CALL, SCIP_OKAY, STP_DELPSEUDO_MAXGRAD, and TRUE.

Referenced by bdkTryDegGe4().

◆ graph_edge_delPseudoPath()

SCIP_RETCODE graph_edge_delPseudoPath	(	SCIP *	scip,
		GRAPH *	g,
		int	edge,
		int	edge_pathtail,
		int	edge_pathhead,
		SCIP_Real *	edgecosts_adapt
	)

Path replacement of edge; path is given by three oriented edges: edge_pathtail -> edge -> edge_pathhead. Middle edges is replaced.

Parameters

scip	SCIP data structure
g	the graph
edge	the edge to be replaced, mind the orientation!
edge_pathtail	tail edge of path
edge_pathhead	head edge of path
edgecosts_adapt	costs to adapt or NULL

Definition at line 1136 of file graph_delpseudo.c.

References delPseudoPath(), graph_edge_isInRange(), GRAPH::head, SCIP_CALL, SCIP_OKAY, and GRAPH::tail.

Referenced by replaceEdgeByPath().

◆ graph_knot_delPseudo()

SCIP_RETCODE graph_knot_delPseudo	(	SCIP *	scip,
		GRAPH *	g,
		const SCIP_Real *	cutoffcosts,
		const SCIP_Real *	cutoffs,
		const SCIP_Real *	cutoffsrev,
		int	vertex,
		REDCOST *	redcostdata,
		SCIP_Bool *	success
	)

pseudo delete node, i.e. reconnect neighbors; maximum degree of STP_DELPSEUDO_MAXGRAD!

Parameters

scip	SCIP data structure
g	the graph
cutoffcosts	edge costs for cutoff
cutoffs	cutoff values for each incident edge (or NULL)
cutoffsrev	reverse edge cutoff values (or NULL if undirected or non-existent)
vertex	the vertex
redcostdata	reduced cost data for adaptation or NULL
success	has node been pseudo-eliminated?

Definition at line 1015 of file graph_delpseudo.c.

References delPseudoDeleteVertex(), delPseudoFreeData(), delPseudoGetReplaceEdges(), delPseudoInit(), delPseudoIsEdgeDeletionMode(), GRAPH::grad, NULL, SCIP_CALL, SCIP_OKAY, STP_DELPSEUDO_MAXGRAD, STP_DELPSEUDO_MAXNEDGES, TRUE, and UNKNOWN.

Referenced by bdkTryDeg3(), bdkTryDegGe4(), boundPruneHeur(), pseudoDelDouble(), pseudodeleteDeleteNode(), pseudoDelSingle(), reduce_applyPseudoDeletions(), reduce_bd34(), reduce_bd34WithSd(), and reduce_bound().

◆ graph_knot_delPseudoCheckIfPossible()

SCIP_RETCODE graph_knot_delPseudoCheckIfPossible	(	SCIP *	scip,
		const GRAPH *	g,
		const SCIP_Real *	cutoffcosts,
		const SCIP_Real *	cutoffs,
		const SCIP_Real *	cutoffsrev,
		int	vertex,
		SCIP_Bool *	isPossible
	)

checks whether pseudo-deletion is possible; maximum degree of STP_DELPSEUDO_MAXGRAD!

Parameters

scip	SCIP data structure
g	the graph
cutoffcosts	edge costs for cutoff
cutoffs	cutoff values for each incident edge (or NULL)
cutoffsrev	reverse edge cutoff values (or NULL if undirected or non-existent)
vertex	the vertex
isPossible	can vertex pseudo-eliminated?

Definition at line 1063 of file graph_delpseudo.c.

References delPseudoCheckReplacement(), delPseudoFreeDataForCheck(), delPseudoInitForCheck(), delPseudoIsEdgeDeletionMode(), GRAPH::grad, NULL, SCIP_CALL, SCIP_OKAY, STP_DELPSEUDO_MAXGRAD, TRUE, and UNKNOWN.

Referenced by pseudodeleteDeleteComputeCutoffs().

◆ 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_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_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_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_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_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_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_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_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.

◆ 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_transNw()

SCIP_RETCODE graph_transNw	(	SCIP *	scip,
		PRESOL *	presol,
		GRAPH *	g
	)

alters the graph for node-weighted Steiner tree problems

Parameters

scip	SCIP data structure
presol	presolving struct
g	the graph

Definition at line 1519 of file graph_trans.c.

References graph_transNw2pc(), graph_transNw2sap(), nwptstpSetRoot(), SCIP_CALL, SCIP_OKAY, STP_NWPTSPG, and GRAPH::stp_type.

Referenced by graph_load().

◆ graph_transNw2sap()

SCIP_RETCODE graph_transNw2sap	(	SCIP *	scip,
		PRESOL *	presol,
		GRAPH *	g
	)

alters the graph for node-weighted Steiner tree problems

Parameters

scip	SCIP data structure
presol	presolving struct
g	the graph

Definition at line 1487 of file graph_trans.c.

References GRAPH::cost, EAT_LAST, presolve_info::fixed, graph_get_nNodes(), GRAPH::ieat, GRAPH::inpbeg, Is_term, nnodes, GRAPH::prize, SCIP_OKAY, SCIP_Real, and GRAPH::term.

Referenced by graph_transNw().

◆ graph_transNw2pc()

SCIP_RETCODE graph_transNw2pc	(	SCIP *	scip,
		PRESOL *	presol,
		GRAPH *	g
	)

alters the graph for node-weighted Steiner tree problems

Parameters

scip	SCIP data structure
presol	presolving struct
g	the graph

Definition at line 1420 of file graph_trans.c.

References BLOCKED, GRAPH::cost, EQ, FARAWAY, presolve_info::fixed, GE, graph_get_nEdges(), graph_get_nNodes(), graph_knot_chg(), graph_transRpc(), GT, Is_term, LT, nnodes, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, GRAPH::source, STP_TERM, GRAPH::term, and GRAPH::terms.

Referenced by graph_transNw().

◆ graph_transGstpClean()

void graph_transGstpClean	(	PRESOL *	presol,
		GRAPH *	graph
	)

cleans up GSTP after transformation todo also compute a better big M than just the trivial one, e.g. by building an SAP and computing bound todo move the whole transformation here from graph_load, quite hacky at the moment

Parameters

presol	presolving struct
graph	the graph

Definition at line 1381 of file graph_trans.c.

References BLOCKED, GRAPH::cost, EQ, presolve_info::fixed, graph_get_nEdges(), GRAPH::head, Is_term, GRAPH::knots, LE, GRAPH::norgmodelknots, GRAPH::norgmodelterms, SCIP_Real, STP_GSTP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, and GRAPH::terms.

Referenced by graph_load().

◆ graph_transPc()

SCIP_RETCODE graph_transPc	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for prize collecting problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 154 of file graph_trans.c.

References GRAPH::edges, GRAPH::esize, GRAPH::extended, FARAWAY, flipedge, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_pc_initTerm2Edge(), graph_pc_shiftNonLeafCosts(), graph_pc_term2edgeIsConsistent(), graph_resize(), graph_valid(), GRAPH::head, initCostOrgPc(), Is_nonleafTerm, Is_term, GRAPH::knots, GRAPH::ksize, markNonLeafTerms_pretransPc(), nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, GRAPH::orgsource, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), GRAPH::source, STP_MWCSP, STP_PCSPG, STP_TERM, STP_TERM_PSEUDO, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, TERM2EDGE_FIXEDTERM, TERM2EDGE_NONLEAFTERM, GRAPH::terms, and TRUE.

Referenced by checkSdWalk(), graph_load(), graph_transMw(), graphBuildV5E5(), localExtendPc(), localInsertion2pc(), localKeyPathExchangePc(), localKeyPathExchangePc2(), localKeyVertexPc(), localKeyVertexPc2(), and stptest_graphSetUpPcExtended().

◆ graph_transPc2Spg()

SCIP_RETCODE graph_transPc2Spg	(	SCIP *	scip,
		PRESOL *	presol,
		GRAPH *	graph
	)

alters the graph for prize collecting problems and transforms it to an SPG

Parameters

scip	SCIP data structure
presol	presolving struct
graph	the graph

Definition at line 257 of file graph_trans.c.

References BLOCKED, GRAPH::edges, EQ, GRAPH::esize, GRAPH::extended, FALSE, FARAWAY, presolve_info::fixed, graph_edge_addBi(), graph_knot_add(), graph_knot_chg(), graph_resize(), Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPfreeMemoryArrayNull, SCIPisGE(), SCIPisLT(), GRAPH::source, STP_SPG, STP_TERM, STP_TERM_NONE, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, and GRAPH::terms.

Referenced by graph_load().

◆ graph_transRpc()

SCIP_RETCODE graph_transRpc	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for rooted prize collecting problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 373 of file graph_trans.c.

References GRAPH::edges, EQ, GRAPH::esize, GRAPH::extended, FARAWAY, flipedge, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_pc_initTerm2Edge(), graph_pc_knotToFixedTermProperty(), graph_pc_shiftNonLeafCosts(), graph_resize(), GRAPH::head, initCostOrgPc(), Is_nonleafTerm, Is_term, GRAPH::knots, GRAPH::ksize, markNonLeafTerms_pretransPc(), nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, nterms, GRAPH::orgsource, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, STP_RPCSPG, STP_TERM, STP_TERM_NONE, STP_TERM_PSEUDO, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, TERM2EDGE_NONLEAFTERM, GRAPH::terms, and TRUE.

Referenced by graph_load(), graph_transNw2pc(), graph_transRpc2FixedProper(), and stptest_graphSetUpRpcExtended().

◆ graph_transRpc2SpgTrivial()

SCIP_RETCODE graph_transRpc2SpgTrivial	(	SCIP *	scip,
		GRAPH *	g
	)

alters the graph from rooted prize collecting problems to SPG if there are not potential terminals. NOTE: deletes some PC data, but keeps history, in order to be able to reconstruct original optimal solution.

Parameters

scip	SCIP data structure
g	the graph

Definition at line 505 of file graph_trans.c.

References GRAPH::costbudget, graph_pc_2orgcheck(), graph_pc_nNonLeafTerms(), graph_pc_nProperPotentialTerms(), GRAPH::prize, SCIP_ERROR, SCIP_OKAY, SCIPerrorMessage, SCIPfreeMemoryArrayNull, STP_RPCSPG, STP_SPG, GRAPH::stp_type, and GRAPH::term2edge.

Referenced by reduce_redLoopPc().

◆ graph_transRpc2FixedProper()

SCIP_RETCODE graph_transRpc2FixedProper	(	SCIP *	scip,
		PRESOL *	presol,
		GRAPH *	graph
	)

changes the graph for rooted prize collecting problems such that no proper potential terminal are fixed

Parameters

scip	SCIP data structure
presol	presolving struct
graph	the graph

Definition at line 531 of file graph_trans.c.

References BLOCKED, GRAPH::edges, GRAPH::esize, GRAPH::extended, FARAWAY, presolve_info::fixed, graph_edge_addBi(), graph_knot_add(), graph_knot_chg(), graph_resize(), graph_transRpc(), Is_term, isNonLeaf_pretransPc(), GRAPH::knots, GRAPH::ksize, nnodes, nterms, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisEQ(), SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, STP_TERM, STP_TERM_NONE, and GRAPH::term.

Referenced by graph_load().

◆ graph_transMw()

SCIP_RETCODE graph_transMw	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for MWCS problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 632 of file graph_trans.c.

References GRAPH::cost, EAT_LAST, graph_get_nNodes(), graph_knot_chg(), graph_transPc(), GRAPH::ieat, GRAPH::inpbeg, Is_term, nnodes, nterms, NULL, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisLE(), SCIPisLT(), STP_MWCSP, GRAPH::stp_type, GRAPH::term, and GRAPH::terms.

Referenced by graph_load(), and localKeyPathExchangeMw().

◆ graph_transRmw()

SCIP_RETCODE graph_transRmw	(	SCIP *	scip,
		GRAPH *	graph
	)

alters the graph for RMWCS problems

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 687 of file graph_trans.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, EQ, GRAPH::esize, GRAPH::extended, FARAWAY, flipedge, GRAPH::grad, graph_edge_add(), graph_knot_add(), graph_knot_chg(), graph_pc_initTerm2Edge(), graph_pc_knotToFixedTermProperty(), graph_resize(), graph_valid(), GRAPH::head, GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::knots, GRAPH::ksize, LE, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, NULL, GRAPH::orgsource, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPdebugMessage, SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, STP_RMWCSP, STP_TERM, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, GRAPH::terms, and TRUE.

Referenced by graph_load(), and stptest_graphSetUpRmwExtended().

◆ graph_transPcmw2rooted()

SCIP_RETCODE graph_transPcmw2rooted	(	SCIP *	scip,
		GRAPH *	graph,
		SCIP_Real	fixprize,
		SCIP_Bool	verbose
	)

transforms PCSPG or MWCSP to RPCSPG or RMWCSP if possible

Parameters

scip	SCIP data structure
graph	the graph
fixprize	prize at which to make terminals
verbose	be verbose?

Definition at line 809 of file graph_trans.c.

References GRAPH::cost, EAT_LAST, GRAPH::extended, FARAWAY, flipedge, GRAPH::grad, graph_edge_redirect(), graph_knot_chg(), graph_knot_del(), graph_pc_getTwinTerm(), graph_pc_isRootedPcMw(), graph_pc_knotToFixedTermProperty(), graph_pc_knotToNonTermProperty(), graph_pc_presolExit(), graph_valid(), GRAPH::head, Is_pseudoTerm, Is_term, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, GRAPH::rootedgeprevs, SCIP_OKAY, SCIPdebugMessage, SCIPisGE(), GRAPH::source, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_TERM_NONE, GRAPH::stp_type, GRAPH::term, GRAPH::term2edge, TERM2EDGE_NOTERM, GRAPH::terms, and TRUE.

Referenced by propgraphApplyBoundchanges(), reduce_redLoopMw(), and reduce_redLoopPc().

◆ graph_transPcGetSap()

SCIP_RETCODE graph_transPcGetSap	(	SCIP *	scip,
		GRAPH *	graph,
		GRAPH **	newgraph,
		SCIP_Real *	offset
	)

obtains an SAP from prize collecting problems

Parameters

scip	SCIP data structure
graph	the graph
newgraph	the new graph
offset	offset (in/out)

Definition at line 931 of file graph_trans.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::esize, GRAPH::extended, FALSE, FARAWAY, flipedge, graph_copy(), graph_edge_add(), graph_edge_redirect(), graph_knot_add(), graph_pc_getNonLeafTermOffset(), graph_pc_isPc(), graph_pc_knotIsDummyTerm(), graph_pc_presolExit(), graph_pc_presolInit(), graph_resize(), GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::ksize, nnodes, nterms, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPisLT(), SCIPisZero(), GRAPH::source, STP_PCSPG, STP_SAP, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, and TRUE.

Referenced by dualascent_execPcMw(), reduce_daPcMw(), and testDaPathsPcMw3EdgesWorks().

◆ graph_transPcGetRsap()

SCIP_RETCODE graph_transPcGetRsap	(	SCIP *	scip,
		GRAPH *	graph,
		GRAPH **	newgraph,
		const int *	rootcands,
		int	nrootcands,
		int	saproot
	)

builds new rooted SAP graph for prize-collecting problems (with given root for SAP)

Parameters

scip	SCIP data structure
graph	the graph
newgraph	the new graph
rootcands	array containing all vertices that could be used as root
nrootcands	number of all vertices that could be used as root
saproot	the root of the new SAP

Definition at line 1043 of file graph_trans.c.

References GRAPH::cost, EAT_LAST, GRAPH::edges, GRAPH::esize, FALSE, FARAWAY, flipedge, GRAPH::grad, graph_copy(), graph_edge_del(), graph_edge_redirect(), graph_knot_chg(), graph_knot_del(), graph_pc_2transcheck(), graph_pc_initPrizes(), graph_pc_initTerm2Edge(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotToFixedTermProperty(), graph_pc_presolExit(), graph_pc_presolInit(), GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::ksize, GRAPH::mark, nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, GRAPH::source, STP_SAP, STP_TERM, STP_TERM_NONE, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::term2edge, TERM2EDGE_FIXEDTERM, TERM2EDGE_NOTERM, and TRUE.

Referenced by reduce_daPcMw().

◆ graph_transRpcGetSpg()

SCIP_RETCODE graph_transRpcGetSpg	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_Real	primalbound,
		SCIP_Real *	offset,
		int **	edgemap_new2org,
		GRAPH **	newgraph
	)

constructs equivalent SPG for given RPC

Parameters

scip	SCIP data structure
graph	the graph
primalbound	primal bound for graph
offset	offset (in/out)
edgemap_new2org	maps edges
newgraph	the new graph

Definition at line 1217 of file graph_trans.c.

References BLOCKED, GRAPH::cost, EAT_LAST, GRAPH::edges, EQ, GRAPH::extended, FARAWAY, flipedge, GRAPH::grad, graph_edge_addBi(), graph_get_nNodes(), graph_init(), graph_isMarked(), graph_knot_add(), graph_knot_isInRange(), graph_knot_printInfo(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_nNonLeafTerms(), graph_pc_nProperPotentialTerms(), graph_transRpcToSpgIsStable(), GT, GRAPH::head, Is_term, GRAPH::knots, LT, GRAPH::mark, MAX, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocMemoryArray, SCIPdebugMessage, SCIPfreeMemoryArray, GRAPH::source, STP_SPG, STP_TERM, STP_TERM_NONE, GRAPH::stp_type, and GRAPH::term.

Referenced by reduce_impliedProfitBasedRpc().

◆ graph_transRpcToSpgIsStable()

SCIP_Bool graph_transRpcToSpgIsStable	(	const GRAPH *	graph,
		SCIP_Real	primalbound
	)

is a transformation stable?

Parameters

graph	the graph
primalbound	primal bound for graph

Definition at line 1188 of file graph_trans.c.

References FALSE, FARAWAY, GE, graph_get_nNodes(), GT, LE, LT, nnodes, GRAPH::prize, SCIP_Real, STP_RPCSPG, GRAPH::stp_type, and TRANS_MAXPRIZESUM.

Referenced by graph_transRpcGetSpg(), and reduce_impliedProfitBasedRpc().

◆ graph_pc_knotToNonTermProperty()

void graph_pc_knotToNonTermProperty	(	GRAPH *	g,
		int	node
	)

change property of node to be a non-terminal; prize is not changed!

Parameters

g	the graph
node	node to be changed

Definition at line 1044 of file graph_pcbase.c.

References graph_knot_chg(), graph_pc_isPcMw(), STP_TERM_NONE, GRAPH::term2edge, and TERM2EDGE_NOTERM.

Referenced by graph_pc_deleteTerm(), graph_pc_termToNonTerm(), graph_transPcmw2rooted(), and pcmwReduceTerm0Prize().

◆ graph_pc_knotToFixedTermProperty()

void graph_pc_knotToFixedTermProperty	(	GRAPH *	g,
		int	node
	)

change property of node to be a terminal; prize is changed, but no edges are deleted!

Parameters

g	the graph
node	node to be changed

Definition at line 1062 of file graph_pcbase.c.

References FARAWAY, graph_knot_chg(), GRAPH::prize, STP_TERM, GRAPH::term2edge, and TERM2EDGE_FIXEDTERM.

Referenced by graph_pc_enforceNode(), graph_pc_enforceNonLeafTerm(), graph_transPcGetRsap(), graph_transPcmw2rooted(), graph_transRmw(), and graph_transRpc().

◆ graph_pc_termToNonLeafTerm()

void graph_pc_termToNonLeafTerm	(	SCIP *	scip,
		GRAPH *	g,
		int	term,
		SCIP_Bool	force
	)

change property of (non-fixed) terminal to be a non-leaf terminal NOTE: if force == FALSE, then nothing is done if term is the last terminal

Parameters

scip	SCIP data structure
g	the graph
term	terminal to be changed
force	force the transformation? Should usually be FALSE

Definition at line 1210 of file graph_pcbase.c.

References GRAPH::extended, FALSE, graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), Is_term, isLastTerm(), GRAPH::term, GRAPH::term2edge, TERM2EDGE_NONLEAFTERM, and termDeleteExtension().

Referenced by contractEdgeNoFixedEnd(), and reduce_identifyNonLeafTerms().

◆ graph_pc_termToNonTerm()

void graph_pc_termToNonTerm	(	SCIP *	scip,
		GRAPH *	g,
		int	term
	)

Makes a non-fixed terminal a non-terminal. Also sets the prize to 0.0 for (R)PC!

Parameters

scip	SCIP data structure
g	graph data structure
term	terminal to be unfixed

Definition at line 1158 of file graph_pcbase.c.

References GRAPH::extended, FALSE, graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_knotToNonTermProperty(), graph_pc_termIsNonLeafTerm(), Is_anyTerm, GRAPH::prize, GRAPH::source, GRAPH::term, and termDeleteExtension().

Referenced by contractEdgeNoFixedEnd(), contractEdgeWithFixedEnd(), and delPseudoInit().

◆ graph_pc_fixedTermToNonTerm()

void graph_pc_fixedTermToNonTerm	(	SCIP *	scip,
		GRAPH *	g,
		int	term
	)

Makes a fixed terminal a non-terminal

Parameters

scip	SCIP data structure
g	graph data structure
term	terminal to be unfixed

Definition at line 1189 of file graph_pcbase.c.

References graph_knot_chg(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), Is_anyTerm, GRAPH::prize, GRAPH::source, STP_TERM_NONE, GRAPH::term, GRAPH::term2edge, and TERM2EDGE_NOTERM.

Referenced by contractEdgeWithFixedEnd().

◆ graph_pc_knotToFixedTerm()

void graph_pc_knotToFixedTerm	(	SCIP *	scip,
		GRAPH *	g,
		int	node,
		SCIP_Real *	offset
	)

Makes a node a fixed terminal

Parameters

scip	SCIP data structure
g	graph data structure
node	node
offset	offset needed for RMW, or NULL

Definition at line 1079 of file graph_pcbase.c.

References GRAPH::extended, graph_knot_chg(), graph_pc_isMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_nonTermToFixedTerm(), graph_pc_termIsNonLeafTerm(), Is_pseudoTerm, Is_term, GRAPH::prize, SCIP_Bool, GRAPH::source, STP_TERM_NONE, GRAPH::term, GRAPH::term2edge, TERM2EDGE_NOTERM, termDeleteExtension(), and TRUE.

Referenced by contractEdgeWithFixedEnd(), dapathsFixPotTerms(), propgraphApplyImplicationsPcMw(), propgraphFixNode(), and reduce_sl().

◆ graph_pc_nonTermToFixedTerm()

void graph_pc_nonTermToFixedTerm	(	GRAPH *	g,
		int	node,
		SCIP_Real *	offset
	)

makes a non-terminal node a fixed terminal

Parameters

g	graph data structure
node	node
offset	offset needed for RMW, or NULL

Definition at line 1115 of file graph_pcbase.c.

References GRAPH::cost, EAT_LAST, EQ, FARAWAY, GRAPH::grad, graph_knot_chg(), graph_pc_isMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), GRAPH::ieat, GRAPH::inpbeg, Is_pseudoTerm, Is_term, NULL, GRAPH::prize, SCIP_Bool, SCIP_Real, GRAPH::source, STP_TERM, STP_TERM_NONE, GRAPH::term, GRAPH::term2edge, TERM2EDGE_FIXEDTERM, and TERM2EDGE_NOTERM.

Referenced by applyBranchHistoryToGraph(), graph_pc_enforceNode(), and graph_pc_knotToFixedTerm().

◆ graph_pc_updateSubgraphEdge()

void graph_pc_updateSubgraphEdge	(	const GRAPH *	orggraph,
		const int *	nodemapOrg2sub,
		int	orgedge,
		GRAPH *	subgraph
	)

Updates prize-collecting data for an edge added to subgraph of given graph 'orggraph'. Needs to be called right before corresponding edge is added

Parameters

orggraph	original graph
nodemapOrg2sub	node mapping from original to subgraph
orgedge	original edge
subgraph	the subgraph

Definition at line 1661 of file graph_pcbase.c.

References GRAPH::cost_org_pc, GRAPH::edges, GRAPH::esize, GRAPH::extended, flipedge, graph_pc_isPc(), GRAPH::head, Is_anyTerm, GRAPH::source, GRAPH::tail, GRAPH::term, GRAPH::term2edge, and TERM2EDGE_NOTERM.

Referenced by graph_edge_addSubgraph().

◆ graph_pc_enforcePseudoTerm()

void graph_pc_enforcePseudoTerm	(	SCIP *	scip,
		GRAPH *	graph,
		int	pterm
	)

Enforces given pseudo-terminal without deleting edges. I.e. the terminal is part of any optimal solution.

Parameters

scip	SCIP data
graph	graph
pterm	the pseudo-terminal

Definition at line 1530 of file graph_pcbase.c.

References BLOCKED_MINOR, GRAPH::cost, graph_pc_getRoot2PtermEdge(), graph_pc_getTwinTerm(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsPropPotTerm(), GRAPH::prize, SCIPisEQ(), and SCIPisLT().

Referenced by applyBranchHistoryToGraph(), and graph_pc_enforceNode().

◆ graph_pc_enforceNonLeafTerm()

void graph_pc_enforceNonLeafTerm	(	SCIP *	scip,
		GRAPH *	graph,
		int	nonleafterm
	)

Enforces non-leaf terminal without deleting edges. I.e. the terminal is part of any optimal solution.

Parameters

scip	SCIP data
graph	graph
nonleafterm	the terminal

Definition at line 1556 of file graph_pcbase.c.

References BLOCKED, GRAPH::cost, GRAPH::cost_org_pc, EAT_LAST, GRAPH::extended, graph_pc_isMw(), graph_pc_isPc(), graph_pc_isRootedPcMw(), graph_pc_knotIsNonLeafTerm(), graph_pc_knotToFixedTermProperty(), GRAPH::ieat, GRAPH::inpbeg, GRAPH::prize, and SCIPisLT().

Referenced by applyBranchHistoryToGraph().

◆ graph_pc_nonLeafTermIsEnforced()

SCIP_Bool graph_pc_nonLeafTermIsEnforced	(	SCIP *	scip,
		const GRAPH *	graph,
		int	nonleafterm
	)

is non-leaf term enforced?

Parameters

scip	SCIP data
graph	graph
nonleafterm	the terminal

Definition at line 1589 of file graph_pcbase.c.

References BLOCKED_MINOR, GRAPH::extended, graph_pc_isPcMw(), graph_pc_knotIsNonLeafTerm(), GRAPH::prize, and SCIPisEQ().

◆ graph_pc_enforceNode()

void graph_pc_enforceNode	(	SCIP *	scip,
		GRAPH *	graph,
		int	term,
		SCIP_Real *	offset
	)

Tries to enforce node without deleting or adding edges. I.e. the terminal is part of any optimal solution. Is not always possible!

Parameters

scip	SCIP data
graph	graph
term	the terminal
offset	pointer to the offset, for RMW only

Definition at line 1606 of file graph_pcbase.c.

References GRAPH::extended, graph_pc_enforcePseudoTerm(), graph_pc_isMw(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), graph_pc_knotIsPropPotTerm(), graph_pc_knotToFixedTermProperty(), graph_pc_nonTermToFixedTerm(), Is_pseudoTerm, Is_term, and GRAPH::term.

Referenced by initReceivedSubproblem(), and propgraphFixNode().

◆ graph_pc_subtractPrize()

void graph_pc_subtractPrize	(	SCIP *	scip,
		GRAPH *	g,
		SCIP_Real	cost,
		int	i
	)

subtract a given sum from the prize of a terminal

Parameters

scip	SCIP data structure
g	the graph
cost	cost to be subtracted
i	the terminal

Definition at line 2315 of file graph_pcbase.c.

References GRAPH::cost, GRAPH::extended, graph_pc_getRoot2PtermEdge(), graph_pc_getTwinTerm(), graph_pc_isMw(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_termIsNonLeafTerm(), GRAPH::head, Is_term, GRAPH::mark, GRAPH::prize, SCIPisEQ(), SCIPisGE(), GRAPH::source, GRAPH::tail, and GRAPH::term.

Referenced by contractEdgeNoFixedEnd().

◆ graph_pc_knotChgPrize()

void graph_pc_knotChgPrize	(	GRAPH *	g,
		SCIP_Real	newprize,
		int	node
	)

changes prize of a node

Parameters

g	the graph
newprize	new prize
node	the node

Definition at line 1399 of file graph_pcbase.c.

References GRAPH::cost, EQ, GE, graph_pc_getRoot2PtermEdge(), graph_pc_getTwinTerm(), graph_pc_isPcMw(), graph_pc_knotIsPropPotTerm(), Is_term, mwKnotUpdateIncEdges(), GRAPH::prize, SCIP_Bool, STP_MWCSP, STP_RMWCSP, GRAPH::stp_type, and GRAPH::term.

Referenced by propgraphMarkFixedTermsPcMw().

◆ graph_pc_2org()

void graph_pc_2org	(	SCIP *	scip,
		GRAPH *	graph
	)

mark terminals and switch terminal property to original terminals

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 1976 of file graph_pcbase.c.

References GRAPH::extended, FALSE, graph_get_nNodes(), graph_knot_chg(), graph_mark(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), Is_nonleafTerm, Is_pseudoTerm, Is_term, nnodes, SCIP_STAGE_INITSOLVE, SCIPgetStage(), setCostToOrgPc(), setCostToOrgPcPreState(), GRAPH::source, STP_TERM, STP_TERM_PSEUDO, and GRAPH::term.

Referenced by checkSdWalk(), computeSteinerTree(), daPcFindRoots(), daPcMarkRoots(), daRoundInit(), findSolPcMw2Term(), findSolRPcMw(), fixVarsExtendedRed(), graph_pc_2orgcheck(), propgraphApplyBoundchanges(), redcosts_initializeDistances(), reduce_dapaths(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_redLoopMw(), reduce_redLoopPc(), reduce_sollocalRebuildTry(), reduce_unconnectedRpcRmwInfeas(), SCIP_DECL_CONSSEPALP(), SCIPStpHeurLocalExtendPcMwOut(), SCIPStpHeurPruneRun(), stptest_graphSetUpPcOrg(), stptest_graphSetUpRmwOrg(), and stptest_graphSetUpRpcOrg().

◆ graph_pc_2trans()

void graph_pc_2trans	(	SCIP *	scip,
		GRAPH *	graph
	)

mark transformed graph and adapt terminal properties to transformed graph

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 2018 of file graph_pcbase.c.

References BMScopyMemoryArray, GRAPH::cost, GRAPH::cost_org_pc, GRAPH::edges, GRAPH::extended, graph_knot_chg(), graph_mark(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsFixedTerm(), graph_pc_shiftNonLeafCosts(), Is_pseudoTerm, Is_term, GRAPH::knots, markNonLeafTerms_2trans(), nnodes, GRAPH::source, STP_TERM, STP_TERM_PSEUDO, GRAPH::term, and TRUE.

Referenced by computeSteinerTree(), daPcFindRoots(), daPcMarkRoots(), daRoundExit(), extreduce_pseudoDeleteNodes(), findSolPcMw2Term(), findSolRPcMw(), fixVarsExtendedRed(), graph_pc_2transcheck(), propgraphApplyBoundchanges(), redcosts_initializeDistances(), reduce_applyPseudoDeletions(), reduce_da(), reduce_dapaths(), reduce_daPcMw(), reduce_daSlackPrune(), reduce_redLoopMw(), reduce_redLoopPc(), reduce_sollocalRebuildTry(), reduce_unconnectedRpcRmwInfeas(), SCIP_DECL_CONSSEPALP(), SCIPStpHeurLocalExtendPcMwOut(), and SCIPStpHeurPruneRun().

◆ graph_pc_2orgcheck()

void graph_pc_2orgcheck	(	SCIP *	scip,
		GRAPH *	graph
	)

graph_pc_2org if extended

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 2062 of file graph_pcbase.c.

References GRAPH::extended, and graph_pc_2org().

Referenced by extreduce_pseudoDeleteNodes(), graph_transRpc2SpgTrivial(), reduce_applyPseudoDeletions(), reduce_da(), reduce_daPcMw(), reducePcMw(), and SCIPStpHeurLocalExtendPcMwOut().

◆ graph_pc_2transcheck()

void graph_pc_2transcheck	(	SCIP *	scip,
		GRAPH *	graph
	)

graph_pc_2trans if not extended

Parameters

scip	SCIP data structure
graph	the graph

Definition at line 2076 of file graph_pcbase.c.

References GRAPH::extended, and graph_pc_2trans().

Referenced by computePertubedSol(), dualascent_paths(), graph_transPcGetRsap(), SCIPStpHeurLocalExtendPcMw(), and SCIPStpHeurTMRun().

◆ graph_pc_getNorgEdges()

int graph_pc_getNorgEdges ( const GRAPH * graph )

gets number of undeleted, original edges (not going to dummy terminals)

Parameters

graph the graph

Definition at line 1722 of file graph_pcbase.c.

References GRAPH::cost, EAT_FREE, FARAWAY, graph_get_nEdges(), graph_pc_knotIsDummyTerm(), GRAPH::head, LT, GRAPH::oeat, and GRAPH::tail.

◆ graph_pc_getReductionRatios()

void graph_pc_getReductionRatios	(	const GRAPH *	graph,
		SCIP_Real *	ratio_nodes,
		SCIP_Real *	ratio_edges
	)

gets ratio of remaining nodes/edges

Parameters

graph	graph
ratio_nodes	nodes ratio
ratio_edges	edges ratio

Definition at line 1751 of file graph_pcbase.c.

References GRAPH::edges, GRAPH::extended, GRAPH::grad, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_nNonFixedTerms(), Is_pseudoTerm, Is_term, GRAPH::knots, nnodes, GRAPH::norgmodeledges, GRAPH::norgmodelknots, SCIP_Bool, SCIP_Real, GRAPH::source, GRAPH::term, and GRAPH::terms.

Referenced by getEdgeReductionRatio(), and getReductionRatiosPcMw().

◆ graph_pc_getOrgCosts()

void graph_pc_getOrgCosts	(	SCIP *	scip,
		const GRAPH *	graph,
		SCIP_Real *	edgecosts
	)

gets original edge costs, when in extended mode

Parameters

scip	SCIP data structure
graph	the graph
edgecosts	original costs to be filled

Definition at line 1829 of file graph_pcbase.c.

References BLOCKED, BLOCKED_MINOR, BMScopyMemoryArray, GRAPH::cost, GRAPH::cost_org_pc, EQ, GRAPH::extended, graph_edge_isBlocked(), graph_get_nEdges(), graph_pc_isPcMw(), graph_pc_transOrgAreConistent(), SCIP_Bool, SCIP_Real, SCIP_STAGE_INITSOLVE, SCIPgetStage(), and TRUE.

Referenced by graph_pc_costsEqualOrgCosts(), localKeyVertexHeuristics(), localVertexInsertion(), runTmPcMW_mode(), and solstp_prune().

◆ graph_pc_getOrgCostsCsr()

void graph_pc_getOrgCostsCsr	(	SCIP *	scip,
		const GRAPH *	g,
		CSR *	csr
	)

gets original edge costs for CSR, when in extended mode

Parameters

scip	SCIP data structure
g	the graph
csr	CSR

Definition at line 1871 of file graph_pcbase.c.

References BLOCKED, BLOCKED_MINOR, csr_storage::cost, GRAPH::cost, GRAPH::cost_org_pc, csr_storage::edge_id, EQ, GRAPH::extended, graph_edge_isBlocked(), graph_get_nEdges(), graph_get_nNodes(), graph_pc_isPc(), graph_pc_transOrgAreConistent(), nnodes, csr_storage::nnodes, SCIP_Bool, SCIP_Real, csr_storage::start, and TRUE.

Referenced by tmBaseInit().

◆ graph_pc_markOrgGraph()

void graph_pc_markOrgGraph ( GRAPH * g )

mark original graph (without dummy terminals)

Parameters

g the graph

Definition at line 1944 of file graph_pcbase.c.

References GRAPH::cost, EAT_LAST, GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), GT, GRAPH::head, GRAPH::k

SCIP

Detailed Description

Functions

Function Documentation

◆ graph_initContractTracing()

◆ graph_contractTrace()

◆ graph_knot_hasContractTrace()

◆ graph_fixed_resetMoved()

◆ graph_singletonAncestors_init()

◆ graph_singletonAncestors_freeMembers()

◆ graph_valid_ancestors()

◆ graph_initAncestors()

◆ graph_initPseudoAncestors()

◆ graph_initPseudoAncestorsSized()

◆ graph_freePseudoAncestors()

◆ graph_edge_delPseudoAncestors()

◆ graph_knot_delPseudoAncestors()

◆ graph_edge_printPseudoAncestors()

◆ graph_knot_printPseudoAncestors()

◆ graph_edge_nPseudoAncestors()

◆ graph_knot_nPseudoAncestors()

◆ graph_edge_getPseudoAncestors()

◆ graph_edge_getAncestors()

◆ graph_knot_getPseudoAncestors()

◆ graph_getNpseudoAncestors()

◆ graph_addPseudoAncestor()

◆ graph_addPseudoAncestors()

◆ graph_pseudoAncestors_appendCopyEdge()

◆ graph_pseudoAncestors_appendCopyNode()

◆ graph_pseudoAncestors_appendCopyNodeToEdge()

◆ graph_pseudoAncestors_appendCopyEdgeToNode()

◆ graph_pseudoAncestors_appendCopySingToEdge()

◆ graph_pseudoAncestors_appendCopyArrayToEdge()

◆ graph_pseudoAncestors_appendMoveEdge()

◆ graph_pseudoAncestors_appendMoveNode()

◆ graph_pseudoAncestors_addToEdge()

◆ graph_pseudoAncestors_addToNode()

◆ graph_free_pseudoAncestorsBlock()

◆ graph_pseudoAncestorsGetHashArraySize()

◆ graph_pseudoAncestors_hashNode()

◆ graph_pseudoAncestors_hashEdge()

◆ graph_pseudoAncestors_unhashNode()

◆ graph_pseudoAncestors_unhashEdge()

◆ graph_pseudoAncestors_hashNodeDirty()

◆ graph_pseudoAncestors_hashEdgeDirty()

◆ graph_pseudoAncestors_unhashNodeDirty()

◆ graph_pseudoAncestors_unhashEdgeDirty()

◆ graph_pseudoAncestors_edgeIsHashed()

◆ graph_pseudoAncestors_nodeIsHashed()

◆ graph_pseudoAncestors_edgesInConflict()

◆ graph_valid_pseudoAncestors()

◆ graph_init_fixed()

◆ graph_free_fixed()

◆ graph_free_fixedEdgesOnly()

◆ graph_fixed_add()

◆ graph_fixed_addEdge()

◆ graph_fixed_addNodePc()

◆ graph_fixed_moveNodePc()

◆ graph_copyFixed()

◆ graph_getFixedges()

◆ graph_getFixpseudonodes()

◆ graph_getNfixpseudonodes()

◆ graph_termsReachable()

◆ graph_findCentralTerminal()

◆ graph_trail_arr()

◆ graph_trail_costAware()

◆ graph_heap_create()

◆ graph_heap_free()

◆ graph_heap_deleteMin()

◆ graph_heap_deleteMinGetNode()

◆ graph_heap_deleteMinReturnNode()

◆ graph_heap_clean()

◆ graph_heap_correct()

◆ graph_heap_isClean()

◆ graph_init_csr()

◆ graph_init_csrWithEdgeId()

◆ graph_free_csr()

◆ graph_csr_alloc()

◆ graph_csr_allocWithEdgeId()

◆ graph_csr_copy()