Contains functions related to managing ParentSetData. More...

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include "parent_set_data.h"
#include "utils.h"
#include "vector.h"
#include "vectorlist.h"
#include "stack.h"
#include "scip/pub_var.h"

Include dependency graph for parent_set_data.c:

Functions
static SCIP_RETCODE	findStronglyConnectedComponents (int n, int current_node, int current_index, SCIP_Bool adj_matrix, Vector index_array, Vector lowlink, Stack s, VectorList *components)
	Finds strongly connected components in an adjacency matrix. More...

SCIP_RETCODE	PS_copyParentSetData (SCIP scip, ParentSetData original, ParentSetData **duplicate)
	Makes a deep copy of a ParentSetData structure. More...

SCIP_RETCODE	PS_deallocateParentSetData (SCIP scip, ParentSetData *psd, SCIP_Bool releasevars)
	Deallocates the memory associated with a ParentSetData structure. More...

SCIP_RETCODE	PS_parse (SCIP scip, char str, ParentSetData **psd)
	Parses a ParentSetData structure from a sting. More...

SCIP_RETCODE	PS_specialiseFor (SCIP scip, ParentSetData original, int nodes, int num_nodes, ParentSetData *specialisation)
	Creates a subset of parent set data mentioning only the given nodes. More...

SCIP_RETCODE	PS_splitToComponents (SCIP scip, ParentSetData original, int num_components, ParentSetData **components)
	Splits a single set of parent set data in to its strongly connected components. More...

SCIP_RETCODE	PS_writeToFile (SCIP scip, FILE file, ParentSetData *psd)
	Writes a ParentSetData structure to file. More...

Detailed Description

Contains functions related to managing ParentSetData.

Function Documentation

◆ findStronglyConnectedComponents()

static SCIP_RETCODE findStronglyConnectedComponents	(	int	n,
		int	current_node,
		int *	current_index,
		SCIP_Bool **	adj_matrix,
		Vector *	index_array,
		Vector *	lowlink,
		Stack *	s,
		VectorList *	components
	)

static

Finds strongly connected components in an adjacency matrix.

The algorithm used is Tarjan's Algorithm. See the Wikipedia page for details. See PS_splitToComponents() to see how the intermediate data structures should be intialised.

Parameters

n	The number of nodes.
current_node	The node to consider next.
current_index	The current depth index.
adj_matrix	The adjacency matrix to calculate on.
index_array	An intermediate data structure.
lowlink	An intermediate data structure.
s	An intermediate datastructure.
components	The strongly connected components found in the matrix.

Returns: SCIP_OKAY if the procedure worked correctly, or an error otherwsie.

References Vector::items, StackContains(), StackPop(), StackPush(), StackSize(), VectorAppend(), VectorCreate(), and VectorListAppend().

Referenced by PS_splitToComponents().

Here is the call graph for this function:

◆ PS_copyParentSetData()

SCIP_RETCODE PS_copyParentSetData	(	SCIP *	scip,
		ParentSetData *	original,
		ParentSetData **	duplicate
	)

Makes a deep copy of a ParentSetData structure.

Parameters

scip	The SCIP instance to which the data belongs.
original	The original data structure.
duplicate	A pointer to the duplicated data structure.

Returns: SCIP_OKAY if copying suceeded.

References ParentSetData::arrow, ParentSetData::edge, get_arrow(), get_edge(), hashtableCreateArrow(), ParentSetData::n, ParentSetData::nodeNames, ParentSetData::nParents, ParentSetData::nParentSets, ParentSetData::ParentSets, ParentSetData::PaVars, put_arrow(), and put_edge().

Referenced by createConsData(), and MD_setParentSetData().

Here is the call graph for this function:

◆ PS_deallocateParentSetData()

SCIP_RETCODE PS_deallocateParentSetData	(	SCIP *	scip,
		ParentSetData **	psd,
		SCIP_Bool	releasevars
	)

Deallocates the memory associated with a ParentSetData structure.

Parameters

scip	The SCIP instance which the data refers to.
psd	A pointer to the data structure to deallocate.
releasevars	Whether to release the variables (family, arrow and edge)

Returns: SCIP_OKAY if the allocation succeeded.

References get_arrow(), get_edge(), and hashtablefreeArrow().

Referenced by addAcyclicityConstraints(), DC_tryToSplit(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSFREE(), SCIP_DECL_CONSPARSE(), and SCIP_DECL_PROBDELORIG().

Here is the call graph for this function:

◆ PS_parse()

SCIP_RETCODE PS_parse	(	SCIP *	scip,
		char *	str,
		ParentSetData **	psd
	)

Parses a ParentSetData structure from a sting.

Parameters

scip	The SCIP instance the data will belong to.
str	The string to parse.
psd	A pointer to the data structure resulting from parsing.

Returns: SCIP_OKAY if parsing succeeded.

References hashtableCreateArrow(), put_arrow(), put_edge(), UT_parseArray(), UT_parseIntArray(), UT_parseIntArrayArray(), UT_parseIntArrayArrayArray(), UT_parseStringArray(), and UT_parseVarArrayArray().

Referenced by SCIP_DECL_CONSPARSE().

Here is the call graph for this function:

◆ PS_specialiseFor()

SCIP_RETCODE PS_specialiseFor	(	SCIP *	scip,
		ParentSetData *	original,
		int *	nodes,
		int	num_nodes,
		ParentSetData **	specialisation
	)

Creates a subset of parent set data mentioning only the given nodes.

Parameters

scip	The SCIP instance the parent set dtaa is used in.
original	The original data from which the subset will be taken.
nodes	The nodes which the new subset should be limited to.
num_nodes	The number of nodes the subset will be limited to.
specialisation	The subset of the parent set data containing only references to the requested nodes.

Returns: SCIP_OKAY if the procedure worked, or an appropriate error otherwise.

References get_arrow(), get_edge(), hashtableCreateArrow(), ParentSetData::n, ParentSetData::nodeNames, ParentSetData::nParents, ParentSetData::nParentSets, ParentSetData::ParentSets, ParentSetData::PaVars, put_arrow(), and put_edge().

Referenced by PS_splitToComponents().

Here is the call graph for this function:

◆ PS_splitToComponents()

SCIP_RETCODE PS_splitToComponents	(	SCIP *	scip,
		ParentSetData *	original,
		int *	num_components,
		ParentSetData ***	components
	)

Splits a single set of parent set data in to its strongly connected components.

If any variables are fixed at zero locally, the parent set the variable refers to is treated as if it did not exist for the purposes of finding the components.

Parameters

scip	The SCIP instance being used.
original	The parent set data to search for components in.
num_components	The number of strongly connected components found.
components	The strongly connected components of the data.