graph structure with common algorithms for directed and undirected graphs
SCIP_RETCODE SCIPdigraphResize | ( | SCIP_DIGRAPH * | digraph, |
int | nnodes ) |
resize directed graph structure
digraph | directed graph |
nnodes | new number of nodes |
Definition at line 7417 of file misc.c.
References SCIP_Digraph::arcdata, assert(), 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.
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
digraph | directed graph |
sizes | sizes of the successor lists |
Definition at line 7547 of file misc.c.
References SCIP_Digraph::arcdata, assert(), SCIP_Digraph::blkmem, BMSallocBlockMemoryArray, i, SCIP_Digraph::nnodes, SCIP_Digraph::nsuccessors, NULL, SCIP_ALLOC, SCIP_OKAY, SCIP_Digraph::successors, and SCIP_Digraph::successorssize.
Referenced by findComponents().
void SCIPdigraphFree | ( | SCIP_DIGRAPH ** | digraph | ) |
frees given directed graph structure
digraph | pointer to the directed graph |
Definition at line 7571 of file misc.c.
References SCIP_Digraph::arcdata, SCIP_Digraph::articulations, SCIP_Digraph::articulationscheck, assert(), BMSfreeBlockMemory, BMSfreeBlockMemoryArray, BMSfreeBlockMemoryArrayNull, SCIP_Digraph::components, SCIP_Digraph::componentstarts, SCIP_Digraph::componentstartsize, i, 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(), freeImplGraphSOS1(), heurdataFree(), presolRoundConssSOS1(), presolRoundVarsSOS1(), readFile(), readFile(), SCIP_DECL_CONSEXITSOL(), SCIP_DECL_PROBDELORIG(), SCIP_DECL_PROBDELTRANS(), SCIP_DECL_READERREAD(), SCIP_DECL_SEPAEXECLP(), sortGenVBounds(), and tightenVarsBoundsSOS1().
SCIP_RETCODE SCIPdigraphAddArc | ( | SCIP_DIGRAPH * | digraph, |
int | startnode, | ||
int | endnode, | ||
void * | data ) |
add (directed) arc and a related data to the directed graph structure
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 7665 of file misc.c.
References SCIP_Digraph::arcdata, SCIP_Digraph::articulationscheck, assert(), ensureSuccessorsSize(), FALSE, nnodes, SCIP_Digraph::nsuccessors, NULL, SCIP_CALL, SCIP_OKAY, and SCIP_Digraph::successors.
Referenced by addBranchingComplementaritiesSOS1(), buildBlockGraph(), createVariables(), fillDigraph(), getPrecedence(), parseDetails(), parseDetails(), SCIP_DECL_SEPAEXECLP(), SCIPdigraphComputeUndirectedComponents(), sortGenVBounds(), and updateArcData().
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
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 7696 of file misc.c.
References SCIP_Digraph::arcdata, SCIP_Digraph::articulationscheck, assert(), ensureSuccessorsSize(), FALSE, i, nnodes, SCIP_Digraph::nsuccessors, NULL, SCIP_CALL, SCIP_OKAY, and SCIP_Digraph::successors.
Referenced by enforceConflictgraph(), extensionOperatorSOS1(), genConflictgraphLinearCons(), handleNewVariableSOS1(), initConflictgraph(), performImplicationGraphAnalysis(), and presolRoundConssSOS1().
SCIP_RETCODE SCIPdigraphSetNSuccessors | ( | SCIP_DIGRAPH * | digraph, |
int | node, | ||
int | nsuccessors ) |
sets the number of successors to a given value
digraph | directed graph |
node | node for which the number of successors has to be changed |
nsuccessors | new number of successors |
Definition at line 7733 of file misc.c.
References assert(), nnodes, SCIP_Digraph::nsuccessors, NULL, and SCIP_OKAY.
Referenced by resetConflictgraphSOS1().
int SCIPdigraphGetNNodes | ( | SCIP_DIGRAPH * | digraph | ) |
returns the number of nodes of the given digraph
digraph | directed graph |
Definition at line 7749 of file misc.c.
References assert(), SCIP_Digraph::nnodes, and NULL.
Referenced by addPathCuts(), addSubtourCuts(), addTourCuts(), buildBlockGraph(), cliqueGetCommonSuccessorsSOS1(), computeNextAdjacency(), nodeGetSolvalBinaryBigMSOS1(), nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), performImplicationGraphAnalysis(), SCIPnodeGetVarSOS1(), and sortGenVBounds().
void * SCIPdigraphGetNodeData | ( | SCIP_DIGRAPH * | digraph, |
int | node ) |
returns the node data, or NULL if no data exist
digraph | directed graph |
node | node for which the node data is returned |
Definition at line 7759 of file misc.c.
References assert(), nnodes, SCIP_Digraph::nodedata, and NULL.
Referenced by addBranchingComplementaritiesSOS1(), checkConComponentsVarbound(), detectVarboundSOS1(), freeConflictgraph(), freeImplGraphSOS1(), generateBoundInequalityFromSOS1Nodes(), getBoundConsFromVertices(), nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), passConComponentVarbound(), propVariableNonzero(), SCIPnodeGetVarSOS1(), and sepaImplBoundCutsSOS1().
void SCIPdigraphSetNodeData | ( | SCIP_DIGRAPH * | digraph, |
void * | dataptr, | ||
int | node ) |
sets the node data
sets the node data
digraph | directed graph |
dataptr | user node data pointer, or NULL |
node | node for which the node data is returned |
Definition at line 7775 of file misc.c.
References assert(), nnodes, SCIP_Digraph::nodedata, and NULL.
Referenced by freeConflictgraph(), freeImplGraphSOS1(), initConflictgraph(), and initImplGraphSOS1().
int SCIPdigraphGetNArcs | ( | SCIP_DIGRAPH * | digraph | ) |
returns the total number of arcs in the given digraph
digraph | directed graph |
Definition at line 7789 of file misc.c.
References assert(), i, narcs, SCIP_Digraph::nnodes, SCIP_Digraph::nsuccessors, and NULL.
Referenced by SCIP_DECL_SEPAEXECLP(), and sepaImplBoundCutsSOS1().
int SCIPdigraphGetNSuccessors | ( | SCIP_DIGRAPH * | digraph, |
int | node ) |
returns the number of successor nodes of the given node
digraph | directed graph |
node | node for which the number of outgoing arcs is returned |
Definition at line 7807 of file misc.c.
References assert(), nnodes, SCIP_Digraph::nsuccessors, NULL, and SCIP_Digraph::successorssize.
Referenced by addBranchingComplementaritiesSOS1(), addPathCuts(), addSubtourCuts(), addTourCuts(), buildBlockGraph(), checkConComponentsVarbound(), checkSwitchNonoverlappingSOS1Methods(), cliqueGetCommonSuccessorsSOS1(), computeNextAdjacency(), computeUbmakespan(), computeVarsCoverSOS1(), enforceConflictgraph(), findArticulationPointsUtil(), freeImplGraphSOS1(), genConflictgraphLinearCons(), getBoundConsFromVertices(), getBranchingPrioritiesSOS1(), getBranchingVerticesSOS1(), getCoverVertices(), getDiveBdChgsSOS1conflictgraph(), getSOS1Implications(), getVectorOfWeights(), handleNewVariableSOS1(), initConflictgraph(), initImplGraphSOS1(), initTCliquegraph(), isConnectedSOS1(), isImpliedZero(), isViolatedSOS1(), markNeighborsMWISHeuristic(), maxWeightIndSetHeuristic(), passConComponentVarbound(), performImplicationGraphAnalysis(), presolRoundConssSOS1(), presolRoundVarsSOS1(), propagateEst(), propagateLst(), propVariableNonzero(), resetConflictgraphSOS1(), SCIP_DECL_CONSPRESOL(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXECLP(), SCIPcreateSchedulingProblem(), sepaImplBoundCutsSOS1(), tightenVarsBoundsSOS1(), and updateArcData().
int * SCIPdigraphGetSuccessors | ( | SCIP_DIGRAPH * | digraph, |
int | node ) |
returns the array of indices of the successor nodes; this array must not be changed from outside
digraph | directed graph |
node | node for which the array of outgoing arcs is returned |
Definition at line 7822 of file misc.c.
References assert(), 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(), isImpliedZero(), isViolatedSOS1(), markNeighborsMWISHeuristic(), passConComponentVarbound(), performImplicationGraphAnalysis(), presolRoundConssSOS1(), propagateEst(), propagateLst(), propVariableNonzero(), resetConflictgraphSOS1(), SCIP_DECL_CONSPRESOL(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAEXECLP(), SCIPcreateSchedulingProblem(), sepaImplBoundCutsSOS1(), tightenVarsBoundsSOS1(), and updateArcData().
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
digraph | directed graph |
node | node for which the data corresponding to the outgoing arcs is returned |
Definition at line 7840 of file misc.c.
References SCIP_Digraph::arcdata, assert(), nnodes, SCIP_Digraph::nsuccessors, NULL, and SCIP_Digraph::successorssize.
Referenced by computeUbmakespan(), freeImplGraphSOS1(), getSOS1Implications(), performImplicationGraphAnalysis(), presolRoundVarsSOS1(), propVariableNonzero(), SCIPcreateSchedulingProblem(), sepaImplBoundCutsSOS1(), and updateArcData().
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
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 8003 of file misc.c.
References SCIP_Digraph::articulations, SCIP_Digraph::articulationscheck, assert(), SCIP_Digraph::blkmem, BMSallocBlockMemoryArray, BMSallocMemoryArray, BMSfreeBlockMemoryArray, BMSfreeMemoryArrayNull, FALSE, findArticulationPointsUtil(), SCIP_Digraph::narticulations, SCIP_Digraph::nnodes, NULL, SCIP_ALLOC_TERMINATE, SCIP_OKAY, and TRUE.
Referenced by buildBlockGraph().
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents | ( | SCIP_DIGRAPH * | digraph, |
int | minsize, | ||
int * | components, | ||
int * | ncomponents ) |
Compute undirected connected components on the given graph.
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 8092 of file misc.c.
References assert(), SCIP_Digraph::blkmem, BMSallocBlockMemoryArray, BMSallocClearMemoryArray, BMSallocMemoryArray, BMSclearMemoryArray, BMScopyMemoryArray, BMSfreeMemoryArrayNull, BMSreallocBlockMemoryArray, SCIP_Digraph::components, SCIP_Digraph::componentstarts, SCIP_Digraph::componentstartsize, depthFirstSearch(), i, SCIP_Digraph::ncomponents, SCIP_Digraph::nnodes, SCIP_Digraph::nsuccessors, NULL, SCIP_ALLOC, SCIP_ALLOC_TERMINATE, SCIP_CALL_TERMINATE, SCIP_OKAY, SCIPdigraphAddArc(), SCIPdigraphFreeComponents(), and SCIP_Digraph::successors.
Referenced by buildBlockGraph(), findComponents(), heurdataInit(), and sortGenVBounds().
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).
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 8433 of file misc.c.
References assert(), BMSallocMemoryArray, BMSfreeMemoryArrayNull, SCIP_Digraph::components, SCIP_Digraph::componentstarts, FALSE, i, nnodes, SCIP_Digraph::nnodes, NULL, SCIP_ALLOC_TERMINATE, SCIP_OKAY, SCIPdebugMessage, tarjan(), and TRUE.
Referenced by sortGenVBounds().
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().
Performs an (almost) topological sort on the undirected components of the given directed graph. The undirected components should be computed before using SCIPdigraphComputeUndirectedComponents().
digraph | directed graph |
Definition at line 8222 of file misc.c.
References assert(), BMSallocClearMemoryArray, BMSallocMemoryArray, BMSfreeMemoryArrayNull, SCIP_Digraph::components, SCIP_Digraph::componentstarts, depthFirstSearch(), i, SCIP_Digraph::ncomponents, SCIP_Digraph::nnodes, NULL, SCIP_ALLOC_TERMINATE, and SCIP_OKAY.
Referenced by heurdataInit(), and sortGenVBounds().
int SCIPdigraphGetNComponents | ( | SCIP_DIGRAPH * | digraph | ) |
returns the number of previously computed undirected components for the given directed graph
digraph | directed graph |
Definition at line 8288 of file misc.c.
References assert(), SCIP_Digraph::componentstartsize, SCIP_Digraph::ncomponents, and NULL.
Referenced by buildBlockGraph(), heurdataInit(), sortComponents(), and sortGenVBounds().
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.
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 8301 of file misc.c.
References assert(), SCIP_Digraph::components, SCIP_Digraph::componentstarts, nnodes, and NULL.
Referenced by executeHeuristic(), sortComponents(), and sortGenVBounds().
void SCIPdigraphFreeComponents | ( | SCIP_DIGRAPH * | digraph | ) |
frees the component information for the given directed graph
digraph | directed graph |
Definition at line 8521 of file misc.c.
References assert(), 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(), and SCIPdigraphFree().
void SCIPdigraphPrint | ( | SCIP_DIGRAPH * | digraph, |
SCIP_MESSAGEHDLR * | messagehdlr, | ||
FILE * | file ) |
output of the given directed graph via the given message handler
digraph | directed graph |
messagehdlr | message handler |
file | output file (or NULL for standard output) |
Definition at line 8553 of file misc.c.
References SCIP_Digraph::nnodes, SCIP_Digraph::nsuccessors, SCIPmessageFPrintInfo(), and SCIP_Digraph::successors.
void SCIPdigraphPrintGml | ( | SCIP_DIGRAPH * | digraph, |
FILE * | file ) |
prints the given directed graph structure in GML format into the given file
digraph | directed graph |
file | file to write to |
Definition at line 8588 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().
void SCIPdigraphPrintComponents | ( | SCIP_DIGRAPH * | digraph, |
SCIP_MESSAGEHDLR * | messagehdlr, | ||
FILE * | file ) |
output of the given directed graph via the given message handler
digraph | directed graph |
messagehdlr | message handler |
file | output file (or NULL for standard output) |
Definition at line 8627 of file misc.c.
References c, SCIP_Digraph::components, SCIP_Digraph::componentstarts, i, SCIP_Digraph::ncomponents, and SCIPmessageFPrintInfo().
Referenced by heurdataInit().
SCIP_RETCODE SCIPcreateDigraph | ( | SCIP * | scip, |
SCIP_DIGRAPH ** | digraph, | ||
int | nnodes ) |
creates directed graph structure
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 assert(), nnodes, NULL, SCIP_CALL, SCIP_OKAY, and SCIPdigraphCreate().
Referenced by addBranchingComplementaritiesSOS1(), buildBlockGraph(), enforceConflictgraph(), findComponents(), getPrecedence(), initConflictgraph(), initImplGraphSOS1(), presolRoundConssSOS1(), presolRoundVarsSOS1(), readFile(), readFile(), SCIP_DECL_CONSINITSOL(), SCIP_DECL_SEPAEXECLP(), SCIPcreateProbCyc(), sortGenVBounds(), and tightenVarsBoundsSOS1().
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.
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.
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 assert(), NULL, SCIP_CALL, SCIP_OKAY, and SCIPdigraphCopy().
Referenced by heurdataInit(), SCIP_DECL_PROBCOPY(), and SCIP_DECL_PROBTRANS().