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)
int	SCIPdigraphGetNNodes (SCIP_DIGRAPH *digraph)
void *	SCIPdigraphGetNodeDatas (SCIP_DIGRAPH *digraph, int node)
void	SCIPdigraphSetNodeDatas (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 **	SCIPdigraphGetSuccessorsDatas (SCIP_DIGRAPH *digraph, int node)
SCIP_RETCODE	SCIPdigraphComputeUndirectedComponents (SCIP_DIGRAPH *digraph, int minsize, int *components, int *ncomponents)
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

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

Definition at line 5326 of file misc.c.

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

Referenced by presolComponents(), and sortGenVBounds().

SCIP_RETCODE SCIPdigraphResize	(	SCIP_DIGRAPH *	digraph,
		int	nnodes
	)

resize directed graph structure

Parameters

digraph	directed graph
nnodes	new number of nodes

Definition at line 5354 of file misc.c.

References SCIP_Digraph::arcdatas, BMSreallocMemoryArray, SCIP_Digraph::nnodes, SCIP_Digraph::nodedatas, 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

Parameters

targetdigraph	pointer to store the copied directed graph
sourcedigraph	source directed graph

Definition at line 5386 of file misc.c.

References SCIP_Digraph::arcdatas, BMSallocClearMemoryArray, BMSallocMemory, BMSduplicateMemoryArray, SCIP_Digraph::components, SCIP_Digraph::componentstarts, SCIP_Digraph::ncomponents, SCIP_Digraph::nnodes, 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

digraph	directed graph
sizes	sizes of the successor lists

Definition at line 5442 of file misc.c.

References SCIP_Digraph::arcdatas, 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

digraph

pointer to the directed graph

Definition at line 5464 of file misc.c.

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

Referenced by presolComponents(), and sortGenVBounds().

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 5535 of file misc.c.

References SCIP_Digraph::arcdatas, ensureSuccessorsSize(), SCIP_Digraph::nsuccessors, NULL, SCIP_CALL, SCIP_OKAY, and SCIP_Digraph::successors.

Referenced by fillDigraph(), SCIPdigraphComputeUndirectedComponents(), and sortGenVBounds().

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 5563 of file misc.c.

References SCIP_Digraph::arcdatas, ensureSuccessorsSize(), SCIP_Digraph::nsuccessors, NULL, SCIP_CALL, SCIP_OKAY, and SCIP_Digraph::successors.

int SCIPdigraphGetNNodes

(

SCIP_DIGRAPH *

digraph

)

returns the number of nodes of the given digraph

Parameters

digraph

directed graph

Definition at line 5597 of file misc.c.

References SCIP_Digraph::nnodes, and NULL.

void* SCIPdigraphGetNodeDatas	(	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 5607 of file misc.c.

References SCIP_Digraph::nodedatas, and NULL.

void SCIPdigraphSetNodeDatas	(	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 5623 of file misc.c.

References SCIP_Digraph::nodedatas, and NULL.

int SCIPdigraphGetNArcs

(

SCIP_DIGRAPH *

digraph

)

returns the total number of arcs in the given digraph

Parameters

digraph

directed graph

Definition at line 5637 of file misc.c.

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

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 5655 of file misc.c.

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

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 5670 of file misc.c.

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

void** SCIPdigraphGetSuccessorsDatas	(	SCIP_DIGRAPH *	digraph,
		int	node
	)

returns the array of datas 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 5688 of file misc.c.

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

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

digraph

directed graph

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

digraph

directed graph

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

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

digraph

directed graph

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

digraph	directed graph
messagehdlr	message handler
file	output file (or NULL for standard output)

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

digraph	directed graph
file	file to write to

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

digraph	directed graph
messagehdlr	message handler
file	output file (or NULL for standard output)

Definition at line 6089 of file misc.c.

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