Scippy

SCIP

Solving Constraint Integer Programs

Directed Graph

Detailed Description

Functions

SCIP_RETCODE SCIPdigraphCreate (SCIP_DIGRAPH **digraph, int nnodes)
 
SCIP_RETCODE SCIPdigraphResize (SCIP_DIGRAPH *digraph, int nnodes)
 
SCIP_RETCODE SCIPdigraphCopy (SCIP_DIGRAPH **targetdigraph, SCIP_DIGRAPH *sourcedigraph)
 
SCIP_RETCODE SCIPdigraphSetSizes (SCIP_DIGRAPH *digraph, int *sizes)
 
void SCIPdigraphFree (SCIP_DIGRAPH **digraph)
 
SCIP_RETCODE SCIPdigraphAddArc (SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
 
SCIP_RETCODE SCIPdigraphAddArcSafe (SCIP_DIGRAPH *digraph, int startnode, int endnode, void *data)
 
SCIP_RETCODE SCIPdigraphSetNSuccessors (SCIP_DIGRAPH *digraph, int node, int nsuccessors)
 
int SCIPdigraphGetNNodes (SCIP_DIGRAPH *digraph)
 
void * SCIPdigraphGetNodeData (SCIP_DIGRAPH *digraph, int node)
 
void SCIPdigraphSetNodeData (SCIP_DIGRAPH *digraph, void *dataptr, int node)
 
int SCIPdigraphGetNArcs (SCIP_DIGRAPH *digraph)
 
int SCIPdigraphGetNSuccessors (SCIP_DIGRAPH *digraph, int node)
 
int * SCIPdigraphGetSuccessors (SCIP_DIGRAPH *digraph, int node)
 
void ** SCIPdigraphGetSuccessorsData (SCIP_DIGRAPH *digraph, int node)
 
SCIP_RETCODE SCIPdigraphComputeUndirectedComponents (SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
 
SCIP_RETCODE SCIPdigraphComputeDirectedComponents (SCIP_DIGRAPH *digraph, int compidx, int *strongcomponents, int *strongcompstartidx, int *nstrongcomponents)
 
SCIP_RETCODE SCIPdigraphTopoSortComponents (SCIP_DIGRAPH *digraph)
 
int SCIPdigraphGetNComponents (SCIP_DIGRAPH *digraph)
 
void SCIPdigraphGetComponent (SCIP_DIGRAPH *digraph, int compidx, int **nodes, int *nnodes)
 
void SCIPdigraphFreeComponents (SCIP_DIGRAPH *digraph)
 
void SCIPdigraphPrint (SCIP_DIGRAPH *digraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
 
void SCIPdigraphPrintGml (SCIP_DIGRAPH *digraph, FILE *file)
 
void SCIPdigraphPrintComponents (SCIP_DIGRAPH *digraph, SCIP_MESSAGEHDLR *messagehdlr, FILE *file)
 

Function Documentation

SCIP_RETCODE SCIPdigraphCreate ( SCIP_DIGRAPH **  digraph,
int  nnodes 
)

creates directed graph structure

Parameters
digraphpointer to store the created directed graph
nnodesnumber of nodes

Definition at line 5596 of file misc.c.

References BMSallocClearMemoryArray, BMSallocMemory, NULL, SCIP_ALLOC, and SCIP_OKAY.

Referenced by addBranchingComplementaritiesSOS1(), enforceConflictgraph(), initConflictgraph(), initImplGraphSOS1(), presolComponents(), presolRoundConssSOS1(), presolRoundVarsSOS1(), sortGenVBounds(), and tightenVarsBoundsSOS1().

SCIP_RETCODE SCIPdigraphResize ( SCIP_DIGRAPH digraph,
int  nnodes 
)

resize directed graph structure

Parameters
digraphdirected graph
nnodesnew number of nodes

Definition at line 5625 of file misc.c.

References SCIP_Digraph::arcdata, BMSreallocMemoryArray, SCIP_Digraph::nnodes, SCIP_Digraph::nodedata, SCIP_Digraph::nsuccessors, NULL, SCIP_ALLOC, SCIP_OKAY, SCIP_Digraph::successors, and SCIP_Digraph::successorssize.

SCIP_RETCODE SCIPdigraphCopy ( SCIP_DIGRAPH **  targetdigraph,
SCIP_DIGRAPH sourcedigraph 
)

copies directed graph structure

Note
The data in nodedata is copied verbatim. This possibly has to be adapted by the user.
Parameters
targetdigraphpointer to store the copied directed graph
sourcedigraphsource directed graph

Definition at line 5661 of file misc.c.

References SCIP_Digraph::arcdata, BMSallocClearMemoryArray, BMSallocMemory, BMSduplicateMemoryArray, SCIP_Digraph::components, SCIP_Digraph::componentstarts, SCIP_Digraph::ncomponents, SCIP_Digraph::nnodes, SCIP_Digraph::nodedata, SCIP_Digraph::nsuccessors, NULL, SCIP_ALLOC, SCIP_OKAY, and SCIP_Digraph::successors.

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
digraphdirected graph
sizessizes of the successor lists

Definition at line 5720 of file misc.c.

References SCIP_Digraph::arcdata, BMSallocMemoryArray, SCIP_Digraph::nnodes, SCIP_Digraph::nsuccessors, NULL, SCIP_ALLOC, SCIP_OKAY, SCIP_Digraph::successors, and SCIP_Digraph::successorssize.

Referenced by presolComponents().

void SCIPdigraphFree ( SCIP_DIGRAPH **  digraph)

frees given directed graph structure

Parameters
digraphpointer to the directed graph

Definition at line 5742 of file misc.c.

References BMSfreeMemory, BMSfreeMemoryArray, BMSfreeMemoryArrayNull, NULL, and SCIPdigraphFreeComponents().

Referenced by freeConflictgraph(), presolComponents(), presolRoundConssSOS1(), presolRoundVarsSOS1(), 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

Note
if the arc is already contained, it is added a second time
Parameters
digraphdirected graph
startnodestart node of the arc
endnodestart node of the arc
datadata that should be stored for the arc; or NULL

Definition at line 5814 of file misc.c.

References SCIP_Digraph::arcdata, BMS_BufMem::data, ensureSuccessorsSize(), SCIP_Digraph::nsuccessors, NULL, SCIP_CALL, SCIP_OKAY, and SCIP_Digraph::successors.

Referenced by addBranchingComplementaritiesSOS1(), fillDigraph(), 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

Note
if there already exists an arc from startnode to endnode, the new arc is not added, even if its data is different
Parameters
digraphdirected graph
startnodestart node of the arc
endnodestart node of the arc
datadata that should be stored for the arc; or NULL

Definition at line 5842 of file misc.c.

References SCIP_Digraph::arcdata, BMS_BufMem::data, ensureSuccessorsSize(), 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

Parameters
digraphdirected graph
nodenode for which the number of successors has to be changed
nsuccessorsnew number of successors

Definition at line 5876 of file misc.c.

References SCIP_Digraph::nsuccessors, NULL, and SCIP_OKAY.

Referenced by resetConflictgraphSOS1().

int SCIPdigraphGetNNodes ( SCIP_DIGRAPH digraph)

returns the number of nodes of the given digraph

Parameters
digraphdirected graph

Definition at line 5892 of file misc.c.

References SCIP_Digraph::nnodes, and NULL.

Referenced by cliqueGetCommonSuccessorsSOS1(), nodeGetSolvalBinaryBigMSOS1(), nodeGetSolvalVarboundLbSOS1(), nodeGetSolvalVarboundUbSOS1(), performImplicationGraphAnalysis(), and sortGenVBounds().

void* SCIPdigraphGetNodeData ( SCIP_DIGRAPH digraph,
int  node 
)
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
digraphdirected graph
dataptruser node data pointer, or NULL
nodenode for which the node data is returned

Definition at line 5918 of file misc.c.

References SCIP_Digraph::nodedata, and NULL.

Referenced by freeConflictgraph(), initConflictgraph(), and initImplGraphSOS1().

int SCIPdigraphGetNArcs ( SCIP_DIGRAPH digraph)

returns the total number of arcs in the given digraph

Parameters
digraphdirected graph

Definition at line 5932 of file misc.c.

References SCIP_Digraph::nnodes, SCIP_Digraph::nsuccessors, and NULL.

Referenced by SCIP_DECL_SEPAEXECLP(), and sepaImplBoundCutsSOS1().

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
digraphdirected graph
nodenode for which the data corresponding to the outgoing arcs is returned

Definition at line 5983 of file misc.c.

References SCIP_Digraph::arcdata, SCIP_Digraph::nsuccessors, NULL, and SCIP_Digraph::successorssize.

Referenced by getSOS1Implications(), performImplicationGraphAnalysis(), presolRoundVarsSOS1(), propVariableNonzero(), sepaImplBoundCutsSOS1(), and updateArcData().

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
digraphdirected graph
minsizeall components with less nodes are ignored
componentsarray 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()
ncomponentspointer to store the number of components; or NULL, if the number of components is accessed by SCIPdigraphGetNComponents()

Definition at line 6077 of file misc.c.

References BMSallocClearMemoryArray, BMSallocMemoryArray, BMSclearMemoryArray, BMScopyMemoryArray, BMSfreeMemoryArray, BMSreallocMemoryArray, SCIP_Digraph::components, SCIP_Digraph::componentstarts, SCIP_Digraph::componentstartsize, depthFirstSearch(), SCIP_Digraph::ncomponents, SCIP_Digraph::nnodes, SCIP_Digraph::nsuccessors, NULL, SCIP_ALLOC, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIPdigraphAddArc(), SCIPdigraphFreeComponents(), and SCIP_Digraph::successors.

Referenced by presolComponents(), 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).

Note
In general a topological sort of the strongly connected components is not unique.
Parameters
digraphdirected graph
compidxnumber of the undirected connected component
strongcomponentsarray to store the strongly connected components (length >= size of the component)
strongcompstartidxarray to store the start indices of the strongly connected components (length >= size of the component)
nstrongcomponentspointer to store the number of strongly connected components

Definition at line 6398 of file misc.c.

References BMSallocMemoryArray, BMSfreeMemoryArrayNull, SCIP_Digraph::components, SCIP_Digraph::componentstarts, FALSE, SCIP_Digraph::nnodes, NULL, SCIP_ALLOC_TERMINATE, SCIP_Bool, 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().

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
digraphdirected graph

Definition at line 6189 of file misc.c.

References BMSallocClearMemoryArray, BMSallocMemoryArray, BMSfreeMemoryArray, SCIP_Digraph::components, SCIP_Digraph::componentstarts, depthFirstSearch(), SCIP_Digraph::ncomponents, SCIP_Digraph::nnodes, NULL, SCIP_ALLOC, SCIP_Bool, and SCIP_OKAY.

Referenced by sortGenVBounds().

int SCIPdigraphGetNComponents ( SCIP_DIGRAPH digraph)

returns the number of previously computed undirected components for the given directed graph

Parameters
digraphdirected graph

Definition at line 6253 of file misc.c.

References SCIP_Digraph::componentstartsize, SCIP_Digraph::ncomponents, and NULL.

Referenced by 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.

Parameters
digraphdirected graph
compidxnumber of the component to return
nodespointer to store the nodes in the component; or NULL, if not needed
nnodespointer to store the number of nodes in the component; or NULL, if not needed

Definition at line 6266 of file misc.c.

References SCIP_Digraph::components, SCIP_Digraph::componentstarts, and NULL.

Referenced by presolComponents(), and sortGenVBounds().

void SCIPdigraphFreeComponents ( SCIP_DIGRAPH digraph)

frees the component information for the given directed graph

Parameters
digraphdirected graph

Definition at line 6485 of file misc.c.

References BMSfreeMemoryArray, SCIP_Digraph::components, SCIP_Digraph::componentstarts, SCIP_Digraph::componentstartsize, SCIP_Digraph::ncomponents, and NULL.

Referenced by SCIPdigraphComputeUndirectedComponents(), and SCIPdigraphFree().

void SCIPdigraphPrint ( SCIP_DIGRAPH digraph,
SCIP_MESSAGEHDLR messagehdlr,
FILE *  file 
)

output of the given directed graph via the given message handler

Parameters
digraphdirected graph
messagehdlrmessage handler
fileoutput file (or NULL for standard output)

Definition at line 6512 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

Parameters
digraphdirected graph
filefile to write to

Definition at line 6547 of file misc.c.

References SCIP_Digraph::nnodes, SCIP_Digraph::nsuccessors, NULL, SCIP_MAXSTRLEN, SCIPgmlWriteArc(), SCIPgmlWriteClosing(), SCIPgmlWriteNode(), SCIPgmlWriteOpening(), SCIPsnprintf(), SCIP_Digraph::successors, and TRUE.

void SCIPdigraphPrintComponents ( SCIP_DIGRAPH digraph,
SCIP_MESSAGEHDLR messagehdlr,
FILE *  file 
)

output of the given directed graph via the given message handler

Parameters
digraphdirected graph
messagehdlrmessage handler
fileoutput file (or NULL for standard output)

Definition at line 6586 of file misc.c.

References SCIP_Digraph::components, SCIP_Digraph::componentstarts, SCIP_Digraph::ncomponents, and SCIPmessageFPrintInfo().