

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) 

creates directed graph structure
 Parameters

digraph  pointer to store the created directed graph 
nnodes  number of nodes 
resize directed graph structure
 Parameters

digraph  directed graph 
nnodes  new number of nodes 
copies directed graph structure
 Note
 The data in nodedata is copied verbatim. This possibly has to be adapted by the user.
 Parameters

targetdigraph  pointer to store the copied directed graph 
sourcedigraph  source directed graph 
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 
frees given directed graph structure
 Parameters

digraph  pointer to the directed graph 
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 
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 
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 
returns the number of nodes of the given digraph
 Parameters

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 
void SCIPdigraphSetNodeData 
( 
SCIP_DIGRAPH * 
digraph, 


void * 
dataptr, 


int 
node 

) 
 
sets the node data
 Parameters

digraph  directed graph 
dataptr  user node data pointer, or NULL 
node  node for which the node data is returned 
returns the total number of arcs in the given digraph
 Parameters

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 
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 
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 
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 onebyone using SCIPdigraphGetComponent() 
ncomponents  pointer to store the number of components; or NULL, if the number of components is accessed by SCIPdigraphGetNComponents() 
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 
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

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

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 
frees the component information for the given directed graph
 Parameters

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