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