Detailed Description
graph structure with common algorithms for directed and undirected graphs
Function Documentation
◆ SCIPdigraphResize()
SCIP_RETCODE SCIPdigraphResize | ( | SCIP_DIGRAPH * | digraph, |
int | nnodes | ||
) |
resize directed graph structure
- Parameters
-
digraph directed graph nnodes new number of nodes
Definition at line 7326 of file misc.c.
References SCIP_Digraph::arcdata, SCIP_Digraph::blkmem, BMSreallocBlockMemoryArray, nnodes, SCIP_Digraph::nnodes, SCIP_Digraph::nodedata, SCIP_Digraph::nsuccessors, NULL, SCIP_ALLOC, SCIP_OKAY, SCIP_Digraph::successors, and SCIP_Digraph::successorssize.
Referenced by SCIPrealHashCode().
◆ SCIPdigraphSetSizes()
SCIP_RETCODE SCIPdigraphSetSizes | ( | SCIP_DIGRAPH * | digraph, |
int * | sizes | ||
) |
sets the sizes of the successor lists for the nodes in a directed graph and allocates memory for the lists
- Parameters
-
digraph directed graph sizes sizes of the successor lists
Definition at line 7456 of file misc.c.
References SCIP_Digraph::arcdata, SCIP_Digraph::blkmem, BMSallocBlockMemoryArray, SCIP_Digraph::nnodes, SCIP_Digraph::nsuccessors, NULL, SCIP_ALLOC, SCIP_OKAY, SCIP_Digraph::successors, and SCIP_Digraph::successorssize.
Referenced by findComponents(), and SCIPrealHashCode().
◆ SCIPdigraphFree()
void SCIPdigraphFree | ( | SCIP_DIGRAPH ** | digraph | ) |
frees given directed graph structure
- Parameters
-
digraph pointer to the directed graph
Definition at line 7480 of file misc.c.
References SCIP_Digraph::arcdata, SCIP_Digraph::articulations, SCIP_Digraph::articulationscheck, BMSfreeBlockMemory, BMSfreeBlockMemoryArray, BMSfreeBlockMemoryArrayNull, SCIP_Digraph::components, SCIP_Digraph::componentstarts, SCIP_Digraph::componentstartsize, SCIP_Digraph::narticulations, SCIP_Digraph::ncomponents, SCIP_Digraph::nnodes, SCIP_Digraph::nodedata, SCIP_Digraph::nsuccessors, NULL, SCIPdigraphFreeComponents(), SCIP_Digraph::successors, and SCIP_Digraph::successorssize.
Referenced by buildBlockGraph(), findComponents(), freeConflictgraph(), freeConflictGraphSST(), heurdataFree(), presolRoundConssSOS1(), presolRoundVarsSOS1(), readFile(), SCIP_DECL_PROBDELORIG(), SCIP_DECL_PROBDELTRANS(), SCIP_DECL_READERREAD(), SCIP_DECL_SEPAEXECLP(), SCIPrealHashCode(), sortGenVBounds(), and tightenVarsBoundsSOS1().
◆ SCIPdigraphAddArc()
SCIP_RETCODE SCIPdigraphAddArc | ( | SCIP_DIGRAPH * | digraph, |
int | startnode, | ||
int | endnode, | ||
void * | data | ||
) |
add (directed) arc and a related data to the directed graph structure
- Note
- if the arc is already contained, it is added a second time
- Parameters
-
digraph directed graph startnode start node of the arc endnode start node of the arc data data that should be stored for the arc; or NULL
Definition at line 7574 of file misc.c.
References SCIP_Digraph::arcdata, SCIP_Digraph::articulationscheck, ensureSuccessorsSize(), FALSE, nnodes, SCIP_Digraph::nsuccessors, NULL, SCIP_CALL, SCIP_OKAY, and SCIP_Digraph::successors.
Referenced by addBranchingComplementaritiesSOS1(), buildBlockGraph(), createVariables(), fillDigraph(), getPrecedence(), parseDetails(), SCIP_DECL_SEPAEXECLP(), SCIPdigraphComputeUndirectedComponents(), SCIPrealHashCode(), sortGenVBounds(), and updateArcData().
◆ SCIPdigraphAddArcSafe()
SCIP_RETCODE SCIPdigraphAddArcSafe | ( | SCIP_DIGRAPH * | digraph, |
int | startnode, | ||
int | endnode, | ||
void * | data | ||
) |
add (directed) arc to the directed graph structure, if it is not contained, yet
- Note
- if there already exists an arc from startnode to endnode, the new arc is not added, even if its data is different
- Parameters
-
digraph directed graph startnode start node of the arc endnode start node of the arc data data that should be stored for the arc; or NULL
Definition at line 7605 of file misc.c.
References SCIP_Digraph::arcdata, SCIP_Digraph::articulationscheck, ensureSuccessorsSize(), FALSE, nnodes, SCIP_Digraph::nsuccessors, NULL, SCIP_CALL, SCIP_OKAY, and SCIP_Digraph::successors.
Referenced by createConflictGraphSST(), enforceConflictgraph(), extensionOperatorSOS1(), genConflictgraphLinearCons(), handleNewVariableSOS1(), initConflictgraph(), performImplicationGraphAnalysis(), presolRoundConssSOS1(), and SCIPrealHashCode().
◆ SCIPdigraphSetNSuccessors()
SCIP_RETCODE SCIPdigraphSetNSuccessors | ( | SCIP_DIGRAPH * | digraph, |
int | node, | ||
int | nsuccessors | ||
) |
sets the number of successors to a given value
- Parameters
-
digraph directed graph node node for which the number of successors has to be changed nsuccessors new number of successors
Definition at line 7642 of file misc.c.
References nnodes, SCIP_Digraph::nsuccessors, NULL, and SCIP_OKAY.
Referenced by resetConflictgraphSOS1(), and SCIPrealHashCode().
◆ SCIPdigraphGetNNodes()
int SCIPdigraphGetNNodes | ( | SCIP_DIGRAPH * | digraph | ) |
returns the number of nodes of the given digraph
- Parameters
-
digraph directed graph
Definition at line 7658 of file misc.c.
References SCIP_Digraph::nnodes, and NULL.
Referenced by addPathCuts(), addSubtourCuts(), addTourCuts(), buildBlockGraph(), cliqueGetCommonSuccessorsSOS1(), computeNextAdjacency(), nodeGetSolvalBinaryBigMSOS1(), nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), performImplicationGraphAnalysis(), SCIPrealHashCode(), selectOrbitLeaderSSTConss(), and sortGenVBounds().
◆ SCIPdigraphGetNodeData()
void* SCIPdigraphGetNodeData | ( | SCIP_DIGRAPH * | digraph, |
int | node | ||
) |
returns the node data, or NULL if no data exist
- Parameters
-
digraph directed graph node node for which the node data is returned
Definition at line 7668 of file misc.c.
References nnodes, SCIP_Digraph::nodedata, and NULL.
Referenced by addBranchingComplementaritiesSOS1(), addSSTConssOrbitAndUpdateSST(), checkConComponentsVarbound(), detectVarboundSOS1(), freeConflictgraph(), freeConflictGraphSST(), generateBoundInequalityFromSOS1Nodes(), getBoundConsFromVertices(), nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), passConComponentVarbound(), propVariableNonzero(), SCIPrealHashCode(), selectOrbitLeaderSSTConss(), sepaImplBoundCutsSOS1(), and updateSymInfoConflictGraphSST().
◆ SCIPdigraphSetNodeData()
void SCIPdigraphSetNodeData | ( | SCIP_DIGRAPH * | digraph, |
void * | dataptr, | ||
int | node | ||
) |
sets the node data
sets the node data
- Note
- The old user pointer is not freed. This has to be done by the user
- Parameters
-
digraph directed graph dataptr user node data pointer, or NULL node node for which the node data is returned
Definition at line 7684 of file misc.c.
References nnodes, SCIP_Digraph::nodedata, and NULL.
Referenced by freeConflictgraph(), initConflictgraph(), initImplGraphSOS1(), SCIPrealHashCode(), and updateSymInfoConflictGraphSST().
◆ SCIPdigraphGetNArcs()
int SCIPdigraphGetNArcs | ( | SCIP_DIGRAPH * | digraph | ) |
returns the total number of arcs in the given digraph
- Parameters
-
digraph directed graph
Definition at line 7698 of file misc.c.
References narcs, SCIP_Digraph::nnodes, SCIP_Digraph::nsuccessors, and NULL.
Referenced by SCIP_DECL_SEPAEXECLP(), SCIPrealHashCode(), and sepaImplBoundCutsSOS1().
◆ SCIPdigraphGetNSuccessors()
int SCIPdigraphGetNSuccessors | ( | SCIP_DIGRAPH * | digraph, |
int | node | ||
) |
returns the number of successor nodes of the given node
- Parameters
-
digraph directed graph node node for which the number of outgoing arcs is returned
Definition at line 7716 of file misc.c.
References nnodes, SCIP_Digraph::nsuccessors, NULL, and SCIP_Digraph::successorssize.
Referenced by addBranchingComplementaritiesSOS1(), addPathCuts(), addSubtourCuts(), addTourCuts(), buildBlockGraph(), checkConComponentsVarbound(), checkSwitchNonoverlappingSOS1Methods(), cliqueGetCommonSuccessorsSOS1(), computeNextAdjacency(), computeUbmakespan(), computeVarsCoverSOS1(), enforceConflictgraph(), findArticulationPointsUtil(), genConflictgraphLinearCons(), getBoundConsFromVertices(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), getCoverVertices(), getDiveBdChgsSOS1conflictgraph(), getSOS1Implications(), getVectorOfWeights(), handleNewVariableSOS1(), initConflictgraph(), initImplGraphSOS1(), initTCliquegraph(), isConnectedSOS1(), isViolatedSOS1(), markNeighborsMWISHeuristic(), maxWeightIndSetHeuristic(), passConComponentVarbound(), performImplicationGraphAnalysis(), presolRoundConssSOS1(), presolRoundVarsSOS1(), propagateEst(), propagateLst(), propVariableNonzero(), resetConflictgraphSOS1(), SCIP_DECL_SEPAEXECLP(), SCIPcreateSchedulingProblem(), SCIPrealHashCode(), selectOrbitLeaderSSTConss(), sepaImplBoundCutsSOS1(), tightenVarsBoundsSOS1(), updateArcData(), and updateSymInfoConflictGraphSST().
◆ SCIPdigraphGetSuccessors()
int* SCIPdigraphGetSuccessors | ( | SCIP_DIGRAPH * | digraph, |
int | node | ||
) |
returns the array of indices of the successor nodes; this array must not be changed from outside
- Parameters
-
digraph directed graph node node for which the array of outgoing arcs is returned
Definition at line 7731 of file misc.c.
References nnodes, SCIP_Digraph::nsuccessors, NULL, SCIP_Digraph::successors, and SCIP_Digraph::successorssize.
Referenced by addBranchingComplementaritiesSOS1(), addPathCuts(), addSubtourCuts(), addTourCuts(), buildBlockGraph(), checkConComponentsVarbound(), cliqueGetCommonSuccessorsSOS1(), computeNextAdjacency(), computeVarsCoverSOS1(), enforceConflictgraph(), findArticulationPointsUtil(), genConflictgraphLinearCons(), getBoundConsFromVertices(), getBranchingVerticesSOS1(), getCoverVertices(), getDiveBdChgsSOS1conflictgraph(), getSOS1Implications(), getVectorOfWeights(), handleNewVariableSOS1(), initConflictgraph(), initImplGraphSOS1(), initTCliquegraph(), isConnectedSOS1(), isViolatedSOS1(), markNeighborsMWISHeuristic(), passConComponentVarbound(), performImplicationGraphAnalysis(), presolRoundConssSOS1(), propagateEst(), propagateLst(), propVariableNonzero(), resetConflictgraphSOS1(), SCIP_DECL_SEPAEXECLP(), SCIPcreateSchedulingProblem(), SCIPrealHashCode(), selectOrbitLeaderSSTConss(), sepaImplBoundCutsSOS1(), tightenVarsBoundsSOS1(), updateArcData(), and updateSymInfoConflictGraphSST().
◆ SCIPdigraphGetSuccessorsData()
void** SCIPdigraphGetSuccessorsData | ( | SCIP_DIGRAPH * | digraph, |
int | node | ||
) |
returns the array of data corresponding to the arcs originating at the given node, or NULL if no data exist; this array must not be changed from outside
- Parameters
-
digraph directed graph node node for which the data corresponding to the outgoing arcs is returned
Definition at line 7749 of file misc.c.
References SCIP_Digraph::arcdata, nnodes, SCIP_Digraph::nsuccessors, NULL, and SCIP_Digraph::successorssize.
Referenced by computeUbmakespan(), getSOS1Implications(), performImplicationGraphAnalysis(), presolRoundVarsSOS1(), propVariableNonzero(), SCIPcreateSchedulingProblem(), SCIPrealHashCode(), sepaImplBoundCutsSOS1(), and updateArcData().
◆ SCIPdigraphGetArticulationPoints()
SCIP_RETCODE SCIPdigraphGetArticulationPoints | ( | SCIP_DIGRAPH * | digraph, |
int ** | articulations, | ||
int * | narticulations | ||
) |
identifies the articulation points in a given directed graph uses the helper recursive function findArticulationPointsUtil
- Parameters
-
digraph directed graph articulations array to store the sorted node indices of the computed articulation points, or NULL narticulations number of the computed articulation points, or NULL
Definition at line 7912 of file misc.c.
References SCIP_Digraph::articulations, SCIP_Digraph::articulationscheck, SCIP_Digraph::blkmem, BMSallocBlockMemoryArray, BMSallocMemoryArray, BMSfreeBlockMemoryArray, BMSfreeMemoryArrayNull, FALSE, findArticulationPointsUtil(), SCIP_Digraph::narticulations, SCIP_Digraph::nnodes, NULL, SCIP_ALLOC_TERMINATE, SCIP_Bool, SCIP_OKAY, and TRUE.
Referenced by buildBlockGraph(), and SCIPrealHashCode().
◆ SCIPdigraphComputeUndirectedComponents()
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents | ( | SCIP_DIGRAPH * | digraph, |
int | minsize, | ||
int * | components, | ||
int * | ncomponents | ||
) |
Compute undirected connected components on the given graph.
- Note
- For each arc, its reverse is added, so the graph does not need to be the directed representation of an undirected graph.
- Parameters
-
digraph directed graph minsize all components with less nodes are ignored components array with as many slots as there are nodes in the directed graph to store for each node the component to which it belongs (components are numbered 0 to ncomponents - 1); or NULL, if components are accessed one-by-one using SCIPdigraphGetComponent() ncomponents pointer to store the number of components; or NULL, if the number of components is accessed by SCIPdigraphGetNComponents()
Definition at line 8001 of file misc.c.
References SCIP_Digraph::blkmem, BMSallocBlockMemoryArray, BMSallocClearMemoryArray, BMSallocMemoryArray, BMSclearMemoryArray, BMScopyMemoryArray, BMSfreeMemoryArrayNull, BMSreallocBlockMemoryArray, SCIP_Digraph::components, SCIP_Digraph::componentstarts, SCIP_Digraph::componentstartsize, depthFirstSearch(), SCIP_Digraph::ncomponents, SCIP_Digraph::nnodes, SCIP_Digraph::nsuccessors, NULL, SCIP_ALLOC, SCIP_ALLOC_TERMINATE, SCIP_Bool, SCIP_CALL_TERMINATE, SCIP_OKAY, SCIPdigraphAddArc(), SCIPdigraphFreeComponents(), and SCIP_Digraph::successors.
Referenced by buildBlockGraph(), findComponents(), heurdataInit(), SCIPrealHashCode(), and sortGenVBounds().
◆ SCIPdigraphComputeDirectedComponents()
SCIP_RETCODE SCIPdigraphComputeDirectedComponents | ( | SCIP_DIGRAPH * | digraph, |
int | compidx, | ||
int * | strongcomponents, | ||
int * | strongcompstartidx, | ||
int * | nstrongcomponents | ||
) |
Computes all strongly connected components of an undirected connected component with Tarjan's Algorithm. The resulting strongly connected components are sorted topologically (starting from the end of the strongcomponents array).
- Note
- In general a topological sort of the strongly connected components is not unique.
- Parameters
-
digraph directed graph compidx number of the undirected connected component strongcomponents array to store the strongly connected components (length >= size of the component) strongcompstartidx array to store the start indices of the strongly connected components (length >= size of the component) nstrongcomponents pointer to store the number of strongly connected components
Definition at line 8341 of file misc.c.
References BMSallocMemoryArray, BMSfreeMemoryArrayNull, SCIP_Digraph::components, SCIP_Digraph::componentstarts, FALSE, nnodes, SCIP_Digraph::nnodes, NULL, SCIP_ALLOC_TERMINATE, SCIP_Bool, SCIP_OKAY, SCIPdebugMessage, tarjan(), and TRUE.
Referenced by SCIPrealHashCode(), and sortGenVBounds().
◆ SCIPdigraphTopoSortComponents()
SCIP_RETCODE SCIPdigraphTopoSortComponents | ( | SCIP_DIGRAPH * | digraph | ) |
Performes an (almost) topological sort on the undirected components of the given directed graph. The undirected components should be computed before using SCIPdigraphComputeUndirectedComponents().
- Note
- In general a topological sort is not unique. Note, that there might be directed cycles, that are randomly broken, which is the reason for having only almost topologically sorted arrays.
Performs an (almost) topological sort on the undirected components of the given directed graph. The undirected components should be computed before using SCIPdigraphComputeUndirectedComponents().
- Note
- In general a topological sort is not unique. Note, that there might be directed cycles, that are randomly broken, which is the reason for having only almost topologically sorted arrays.
- Parameters
-
digraph directed graph
Definition at line 8130 of file misc.c.
References BMSallocClearMemoryArray, BMSallocMemoryArray, BMSfreeMemoryArrayNull, SCIP_Digraph::components, SCIP_Digraph::componentstarts, depthFirstSearch(), SCIP_Digraph::ncomponents, SCIP_Digraph::nnodes, NULL, SCIP_ALLOC_TERMINATE, SCIP_Bool, and SCIP_OKAY.
Referenced by heurdataInit(), SCIPrealHashCode(), and sortGenVBounds().
◆ SCIPdigraphGetNComponents()
int SCIPdigraphGetNComponents | ( | SCIP_DIGRAPH * | digraph | ) |
returns the number of previously computed undirected components for the given directed graph
- Parameters
-
digraph directed graph
Definition at line 8196 of file misc.c.
References SCIP_Digraph::componentstartsize, SCIP_Digraph::ncomponents, and NULL.
Referenced by buildBlockGraph(), heurdataInit(), SCIPrealHashCode(), sortComponents(), and sortGenVBounds().
◆ SCIPdigraphGetComponent()
void SCIPdigraphGetComponent | ( | SCIP_DIGRAPH * | digraph, |
int | compidx, | ||
int ** | nodes, | ||
int * | nnodes | ||
) |
Returns the previously computed undirected component of the given number for the given directed graph. If the components were sorted using SCIPdigraphTopoSortComponents(), the component is (almost) topologically sorted.
- Parameters
-
digraph directed graph compidx number of the component to return nodes pointer to store the nodes in the component; or NULL, if not needed nnodes pointer to store the number of nodes in the component; or NULL, if not needed
Definition at line 8209 of file misc.c.
References SCIP_Digraph::components, SCIP_Digraph::componentstarts, and NULL.
Referenced by executeHeuristic(), SCIPrealHashCode(), sortComponents(), and sortGenVBounds().
◆ SCIPdigraphFreeComponents()
void SCIPdigraphFreeComponents | ( | SCIP_DIGRAPH * | digraph | ) |
frees the component information for the given directed graph
- Parameters
-
digraph directed graph
Definition at line 8429 of file misc.c.
References SCIP_Digraph::blkmem, BMSfreeBlockMemoryArray, SCIP_Digraph::components, SCIP_Digraph::componentstarts, SCIP_Digraph::componentstartsize, SCIP_Digraph::ncomponents, SCIP_Digraph::nnodes, and NULL.
Referenced by SCIP_DECL_PROBDELORIG(), SCIP_DECL_PROBDELTRANS(), SCIP_DECL_SEPAEXECLP(), SCIPdigraphComputeUndirectedComponents(), SCIPdigraphFree(), and SCIPrealHashCode().
◆ SCIPdigraphPrint()
void SCIPdigraphPrint | ( | SCIP_DIGRAPH * | digraph, |
SCIP_MESSAGEHDLR * | messagehdlr, | ||
FILE * | file | ||
) |
output of the given directed graph via the given message handler
- Parameters
-
digraph directed graph messagehdlr message handler file output file (or NULL for standard output)
Definition at line 8461 of file misc.c.
References SCIP_Digraph::nnodes, SCIP_Digraph::nsuccessors, SCIPmessageFPrintInfo(), and SCIP_Digraph::successors.
Referenced by SCIPrealHashCode().
◆ SCIPdigraphPrintGml()
void SCIPdigraphPrintGml | ( | SCIP_DIGRAPH * | digraph, |
FILE * | file | ||
) |
prints the given directed graph structure in GML format into the given file
- Parameters
-
digraph directed graph file file to write to
Definition at line 8496 of file misc.c.
References SCIP_Digraph::nnodes, SCIP_Digraph::nsuccessors, NULL, SCIP_MAXSTRLEN, SCIPgmlWriteArc(), SCIPgmlWriteClosing(), SCIPgmlWriteNode(), SCIPgmlWriteOpening(), SCIPsnprintf(), SCIP_Digraph::successors, and TRUE.
Referenced by SCIP_DECL_READERREAD(), and SCIPrealHashCode().
◆ SCIPdigraphPrintComponents()
void SCIPdigraphPrintComponents | ( | SCIP_DIGRAPH * | digraph, |
SCIP_MESSAGEHDLR * | messagehdlr, | ||
FILE * | file | ||
) |
output of the given directed graph via the given message handler
- Parameters
-
digraph directed graph messagehdlr message handler file output file (or NULL for standard output)
Definition at line 8535 of file misc.c.
References SCIP_Digraph::components, SCIP_Digraph::componentstarts, SCIP_Digraph::ncomponents, and SCIPmessageFPrintInfo().
Referenced by heurdataInit(), and SCIPrealHashCode().
◆ SCIPcreateDigraph()
SCIP_RETCODE SCIPcreateDigraph | ( | SCIP * | scip, |
SCIP_DIGRAPH ** | digraph, | ||
int | nnodes | ||
) |
creates directed graph structure
- Parameters
-
scip SCIP data structure digraph pointer to store the created directed graph nnodes number of nodes
Definition at line 617 of file scip_datastructures.c.
References Scip::mem, NULL, SCIP_Mem::probmem, SCIP_CALL, SCIP_OKAY, and SCIPdigraphCreate().
Referenced by addBranchingComplementaritiesSOS1(), buildBlockGraph(), createConflictGraphSST(), enforceConflictgraph(), findComponents(), getPrecedence(), initConflictgraph(), initImplGraphSOS1(), presolRoundConssSOS1(), presolRoundVarsSOS1(), readFile(), SCIP_DECL_SEPAEXECLP(), SCIPcreateProbCyc(), sortGenVBounds(), and tightenVarsBoundsSOS1().
◆ SCIPcopyDigraph()
SCIP_RETCODE SCIPcopyDigraph | ( | SCIP * | scip, |
SCIP_DIGRAPH ** | targetdigraph, | ||
SCIP_DIGRAPH * | sourcedigraph | ||
) |
! [SnippetCodeStyleComment] copies directed graph structure
The copying procedure uses the memory of the passed SCIP instance. The user must ensure that the digraph lives as most as long as the SCIP instance.
- Note
- The data in nodedata is copied verbatim. This possibly has to be adapted by the user.
copies directed graph structure
The copying procedure uses the memory of the passed SCIP instance. The user must ensure that the digraph lives as most as long as the SCIP instance.
- Note
- The data in nodedata is copied verbatim. This possibly has to be adapted by the user.
- Parameters
-
scip SCIP data structure targetdigraph pointer to store the copied directed graph sourcedigraph source directed graph
Definition at line 638 of file scip_datastructures.c.
References Scip::mem, NULL, SCIP_Mem::probmem, SCIP_CALL, SCIP_OKAY, and SCIPdigraphCopy().
Referenced by heurdataInit(), SCIP_DECL_PROBCOPY(), and SCIP_DECL_PROBTRANS().