Scippy

SCIP

Solving Constraint Integer Programs

graph.h File Reference

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)
 
IDXgraph_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 *)
 
IDXgraph_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
scipSCIP data structure
graphgraph

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
nodenode to trace back from
graphgraph

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
nodenode to trace back from
graphgraph

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
gthe 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()

◆ graph_singletonAncestors_freeMembers()

void graph_singletonAncestors_freeMembers ( SCIP scip,
SINGLETONANS singletonans 
)

◆ graph_valid_ancestors()

◆ graph_initAncestors()

SCIP_RETCODE graph_initAncestors ( SCIP scip,
GRAPH g 
)

initializes edge ancestors

Parameters
scipSCIP data structure
gthe 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
scipSCIP data structure
gthe 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 
)

◆ graph_freePseudoAncestors()

void graph_freePseudoAncestors ( SCIP scip,
GRAPH g 
)

frees pseudo ancestors

Parameters
scipSCIP data structure
gthe 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
scipSCIP data structure
edge_freeedge for which to free pseudo ancestors
gthe 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
scipSCIP data structure
node_freenode for which to free pseudo ancestors
gthe 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
gthe graph
edgeedge 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
gthe graph
nodenode 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()

◆ graph_knot_nPseudoAncestors()

int graph_knot_nPseudoAncestors ( const GRAPH g,
int  node 
)

returns number of pseudo ancestors for given node

Parameters
gthe graph
nodenode 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 
)

◆ graph_edge_getAncestors()

◆ graph_knot_getPseudoAncestors()

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

returns pseudo ancestors for given node

Parameters
gthe graph
nodenode 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)

◆ graph_addPseudoAncestor()

void graph_addPseudoAncestor ( GRAPH g,
int *  pseudoancestor 
)

adds new pseudo ancestor and provides index

Parameters
gthe graph (in/out)
pseudoancestorgives 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
naddnumber of ancestors to add
gthe 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
scipSCIP data structure
edge_targetedge target
edge_sourceedge source
revertIfConflictbreak on conflict
gthe graph
conflictconflict?

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
scipSCIP data structure
node_targetnode target
node_sourcenode source
revertIfConflictbreak on conflict
gthe graph
conflictconflict?

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
scipSCIP data structure
edge_targetedge target
node_sourcenode source
revertIfConflictbreak on conflict
gthe graph
conflictconflict?

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
scipSCIP data structure
node_targetnode target
edge_sourceedge source
revertIfConflictbreak on conflict
gthe graph
conflictconflict?

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
scipSCIP data structure
edge_targetedge target
sourcesource
revertIfConflictbreak on conflict
gthe graph
conflictconflict?

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
scipSCIP data structure
edge_targetedge target
ancestorspseudo ancestors array
nancestorsnumber of ancestors
gthe graph
conflictconflict?

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
scipSCIP data structure
edge_targettarget edge
edge_sourcesource edge
revertIfConflictbreak on conflict
gthe graph
conflictconflict?

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
scipSCIP data structure
node_targettarget node
node_sourcesource node
revertIfConflictbreak on conflict
gthe graph
conflictconflict?

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
scipSCIP data structure
edge_targetedge for which to add pseudo ancestor
ancestor(index of) pseudo ancestor
gthe 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
scipSCIP data structure
node_targetnode for which to add pseudo ancestor
ancestor(index of) pseudo ancestor
gthe 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()

◆ graph_pseudoAncestors_hashNode()

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

hash ancestors of given node

Parameters
pseudoancestorspseudo-ancestors
nodenode for which to hash
hasharrhash 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
pseudoancestorspseudo-ancestors
edgeedge for which to hash
hasharrhash 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
pseudoancestorspseudo-ancestors
nodenode for which to unhash
hasharrhash 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 
)

◆ 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
pseudoancestorspseudo-ancestors
nodenode for which to hash
revertIfConflictrevert on conflict?
conflictconflict?
hasharrhash 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
pseudoancestorspseudo-ancestors
edgeedge for which to hash
revertIfConflictrevert on conflict?
conflictconflict?
hasharrhash 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
pseudoancestorspseudo-ancestors
nodenode for which to unhash
hasharrhash 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
pseudoancestorspseudo-ancestors
edgeedge for which to unhash
hasharrhash 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
pseudoancestorspseudo-ancestors
edgeedge for which to check
hasharrhash 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
pseudoancestorspseudo-ancestors
nodenode for which to check
hasharrhash 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
scipSCIP data structure
gthe graph
edgesedges to check
nedgesnumber 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
scipSCIP data structure
gthe 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 
)

◆ graph_free_fixed()

◆ graph_free_fixedEdgesOnly()

void graph_free_fixedEdgesOnly ( SCIP scip,
GRAPH g 
)

frees fixed edges

Parameters
scipSCIP data structure
gthe 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 
)

◆ graph_fixed_addEdge()

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

adds ancestors from given edges

Parameters
scipSCIP data structure
edgeedge
gthe 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
scipSCIP data structure
nodenode
gthe 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
scipSCIP data structure
nodenode
gthe 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
scipSCIP data structure
gthe original graph
moveFixedEdgesmove fixed edges? If false, nothing is done!
g_copythe 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()

◆ graph_getFixpseudonodes()

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

gets fixed pseudo eliminated nodes

Parameters
scipSCIP data structure
gthe 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
gthe 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
scipscip struct
gthe new graph
reachableare 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()

◆ 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
scipSCIP
gthe new graph
startnode to start from
nodevisitedmarks 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
scipSCIP
gthe new graph
startnode to start from
nodevisitedmarks 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
scipSCIP
capacityheap capacity
positionheap position array or NULL
entriesentries array or NULL
heapthe 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
scipSCIP
freePositionsfree positions array?
freeEntriesfree entries array?
heapthe 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
nodepointer to value of minimum
keypointer to key of minimum
heapthe 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
nodepointer to node stored in minimum (set by method)
heapthe 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()

◆ graph_heap_clean()

◆ graph_heap_correct()

◆ graph_heap_isClean()

SCIP_Bool graph_heap_isClean ( const DHEAP heap)

is the heap clean?

Parameters
heapthe 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
scipSCIP data structure
gthe 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
scipSCIP data structure
gthe 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
scipSCIP data structure
gthe 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 
)

◆ graph_csr_allocWithEdgeId()

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

allocates empty (and invalid!) CSR storage

Parameters
scipSCIP data structure
nnodesnodes
nedgesedges
csrCSR

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 
)

◆ graph_csr_build()

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

◆ 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
gthe graph
edgecostsedge costs (w.r.t graph 'g')
csrCSR

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
csrCSR 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)

◆ graph_csr_free()

void graph_csr_free ( SCIP scip,
CSR **  csr 
)

◆ 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
gthe graph
csrCSR
edgecosts_gedge 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
csrthe CSR graph
verbosebe 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
gthe graph
verbosebe 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
gthe graph
mapmap

Definition at line 560 of file graph_util.c.

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

◆ graph_csrdepo_init()

◆ graph_csrdepo_free()

◆ graph_csrdepo_print()

void graph_csrdepo_print ( const CSRDEPO depository)

Prints depository.

Parameters
depositorythe 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
depositorythe depository
indexthe index of the CSR to get
csrpointer 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 
)

◆ graph_csrdepo_getNcsrs()

int graph_csrdepo_getNcsrs ( const CSRDEPO depository)

◆ graph_csrdepo_getDataSize()

int graph_csrdepo_getDataSize ( const CSRDEPO depository)

◆ graph_csrdepo_clean()

void graph_csrdepo_clean ( CSRDEPO depository)

cleans CSR depository

Parameters
depositorythe 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()

◆ graph_csrdepo_addEmptyTop()

◆ graph_csrdepo_addEmptyTopTree()

void graph_csrdepo_addEmptyTopTree ( CSRDEPO depository,
int  nnodes 
)

adds empty top for tree to CSR depository

Parameters
depositorythe depository
nnodesnodes 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)

◆ graph_csrdepo_hasEmptyTop()

SCIP_Bool graph_csrdepo_hasEmptyTop ( const CSRDEPO depository)

is top of CSR depository empty?

Parameters
depositorythe 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
depositorythe depository
csrpointer 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)

◆ graph_init_dcsr()

◆ graph_update_dcsr()

void graph_update_dcsr ( SCIP scip,
GRAPH g 
)

updates dynamic CSR storage

Parameters
scipSCIP data structure
gthe 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
dcsrDCSR container
tailtail of edge
e_csrCSR 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 
)

◆ graph_free_dcsr()

◆ graph_valid_dcsr()

◆ graph_dijkLimited_init()

◆ graph_dijkLimited_initPcShifts()

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

initializes PC shifts per node

Parameters
scipSCIP
gthe graph
dijkdatadata 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 
)

◆ graph_dijkLimited_clean()

◆ graph_dijkLimited_free()

◆ graph_mark()

void graph_mark ( GRAPH g)

marks the current graph

Parameters
gthe 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()

◆ graph_uncover()

void graph_uncover ( GRAPH g)

reinsert all hidden edges

Parameters
gthe 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
scipSCIP data structure
graphgraph to be freed
finaldelete 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 
)

◆ graph_freeHistoryDeep()

void graph_freeHistoryDeep ( SCIP scip,
GRAPH p 
)

◆ graph_getIsTermArray()

void graph_getIsTermArray ( const GRAPH ,
SCIP_Bool  
)

◆ graph_getTerms()

void graph_getTerms ( const GRAPH g,
int *  terms 
)

gets terminals

Parameters
gthe graph
termsarray 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
scipSCIP data structure
gthe graph
termsarray 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()

◆ 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
scipSCIP data structure
ggraph to be resized
ksizenew node slots
esizenew edge slots
layerslayers (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 
)

◆ graph_copyPseudoAncestors()

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

◆ graph_copyData()

◆ graph_pack()

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

◆ graph_init()

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

initialize graph

Parameters
scipSCIP data structure
gnew graph
ksizeslots for nodes
esizeslots for edges
layersnumber 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()

◆ graph_isMarked()

◆ graph_isSetUp()

SCIP_Bool graph_isSetUp ( const GRAPH g)

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

Parameters
gthe 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
scipSCIP data structure
gnew graph
nnodesnumber 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
scipscip struct
gthe 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()

◆ graph_knotIsNWLeaf()

SCIP_Bool graph_knotIsNWLeaf ( const GRAPH ,
int   
)

◆ 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
scipSCIP data structure
orggraphoriginal graph
subinoutdata structure for inserting/extracting sub-problem
subgraphgraph 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
scipSCIP data structure
orggraphoriginal graph
subinoutdata 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
scipSCIP data structure
subinoutdata 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
scipSCIP data structure
subinoutdata 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
subinoutdata 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
orggraphoriginal graph
subinoutdata 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
subinoutdata 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
subinoutdata 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
subinoutdata 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
subinoutdata 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
subinoutdata 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
nodenode to get ancestors for
subinoutdata 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
scipSCIP data structure
edgemap_subToOrgmaps edges of subgraph to original graph
orggraphoriginal graph
subgraphgraph 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
scipSCIP data structure
subinoutdata structure for handling inclusion/exclusion of sub-problems
orggraphoriginal graph
subgraphgraph 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
scipSCIP data structure
subgraphgraph 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
scipSCIP data structure
gridgraphthe grid graph to be constructed
coordscoordinates
ntermsnumber of terminals
grid_dimproblem dimension
scale_orderscale 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
scipSCIP data structure
gridgraphthe (obstacle) grid graph to be constructed
coordscoordinates of all points
obst_coordscoordinates of obstacles
ntermsnumber of terminals
grid_dimdimension of the problem
nobstaclesnumber of obstacles
scale_orderscale 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
scipSCIP data structure
coordscoordinates
nodecoordscoordinates of the node (to be computed)
ncoordsarray with number of coordinate
nodethe node
grid_dimproblem dimension

Definition at line 486 of file graph_grid.c.

References NULL, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

Referenced by SCIPprobdataWriteSolution().

◆ graph_edge_add()

◆ 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
scipSCIP data structure
orggraphoriginal graph
nodemapOrg2subnode mapping from original to subgraph
orgedgeoriginal edge
subgraphthe 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
scipSCIP data structure
gthe graph
ethe edge
freeancestorsfree 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
scipSCIP data structure
gthe graph
ethe edge
freeancestorsfree 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
scipSCIP data structure
gthe graph
edge_deletablemarks edges to delete (of size nedges / 2)
freeancestorsfree 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
scipSCIP data
ggraph data
edgeedge 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
gthe graph
ethe 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
scipSCIP data structure
gthe graph
ekithe edge
knew tail
jnew head
costnew cost
forcedeletedelete edge eki if it is not used?
checkexistcheck 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()

◆ 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
scipSCIP data structure
ggraph data structure
solnodenode array to mark whether an node is part of a given solution (CONNECT), or NULL
edgethe edge
ttail node to be contracted (surviving node)
shead 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
scipSCIP data structure
ggraph data structure
solnodenode array to mark whether an node is part of a given solution (CONNECT), or NULL
ttail node to be contracted
shead 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()

◆ 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
scipSCIP data structure
gthe graph
edgeedge to reinsert
tailnew tail
headnew head
costnew edge cost
ancestornodenode to copy ancestors from or -1
ancestorsBackwardbackwards (edge) ancestors
ancestorsForwardforward (edge) ancestors
insertedgepointer to inserted edge or -1
conflictdoes 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
gthe graph
kthe 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
pthe graph
termterminal 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
pthe graph
nodenode to be changed
termterminal 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()

◆ graph_knot_delFull()

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

deletes node, and also adapts DCSR storage

Parameters
scipSCIP data structure
gthe graph
kthe node
freeancestorsfree 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
scipSCIP data structure
gthe graph
cutoffcostsedge costs for cutoff
cutoffscutoff values for each incident edge (or NULL)
cutoffsrevreverse edge cutoff values (or NULL if undirected or non-existent)
edgethe edge, mind the orientation!
edgecosts_adaptcosts to adapt or NULL
successhas 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
scipSCIP data structure
gthe graph
edgethe edge to be replaced, mind the orientation!
edge_pathtailtail edge of path
edge_pathheadhead edge of path
edgecosts_adaptcosts 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
scipSCIP data structure
gthe graph
cutoffcostsedge costs for cutoff
cutoffscutoff values for each incident edge (or NULL)
cutoffsrevreverse edge cutoff values (or NULL if undirected or non-existent)
vertexthe vertex
redcostdatareduced cost data for adaptation or NULL
successhas 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
scipSCIP data structure
gthe graph
cutoffcostsedge costs for cutoff
cutoffscutoff values for each incident edge (or NULL)
cutoffsrevreverse edge cutoff values (or NULL if undirected or non-existent)
vertexthe vertex
isPossiblecan 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()

◆ graph_edge_printInfo()

◆ graph_edge_isBlocked()

SCIP_Bool graph_edge_isBlocked ( const GRAPH g,
int  e 
)

is the edge blocked?

Parameters
gthe graph
ethe 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()

◆ graph_edge_isInRange()

SCIP_Bool graph_edge_isInRange ( const GRAPH g,
int  e 
)

is edge in range?

Parameters
gthe graph
ethe 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
scipSCIP data structure
ggraph data structure
verbosebe 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
gthe 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()

◆ graph_printInfo()

◆ graph_printInfoReduced()

◆ graph_get_nNodes()

int graph_get_nNodes ( const GRAPH graph)

get number of nodes

Parameters
graphthe 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
graphthe 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
graphthe 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 
)

◆ graph_get_avgDeg()

SCIP_Real graph_get_avgDeg ( const GRAPH graph)

get (real) average degree of graph

Parameters
graphthe graph

Definition at line 613 of file graph_stats.c.

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

◆ graph_typeIsSpgLike()

◆ graph_typeIsUndirected()

◆ graph_typeIsDirected()

◆ graph_transNw()

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

alters the graph for node-weighted Steiner tree problems

Parameters
scipSCIP data structure
presolpresolving struct
gthe 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
scipSCIP data structure
presolpresolving struct
gthe 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
scipSCIP data structure
presolpresolving struct
gthe 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
presolpresolving struct
graphthe 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()

◆ 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
scipSCIP data structure
presolpresolving struct
graphthe 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()

◆ 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
scipSCIP data structure
gthe 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
scipSCIP data structure
presolpresolving struct
graphthe 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 
)

◆ graph_transRmw()

◆ graph_transPcmw2rooted()

◆ graph_transPcGetSap()

◆ 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
scipSCIP data structure
graphthe graph
newgraphthe new graph
rootcandsarray containing all vertices that could be used as root
nrootcandsnumber of all vertices that could be used as root
saprootthe 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 
)

◆ graph_transRpcToSpgIsStable()

SCIP_Bool graph_transRpcToSpgIsStable ( const GRAPH graph,
SCIP_Real  primalbound 
)

is a transformation stable?

Parameters
graphthe graph
primalboundprimal 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
gthe graph
nodenode 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
gthe graph
nodenode 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
scipSCIP data structure
gthe graph
termterminal to be changed
forceforce 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
scipSCIP data structure
ggraph data structure
termterminal 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
scipSCIP data structure
ggraph data structure
termterminal 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 
)

◆ graph_pc_nonTermToFixedTerm()

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

◆ 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
orggraphoriginal graph
nodemapOrg2subnode mapping from original to subgraph
orgedgeoriginal edge
subgraphthe 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
scipSCIP data
graphgraph
ptermthe 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
scipSCIP data
graphgraph
nonleaftermthe 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
scipSCIP data
graphgraph
nonleaftermthe 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
scipSCIP data
graphgraph
termthe terminal
offsetpointer 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
scipSCIP data structure
gthe graph
costcost to be subtracted
ithe 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
gthe graph
newprizenew prize
nodethe 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()

◆ graph_pc_2trans()

◆ graph_pc_2orgcheck()

void graph_pc_2orgcheck ( SCIP scip,
GRAPH graph 
)

graph_pc_2org if extended

Parameters
scipSCIP data structure
graphthe 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
scipSCIP data structure
graphthe 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
graphthe 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 
)

◆ graph_pc_getOrgCosts()

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

gets original edge costs, when in extended mode

Parameters
scipSCIP data structure
graphthe graph
edgecostsoriginal 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
scipSCIP data structure
gthe graph
csrCSR

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)

◆ graph_pc_adaptSap()

void graph_pc_adaptSap ( SCIP_Real  bigM,
GRAPH graph,
SCIP_Real offset 
)

adapts SAP deriving from PCST or MWCS problem with new big M

Parameters
bigMnew big M value
graphthe SAP graph
offsetthe offset

Definition at line 2156 of file graph_pcbase.c.

References GRAPH::cost, EAT_LAST, EQ, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_Real, SCIPdebugMessage, and GRAPH::source.

◆ graph_pc_presolExit()

void graph_pc_presolExit ( SCIP scip,
GRAPH g 
)

changes graph of PC and MW problems needed after exiting presolving routines

Parameters
scipSCIP data structure
gthe graph

Definition at line 858 of file graph_pcbase.c.

References NULL, GRAPH::rootedgeprevs, SCIPfreeMemoryArray, STP_RPCSPG, and GRAPH::stp_type.

Referenced by graph_transPcGetRsap(), graph_transPcGetSap(), graph_transPcmw2rooted(), and reduce_redLoopPc().

◆ graph_pc_getBiased()

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

◆ graph_pc_termMarkProper()

void graph_pc_termMarkProper ( const GRAPH g,
int *  termmark 
)

check whether terminal is not a leaf in at least one optimal tree

Parameters
gthe graph
termmarkterminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise)

Definition at line 1500 of file graph_pcbase.c.

References GRAPH::extended, graph_pc_termIsNonLeafTerm(), Is_term, GRAPH::knots, nnodes, and GRAPH::term.

Referenced by daPcFindRoots(), reduce_sdWalk(), reduce_sdWalk_csr(), reduce_sdWalkExt2(), reduce_sdWalkTriangle(), and sepaspecial_pcimplicationsInit().

◆ graph_pc_shiftNonLeafCosts()

void graph_pc_shiftNonLeafCosts ( SCIP scip,
GRAPH g 
)

shift costs of non-leaf terminals (call right after transformation to extended has been performed)

Parameters
scipSCIP
gthe graph

Definition at line 671 of file graph_pcbase.c.

References GRAPH::cost, GRAPH::cost_org_pc, EAT_LAST, GRAPH::edges, GRAPH::extended, FARAWAY, flipedge, graph_edge_isBlocked(), graph_pc_isPc(), GRAPH::ieat, GRAPH::inpbeg, Is_nonleafTerm, GRAPH::knots, nnodes, GRAPH::oeat, GRAPH::prize, SCIP_Real, SCIPisEQ(), SCIPisGE(), SCIPisLT(), and GRAPH::term.

Referenced by graph_pc_2trans(), graph_transPc(), and graph_transRpc().

◆ graph_pc_getNonLeafTermOffset()

◆ graph_pc_presolInit()

SCIP_RETCODE graph_pc_presolInit ( SCIP scip,
GRAPH g 
)

changes graph of PC and MW problems needed for presolving routines

Parameters
scipSCIP data structure
gthe graph

Definition at line 815 of file graph_pcbase.c.

References EAT_LAST, GRAPH::edges, GRAPH::grad, GRAPH::ieat, GRAPH::inpbeg, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::rootedgeprevs, SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, GRAPH::source, STP_RPCSPG, and GRAPH::stp_type.

Referenced by graph_transPcGetRsap(), graph_transPcGetSap(), and reduce_redLoopPc().

◆ graph_pc_initSubgraph()

SCIP_RETCODE graph_pc_initSubgraph ( SCIP scip,
GRAPH subgraph 
)

allocates and initializes arrays for subgraph PC/MW

Parameters
scipSCIP data structure
subgraphthe subgraph

Definition at line 763 of file graph_pcbase.c.

References GRAPH::cost_org_pc, GRAPH::edges, GRAPH::esize, graph_pc_initPrizes(), graph_pc_initTerm2Edge(), graph_pc_isPc(), graph_pc_isPcMw(), GRAPH::knots, GRAPH::ksize, SCIP_CALL, SCIP_OKAY, and SCIPallocMemoryArray.

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

◆ graph_pc_finalizeSubgraph()

SCIP_RETCODE graph_pc_finalizeSubgraph ( SCIP scip,
GRAPH subgraph 
)

allocates and initializes arrays for subgraph PC/MW

Parameters
scipSCIP data structure
subgraphthe subgraph

Definition at line 795 of file graph_pcbase.c.

References GRAPH::cost_org_pc, GRAPH::extended, graph_pc_isPc(), graph_pc_isPcMw(), Is_term, NULL, GRAPH::prize, SCIP_OKAY, GRAPH::source, GRAPH::term, and GRAPH::term2edge.

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

◆ graph_pc_initPrizes()

◆ graph_pc_initTerm2Edge()

SCIP_RETCODE graph_pc_initTerm2Edge ( SCIP scip,
GRAPH g,
int  size 
)

initializes term2edge array

Parameters
scipSCIP data structure
gthe graph
sizethe size

Definition at line 721 of file graph_pcbase.c.

References SCIP_CALL, SCIP_OKAY, SCIPallocMemoryArray, GRAPH::term2edge, and TERM2EDGE_NOTERM.

Referenced by graph_pc_initSubgraph(), graph_transPc(), graph_transPcGetRsap(), graph_transRmw(), and graph_transRpc().

◆ graph_pc_contractNodeAncestors()

SCIP_RETCODE graph_pc_contractNodeAncestors ( SCIP scip,
GRAPH g,
int  t,
int  s,
int  ets 
)

contract ancestors of an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem

Parameters
scipSCIP data structure
gthe graph
ttail node to be contracted (surviving node)
shead node to be contracted
etsedge from t to s or -1

Definition at line 2352 of file graph_pcbase.c.

References EAT_LAST, graph_edge_getAncestors(), GRAPH::head, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::pcancestors, SCIP_CALL, SCIP_OKAY, and SCIPintListNodeAppendCopy().

Referenced by contractEdgeNoFixedEnd(), and mwContract0WeightVertices().

◆ graph_pc_contractEdge()

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

contract an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem

Parameters
scipSCIP data structure
gthe graph
solnodesolution nodes or NULL
ttail node to be contracted (surviving node)
shead node to be contracted
term4offsetterminal to add offset to

Definition at line 2385 of file graph_pcbase.c.

References contractEdgeNoFixedEnd(), contractEdgeWithFixedEnd(), EAT_LAST, GRAPH::extended, GRAPH::grad, graph_pc_isMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), GRAPH::head, Is_anyTerm, Is_term, mwKnotUpdateIncEdges(), GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIPdebugMessage, SCIPisEQ(), GRAPH::source, GRAPH::term, GRAPH::term2edge, and TERM2EDGE_NOTERM.

Referenced by graph_pc_contractEdgeUnordered(), mwContract0WeightVertices(), mwContractTerminalsChainWise(), mwContractTerminalsSimple(), mwReduceTermDeg1(), pcReduceTermDeg1(), pcReduceTermDeg2(), reduce_impliedProfitBasedRpc(), reduce_nv(), reduce_nvAdv(), and reduce_sl().

◆ graph_pc_contractEdgeUnordered()

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

contract an edge of (rooted) prize-collecting Steiner tree problem or maximum-weight connected subgraph problem; method decides whether to contract s into t or vice-versa. Offset is added to surviving node

Parameters
scipSCIP data structure
gthe graph
solnodesolution nodes or NULL
ttail node to be contracted
shead node to be contracted

Definition at line 2439 of file graph_pcbase.c.

References GRAPH::grad, graph_pc_contractEdge(), graph_pc_termIsNonLeafTerm(), SCIP_CALL, SCIP_OKAY, and GRAPH::source.

Referenced by pcContractWithAdjacentTerm().

◆ graph_pc_deleteTerm()

int graph_pc_deleteTerm ( SCIP scip,
GRAPH g,
int  term,
SCIP_Real offset 
)

◆ graph_pc_realDegree()

◆ graph_pc_getRoot2PtermEdge()

int graph_pc_getRoot2PtermEdge ( const GRAPH graph,
int  pseudoterm 
)

◆ graph_pc_nFixedTerms()

int graph_pc_nFixedTerms ( const GRAPH graph)

◆ graph_pc_nNonFixedTerms()

int graph_pc_nNonFixedTerms ( const GRAPH graph)

Returns number of non-fixed terminals. Note that it is equal to the number of the proper potential terminals if g->extended, because in this case the non-leaf terminals are not marked explicitly.

Parameters
graphthe graph

Definition at line 2549 of file graph_pcbase.c.

References graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_nFixedTerms(), NULL, and GRAPH::terms.

Referenced by computeSteinerTree_execPcMw(), graph_pc_getReductionRatios(), graph_pc_nProperPotentialTerms(), propgraphApplyImplicationsPcMw(), SCIPStpHeurLocalExtendPcMwImp(), and sepaspecial_pcimplicationsSeparate().

◆ graph_pc_nProperPotentialTerms()

int graph_pc_nProperPotentialTerms ( const GRAPH graph)

returns number of proper potential terminals (potential terminals excluding non-leaf terminals)

Parameters
graphthe graph

Definition at line 2582 of file graph_pcbase.c.

References GRAPH::extended, graph_pc_isPcMw(), graph_pc_nNonFixedTerms(), graph_pc_nNonLeafTerms(), and NULL.

Referenced by graph_printInfo(), graph_printInfoReduced(), graph_transRpc2SpgTrivial(), graph_transRpcGetSpg(), reduce_redLoopPc(), rpcTryFullReduce(), sepaspecial_pcimplicationsInit(), sepaspecial_pcimplicationsSeparate(), and solstp_isValid().

◆ graph_pc_nNonLeafTerms()

int graph_pc_nNonLeafTerms ( const GRAPH graph)

◆ graph_pc_getTwinTerm()

◆ graph_pc_costsEqualOrgCosts()

SCIP_Bool graph_pc_costsEqualOrgCosts ( SCIP scip,
const GRAPH graph,
const SCIP_Real edgecosts 
)

are the given costs equal to the original edge costs?

Parameters
scipSCIP data structure
graphthe graph
edgecostsedge costs to be checked

Definition at line 1913 of file graph_pcbase.c.

References EQ, FALSE, graph_get_nEdges(), graph_pc_getOrgCosts(), SCIP_Bool, SCIP_CALL_ABORT, SCIP_Real, SCIPallocMemoryArray, SCIPfreeMemoryArray, and TRUE.

Referenced by solstp_pruneFromTmHeur(), and strongPruneSteinerTreePc().

◆ graph_pc_edgeIsExtended()

SCIP_Bool graph_pc_edgeIsExtended ( const GRAPH g,
int  edge 
)

is the edge part of the extended graph?

Parameters
gthe graph
edgeedge to be checked

Definition at line 1232 of file graph_pcbase.c.

References GRAPH::cost, EQ, FALSE, FARAWAY, flipedge, graph_pc_isPcMw(), graph_pc_knotIsDummyTerm(), GRAPH::head, LT, GRAPH::tail, and TRUE.

Referenced by fixVarsExtendedRed(), getBoundchanges(), pathreplaceExec(), reduceFixedVars(), reduceLurk(), SCIPStpHeurSlackPruneRun(), and validateEdgestate().

◆ graph_pc_knotIsFixedTerm()

SCIP_Bool graph_pc_knotIsFixedTerm ( const GRAPH g,
int  node 
)

check whether node is fixed terminal

Parameters
gthe graph
nodenode to be checked

Definition at line 1257 of file graph_pcbase.c.

References GRAPH::cost, EAT_LAST, EQ, FARAWAY, graph_pc_isMw(), GRAPH::ieat, GRAPH::inpbeg, Is_term, GRAPH::prize, GRAPH::source, GRAPH::term, GRAPH::term2edge, and TERM2EDGE_FIXEDTERM.

Referenced by addToCandidates(), applyBranchHistoryToGraph(), collectFixedTerminals(), collectRoots(), computeSteinerTree_allFixedTermsAreReached(), computeSteinerTree_execRpcMw(), contractEdgeNoFixedEnd(), contractEdgeWithFixedEnd(), createVariables(), daOrderRoots(), daPcFindRoots(), findRootsMark(), findSolRPcMw(), getBiasedMw(), getBiasedPc(), graph_copyData(), graph_knot_printInfo(), graph_path_st_pcmw_extendBiased(), graph_path_st_pcmw_full(), graph_path_st_rpcmw(), graph_pc_2org(), graph_pc_2trans(), graph_pc_contractEdge(), graph_pc_deleteTerm(), graph_pc_enforceNode(), graph_pc_evalTermIsNonLeaf(), graph_pc_fixedTermToNonTerm(), graph_pc_getBiased(), graph_pc_knotHasMaxPrize(), graph_pc_knotIsDummyTerm(), graph_pc_knotToFixedTerm(), graph_pc_nFixedTerms(), graph_pc_nonTermToFixedTerm(), graph_pc_realDegree(), graph_pc_subtractPrize(), graph_pc_term2edgeIsConsistent(), graph_pc_termIsNonLeafTerm(), graph_pc_termToNonLeafTerm(), graph_pc_termToNonTerm(), graph_transRpcGetSpg(), graph_valid(), graph_validInput(), graph_voronoiWithRadius(), graph_writeStp(), graphisValidPcMw(), insertionGetCandidateEdges(), isLastTerm(), mwContractTerminalsChainWise(), mwContractTerminalsSimple(), mwReduceTermDeg1(), pcmwGetStartNodes(), pcmwReduceTerm0Prize(), pcmwUpdate(), pcReduceTermDeg1(), pcReduceTermDeg2(), pcsolMarkGraphNodes(), pcsolMarkGraphNodes_csr(), propgraphApplyImplicationsPcMw(), propgraphDeleteNode(), propgraphFixNode(), pseudodeleteNodeIsPromising(), reduce_bd34(), reduce_bound(), reduce_identifyNonLeafTerms(), reduce_impliedProfitBasedRpc(), reduce_simple_mw(), reduce_simple_pc(), reduce_sl(), reduce_unconnectedRpcRmwInfeas(), reduceRootedProb(), reroot(), runTmPcMW_mode(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalExtendPcMwImp(), SCIPStpHeurTMBuildTreePcMw(), sepaspecial_pcimplicationsInit(), solIsTrivialPcMw(), solstp_isValid(), solstp_pcConnectDummies(), stRpcmwInit(), and termDeleteExtension().

◆ graph_pc_knotIsPropPotTerm()

SCIP_Bool graph_pc_knotIsPropPotTerm ( const GRAPH g,
int  node 
)

◆ graph_pc_knotHasMaxPrize()

SCIP_Bool graph_pc_knotHasMaxPrize ( const GRAPH g,
int  i 
)

is there no vertex of higher prize?

Parameters
ggraph data structure
ithe node to be checked

Definition at line 1315 of file graph_pcbase.c.

References EQ, FARAWAY, graph_get_nNodes(), graph_pc_isPc(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), LT, nnodes, GRAPH::prize, SCIP_Real, STP_RPCSPG, and GRAPH::stp_type.

Referenced by delPseudoInit(), and delPseudoInitForCheck().

◆ graph_pc_knotIsDummyTerm()

SCIP_Bool graph_pc_knotIsDummyTerm ( const GRAPH g,
int  node 
)

check whether node is a dummy (pseudo) terminal

Parameters
gthe graph
nodenode to be checked

Definition at line 1344 of file graph_pcbase.c.

References GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), Is_pseudoTerm, Is_term, NULL, GRAPH::source, GRAPH::term, and TRUE.

Referenced by ansDeleteVertex(), ansProcessCandidate(), blctreeComputeBottlenecks(), blctreeComputeEdgesState(), buildsolgraph(), computeSteinerTree_execRpcMw(), createVariables(), cutNodesSetDfsRoot(), dapathsFixPotTerms(), extreduce_bottleneckMarkRootPath(), extreduce_edgeIsValid(), findSolPcMw1Term(), getBiasedMw(), getBiasedPc(), getBoundchanges(), getBoundchangesPcMW(), getOrgNodeToNodeMap(), graph_csr_build(), graph_csr_chgCosts(), graph_fixed_addNodePc(), graph_path_st_rpcmw(), graph_pc_edgeIsExtended(), graph_pc_enforceNode(), graph_pc_enforcePseudoTerm(), graph_pc_evalTermIsNonLeaf(), graph_pc_getNorgEdges(), graph_pc_getReductionRatios(), graph_pc_knotHasMaxPrize(), graph_pc_knotIsPropPotTerm(), graph_pc_markOrgGraph(), graph_pc_nonTermToFixedTerm(), graph_pseudoAncestors_addToNode(), graph_transPcGetSap(), graph_writeStp(), graphisValidPcMw(), impliedNodesAddTerm(), mwContractTerminalsChainWise(), mwKnotUpdateIncEdges(), mwReduceTermDeg1(), pathExendPrepare(), pcsolGetTrivialEdges(), pcsolMarkGraphNodes(), pcsolMarkGraphNodes_csr(), pcsubtreeDelete(), pcsubtreePruneForProfit(), propgraphApplyImplicationsPcMw(), propgraphDeleteEdge(), propgraphDeleteNode(), propgraphFixEdge(), propgraphFixNode(), pseudodeleteDeleteComputeCutoffs(), redcostGraphBuild(), redcostGraphMark(), redcosts_forLPget(), reduce_ans(), reduce_ansAdv(), reduce_ansAdv2(), reduce_applyPseudoDeletions(), reduce_daSlackPrune(), reduce_simple_mw(), SCIPStpHeurTMBuildTreePcMw(), sdprofitBuild(), sdprofitBuild1stOnly(), shortestpath_computeSteinerTreePcMw(), shortestpath_computeSteinerTreePcMwFull(), shortestpath_computeSteinerTreeRpcMw(), solgraphAdaptForPcMw(), solstp_pcConnectDummies(), strongPruneSteinerTreePc(), and strongPruneSteinerTreePc_csr().

◆ graph_pc_termIsNonLeafTerm()

◆ graph_pc_knotIsNonLeafTerm()

◆ graph_pc_evalTermIsNonLeaf()

SCIP_Bool graph_pc_evalTermIsNonLeaf ( SCIP scip,
const GRAPH g,
int  term 
)

◆ graph_pc_term2edgeIsConsistent()

◆ graph_pc_transOrgAreConistent()

SCIP_Bool graph_pc_transOrgAreConistent ( SCIP scip,
const GRAPH graph,
SCIP_Bool  verbose 
)

transformed problem consistent to original one? Call only for extended graph

Parameters
scipSCIP data structure
graphthe graph
verbosebe verbose?

Definition at line 980 of file graph_pcbase.c.

References GRAPH::cost, GRAPH::cost_org_pc, EAT_FREE, GRAPH::edges, GRAPH::extended, FALSE, FARAWAY, graph_edge_isBlocked(), graph_edge_printInfo(), graph_pc_isPcMw(), GRAPH::head, Is_nonleafTerm, GRAPH::oeat, GRAPH::prize, SCIP_Real, SCIPisEQ(), SCIPisGE(), SCIPisLT(), GRAPH::term, and TRUE.

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

◆ graph_pc_getPosPrizeSum()

SCIP_Real graph_pc_getPosPrizeSum ( SCIP ,
const GRAPH  
)

◆ graph_pc_isPc()

SCIP_Bool graph_pc_isPc ( const GRAPH g)

is this graph a prize-collecting variant?

Parameters
gthe graph

Definition at line 2463 of file graph_pcbase.c.

References NULL, STP_PCSPG, STP_RPCSPG, and GRAPH::stp_type.

Referenced by blctreeBuildNodeMap(), blctreeComputeBottlenecks(), blctreeComputeEdgesState(), blockEdgesWithGlobalFixings(), bottleneckGetDist(), bottleneckMarkEqualityEdges(), closeNodesRunCompute(), computeSteinerTree(), computeSteinerTree_tryConnectNodePcMw(), computeSteinerTreeRedCostsPcMw(), dbgBottleneckFromLeafIsDominated(), delPseudoDeleteVertex(), distCloseNodesCompute(), distGetRestricted(), extInitRedCostArraysPc(), extInnerNodeAdd(), extInnerNodeRemoveTop(), extProbIsPc(), extreduce_bottleneckMarkRootPath(), extreduce_checkComponent(), extreduce_deleteArcs(), extreduce_deleteEdges(), extreduce_deleteGeneralStars(), extreduce_distDataInit(), extreduce_mstLevelHorizontalAdd(), extreduce_mstLevelHorizontalAddEmpty(), extreduce_mstLevelVerticalAddEmpty(), extreduce_mstLevelVerticalAddLeaf(), extreduce_pcdataIsClean(), extreduce_pseudoDeleteNodes(), extreduce_sdshorizontalInSync(), extreduce_sdsTopInSync(), extreduce_sdsverticalInSync(), extreduce_spgCheck3ComponentSimple(), extreduce_treeRecompCosts(), extStackAddCompsExpanded(), extTreeRuleOutSingletonImplied(), fixVarsRedbased(), getBiasedPc(), getEdgeCostUnbiased(), getKeyPathsStar(), graph_copyData(), graph_dijkLimited_initPcShifts(), graph_pack(), graph_path_st_pcmw(), graph_pc_2org(), graph_pc_2trans(), graph_pc_enforceNonLeafTerm(), graph_pc_finalizeSubgraph(), graph_pc_getBiased(), graph_pc_getOrgCostsCsr(), graph_pc_initSubgraph(), graph_pc_knotHasMaxPrize(), graph_pc_shiftNonLeafCosts(), graph_pc_solGetObj(), graph_pc_subtractPrize(), graph_pc_termToNonTerm(), graph_pc_updateSubgraphEdge(), graph_printInfo(), graph_printInfoReduced(), graph_transPcGetSap(), graph_voronoiRepair(), graph_voronoiTerms(), graph_voronoiWithDist(), initCostOrgPc(), insertionInitInsert(), localKeyVertexHeuristics(), localVertexInsertion(), mstCompLeafGetSDs(), mstCompLeafGetSDsToAncestors(), mstCompLeafToAncestorsBiasedRuleOut(), mstCompRuleOut(), mstLevelHorizontalAddSds(), mstLevelLeafExit(), mstLevelLeafInit(), mstLevelLeafTryExtMst(), pcmwSetEdgeCosts(), pcmwUpdateBestSol_csrInSync(), pcsubtreePruneForProfit(), prInit(), pseudodeleteBiasedIsPromising(), pseudodeleteDeleteComputeCutoffs(), pseudodeleteDeleteNode(), pseudodeleteNodeIsPromising(), reduce_applyPseudoDeletions(), reduce_bd34(), reduce_bound(), reduce_da(), reduce_daPcMw(), reduce_getMinNreductions(), reduce_identifyNonLeafTerms(), reduce_removeDeg0NonLeafTerms(), reduce_simple_pc(), reduce_sl(), reduce_sollocalRebuildTry(), reduce_unconnected(), reduceExact(), runTmPcMW(), runTmPcMW_mode(), SCIP_DECL_HEUREXEC(), selectBranchingVertexBySol(), solstp_isValid(), solstp_pcGetObjCsr(), solstp_prune(), solstp_pruneFromTmHeur(), solstp_pruneFromTmHeur_csr(), spg3StarNeighborRuleOut(), spg4VerticesRuleOut(), stpsol_pruningIsPossible(), strongPruneSteinerTreePc_csr(), tmBaseInit(), and useRedcostdata().

◆ graph_pc_isMw()

◆ graph_pc_isPcMw()

SCIP_Bool graph_pc_isPcMw ( const GRAPH g)

is this graph a prize-collecting or maximum-weight variant?

Parameters
gthe graph

Definition at line 2487 of file graph_pcbase.c.

References NULL, STP_BRMWCSP, STP_MWCSP, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, and GRAPH::stp_type.

Referenced by addRedsol(), applyBranchHistoryToGraph(), applyEdgestateToProb(), blctreeBuildMst(), branchruleGetType(), buildsolgraph(), computeHistory(), computeHistoryPcMw(), computePertubedSol(), computeReducedProbSolution(), computeReducedProbSolutionBiased(), computeStarts(), computeSteinerTree(), computeSteinerTree_allFixedTermsAreReached(), computeSteinerTree_allPseudoTermsAreReached(), computeSteinerTree_execPcMw(), computeSteinerTree_execPcMwFull(), computeSteinerTreeDijk(), computeSteinerTreeDijkPcMw(), computeSteinerTreeRedCostsPcMw(), computeSteinerTreeSingleNode(), createVariables(), cutNodesSetDfsRoot(), cutNodesTreeBuildSteinerTree(), cutNodesTreeDeleteComponents(), daPcFindRoots(), delPseudoInit(), delPseudoInitForCheck(), dualascent_paths(), enumeration_findSolPcMw(), enumeration_isPossible(), extGetSd(), extGetSdPcUpdate(), extInit(), extreduce_checkArc(), extreduce_checkEdge(), extreduce_distDataInit(), extreduce_edgeIsValid(), extreduce_extPermaInit(), extreduce_init(), extreduce_mstbiasedCheck3NodeSimple(), extreduce_mstTopCompExtObjValid(), extreduce_mstTopCompInSync(), extreduce_mstTopCompObjValid(), extreduce_mstTopLevelBaseObjValid(), extTreeGetDirectedRedcostProper(), fixVarsExtendedRed(), fixVarsRedbased(), fixVarsRedbasedIsPromising(), getBoundaryPathCost(), getBoundaryPathCostPrized(), getBoundchanges(), getBoundchangesPcMW(), getEdgeCosts(), getEdgeReductionRatio(), getGraphStatesDirected(), getHighSolDegVertex(), getKeyPathReplaceCost(), getKeyPathsStar(), getKeyPathUpper(), getNewPrizeNode(), getOrgNodeToNodeMap(), getReductionRatios(), getReductionRatiosPcMw(), getSolObj(), getTmMode(), graph_copyData(), graph_csr_build(), graph_csr_chgCosts(), graph_edge_addSubgraph(), graph_edge_printInfo(), graph_edge_reinsert(), graph_fixed_addNodePc(), graph_fixed_moveNodePc(), graph_get4nextTTerms(), graph_getIsTermArray(), graph_init_dcsr(), graph_initHistory(), graph_initPseudoAncestorsSized(), graph_isMarked(), graph_knot_delPseudoAncestors(), graph_knot_printInfo(), graph_knot_replaceDeg2(), graph_mark(), graph_pack(), graph_path_st_pcmw(), graph_path_st_pcmw_extendOut(), graph_path_st_pcmw_full(), graph_pc_2org(), graph_pc_2trans(), graph_pc_deleteTerm(), graph_pc_edgeIsExtended(), graph_pc_enforceNode(), graph_pc_evalTermIsNonLeaf(), graph_pc_finalizeSubgraph(), graph_pc_fixedTermToNonTerm(), graph_pc_getBiased(), graph_pc_getOrgCosts(), graph_pc_getReductionRatios(), graph_pc_getTwinTerm(), graph_pc_initSubgraph(), graph_pc_knotChgPrize(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsPropPotTerm(), graph_pc_knotToNonTermProperty(), graph_pc_markOrgGraph(), graph_pc_nFixedTerms(), graph_pc_nNonFixedTerms(), graph_pc_nNonLeafTerms(), graph_pc_nonLeafTermIsEnforced(), graph_pc_nProperPotentialTerms(), graph_pc_realDegree(), graph_pc_solGetObj(), graph_pc_subtractPrize(), graph_pc_term2edgeIsConsistent(), graph_pc_termToNonLeafTerm(), graph_pc_termToNonTerm(), graph_pc_transOrgAreConistent(), graph_printEdgeConflicts(), graph_printInfo(), graph_printInfoReduced(), graph_pseudoAncestors_addToNode(), graph_sdStar(), graph_sdStarBiased(), graph_sdWalks(), graph_sdWalks_csr(), graph_sdWalksConnected(), graph_sdWalksExt(), graph_sdWalksExt2(), graph_sdWalksTriangle(), graph_subgraphExtract(), graph_subgraphReinsert(), graph_tpathsSetAll2(), graph_tpathsSetAll3(), graph_transPcGetRsap(), graph_valid(), graph_valid_ancestors(), graph_valid_pseudoAncestors(), graph_validInput(), graph_voronoiRepair(), graph_writeReductionRatioStats(), graph_writeReductionRatioStatsLive(), graph_writeStp(), graphisValidPcMw(), impliedNodesAddTerm(), initCostsAndPrioLP(), initPropAtFirstCall(), initReceivedSubproblem(), insertionGetCandidateEdges(), insertionInitInsert(), insertionRestoreTree(), isLastTerm(), localKeyVertexHeuristics(), localRun(), localVertexInsertion(), nodesolUpdate(), packNodes(), packPcMwInit(), pcBiasCostsDCSR(), pcmwGetNewEdgePrize(), pcmwGetSolRoot(), pcmwReduceTerm0Prize(), pcmwUpdate(), pcSdToNodeMark(), pcSdToNodeUnmark(), presolveStp(), probAllowsSolBranching(), propgraphApplyBoundchanges(), propgraphApplyImplicationsPcMw(), propgraphDeleteEdge(), propgraphDeleteNode(), propgraphFixEdge(), propgraphFixNode(), propgraphMarkFixedTermsPcMw(), prunegraphInit(), pruneSteinerTreePc(), pruneSteinerTreePc_csr(), pseudodeleteNodeIsPromising(), redcostGraphBuild(), redcostGraphMark(), redcosts_forLPget(), reduce_bd34(), reduce_bd34WithSd(), reduce_bdkWithSd(), reduce_bound(), reduce_contract0Edges(), reduce_dapaths(), reduce_daSlackPrune(), reduce_deleteConflictEdges(), reduce_extendedEdge(), reduce_impliedNodesGet(), reduce_impliedNodesRepair(), reduce_impliedProfitBased(), reduce_nonTerminalComponents(), reduce_sdStar(), reduce_sdStarPc(), reduce_sdStarPc2(), reduce_sdWalk(), reduce_sdWalk_csr(), reduce_sdWalkExt(), reduce_sdWalkExt2(), reduce_sdWalkTriangle(), reduce_solInit(), reduce_sollocalInit(), reduce_sollocalRebuildTry(), reduce_solPack(), reduceCheckEdge(), reduceFixedVars(), reduceLurk(), removeEdge(), replaceEdgeByPath(), reroot(), retransformReducedProbSolution(), ruleOutSubtree(), runTm(), runTmPcMW(), SCIP_DECL_CONSSEPALP(), SCIP_DECL_HEUREXEC(), SCIPprobdataCreateFromGraph(), SCIPprobdataProbIsAdversarial(), SCIPprobdataWriteSolution(), SCIPStpHeurAscendPruneRun(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurLocalExtendPcMwImp(), SCIPStpHeurLocalExtendPcMwOut(), SCIPStpHeurLurkPruneRun(), SCIPStpHeurRecExclude(), SCIPStpHeurSlackPruneRun(), SCIPStpHeurTMBuildTree(), SCIPStpHeurTMRun(), SCIPStpHeurTMRunLP(), sdprofitBuild(), sdprofitBuild1stOnly(), sdStarInit(), selectBranchingVertexByDegree(), selectBranchingVertexBySol(), sepaspecial_pcimplicationsInit(), setCostToOrgPc(), setCostToOrgPcPreState(), setParams(), shortestpath_computeSteinerTreePcMw(), shortestpath_computeSteinerTreePcMwFull(), shortestpath_pcInit(), solgraphSelectSolsDiff(), solhistory_computeHistory(), solIsTrivialPcMw(), solstp_convertCsrToGraph(), solstp_getObjBounded(), solstp_getObjCsr(), solstp_getOrg(), solstp_getTrivialSol(), solstp_isValid(), solstp_pcConnectDummies(), solstp_pcGetObjCsr(), solstp_pcGetSolRoot(), solstp_prune(), solstp_pruneFromTmHeur(), solstp_pruneFromTmHeur_csr(), strongPruneSteinerTreePc(), strongPruneSteinerTreePc_csr(), supergraphComputeMst(), treeDistsAreFlawed(), updateEdgestateFromRed(), updateEdgestateFromRedPcmw(), and validateEdgestate().

◆ graph_pc_isRootedPcMw()

SCIP_Bool graph_pc_isRootedPcMw ( const GRAPH g)

is this graph a rooted prize-collecting or rooted maximum-weight variant?

Parameters
gthe graph

Definition at line 2681 of file graph_pcbase.c.

References NULL, STP_BRMWCSP, STP_RMWCSP, STP_RPCSPG, and GRAPH::stp_type.

Referenced by applyBranchHistoryToGraph(), blctreeBuildMst(), buildsolgraph(), collectFixedTerminals(), collectRoots(), computeHistoryPcMw(), computeStarts(), computeSteinerTree_execPcMw(), computeSteinerTree_execPcMwFull(), computeSteinerTree_execRpcMw(), computeSteinerTreeSingleNode(), computeSteinerTreeTM(), contractEdgeWithFixedEnd(), createInitialCuts(), cutNodesSetDfsRoot(), daOrderRoots(), dapathsFixPotTerms(), daPcFindRoots(), daRoundExit(), daRoundInit(), daRpcmwDeleteTermIncidents(), dualascent_paths(), enumeration_findSolPcMw(), enumeration_isPossible(), findSolPcMw(), findSolRPcMw(), fixVarsExtendedRed(), getBiasedMw(), getBiasedPc(), graph_copyData(), graph_dijkLimited_initPcShifts(), graph_isMarked(), graph_mark(), graph_pack(), graph_path_st_pcmw(), graph_path_st_pcmw_full(), graph_path_st_rpcmw(), graph_pc_contractEdge(), graph_pc_enforceNode(), graph_pc_enforceNonLeafTerm(), graph_pc_evalTermIsNonLeaf(), graph_pc_getReductionRatios(), graph_pc_knotIsDummyTerm(), graph_pc_knotToFixedTerm(), graph_pc_markOrgGraph(), graph_pc_nFixedTerms(), graph_pc_nNonFixedTerms(), graph_pc_nonTermToFixedTerm(), graph_pc_realDegree(), graph_pc_term2edgeIsConsistent(), graph_transPcGetRsap(), graph_transPcmw2rooted(), graphisValidPcMw(), initReceivedSubproblem(), insertionGetCandidateEdges(), isLastTerm(), isMaxprizeTerm(), localKeyVertexHeuristics(), mwContractTerminalsChainWise(), mwContractTerminalsSimple(), packNodes(), packPcMwVanished(), pcmwFindMax2Terms(), pcmwGetSolRoot(), pcmwGetStartNodes(), pcmwUpdate(), pcsolMarkGraphNodes(), pcsolMarkGraphNodes_csr(), propgraphApplyBoundchanges(), propgraphFixNode(), propgraphMarkFixedTermsPcMw(), propgraphPruneUnconnected(), pruneSteinerTreePc(), pruneSteinerTreePc_csr(), redcostGraphBuild(), redcostGraphMark(), redcosts_initializeDistances(), redLoopInnerMw(), redLoopInnerPc(), reduce_boundMw(), reduce_da(), reduce_dapaths(), reduce_daSlackPrune(), reduce_redLoopMw(), reduce_simple_mw(), reduce_unconnectedRpcRmwInfeas(), reduceRootedProb(), runTmPcMW_mode(), SCIPStpHeurLocalExtendPcMw(), SCIPStpHeurPruneRun(), SCIPStpHeurTMBuildTreePcMw(), shortestpath_computeSteinerTreePcMw(), shortestpath_computeSteinerTreeRpcMw(), solgraphAdaptForPcMw(), solIsTrivialPcMw(), solstp_getOrg(), solstp_isValid(), solstp_pcConnectDummies(), solstp_pcGetSolRoot(), stptest_graphSetUpRpcOrg(), strongPruneSteinerTreePc(), termDeleteExtension(), updateEdgestateFromRedPcmw(), updatePropgraph(), and updateSolution().

◆ graph_pc_isUnrootedPcMw()

SCIP_Bool graph_pc_isUnrootedPcMw ( const GRAPH g)

is this graph a un-rooted prize-collecting or rooted maximum-weight variant?

Parameters
gthe graph

Definition at line 2669 of file graph_pcbase.c.

References NULL, STP_MWCSP, STP_PCSPG, and GRAPH::stp_type.

Referenced by reduce_sl(), SCIP_DECL_RELAXEXEC(), SCIPStpHeurTMBuildTreePcMw(), sdprofitBuild(), and sdprofitBuild1stOnly().

◆ graph_pc_solGetObj()

SCIP_Real graph_pc_solGetObj ( SCIP scip,
const GRAPH g,
const int *  soledge,
SCIP_Real  offset 
)

compute solution value for given edge-solution array (CONNECT/UNKNOWN) and offset, takes prizes into account!

Parameters
scipSCIP data structure
gthe graph
soledgesolution
offsetoffset

Definition at line 2603 of file graph_pcbase.c.

References CONNECT, GRAPH::cost, GRAPH::extended, graph_get_nEdges(), graph_get_nNodes(), graph_pc_getNonLeafTermOffset(), graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_knotIsNonLeafTerm(), nnodes, GRAPH::prize, SCIP_CALL_ABORT, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGT(), and solstp_setVertexFromEdge().

Referenced by computeSteinerTree(), and getSolObj().

◆ graph_path_exit()

◆ graph_path_exec()

◆ graph_pathInLimitedExec()

void graph_pathInLimitedExec ( const GRAPH g,
const SCIP_Real edges_cost,
const SCIP_Bool nodes_abort,
int  startnode,
DIJK dijkdata,
SCIP_Real abortdistance 
)

limited Dijkstra on incoming edges

Parameters
ggraph data structure
edges_costedge cost
nodes_abortnodes to abort at
startnodestart
dijkdataDijkstra data
abortdistancedistance at which abort happened

Definition at line 610 of file graph_path.c.

References CONNECT, dijkstra_data::dheap, FARAWAY, graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_knot_isInRange(), GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, LT, dijkstra_data::node_distance, dijkstra_data::node_visited, dijkstra_data::nvisits, dijkstra_heap::position, SCIP_Real, dijkstra_heap::size, GRAPH::tail, TRUE, UNKNOWN, and dijkstra_data::visitlist.

Referenced by dapathsRunShortestPaths().

◆ graph_path_execX()

void graph_path_execX ( SCIP scip,
const GRAPH g,
int  start,
const SCIP_Real cost,
SCIP_Real pathdist,
int *  pathedge 
)

Dijkstra's algorithm starting from node 'start'

Parameters
scipSCIP data structure
ggraph data structure
startstart vertex
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)

Definition at line 905 of file graph_path.c.

References CONNECT, correctX(), EAT_LAST, FARAWAY, GRAPH::head, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIPisGT(), and UNKNOWN.

Referenced by buildTmAllSp(), computeStarts(), computeTransVoronoi(), getRedCost2ndNextDistances(), redcosts_initializeDistances(), reduce_boundHopR(), reduce_boundHopRc(), reduce_daPcMw(), reduce_daSlackPrune(), and reduce_rpt().

◆ graph_path_invroot()

void graph_path_invroot ( SCIP scip,
const GRAPH g,
int  start,
const SCIP_Real cost,
SCIP_Real pathdist,
int *  pathedge 
)

Dijkstra on incoming edges until root is reached

Parameters
scipSCIP data structure
ggraph data structure
startstart vertex
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)

Definition at line 973 of file graph_path.c.

References CONNECT, correctX(), EAT_LAST, FARAWAY, GRAPH::ieat, GRAPH::inpbeg, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, NULL, GRAPH::path_heap, GRAPH::path_state, SCIP_Real, SCIPisGT(), GRAPH::source, GRAPH::tail, and UNKNOWN.

◆ graph_path_st()

void graph_path_st ( const GRAPH g,
const SCIP_Real cost,
SCIP_Real pathdist,
int *  pathedge,
int  start,
STP_Bool connected 
)

Find a directed tree rooted in node 'start' and spanning all terminals

Parameters
ggraph data structure
costedgecosts
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1199 of file graph_path.c.

References correctX(), EAT_LAST, FALSE, FARAWAY, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijk().

◆ graph_path_st_dc()

SCIP_RETCODE graph_path_st_dc ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
SCIP_Real pathdist,
int *  pathedge,
int  start,
STP_Bool connected,
int *  result,
STP_Bool solFound 
)

For DCSTP: Find a directed tree rooted in node 'start' and spanning all terminals, while respecting degree constraints

Parameters
scipSCIP
ggraph data structure
costedgecosts
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree
resultsolution
solFoundpointer to store whether solution was found

Definition at line 1299 of file graph_path.c.

References BMScopyMemoryArray, FALSE, FARAWAY, graph_get_nEdges(), graph_get_nNodes(), graph_knot_isInRange(), graph_knot_printInfo(), Is_term, GRAPH::maxdeg, nnodes, GRAPH::path_heap, GRAPH::path_state, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, sdDcExtendTree(), STP_DCSTP, GRAPH::stp_type, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

◆ graph_path_st_rpcmw()

void graph_path_st_rpcmw ( GRAPH g,
SCIP_Real orderedprizes,
int *  orderedprizes_id,
const SCIP_Real cost,
const SCIP_Real prize,
SCIP_Real pathdist,
int *  pathedge,
int  start,
STP_Bool connected 
)

!!!LEGACY CODE!!! Shortest path heuristic for the RMWCSP and RPCSPG Find a directed tree rooted in node 'start' and connecting all terminals as well as all positive vertices (as long as this is profitable).

Parameters
ggraph data structure
orderedprizeslegacy code
orderedprizes_idlegacy code
costedge costs
prize(possibly biased) prize
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1988 of file graph_path.c.

References correctX(), GRAPH::extended, FARAWAY, GE, graph_pc_isRootedPcMw(), graph_pc_knotIsDummyTerm(), graph_pc_knotIsFixedTerm(), graph_pc_knotIsNonLeafTerm(), GRAPH::head, Is_anyTerm, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, stortest_path_prizecollecting::maxoutprize, nearestX(), nnodes, nterms, GRAPH::oeat, stortest_path_prizecollecting::orderedprizes, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), SCIPdebugMessage, shortestpath_pcConnectNode(), shortestpath_pcReset(), stRpcmwInit(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijkPcMw().

◆ graph_path_st_brmwcs()

SCIP_RETCODE graph_path_st_brmwcs ( SCIP scip,
GRAPH g,
const SCIP_Real prize,
SCIP_Real pathdist,
int *  pathedge,
int  start,
STP_Bool connected,
SCIP_Bool solfound 
)

todo refactor, was copied from Henriette's branch

Parameters
scipSCIP data structure
ggraph data structure
prize(possibly biased) prize
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree
solfoundcould a solution be found?

Definition at line 2146 of file graph_path.c.

References GRAPH::budget, correctX(), GRAPH::costbudget, EAT_LAST, FALSE, FARAWAY, graph_pc_markOrgGraph(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), SCIP_CALL, SCIP_ERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijkBMw().

◆ graph_path_st_pcmw()

void graph_path_st_pcmw ( GRAPH g,
SCIP_Real orderedprizes,
int *  orderedprizes_id,
const SCIP_Real cost,
const SCIP_Real prize,
SCIP_Bool  costIsBiased,
SCIP_Real pathdist,
int *  pathedge,
int  start,
STP_Bool connected 
)

!!!LEGACY CODE!!! Find a tree rooted in node 'start' and connecting positive vertices as long as this is profitable. Note that this function overwrites g->mark.

Parameters
ggraph data structure
orderedprizeslegacy code
orderedprizes_idlegacy code
costedge costs
prize(possibly biased) prize
costIsBiasedis cost biased?
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1430 of file graph_path.c.

References correctX(), EAT_LAST, GRAPH::extended, FALSE, FARAWAY, graph_pc_isPc(), graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsNonLeafTerm(), GRAPH::head, Is_pseudoTerm, GRAPH::knots, LT, GRAPH::mark, stortest_path_prizecollecting::maxoutprize, nearestX(), nnodes, nterms, GRAPH::oeat, stortest_path_prizecollecting::orderedprizes, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIP_Bool, SCIP_Real, SCIPdebugMessage, shortestpath_pcConnectNode(), shortestpath_pcReset(), stPcmwConnectNode(), stPcmwInit(), GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijkPcMw().

◆ graph_path_st_pcmw_full()

void graph_path_st_pcmw_full ( GRAPH g,
const SCIP_Real cost,
SCIP_Real pathdist,
int *  pathedge,
int  start,
STP_Bool connected 
)

Find a tree rooted in node 'start' and connecting all positive vertices. Note that this function overwrites g->mark.

Parameters
ggraph data structure
costedge costs
pathdistdistance array (on vertices)
pathedgepredecessor edge array (on vertices)
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1608 of file graph_path.c.

References correctX(), GRAPH::extended, graph_pc_isPcMw(), graph_pc_isRootedPcMw(), graph_pc_knotIsFixedTerm(), GT, GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, resetX(), stPcmwInit(), stRpcmwInit(), GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by computeSteinerTreeDijkPcMwFull().

◆ graph_path_st_pcmw_reduce()

void graph_path_st_pcmw_reduce ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
SCIP_Real tmpnodeweight,
int *  result,
int  start,
STP_Bool connected 
)

Reduce given solution Note that this function overwrites g->mark.

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
tmpnodeweightnode weight array
resultincoming arc array
startstart vertex
connectedarray to mark whether a vertex is part of computed Steiner tree

Definition at line 1556 of file graph_path.c.

References CONNECT, EAT_LAST, FALSE, GRAPH::head, Is_term, NULL, GRAPH::oeat, GRAPH::outbeg, SCIPfreeBufferArray, SCIPisGE(), GRAPH::term, and UNKNOWN.

◆ graph_path_st_pcmw_extend()

void graph_path_st_pcmw_extend ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
SCIP_Bool  breakearly,
PATH path,
STP_Bool connected,
SCIP_Bool extensions 
)

greedy extension of a given tree for PC or MW problems

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
breakearlyfinish computation early if no profitable extension possible?
pathshortest paths data structure
connectedarray to mark whether a vertex is part of computed Steiner tree
extensionsextensions performed?

Definition at line 1706 of file graph_path.c.

References shortest_path::dist, EAT_LAST, shortest_path::edge, GRAPH::extended, FALSE, FARAWAY, FSP_MODE, GRAPH::grad, GRAPH::head, Is_pseudoTerm, Is_term, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, pathheapCorrect(), pathheapGetNearest(), pathheapReset(), GRAPH::prize, SCIP_Real, SCIPisGE(), SCIPisGT(), GRAPH::source, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurLocalExtendPcMw().

◆ graph_path_st_pcmw_extendBiased()

void graph_path_st_pcmw_extendBiased ( SCIP scip,
GRAPH g,
const SCIP_Real cost,
const SCIP_Real prize,
PATH path,
STP_Bool connected,
SCIP_Bool extensions 
)

greedy extension of a given tree for PC or MW problems; path[i].edge needs to be initialized

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
prize(possibly biased) prize
pathshortest paths data structure with .edge initialized
connectedarray to mark whether a vertex is part of computed Steiner tree
extensionsextensions performed?

Definition at line 1845 of file graph_path.c.

References shortest_path::dist, shortest_path::edge, GRAPH::extended, FALSE, FARAWAY, FSP_MODE, graph_pc_knotIsFixedTerm(), graph_pc_markOrgGraph(), GRAPH::head, Is_pseudoTerm, GRAPH::knots, GRAPH::mark, nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, pathheapCorrect(), pathheapGetNearest(), pathheapReset(), SCIP_Real, SCIPisGE(), GRAPH::source, GRAPH::tail, GRAPH::term, TRUE, and UNKNOWN.

◆ graph_path_st_pcmw_extendOut()

void graph_path_st_pcmw_extendOut ( SCIP scip,
const GRAPH g,
int  start,
STP_Bool connected,
SCIP_Real dist,
int *  pred,
STP_Bool connected_out,
DHEAP dheap,
SCIP_Bool success 
)

extension heuristic

Parameters
scipSCIP data structure
ggraph data structure
startstart
connectedarray to mark whether a vertex is part of computed Steiner tree
distdistances array
predpredecessor node
connected_outarray for internal stuff
dheapDijkstra heap
successextension successful?

Definition at line 1051 of file graph_path.c.

References csr_storage::cost, GRAPH::csr_storage, GRAPH::extended, FALSE, FARAWAY, graph_heap_clean(), graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_pc_isPcMw(), csr_storage::head, Is_term, GRAPH::knots, nnodes, dijkstra_heap::position, GRAPH::prize, SCIP_Real, SCIPisGE(), SCIPisGT(), dijkstra_heap::size, csr_storage::start, GRAPH::term, TRUE, and UNKNOWN.

Referenced by SCIPStpHeurLocalExtendPcMwOut().

◆ graph_pathHeapAdd()

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

◆ graph_path_PcMwSd()

void graph_path_PcMwSd ( SCIP scip,
const GRAPH g,
PATH path,
SCIP_Real cost,
SCIP_Real  distlimit,
int *  pathmaxnode,
int *  heap,
int *  state,
int *  stateblock,
int *  memlbl,
int *  nlbl,
int  tail,
int  head,
int  limit 
)

limited Dijkstra for PCSTP, taking terminals into account

Parameters
scipSCIP data structure
ggraph data structure
pathshortest paths data structure
costedge costs
distlimitdistance limit of the search
pathmaxnodemaximum weight node on path
heaparray representing a heap
statearray to indicate whether a node has been scanned during SP calculation
stateblockarray to indicate whether a node has been scanned during previous SP calculation
memlblarray to save labelled nodes
nlblnumber of labelled nodes
tailtail of the edge
headhead of the edge
limitmaximum number of edges to consider during execution

Definition at line 788 of file graph_path.c.

References CONNECT, shortest_path::dist, EAT_LAST, FALSE, FSP_MODE, GRAPH::grad, GRAPH::head, Is_term, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, pathheapCorrect(), pathheapGetNearest(), GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisLE(), STP_MWCSP, GRAPH::stp_type, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_sdsp(), and sdGetSdPcMw().

◆ graph_path_init()

◆ graph_path_exists()

SCIP_Bool graph_path_exists ( const GRAPH g)

existing?

Parameters
ggraph data structure

Definition at line 497 of file graph_path.c.

References NULL, GRAPH::path_heap, and GRAPH::path_state.

Referenced by graph_free(), reduce_exec(), and substpsolver_solve().

◆ graph_sdPaths()

void graph_sdPaths ( const GRAPH g,
PATH path,
const SCIP_Real cost,
SCIP_Real  distlimit,
int *  heap,
int *  state,
int *  memlbl,
int *  nlbl,
int  tail,
int  head,
int  limit 
)

limited Dijkstra, stopping at terminals

Parameters
ggraph data structure
pathshortest paths data structure
costedge costs
distlimitdistance limit of the search
heaparray representing a heap
statearray to indicate whether a node has been scanned during SP calculation
memlblarray to save labelled nodes
nlblnumber of labelled nodes
tailtail of the edge
headhead of the edge
limitmaximum number of edges to consider during execution

Definition at line 684 of file graph_path.c.

References CONNECT, shortest_path::dist, FALSE, FARAWAY, FSP_MODE, GE, GRAPH::grad, graph_pc_isMw(), graph_typeIsUndirected(), GT, GRAPH::head, Is_term, GRAPH::mark, NULL, GRAPH::oeat, GRAPH::outbeg, pathheapCorrect(), pathheapGetNearest(), SCIP_Bool, GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_getSdByPaths(), reduce_sdsp(), and reduce_sdspSap().

◆ graph_add2ndTermPaths()

void graph_add2ndTermPaths ( const GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
PATH path2,
int *  vbase2,
int *  state2 
)

2nd next terminal to all non terminal nodes NOTE: legacy wrapper

Parameters
ggraph data structure
costedge costs
costrevreversed edge costs
path2path data structure (leading to first and second nearest terminal)
vbase2first and second nearest terminal to each non terminal
state2array to mark the state of each node during calculation

Definition at line 1482 of file graph_tpath.c.

References graph_get_nNodes(), graph_tpathsAdd2nd(), nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by boundPruneHeur(), boundPruneHeurMw(), reduce_bound(), reduce_boundHop(), reduce_boundMw(), and reduce_daPcMw().

◆ graph_add3rdTermPaths()

void graph_add3rdTermPaths ( const GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
PATH path3,
int *  vbase3,
int *  state3 
)

3rd next terminal to all non terminal nodes NOTE: legacy wrapper

Parameters
ggraph data structure
costedge costs
costrevreversed edge costs
path3path data structure (leading to first, second and third nearest terminal)
vbase3first, second and third nearest terminal to each non terminal
state3array to mark the state of each node during calculation

Definition at line 1501 of file graph_tpath.c.

References graph_get_nNodes(), graph_tpathsAdd3rd(), nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by boundPruneHeur(), and reduce_bound().

◆ graph_add4thTermPaths()

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

◆ graph_get2nextTermPaths()

void graph_get2nextTermPaths ( GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
PATH path2,
int *  vbase2,
int *  state2 
)

gets non-terminal shortest paths to 2 closest terminal for each non-terminal NOTE: legacy wrapper

Parameters
ggraph data structure
costedge costs
costrevreversed edge costs
path2path data structure (leading to first, second terminal)
vbase2first, second and third nearest terminal to each non terminal
state2array to mark the state of each node during calculation

Definition at line 1542 of file graph_tpath.c.

References graph_get_nNodes(), graph_tpathsSetAll2(), nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by getRedCost2ndNextDistances(), redcosts_initializeDistances(), and reduce_daSlackPrune().

◆ graph_get3nextTermPaths()

void graph_get3nextTermPaths ( GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
PATH path3,
int *  vbase3,
int *  state3 
)

gets non-terminal shortest paths to 3 closest terminal for each non-terminal NOTE: legacy wrapper

Parameters
ggraph data structure
costedge costs
costrevreversed edge costs
path3path data structure (leading to first, second and third nearest terminal)
vbase3first, second and third nearest terminal to each non terminal
state3array to mark the state of each node during calculation

Definition at line 1562 of file graph_tpath.c.

References graph_get_nNodes(), graph_tpathsSetAll3(), nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by redcosts_initializeDistances().

◆ graph_get4nextTermPaths()

void graph_get4nextTermPaths ( GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
PATH path4,
int *  vbase4,
int *  state4 
)

gets non-terminal shortest paths to 4 closest terminal for each non-terminal NOTE: legacy wrapper

Parameters
ggraph data structure
costedge costs
costrevreversed edge costs
path4path data struture (leading to first, second, third and fouth nearest terminal)
vbase4first, second and third nearest terminal to each non terminal
state4array to mark the state of each node during calculation

Definition at line 1582 of file graph_tpath.c.

References graph_get_nNodes(), graph_tpathsSetAll4(), nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by reduce_sd(), and reduce_sdPc().

◆ graph_get4nextTTerms()

SCIP_RETCODE graph_get4nextTTerms ( SCIP scip,
GRAPH g,
const SCIP_Real cost,
PATH path,
int *  vbase,
int *  heap,
int *  state 
)

get 4 close terminals to each terminal

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
pathpath data structure (leading to first, second, third and fourth nearest terminal)
vbasefirst, second and third nearest terminal to each non terminal
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 1601 of file graph_tpath.c.

References shortest_path::dist, EAT_LAST, GRAPH::edges, FARAWAY, graph_mark(), graph_pc_isPcMw(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nodes_to_terminal_paths::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPfreeBufferArray, GRAPH::tail, GRAPH::term, UNKNOWN, and utdist().

Referenced by reduce_bound(), and reduce_sdPc().

◆ graph_tpathsInit()

SCIP_RETCODE graph_tpathsInit ( SCIP scip,
GRAPH g,
TPATHS **  tpaths 
)

initializes TPATHS structure

Parameters
scipSCIP
ggraph NOTE: will mark the graph, thus not const :( terrible design
tpathsthe terminal paths

Definition at line 1682 of file graph_tpath.c.

References SCIP_CALL, SCIP_OKAY, STP_TPATHS_NTERMBASES, tpathsAlloc(), and tpathsBuild().

Referenced by reduce_sdInit(), testBiasedTerminalPathsTo4NextFound(), testTerminalPathsRepair(), testTerminalPathsRepair2(), testTerminalPathsRepair3(), and testTerminalPathsTo3NextFound().

◆ graph_tpathsInitBiased()

SCIP_RETCODE graph_tpathsInitBiased ( SCIP scip,
const SDPROFIT sdprofit,
GRAPH g,
TPATHS **  tpaths 
)

initializes biased TPATHS structure

Parameters
scipSCIP
sdprofitSD profit
ggraph NOTE: will mark the graph, thus not const :( terrible design
tpathsthe terminal paths

Definition at line 1700 of file graph_tpath.c.

References SCIP_CALL, SCIP_OKAY, STP_TPATHS_NTERMBASES, tpathsAlloc(), and tpathsBuildBiased().

Referenced by reduce_sdInitBiased(), reduce_sdInitBiasedBottleneck(), and testSdGraphStrongBiasedDistsAreValid().

◆ graph_tpathsRecomputeBiased()

SCIP_RETCODE graph_tpathsRecomputeBiased ( const SDPROFIT sdprofit,
GRAPH g,
TPATHS tpaths 
)

recomputes biased TPATHS structure

Parameters
sdprofitSD profit
ggraph NOTE: will mark the graph, thus not const :( terrible design
tpathsthe terminal paths

Definition at line 1776 of file graph_tpath.c.

References SCIP_OKAY, STP_TPATHS_NTERMBASES, and tpathsBuildBiased().

Referenced by reduce_impliedProfitBased(), and reduce_impliedProfitBasedRpc().

◆ graph_tpathsRepair()

SCIP_RETCODE graph_tpathsRepair ( SCIP scip,
int  edge,
SCIP_Bool  withEdgeReplacement,
const GRAPH g,
TPATHS tpaths 
)

repairs TPATHS structure for imminent edge deletion

Parameters
scipSCIP
edgeedge about to be eliminated
withEdgeReplacementwith edge replacement?
ggraph
tpathsthe terminal paths

Definition at line 1744 of file graph_tpath.c.

References graph_edge_isInRange(), graph_isMarked(), NULL, SCIP_CALL, SCIP_OKAY, STP_TPATHS_NTERMBASES, STP_Vectype, nodes_to_terminal_paths::termbases_org, tpathsRepair1st(), tpathsRepair2nd(), tpathsRepair3rd(), tpathsRepair4th(), tpathsRepairExit(), and tpathsRepairInit().

Referenced by reduce_sdRepair(), testTerminalPathsRepair(), testTerminalPathsRepair2(), and testTerminalPathsRepair3().

◆ graph_tpathsRepairSetUp()

◆ graph_tpathsFree()

◆ graph_tpathsPrintForNode()

void graph_tpathsPrintForNode ( const GRAPH g,
const SDPROFIT sdprofit,
const TPATHS tpaths,
int  node 
)

prints terminal paths from given node

Parameters
ggraph data structure
sdprofitSD bias for nodes or NULL
tpathsstorage for terminal paths
nodenode to start from

Definition at line 1793 of file graph_tpath.c.

References shortest_path::dist, graph_get_nNodes(), graph_knot_isInRange(), graph_knot_printInfo(), Is_term, nodes_to_terminal_paths::nnodes, STP_TPATHS_NTERMBASES, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, tpathsPrintPath(), and UNKNOWN.

◆ graph_tpathsGetProfitNodes()

void graph_tpathsGetProfitNodes ( SCIP scip,
const GRAPH g,
const TPATHS tpaths,
const SDPROFIT sdprofit,
int  start,
int  base,
STP_Vectype(int)  profitnodes 
)

gets nodes with positive profit on path

Parameters
scipSCIP
ggraph data structure
tpathsstorage for terminal paths
sdprofitSD bias for nodes
startstart vertex
basebase vertex (terminal)
profitnodesNOTE: needs to be of capacity at least g->knots!

Definition at line 1842 of file graph_tpath.c.

References shortest_path::edge, graph_edge_isInRange(), graph_get_nNodes(), graph_knot_isInRange(), GT, Is_term, GRAPH::knots, nodes_to_terminal_paths::nnodes, reduce_sdprofitGetProfit(), SCIP_Real, STP_TPATHS_NTERMBASES, StpVecClear, StpVecGetcapacity, StpVecGetSize, StpVecPushBack, GRAPH::tail, GRAPH::term, nodes_to_terminal_paths::termbases, and nodes_to_terminal_paths::termpaths.

Referenced by sdgraphUpdateDistgraphFromTpaths().

◆ graph_tpathsAdd1st()

void graph_tpathsAdd1st ( const GRAPH g,
const SCIP_Real cost,
const SDPROFIT sdprofit,
TPATHS tpaths 
)

Computes next terminal to all non-terminal nodes. Essentially a Voronoi diagram

Parameters
ggraph data structure
costedge costs
sdprofitSD bias for nodes or NULL
tpathsstorage for terminal paths

Definition at line 1932 of file graph_tpath.c.

References FARAWAY, graph_get_nNodes(), Is_term, GRAPH::mark, nodes_to_terminal_paths::nnodes, NULL, GRAPH::path_heap, nodes_to_terminal_paths::state, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, tpathsScan1st(), and UNKNOWN.

Referenced by graph_add1stTermPaths(), graph_tpathsSetAll2(), graph_tpathsSetAll3(), and graph_tpathsSetAll4().

◆ graph_tpathsAdd2nd()

void graph_tpathsAdd2nd ( const GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
const SDPROFIT sdprofit,
TPATHS tpaths 
)

computes 2nd next terminal to all non-terminal nodes

Parameters
ggraph data structure
costedge costs
costrevreversed edge costs
sdprofitSD bias for nodes or NULL
tpathsstorage for terminal paths

Definition at line 1987 of file graph_tpath.c.

References EAT_LAST, graph_get_nNodes(), GT, GRAPH::head, Is_term, GRAPH::mark, nodes_to_terminal_paths::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, pathheapCorrectDist(), SCIP_Real, nodes_to_terminal_paths::state, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, tpathsGetDistNew(), tpathsResetMembers(), and tpathsScan2nd().

Referenced by graph_add2ndTermPaths(), graph_tpathsSetAll2(), graph_tpathsSetAll3(), and graph_tpathsSetAll4().

◆ graph_tpathsAdd3rd()

void graph_tpathsAdd3rd ( const GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
const SDPROFIT sdprofit,
TPATHS tpaths 
)

computes 3rd next terminal to all non-terminal nodes

Parameters
ggraph data structure
costedge costs
costrevreversed edge costs
sdprofitSD bias for nodes or NULL
tpathsstorage for terminal paths

Definition at line 2044 of file graph_tpath.c.

References EAT_LAST, graph_get_nNodes(), GT, GRAPH::head, Is_term, GRAPH::mark, nodes_to_terminal_paths::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, pathheapCorrectDist(), SCIP_Real, nodes_to_terminal_paths::state, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, tpathsGetDistNew(), tpathsResetMembers(), and tpathsScan3rd().

Referenced by graph_add3rdTermPaths(), graph_tpathsSetAll3(), and graph_tpathsSetAll4().

◆ graph_tpathsAdd4th()

void graph_tpathsAdd4th ( const GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
const SDPROFIT sdprofit,
TPATHS tpaths 
)

computes 4th next terminal to all non-terminal nodes

Parameters
ggraph data structure
costedge costs
costrevreversed edge costs
sdprofitSD bias for nodes or NULL
tpathsstorage for terminal paths

Definition at line 2112 of file graph_tpath.c.

References EAT_LAST, graph_get_nNodes(), GT, GRAPH::head, Is_term, GRAPH::mark, nodes_to_terminal_paths::nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, pathheapCorrectDist(), SCIP_Real, nodes_to_terminal_paths::state, GRAPH::term, nodes_to_terminal_paths::termbases, nodes_to_terminal_paths::termpaths, tpathsGetDistNew(), tpathsResetMembers(), and tpathsScan4th().

Referenced by graph_add4thTermPaths(), and graph_tpathsSetAll4().

◆ graph_tpathsSetAll2()

void graph_tpathsSetAll2 ( GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
const SDPROFIT sdprofit,
TPATHS tpaths 
)

computes 2 next terminal to all non-terminal nodes

Parameters
ggraph data structure
costedge costs
costrevreversed edge costs
sdprofitSD bias for nodes or NULL
tpathsstorage for terminal paths

Definition at line 2180 of file graph_tpath.c.

References EPSILON, graph_get_nNodes(), graph_mark(), graph_pc_isPcMw(), graph_tpathsAdd1st(), graph_tpathsAdd2nd(), LE_FEAS_EPS, nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by graph_get2nextTermPaths().

◆ graph_tpathsSetAll3()

void graph_tpathsSetAll3 ( GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
const SDPROFIT sdprofit,
TPATHS tpaths 
)

computes 3 next terminal to all non-terminal nodes

Parameters
ggraph data structure
costedge costs
costrevreversed edge costs
sdprofitSD bias for nodes or NULL
tpathsstorage for terminal paths

Definition at line 2219 of file graph_tpath.c.

References EPSILON, graph_get_nNodes(), graph_mark(), graph_pc_isPcMw(), graph_tpathsAdd1st(), graph_tpathsAdd2nd(), graph_tpathsAdd3rd(), LE_FEAS_EPS, nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by graph_get3nextTermPaths().

◆ graph_tpathsSetAll4()

void graph_tpathsSetAll4 ( GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
const SDPROFIT sdprofit,
TPATHS tpaths 
)

computes 4 next terminal to all non-terminal nodes

Parameters
ggraph data structure
costedge costs
costrevreversed edge costs
sdprofitSD bias for nodes or NULL
tpathsstorage for terminal paths

Definition at line 2260 of file graph_tpath.c.

References graph_get_nNodes(), graph_mark(), graph_tpathsAdd1st(), graph_tpathsAdd2nd(), graph_tpathsAdd3rd(), graph_tpathsAdd4th(), LE, nodes_to_terminal_paths::nnodes, NULL, and nodes_to_terminal_paths::termpaths.

Referenced by graph_get4nextTermPaths(), testBiasedTerminalPathsTo4NextFound(), testTerminalPathsRepair(), testTerminalPathsRepair2(), testTerminalPathsRepair3(), testTerminalPathsTo3NextFound(), tpathsBuild(), and tpathsBuildBiased().

◆ graph_tpathsGetClosestTerm()

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

◆ graph_tpathsGet3CloseTerms()

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

◆ graph_tpathsGet4CloseTerms()

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

◆ graph_tpathsGet4CloseTermsLE()

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

Referenced by nsvEdgeGetTermDists().

◆ graph_sdStar()

void graph_sdStar ( SCIP scip,
const GRAPH g,
SCIP_Bool  with_zero_edges,
int  star_root,
int  edgelimit,
int *  star_base,
SCIP_Real dist,
int *  visitlist,
int *  nvisits,
DHEAP dheap,
STP_Bool visited,
SCIP_Bool success 
)

limited Dijkstra, stopping at terminals

Parameters
scipSCIP data structure
ggraph data structure
with_zero_edgestelling name
star_rootroot of the start
edgelimitmaximum number of edges to consider during execution
star_basestar base node, must be initially set to SDSTAR_BASE_UNSET
distdistances array, initially set to FARAWAY
visitliststores all visited nodes
nvisitsnumber of visited nodes
dheapDijkstra heap
visitedstores whether a node has been visited
successwill be set to TRUE iff at least one edge can be deleted

Definition at line 1137 of file graph_sdpath.c.

References CONNECT, dynamic_csr_storage::cost, GRAPH::dcsr_storage, eps, EQ, GRAPH::extended, FALSE, FARAWAY, graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_pc_isPcMw(), GT, dynamic_csr_storage::head, GRAPH::knots, LE, LT, GRAPH::mark, dijkstra_heap::position, dynamic_csr_storage::range, SCIP_Real, SCIPepsilon(), SDSTAR_BASE_UNSET, dijkstra_heap::size, TRUE, and UNKNOWN.

Referenced by reduce_sdStar(), reduce_sdStarPc(), and reduce_sdStarPc2().

◆ graph_sdStarBiased()

SCIP_RETCODE graph_sdStarBiased ( SCIP scip,
const GRAPH g,
const SDPROFIT sdprofit,
int  star_root,
int *  star_base,
DIJK dijkdata,
SCIP_Bool success 
)

limited Dijkstra with node bias

Parameters
scipSCIP data structure
ggraph data structure
sdprofitSD profit
star_rootroot of the start
star_basestar base node, must be initially set to SDSTAR_BASE_UNSET
dijkdataDijkstra data
successwill be set to TRUE iff at least one edge can be deleted

Definition at line 1289 of file graph_sdpath.c.

References CONNECT, dynamic_csr_storage::cost, GRAPH::dcsr_storage, dijkstra_data::dheap, dijkstra_data::edgelimit, eps, EQ, GRAPH::extended, FALSE, FARAWAY, graph_get_nNodes(), graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_pc_isPcMw(), GT, dynamic_csr_storage::head, LE, LT, GRAPH::mark, nnodes, dijkstra_data::node_distance, dijkstra_data::node_visited, dijkstra_data::nvisits, dijkstra_heap::position, dynamic_csr_storage::range, reduce_sdprofitGetProfit(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPepsilon(), SCIPfreeBufferArray, SDSTAR_BASE_UNSET, dijkstra_heap::size, TRUE, UNKNOWN, and dijkstra_data::visitlist.

Referenced by sdStarBiasedProcessNode().

◆ graph_sdCloseNodesBiased()

SCIP_RETCODE graph_sdCloseNodesBiased ( SCIP scip,
const GRAPH g,
const SDPROFIT sdprofit,
int  sourcenode,
DIJK dijkdata 
)

◆ graph_sdWalksConnected()

SCIP_Bool graph_sdWalksConnected ( SCIP scip,
const GRAPH g,
const int *  termmark,
const SCIP_Real cost,
const STP_Bool endpoint,
int  start,
int  edgelimit,
SCIP_Real dist,
int *  visitlist,
int *  nvisits,
STP_Bool visited,
SCIP_Bool  resetarrays 
)

modified Dijkstra along walks for PcMw

Parameters
scipSCIP data structure
ggraph data structure
termmarkterminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise)
costedge costs
endpointstores whether search should be ended at vertex
startstart vertex
edgelimitmaximum number of edges to consider during execution
distdistances array, initially set to FARAWAY
visitliststores all visited nodes
nvisitsnumber of visited nodes
visitedstores whether a node has been visited
resetarraysshould arrays be reset?

Definition at line 2285 of file graph_sdpath.c.

References CONNECT, EAT_LAST, GRAPH::extended, FALSE, FARAWAY, GRAPH::grad, graph_pc_isPcMw(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearestX(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::prize, SCIP_Real, SCIPisGT(), SCIPisLE(), sdwalkCorrectHeap(), sdwalkReset(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by daPcFindRoots(), findRootsMark(), and sepaspecial_pcimplicationsInit().

◆ graph_sdWalks()

SCIP_Bool graph_sdWalks ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
const int *  termmark,
SCIP_Real  distlimit,
int  start,
int  end,
int  edgelimit,
SCIP_Real dist,
int *  heap,
int *  state,
int *  visitlist,
int *  nvisits,
STP_Bool visited 
)

modified Dijkstra along walks for PcMw, returns special distance between start and end

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
termmarkterminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise)
distlimitdistance limit of the search
startstart
endend
edgelimitmaximum number of edges to consider during execution
distdistances array, initially set to FARAWAY
heaparray representing a heap
statearray to indicate whether a node has been scanned
visitliststores all visited nodes
nvisitsnumber of visited nodes
visitedstores whether a node has been visited

Definition at line 1564 of file graph_sdpath.c.

References CONNECT, EAT_LAST, GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), GRAPH::head, GRAPH::mark, MAX, nearestX(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisLE(), sdwalkCorrectHeap(), TRUE, and UNKNOWN.

Referenced by reduce_sdWalk().

◆ graph_sdWalks_csr()

SCIP_Bool graph_sdWalks_csr ( SCIP scip,
const GRAPH g,
const int *  termmark,
SCIP_Real  distlimit,
int  start,
int  end,
int  edgelimit,
SCIP_Real dist,
int *  visitlist,
int *  nvisits,
DHEAP dheap,
STP_Bool visited 
)

modified Dijkstra along walks for PcMw, returns special distance between start and end

Parameters
scipSCIP data structure
ggraph data structure
termmarkterminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise)
distlimitdistance limit of the search
startstart
endend
edgelimitmaximum number of edges to consider during execution
distdistances array, initially set to FARAWAY
visitliststores all visited nodes
nvisitsnumber of visited nodes
dheapDijkstra heap
visitedstores whether a node has been visited

Definition at line 1696 of file graph_sdpath.c.

References CONNECT, dynamic_csr_storage::cost, GRAPH::dcsr_storage, GRAPH::extended, FALSE, GRAPH::grad, graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_pc_isPcMw(), dynamic_csr_storage::head, GRAPH::knots, LT, GRAPH::mark, MAX, dijkstra_heap::position, GRAPH::prize, dynamic_csr_storage::range, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisLE(), dijkstra_heap::size, TRUE, and UNKNOWN.

Referenced by reduce_sdWalk_csr().

◆ graph_sdWalksTriangle()

SCIP_Bool graph_sdWalksTriangle ( SCIP scip,
const GRAPH g,
const int *  termmark,
const int *  stateprev,
SCIP_Real  distlimit,
int  start,
int  end,
int  edgelimit,
SCIP_Real prizeoffset,
SCIP_Real dist,
int *  visitlist,
int *  nvisits,
DHEAP dheap,
STP_Bool visited 
)

modified Dijkstra along walks for PcMw, returns special distance between start and end

Parameters
scipSCIP data structure
ggraph data structure
termmarkterminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise)
stateprevstate of previous run or NULL
distlimitdistance limit of the search
startstart
endend
edgelimitmaximum number of edges to consider during execution
prizeoffsetarray for storing prize offset or NULL
distdistances array, initially set to FARAWAY
visitliststores all visited nodes
nvisitsnumber of visited nodes
dheapDijkstra heap
visitedstores whether a node has been visited

Definition at line 1830 of file graph_sdpath.c.

References CONNECT, dynamic_csr_storage::cost, GRAPH::dcsr_storage, GRAPH::extended, FALSE, GRAPH::grad, graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_pc_isPcMw(), dynamic_csr_storage::head, GRAPH::knots, LT, GRAPH::mark, MAX, dijkstra_heap::position, GRAPH::prize, dynamic_csr_storage::range, SCIP_Bool, SCIP_Real, SCIPisLE(), SCIPisZero(), dijkstra_heap::size, TRUE, and UNKNOWN.

Referenced by reduce_sdWalkTriangle().

◆ graph_sdWalksExt()

SCIP_Bool graph_sdWalksExt ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
SCIP_Real  distlimit,
int  start,
int  end,
int  edgelimit,
int  maxnprevs,
SCIP_Real dist,
int *  prevterms,
int *  nprevterms,
int *  heap,
int *  state,
int *  visitlist,
int *  nvisits,
STP_Bool visited 
)

modified Dijkstra along walks for PcMw, returns special distance between start and end

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
distlimitdistance limit of the search
startstart
endend
edgelimitmaximum number of edges to consider during execution
maxnprevsmaximum number of previous terminals to save
distdistances array, initially set to FARAWAY
prevtermsprevious terminals
nprevtermsnumber of previous terminals
heaparray representing a heap
statearray to indicate whether a node has been scanned
visitliststores all visited nodes
nvisitsnumber of visited nodes
visitedstores whether a node has been visited

Definition at line 1999 of file graph_sdpath.c.

References CONNECT, EAT_LAST, GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), GRAPH::head, Is_term, GRAPH::mark, MAX, nearestX(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisLE(), sdwalkCorrectHeap(), sdwalkHasConflict(), sdwalkUpdate(), GRAPH::term, TRUE, and UNKNOWN.

Referenced by reduce_sdWalkExt().

◆ graph_sdWalksExt2()

SCIP_Bool graph_sdWalksExt2 ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
const int *  termmark,
SCIP_Real  distlimit,
int  start,
int  end,
int  edgelimit,
int  maxnprevs,
SCIP_Real dist,
int *  prevterms,
int *  nprevterms,
int *  prevNPterms,
int *  nprevNPterms,
int *  prevedges,
int *  nprevedges,
int *  heap,
int *  state,
int *  visitlist,
int *  nvisits,
STP_Bool visited 
)

modified Dijkstra along walks for PcMw, returns special distance between start and end

Parameters
scipSCIP data structure
ggraph data structure
costedge costs
termmarkterminal mark (2 for proper terminal, 1 for non-proper terminal, 0 otherwise)
distlimitdistance limit of the search
startstart
endend
edgelimitmaximum number of edges to consider during execution
maxnprevsmaximum number of previous terminals to save
distdistances array, initially set to FARAWAY
prevtermsprevious terminals
nprevtermsnumber of previous terminals
prevNPtermsprevious non-proper terminals
nprevNPtermsnumber of previous non-proper terminals
prevedgesprevious edges
nprevedgesnumber of previous edges
heaparray representing a heap
statearray to indicate whether a node has been scanned
visitliststores all visited nodes
nvisitsnumber of visited nodes
visitedstores whether a node has been visited

Definition at line 2140 of file graph_sdpath.c.

References CONNECT, EAT_LAST, GRAPH::extended, FALSE, GRAPH::grad, graph_pc_isPcMw(), GRAPH::head, GRAPH::mark, MAX, nearestX(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPisZero(), sdwalkCorrectHeap(), sdwalkGetdistnewEdge(), sdwalkGetdistnewPrize(), sdwalkHasConflict(), sdwalkUpdate2(), TRUE, and UNKNOWN.

Referenced by reduce_sdWalkExt2().

◆ graph_sdComputeCliqueStar()

◆ graph_vnoiInit()

SCIP_RETCODE graph_vnoiInit ( SCIP scip,
const GRAPH graph,
SCIP_Bool  useBufferArrays,
VNOI **  vnoi 
)

initializes VNOI structure

Parameters
scipSCIP
graphgraph data structure to work on
useBufferArraysshould buffer arrays be used?
vnoithe VNOI

Definition at line 1265 of file graph_vnoi.c.

References graph_get_nNodes(), nnodes, voronoi_storage::nnodes, voronoi_storage::nodes_base, voronoi_storage::nodes_dist, voronoi_storage::nodes_predEdge, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPallocMemory, SCIPallocMemoryArray, and voronoi_storage::usingBufferArrays.

Referenced by sdgraphBuildDistgraph().

◆ graph_vnoiFree()

void graph_vnoiFree ( SCIP scip,
VNOI **  vnoi 
)

◆ graph_vnoiCompute()

SCIP_RETCODE graph_vnoiCompute ( SCIP scip,
const GRAPH graph,
VNOI vnoi 
)

computes Voronoi region on given graph

Parameters
scipSCIP
graphgraph data structure to work on
vnoithe VNOI

Definition at line 1302 of file graph_vnoi.c.

References graph_get_nNodes(), graph_heap_create(), graph_heap_free(), GRAPH::knots, nnodes, voronoi_storage::nnodes, NULL, SCIP_CALL, SCIP_OKAY, TRUE, vnoiCompute(), and vnoiInit().

Referenced by sdgraphBuildDistgraph().

◆ graph_vnoiComputeImplied()

SCIP_RETCODE graph_vnoiComputeImplied ( SCIP scip,
const GRAPH graph,
const SDPROFIT sdprofit,
VNOI vnoi 
)

computes implied Voronoi region on given graph

Parameters
scipSCIP
graphgraph data structure to work on
sdprofitSD profit
vnoithe VNOI

Definition at line 1323 of file graph_vnoi.c.

References graph_get_nNodes(), graph_heap_create(), graph_heap_free(), GRAPH::knots, nnodes, voronoi_storage::nnodes, NULL, SCIP_CALL, SCIP_OKAY, TRUE, vnoiComputeImplied(), and vnoiInit().

Referenced by sdgraphBuildDistgraph().

◆ graph_voronoi()

void graph_voronoi ( const GRAPH g,
const SCIP_Real cost,
const SCIP_Real costrev,
const STP_Bool basemark,
int *  vbase,
PATH path 
)

build a Voronoi region, w.r.t. shortest paths, for a given set of bases

Parameters
ggraph data structure
costedge costs
costrevreversed edge costs (or NULL if symmetric)
basemarkarray to indicate whether a vertex is a Voronoi base
vbasevoronoi base to each vertex
pathpath data struture (leading to respective Voronoi base)

Definition at line 333 of file graph_vnoi.c.

References CONNECT, correct(), shortest_path::dist, shortest_path::edge, FARAWAY, GT, GRAPH::head, GRAPH::knots, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, GRAPH::source, and UNKNOWN.

Referenced by computeSteinerTreeVnoi(), and localKeyVertexHeuristics().

◆ graph_voronoiTerms()

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

Referenced by reduce_sl().

◆ graph_voronoiRepair()

void graph_voronoiRepair ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
const SCIP_Real cost_org,
int *  nheapelems,
int *  vbase,
PATH path,
int *  newedge,
int  crucnode,
UF uf 
)

repair a Voronoi diagram for a given set of base nodes

Parameters
scipSCIP data structure
ggraph data structure
costedge costs (possibly biased)
cost_orgoriginal edge costs (only needed for PC)
nheapelemspointer to number of heap elements
vbasearray containing Voronoi base of each node
pathVoronoi paths data struture
newedgethe new edge
crucnodethe current crucial node
ufunion find data structure

Definition at line 1100 of file graph_vnoi.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, FARAWAY, graph_get_nNodes(), graph_pc_isPc(), graph_pc_isPcMw(), GRAPH::head, GRAPH::mark, nearest(), nnodes, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIP_Bool, SCIP_Real, SCIPisGT(), SCIPStpunionfindFind(), and UNKNOWN.

Referenced by localKeyVertexHeuristics().

◆ graph_voronoiRepairMult()

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

◆ graph_voronoiWithRadiusMw()

void graph_voronoiWithRadiusMw ( SCIP scip,
const GRAPH g,
PATH path,
const SCIP_Real cost,
SCIP_Real radius,
int *  vbase,
int *  heap,
int *  state 
)

Build partition of graph for MWCSP into regions around the positive vertices. Store the weight of a minimum weight center-boundary path for each region in the radius array (has to be reverted to obtain the final r() value).

Parameters
scipSCIP data structure
ggraph data structure
patharray containing graph decomposition data
costedge costs
radiusarray storing shortest way from a positive vertex out of its region
vbasearray containing base of each node
heaparray representing a heap
statearray to mark state of each node during calculation

Definition at line 973 of file graph_vnoi.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_Real, SCIPisGE(), SCIPisGT(), SCIPisLT(), GRAPH::source, GRAPH::term, GRAPH::terms, and UNKNOWN.

Referenced by reduce_boundMw().

◆ graph_voronoiMw()

void graph_voronoiMw ( SCIP scip,
const GRAPH g,
const SCIP_Real costrev,
PATH path,
int *  vbase,
int *  heap,
int *  state 
)

build a Voronoi region, w.r.t. shortest paths, for all positive vertices

Parameters
scipSCIP data structure
ggraph data structure
costrevreversed edge costs
pathpath data structure (leading to respective Voronoi base)
vbaseVoronoi base to each vertex
heaparray representing a heap
statearray to mark the state of each node during calculation

Definition at line 517 of file graph_vnoi.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FARAWAY, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIPisGT(), GRAPH::term, and UNKNOWN.

Referenced by boundPruneHeurMw(), and reduce_boundMw().

◆ graph_add1stTermPaths()

void graph_add1stTermPaths ( const GRAPH g,
const SCIP_Real cost,
PATH path,
int *  vbase,
int *  state 
)

builds a Voronoi region w.r.t. shortest paths, for all terminals NOTE: serves as a wrapper

Parameters
ggraph data structure
costedge costs
pathpath data structure (leading to respective Voronoi base)
vbaseVoronoi base to each vertex
statearray to mark the state of each node during calculation

Definition at line 1464 of file graph_tpath.c.

References graph_get_nNodes(), graph_tpathsAdd1st(), nodes_to_terminal_paths::nnodes, NULL, nodes_to_terminal_paths::state, and nodes_to_terminal_paths::termpaths.

Referenced by computeTransVoronoi(), redcosts_initializeDistances(), reduce_boundHopR(), reduce_boundHopRc(), and reduce_daPcMw().

◆ voronoiSteinerTreeExt()

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

◆ graph_voronoiExtend()

SCIP_RETCODE graph_voronoiExtend ( SCIP scip,
const GRAPH g,
const SCIP_Real cost,
PATH path,
SCIP_Real **  distarr,
int **  basearr,
int **  edgearr,
STP_Bool termsmark,
int *  reachednodes,
int *  nreachednodes,
int *  nodenterms,
int  nneighbterms,
int  base,
int  countex 
)

extend a Voronoi region until all neighbouring terminals are spanned

Parameters
scipSCIP data structure
ggraph data structure
costedgecosts
pathshortest paths data structure
distarrarray to store distance from each node to its base
basearrarray to store the bases
edgearrarray to store the ancestor edge
termsmarkarray to mark terminal
reachednodesarray to mark reached nodes
nreachednodespointer to number of reached nodes
nodentermsarray to store number of terimals to each node
nneighbtermsnumber of neighbouring terminals
basevoronoi base
countexcount of heap elements

Definition at line 253 of file graph_vnoi.c.

References CONNECT, correct(), shortest_path::dist, EAT_LAST, shortest_path::edge, FALSE, GT, GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::path_heap, GRAPH::path_state, SCIP_OKAY, GRAPH::term, and TRUE.

Referenced by computeSteinerTreeVnoi().

◆ graph_voronoiWithDist()

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

Referenced by reduce_nv(), and reduce_nvAdv().

◆ graph_voronoiWithRadius()

SCIP_RETCODE graph_voronoiWithRadius ( SCIP scip,
const GRAPH graph,
GRAPH adjgraph,
PATH path,
SCIP_Real rad,
SCIP_Real cost,
SCIP_Real costrev,
int *  vbase,
int *  heap,
int *  state 
)

build voronoi regions, w.r.t. shortest paths, for all terminals and compute the radii

Parameters
scipSCIP data structure
graphgraph data structure
adjgraphgraph data structure
patharray containing Voronoi paths data
radarray storing shortest way from a terminal out of its Voronoi region
costedge costs
costrevreversed edge costs
vbasearray containing Voronoi base of each node
heaparray representing a heap
statearray to mark state of each node during calculation

Definition at line 774 of file graph_vnoi.c.

References CONNECT, correct(), GRAPH::cost, shortest_path::dist, EAT_LAST, shortest_path::edge, Edge_anti, GRAPH::extended, FARAWAY, graph_edge_add(), graph_knot_add(), graph_pc_knotIsFixedTerm(), GRAPH::head, Is_term, GRAPH::knots, GRAPH::mark, nearest(), nnodes, nterms, NULL, GRAPH::oeat, GRAPH::outbeg, GRAPH::prize, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPisGE(), SCIPisGT(), GRAPH::source, STP_DHCSTP, STP_MWCSP, STP_PCSPG, STP_RPCSPG, GRAPH::stp_type, GRAPH::tail, GRAPH::term, GRAPH::terms, TRUE, and UNKNOWN.

Referenced by boundPruneHeur(), reduce_bound(), and reduce_boundHop().

◆ graph_mincut_exit()

◆ graph_mincut_exec()

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   
)

Referenced by mincut_separateLp(), and mincutExec().

◆ graph_mincut_init()

SCIP_RETCODE graph_mincut_init ( SCIP scip,
GRAPH p 
)

initialize min cut arrays

Parameters
scipSCIP data structure
pgraph data structure

Definition at line 1105 of file graph_mcut.c.

References GRAPH::edges, graph_mincut_isInitialized(), GRAPH::knots, mincutInit(), NULL, SCIP_CALL, and SCIP_OKAY.

Referenced by createModel(), graph_mincut_exec(), initReceivedSubproblem(), and SCIP_DECL_PROBCOPY().

◆ graph_mincut_reInit()

SCIP_RETCODE graph_mincut_reInit ( SCIP scip,
int  nnodes,
int  nedges,
GRAPH p 
)

reinitializes minimum cut arrays

Parameters
scipSCIP data structure
nnodesnumber of nodes
nedgesnumber of edges
pgraph data structure

Definition at line 1120 of file graph_mcut.c.

References graph_mincut_exit(), graph_mincut_isInitialized(), mincutInit(), SCIP_CALL, and SCIP_OKAY.

Referenced by mincutInitForTermSepa().

◆ graph_mincut_isInitialized()

SCIP_Bool graph_mincut_isInitialized ( const GRAPH p)

◆ graph_mincut_setDefaultVals()

void graph_mincut_setDefaultVals ( GRAPH g)

sets default values

Parameters
ggraph data structure

Definition at line 1081 of file graph_mcut.c.

References GRAPH::knots, GRAPH::mincut_e, GRAPH::mincut_head, GRAPH::mincut_head_inact, GRAPH::mincut_nnodes, nnodes, and Q_NULL.

Referenced by mincut_findTerminalSeparators(), and mincut_separateLp().

◆ graph_load()

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

Definition at line 885 of file graph_load.c.

References BLOCKED, GRAPH::budget, check_inputgraph(), GRAPH::cost, GRAPH::costbudget, DIRSEP, EAT_LAST, GRAPH::edges, EXTSEP, FAILURE, FALSE, FARAWAY, current_file::filename, presolve_info::fixed, section::flag, FLAG_REQUIRED, key::format, current_file::fp, get_arguments(), GRAPH::grad, graph_edge_add(), graph_get_nNodes(), graph_grid_create(), graph_hasMultiEdges(), graph_init(), graph_knot_add(), graph_knot_chg(), graph_obstgrid_create(), graph_pc_initPrizes(), graph_transGstpClean(), graph_transMw(), graph_transNw(), graph_transPc(), graph_transPc2Spg(), graph_transRmw(), graph_transRpc(), graph_transRpc2FixedProper(), graph_valid(), GRAPH::hoplimit, GRAPH::ieat, init_coordinates(), GRAPH::inpbeg, Is_term, KEY_BUDGET_B, KEY_COMMENT_CREATOR, KEY_COMMENT_DATE, KEY_COMMENT_NAME, KEY_COMMENT_PROBLEM, KEY_COMMENT_REMARK, KEY_COORDINATES_DD, KEY_COORDINATES_DDD, KEY_COORDINATES_DDDD, KEY_COORDINATES_DDDDD, KEY_COORDINATES_DDDDDD, KEY_COORDINATES_DDDDDDD, KEY_COORDINATES_DDDDDDDD, KEY_COORDINATES_END, KEY_COORDINATES_GRID, KEY_END, KEY_EOF, KEY_GRAPH_A, KEY_GRAPH_AA, KEY_GRAPH_E, KEY_GRAPH_EDGES, KEY_GRAPH_HOPLIMIT, KEY_GRAPH_NODES, KEY_GRAPH_OBSTACLES, KEY_MAXDEGS_MD, KEY_NODEWEIGHTS_END, KEY_NODEWEIGHTS_NW, KEY_OBSTACLES_END, KEY_OBSTACLES_RR, KEY_PRESOLVE_DATE, KEY_PRESOLVE_EA, KEY_PRESOLVE_EC, KEY_PRESOLVE_ED, KEY_PRESOLVE_ES, KEY_PRESOLVE_FIXED, KEY_PRESOLVE_LOWER, KEY_PRESOLVE_TIME, KEY_PRESOLVE_UPPER, KEY_SECTION, KEY_TERMINALS_END, KEY_TERMINALS_GROUPS, KEY_TERMINALS_RB, KEY_TERMINALS_ROOT, KEY_TERMINALS_ROOTP, KEY_TERMINALS_T, KEY_TERMINALS_TB, KEY_TERMINALS_TERMINALS, KEY_TERMINALS_TF, KEY_TERMINALS_TG, KEY_TERMINALS_TL, KEY_TERMINALS_TP, KEY_TERMINALS_TR, KEY_TREE_S, key::keyword, GRAPH::knots, current_file::line, presolve_info::lower, section::mark, MAX_ARGUMENTS, MAX_KEYWORD_LEN, MAX_LINE_LEN, MAX_PATH_LEN, GRAPH::maxdeg, message(), MSG_DEBUG, MSG_ERROR, MSG_FATAL, MSG_INFO, parameter::n, section::name, nnodes, NULL, GRAPH::oeat, open_file(), GRAPH::outbeg, GRAPH::prize, scale_coords(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_READERROR, SCIPallocBufferArray, SCIPallocMemoryArray, SCIPerrorMessage, SCIPfreeBufferArrayNull, SCIPfreeMemoryArrayNull, SCIPgetBoolParam(), SCIPisGT(), SCIPsnprintf(), current_file::section, SECTION_EXISTEND, SECTION_MISSING, GRAPH::source, start_section(), STP_BRMWCSP, STP_DCSTP, STP_DHCSTP, STP_GSTP, STP_MWCSP, STP_NWPTSPG, STP_NWSPG, STP_OARSMT, STP_PCSPG, STP_RMWCSP, STP_RPCSPG, STP_RSMT, STP_SAP, STP_SPG, STP_TERM, GRAPH::stp_type, SUCCESS, key::sw_code, GRAPH::tail, GRAPH::term, GRAPH::terms, presolve_info::time, TRUE, UNKNOWN, and presolve_info::upper.

Referenced by SCIPprobdataCreate().

◆ graph_save()

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

Definition at line 370 of file graph_save.c.

References bea_save(), FALSE, FF_BEA, FF_GRD, FF_PRB, FF_STP, graph_valid(), NULL, and stp_save().

◆ graph_writeReductionStats()

void graph_writeReductionStats ( const GRAPH graph,
const char *  probname,
const char *  filename 
)

Write (append) reduction statistics of current graph to file. Call before graph packing!

Parameters
graphGraph to be printed
probnameName of the problem
filenameName of the output file

Definition at line 412 of file graph_save.c.

References graph_get_nEdges(), graph_get_nNodes(), graph_get_nVET(), nnodes, and NULL.

◆ graph_writeReductionRatioStats()

void graph_writeReductionRatioStats ( const GRAPH graph,
const char *  probname,
const char *  filename 
)

Write (append) reduction ratio statistics of current graph to file. Call before graph packing!

Parameters
graphGraph to be printed
probnameName of the problem
filenameName of the output file

Definition at line 285 of file graph_save.c.

References getReductionRatios(), getReductionRatiosPcMw(), graph_pc_isPcMw(), and SCIP_Real.

◆ graph_writeReductionRatioStatsLive()

SCIP_RETCODE graph_writeReductionRatioStatsLive ( SCIP scip,
GRAPH graph,
const char *  probname 
)

Write (append) reduction ratio statistics of current graph to file. NOTE: Only for testing! Graph will be killed

Parameters
scipSCIP data
graphGraph to be printed
probnameName of the problem

Definition at line 316 of file graph_save.c.

References getReductionRatios(), getReductionRatiosPcMw(), graph_pc_isPcMw(), graph_typeIsSpgLike(), reduce_exec(), reduce_solFree(), reduce_solInit(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPgetIntParam(), SCIPgetStringParam(), STP_REDUCTION_ADVANCED, and TRUE.

Referenced by presolveStp().

◆ graph_writeGml()

SCIP_RETCODE graph_writeGml ( const GRAPH graph,
const char *  filename,
const SCIP_Bool edgemark 
)

print graph (in undirected form) in GML format

Parameters
graphGraph to be printed
filenameName of the output file
edgemarkArray of (undirected) edges to highlight

Definition at line 441 of file graph_save.c.

References EAT_FREE, GRAPH::edges, FALSE, gmlWriteEdge(), gmlWriteNode(), GRAPH::grad, GRAPH::head, GRAPH::knots, NULL, GRAPH::oeat, SCIP_OKAY, SCIPgmlWriteClosing(), SCIPgmlWriteOpening(), GRAPH::source, and GRAPH::tail.

Referenced by SCIPprobdataCreateFromGraph(), and SCIPprobdataPrintGraph().

◆ graph_writeGmlSub()

SCIP_RETCODE graph_writeGmlSub ( const GRAPH graph,
const char *  filename,
const SCIP_Bool subnodesmark 
)

prints subgraph of given graph (in undirected form) in GML format

Parameters
graphGraph to be printed
filenameName of the output file
subnodesmarkArray to mark the nodes of the subgraph

Definition at line 490 of file graph_save.c.

References GRAPH::cost, EAT_FREE, GRAPH::edges, FALSE, gmlWriteNode(), GRAPH::grad, GRAPH::head, GRAPH::knots, NULL, GRAPH::oeat, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPgmlWriteClosing(), SCIPgmlWriteEdge(), SCIPgmlWriteOpening(), SCIPsnprintf(), GRAPH::source, and GRAPH::tail.

◆ graph_writeStp()

◆ graph_writeStpByName()

void graph_writeStpByName ( SCIP scip,
const GRAPH g,
const char *  filename,
SCIP_Real  offset 
)

writes graph in .stp format to file

Definition at line 550 of file graph_save.c.

References graph_writeStp().

◆ graph_writeStpOrg()

void graph_writeStpOrg ( SCIP scip,
const GRAPH graph,
const char *  filename 
)

writes SPG (no variant!) to a file; deprecated

Parameters
scipSCIP data structure
graphgraph data structure
filenamefile name

Definition at line 799 of file graph_save.c.

References GRAPH::cost, GRAPH::edges, GRAPH::head, Is_term, GRAPH::knots, NULL, GRAPH::tail, GRAPH::term, and GRAPH::terms.

◆ SCIPStpValidateSol()

SCIP_RETCODE SCIPStpValidateSol ( SCIP scip,
const GRAPH g,
const double *  xval,
SCIP_Bool  allow_cyles,
SCIP_Bool feasible 
)

validates whether a (LP) solution is feasible

Parameters
scipSCIP
gthe new graph
xval(LP) solution
allow_cylesallow cycles?
feasibleis feasible?

Definition at line 202 of file validate.c.

References EAT_LAST, GRAPH::edges, EPSILON, FALSE, flipedge, GE, GRAPH::grad, graph_get_nNodes(), graph_valid(), GRAPH::maxdeg, nail(), nnodes, GRAPH::oeat, GRAPH::outbeg, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPallocBufferArray, SCIPdebugMessage, SCIPfreeBufferArray, GRAPH::source, STP_DCSTP, GRAPH::stp_type, GRAPH::term, trail(), and TRUE.

Referenced by SCIP_DECL_CONSCHECK(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), and solAddTry().