Detailed Description

internal methods for dealing with hypergraphs

Author: Matthias Walter

Definition in file hypergraph.c.

#include <assert.h>
#include "scip/hypergraph.h"
#include "scip/misc.h"
#include "scip/pub_message.h"
#include "scip/struct_hypergraph.h"

Go to the source code of this file.

Functions
static SCIP_RETCODE	ensureNumVertices (SCIP_HYPERGRAPH *hypergraph, int required)
	enlarges vertex arrays to have capacity for at least `required` vertices
static SCIP_RETCODE	ensureNumEdges (SCIP_HYPERGRAPH *hypergraph, int required)
	enlarges edge arrays to have capacity for at least `required` edges
static SCIP_RETCODE	ensureNumEdgesVertices (SCIP_HYPERGRAPH *hypergraph, int required)
	enlarges arrays for incident vertex/edge pairs to have capacity for at least `required`
static SCIP_RETCODE	ensureNumOverlaps (SCIP_HYPERGRAPH *hypergraph, int required)
	enlarges overlap arrays to have capacity for at least `required` overlaps
static SCIP_RETCODE	ensureNumOverlapsVertices (SCIP_HYPERGRAPH *hypergraph, int required)
	enlarges overlapVertices array to have capacity for at least `required` overlaps' vertices
SCIP_RETCODE	SCIPhypergraphCreate (SCIP_HYPERGRAPH *phypergraph, BMS_BLKMEM blkmem, int memvertices, int memedges, int memoverlaps, int memedgesvertices, size_t sizevertexdata, size_t sizeedgedata, size_t sizeoverlapdata)
	creates a hypergraph
SCIP_RETCODE	SCIPhypergraphFree (SCIP_HYPERGRAPH **phypergraph)
	frees a hypergraph
SCIP_RETCODE	SCIPhypergraphClear (SCIP_HYPERGRAPH *hypergraph)
	clears a hypergraph, deleting all vertices and edges
SCIP_RETCODE	SCIPhypergraphAddVertex (SCIP_HYPERGRAPH hypergraph, SCIP_HYPERGRAPH_VERTEX pvertex, SCIP_HYPERGRAPH_VERTEXDATA **pvertexdata)
	adds a new vertex to the hypergraph
SCIP_RETCODE	SCIPhypergraphAddEdge (SCIP_HYPERGRAPH hypergraph, int nvertices, SCIP_HYPERGRAPH_VERTEX vertices, SCIP_HYPERGRAPH_EDGE pedge, SCIP_HYPERGRAPH_EDGEDATA *pedgedata)
	adds a new edge to the hypergraph
static	SCIP_DECL_HASHGETKEY (overlapHashGetKey)
	get-key function for overlap hashtable
static	SCIP_DECL_HASHKEYEQ (overlapHashKeyEqPtr)
	equality function for overlap hashtable
static	SCIP_DECL_HASHKEYVAL (overlapHashKeyValPtr)
	hash function for overlap hashtable
static SCIP_RETCODE	findOverlap (SCIP_HYPERGRAPH hypergraph, int nvertices, int vertices, int poverlap, SCIP_Bool add, SCIP_Bool padded)
	finds an overlap specified by a sorted vertex set, potentially adding it
SCIP_RETCODE	SCIPhypergraphComputeOverlaps (SCIP_HYPERGRAPH hypergraph, SCIP_DECL_HYPERGRAPH_OVERLAP((handler)), void *userdata)
	computes all overlaps and stores overlaps' vertices and all edges' overlaps
SCIP_RETCODE	SCIPhypergraphComputeVerticesEdges (SCIP_HYPERGRAPH *hypergraph)
	computes each vertex' list of incident edges
SCIP_RETCODE	SCIPhypergraphOverlapFind (SCIP_HYPERGRAPH hypergraph, int nvertices, SCIP_HYPERGRAPH_VERTEX vertices, SCIP_HYPERGRAPH_OVERLAP *poverlap)
	finds the overlap corresponding to vertex set `vertices`; returns -1 if it is not found
SCIP_RETCODE	SCIPhypergraphIntersectEdges (SCIP_HYPERGRAPH hypergraph, SCIP_HYPERGRAPH_EDGE first, SCIP_HYPERGRAPH_EDGE second, SCIP_HYPERGRAPH_OVERLAP poverlap, SCIP_HYPERGRAPH_VERTEX *pvertex)
	finds the overlap or singleton vertex corresponding to the intersection of edges `first` and `second`
SCIP_RETCODE	SCIPhypergraphComputeOverlapsEdges (SCIP_HYPERGRAPH *hypergraph)
	computes all overlaps' lists of incident edges
SCIP_RETCODE	SCIPhypergraphComputeVerticesOverlaps (SCIP_HYPERGRAPH *hypergraph)
	computes all vertices' lists of incident overlaps
SCIP_Bool	SCIPhypergraphOverlapsDisjoint (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_OVERLAP overlap1, SCIP_HYPERGRAPH_OVERLAP overlap2)
	returns whether overlaps `overlap1` and `overlap2` are disjoint
SCIP_Bool	SCIPhypergraphIsValid (SCIP_HYPERGRAPH hypergraph, FILE file)
	asserts that the hypergraph data structures are valid
SCIP_RETCODE	SCIPhypergraphIterInit (SCIP_HYPERGRAPH hypergraph, SCIP_HYPERGRAPH_ITER iterator)
	initializes a hypergraph iterator's internal memory
void	SCIPhypergraphIterClear (SCIP_HYPERGRAPH hypergraph, SCIP_HYPERGRAPH_ITER iterator)
	frees a hypergraph iterator's internal memory
void	SCIPhypergraphIterStart (SCIP_HYPERGRAPH hypergraph, SCIP_HYPERGRAPH_ITER iterator, SCIP_HYPERGRAPH_EDGE base, unsigned int minoverlapsize, SCIP_Bool onlylater, SCIP_Bool findoverlaps)
	initializes the iterator to the first adjacent edge of `base`
SCIP_Bool	SCIPhypergraphIterValid (SCIP_HYPERGRAPH_ITER *iterator)
	returns whether the iterator is valid
void	SCIPhypergraphIterNext (SCIP_HYPERGRAPH hypergraph, SCIP_HYPERGRAPH_ITER iterator)
	initializes the iterator to the first adjacent edge of `base`
SCIP_HYPERGRAPH_EDGE	SCIPhypergraphIterBase (SCIP_HYPERGRAPH_ITER *iterator)
	returns the base edge
SCIP_HYPERGRAPH_EDGE	SCIPhypergraphIterAdjacent (SCIP_HYPERGRAPH_ITER *iterator)
	returns the current adjacent edge
SCIP_HYPERGRAPH_VERTEX	SCIPhypergraphIterMinVertex (SCIP_HYPERGRAPH_ITER *iterator)
	returns the minimum vertex in the intersection of the base and the current adjacent edge
SCIP_HYPERGRAPH_OVERLAP	SCIPhypergraphIterOverlap (SCIP_HYPERGRAPH_ITER *iterator)
	returns the overlap for the intersection of the base and the current adjacent edge
int	SCIPhypergraphGetNVertices (SCIP_HYPERGRAPH *hypergraph)
	returns the number of vertices
int	SCIPhypergraphGetNEdges (SCIP_HYPERGRAPH *hypergraph)
	returns the number of edges
BMS_BLKMEM *	SCIPhypergraphBlkmem (SCIP_HYPERGRAPH *hypergraph)
	returns the hypergraph's block memory structure
int	SCIPhypergraphGetNOverlaps (SCIP_HYPERGRAPH *hypergraph)
	returns the number of overlaps
int	SCIPhypergraphGetNIncidences (SCIP_HYPERGRAPH *hypergraph)
	returns the number of edge-vertex incidences
SCIP_HYPERGRAPH_VERTEXDATA *	SCIPhypergraphVertexData (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_VERTEX vertex)
	returns additional data of `vertex`
SCIP_HYPERGRAPH_EDGEDATA *	SCIPhypergraphEdgeData (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_EDGE edge)
	returns additional data of `edge`
SCIP_HYPERGRAPH_OVERLAPDATA *	SCIPhypergraphOverlapData (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_OVERLAP overlap)
	returns additional data of `overlap`
int	SCIPhypergraphEdgeSize (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_EDGE edge)
	returns the number of vertices of `edge`
SCIP_HYPERGRAPH_VERTEX *	SCIPhypergraphEdgeVertices (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_EDGE edge)
	returns the array of vertices of `edge`
SCIP_Bool	SCIPhypergraphHasVertexEdges (SCIP_HYPERGRAPH *hypergraph)
	returns whether vertices' incident edges are known.
int	SCIPhypergraphVertexEdgesFirst (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_VERTEX vertex)
	returns an index for the first edge incident to `vertex`
int	SCIPhypergraphVertexEdgesBeyond (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_VERTEX vertex)
	returns an index beyond the last edge incident to `vertex`
SCIP_HYPERGRAPH_EDGE	SCIPhypergraphVertexEdgesGetAtIndex (SCIP_HYPERGRAPH *hypergraph, int idx)
	returns the edge corresponding to `index` that is incident to a vertex
SCIP_Bool	SCIPhypergraphHasOverlaps (SCIP_HYPERGRAPH *hypergraph)
	returns whether edges' overlaps and overlaps' vertices are known.
int	SCIPhypergraphOverlapSize (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_OVERLAP overlap)
	returns the number of vertices of `overlap`
SCIP_HYPERGRAPH_VERTEX *	SCIPhypergraphOverlapVertices (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_OVERLAP overlap)
	returns the array of sorted vertices of `overlap`
int	SCIPhypergraphEdgesOverlapsFirst (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_EDGE edge)
	returns an index for the first overlap incident to `edge`
int	SCIPhypergraphEdgesOverlapsBeyond (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_EDGE edge)
	returns an index beyond the last overlap incident to `edge`
SCIP_HYPERGRAPH_OVERLAP	SCIPhypergraphEdgesOverlapsGetAtIndex (SCIP_HYPERGRAPH *hypergraph, int idx)
	returns the overlap corresponding to `idx` that is incident to an edge
SCIP_Bool	SCIPhypergraphHasOverlapsEdges (SCIP_HYPERGRAPH *hypergraph)
	returns whether overlaps' incident edges are known.
int	SCIPhypergraphOverlapsEdgesFirst (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_OVERLAP overlap)
	returns an index for the first edge incident to `overlap`
int	SCIPhypergraphOverlapsEdgesBeyond (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_OVERLAP overlap)
	returns an index beyond the last edge incident to `overlap`
SCIP_HYPERGRAPH_OVERLAP	SCIPhypergraphOverlapsEdgesGetAtIndex (SCIP_HYPERGRAPH *hypergraph, int idx)
	returns the edge corresponding to `idx` that is incident to an overlap
SCIP_Bool	SCIPhypergraphHasVertexOverlaps (SCIP_HYPERGRAPH *hypergraph)
	returns whether vertices' incident overlaps are known
int	SCIPhypergraphVertexOverlapsFirst (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_VERTEX vertex)
	returns an index for the first overlap containing `vertex`
int	SCIPhypergraphVertexOverlapsBeyond (SCIP_HYPERGRAPH *hypergraph, SCIP_HYPERGRAPH_VERTEX vertex)
	returns an index beyond the last overlap incident to `vertex`
SCIP_HYPERGRAPH_OVERLAP	SCIPhypergraphVertexOverlapsGetAtIndex (SCIP_HYPERGRAPH *hypergraph, int idx)
	returns the overlap corresponding to `idx` that is incident to a vertex

Function Documentation

◆ ensureNumVertices()

SCIP_RETCODE ensureNumVertices	(	SCIP_HYPERGRAPH *	hypergraph,
		int	required )

static

enlarges vertex arrays to have capacity for at least required vertices

Parameters

hypergraph	The hypergraph.
required	Required vertex capacity.

Definition at line 45 of file hypergraph.c.

References assert(), SCIP_Hypergraph::blkmem, BMSreallocBlockMemoryArray, MAX, SCIP_Hypergraph::memvertices, SCIP_ALLOC, SCIP_OKAY, SCIPdebugMessage, SCIP_Hypergraph::sizevertexdata, and SCIP_Hypergraph::verticesdata.

Referenced by SCIPhypergraphAddVertex(), and SCIPhypergraphCreate().

◆ ensureNumEdges()

SCIP_RETCODE ensureNumEdges	(	SCIP_HYPERGRAPH *	hypergraph,
		int	required )

static

enlarges edge arrays to have capacity for at least required edges

Parameters

hypergraph	The hypergraph.
required	Required edge capacity.

Definition at line 73 of file hypergraph.c.

References assert(), SCIP_Hypergraph::blkmem, BMSallocBlockMemoryArray, BMSreallocBlockMemoryArray, SCIP_Hypergraph::edgesdata, SCIP_Hypergraph::edgesverticesbeg, MAX, SCIP_Hypergraph::memedges, SCIP_ALLOC, SCIP_OKAY, SCIPdebugMessage, and SCIP_Hypergraph::sizeedgedata.

Referenced by SCIPhypergraphAddEdge(), and SCIPhypergraphCreate().

◆ ensureNumEdgesVertices()

SCIP_RETCODE ensureNumEdgesVertices	(	SCIP_HYPERGRAPH *	hypergraph,
		int	required )

static

enlarges arrays for incident vertex/edge pairs to have capacity for at least required

Parameters

hypergraph	The hypergraph.
required	Required incident vertex/edge capacity.

Definition at line 113 of file hypergraph.c.

References assert(), SCIP_Hypergraph::blkmem, BMSreallocBlockMemoryArray, SCIP_Hypergraph::edgesvertices, MAX, SCIP_Hypergraph::memedgesvertices, SCIP_ALLOC, SCIP_OKAY, and SCIPdebugMessage.

Referenced by SCIPhypergraphAddEdge(), and SCIPhypergraphCreate().

◆ ensureNumOverlaps()

SCIP_RETCODE ensureNumOverlaps	(	SCIP_HYPERGRAPH *	hypergraph,
		int	required )

static

enlarges overlap arrays to have capacity for at least required overlaps

Parameters

hypergraph	The hypergraph.
required	Required overlap capacity.

Definition at line 139 of file hypergraph.c.

References assert(), SCIP_Hypergraph::blkmem, BMSallocBlockMemoryArray, BMSreallocBlockMemoryArray, MAX, SCIP_Hypergraph::memoverlaps, SCIP_Hypergraph::overlapsdata, SCIP_Hypergraph::overlapsverticesbeg, SCIP_ALLOC, SCIP_OKAY, SCIPdebugMessage, and SCIP_Hypergraph::sizeoverlapdata.

Referenced by findOverlap(), and SCIPhypergraphCreate().

◆ ensureNumOverlapsVertices()

SCIP_RETCODE ensureNumOverlapsVertices	(	SCIP_HYPERGRAPH *	hypergraph,
		int	required )

static

enlarges overlapVertices array to have capacity for at least required overlaps' vertices

Parameters

hypergraph	The hypergraph.
required	Required overlapVertices capacity.

Definition at line 185 of file hypergraph.c.

References assert(), SCIP_Hypergraph::blkmem, BMSreallocBlockMemoryArray, MAX, SCIP_Hypergraph::memoverlapsvertices, SCIP_Hypergraph::overlapsvertices, SCIP_ALLOC, SCIP_OKAY, and SCIPdebugMessage.

Referenced by findOverlap().

◆ SCIPhypergraphCreate()

SCIP_RETCODE SCIPhypergraphCreate	(	SCIP_HYPERGRAPH **	phypergraph,
		BMS_BLKMEM *	blkmem,
		int	memvertices,
		int	memedges,
		int	memoverlaps,
		int	memedgesvertices,
		size_t	sizevertexdata,
		size_t	sizeedgedata,
		size_t	sizeoverlapdata )

creates a hypergraph

Parameters

phypergraph	Pointer for storing the hypergraph.
blkmem	Block memory for storage.
memvertices	Upper bound on expected number of vertices.
memedges	Upper bound on expected number of edges.
memoverlaps	Upper bound on expected number of overlaps.
memedgesvertices	Upper bound on expected average size of edges.
sizevertexdata	Size (in bytes) of additional vertex data.
sizeedgedata	Size (in bytes) of additional edge data.
sizeoverlapdata	Size (in bytes) of additional overlap data.

Definition at line 210 of file hypergraph.c.

Referenced by constructHypergraph().

◆ SCIPhypergraphFree()

SCIP_RETCODE SCIPhypergraphFree ( SCIP_HYPERGRAPH ** phypergraph )

frees a hypergraph

Parameters

phypergraph Pointer to the hypergraph.

Definition at line 281 of file hypergraph.c.

Referenced by SCIP_DECL_SEPAEXITSOL(), and separate().

◆ SCIPhypergraphClear()

SCIP_RETCODE SCIPhypergraphClear ( SCIP_HYPERGRAPH * hypergraph )

clears a hypergraph, deleting all vertices and edges

Parameters

hypergraph The hypergraph.

Definition at line 361 of file hypergraph.c.

References assert(), SCIP_Hypergraph::edgesverticesbeg, FALSE, SCIP_Hypergraph::hasoverlaps, SCIP_Hypergraph::hasoverlapsedges, SCIP_Hypergraph::hasvertexedges, SCIP_Hypergraph::hasverticesoverlaps, SCIP_Hypergraph::nedges, SCIP_Hypergraph::noverlaps, SCIP_Hypergraph::nvertices, SCIP_Hypergraph::overlaphashtable, SCIP_OKAY, and SCIPhashtableFree().

Referenced by SCIPhypergraphCreate().

◆ SCIPhypergraphAddVertex()

SCIP_RETCODE SCIPhypergraphAddVertex	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_VERTEX *	pvertex,
		SCIP_HYPERGRAPH_VERTEXDATA **	pvertexdata )

adds a new vertex to the hypergraph

Parameters

hypergraph	The hypergraph.
pvertex	Pointer for storing the new vertex.
pvertexdata	Pointer for returning the vertex's data (may be `NULL`).

Definition at line 386 of file hypergraph.c.

References assert(), ensureNumVertices(), FALSE, SCIP_Hypergraph::hasvertexedges, NULL, SCIP_Hypergraph::nvertices, SCIP_CALL, SCIP_OKAY, SCIP_Hypergraph::sizevertexdata, and SCIP_Hypergraph::verticesdata.

Referenced by constructHypergraph().

◆ SCIPhypergraphAddEdge()

SCIP_RETCODE SCIPhypergraphAddEdge	(	SCIP_HYPERGRAPH *	hypergraph,
		int	nvertices,
		SCIP_HYPERGRAPH_VERTEX *	vertices,
		SCIP_HYPERGRAPH_EDGE *	pedge,
		SCIP_HYPERGRAPH_EDGEDATA **	pedgedata )

adds a new edge to the hypergraph

Does not update the vertices' or overlaps' lists of incident edges.

Parameters

hypergraph	The hypergraph.
nvertices	Number of vertices of this edge.
vertices	Array with vertices.
pedge	Pointer for storing the new edge.
pedgedata	Pointer for returning the edge's data (may be `NULL`).

Definition at line 416 of file hypergraph.c.

References assert(), SCIP_Hypergraph::edgesdata, SCIP_Hypergraph::edgesvertices, SCIP_Hypergraph::edgesverticesbeg, ensureNumEdges(), ensureNumEdgesVertices(), FALSE, SCIP_Hypergraph::hasvertexedges, i, SCIP_Hypergraph::nedges, NULL, SCIP_CALL, SCIP_OKAY, SCIPsortInt(), and SCIP_Hypergraph::sizeedgedata.

Referenced by constructHypergraph().

◆ SCIP_DECL_HASHGETKEY()

SCIP_DECL_HASHGETKEY ( overlapHashGetKey )

static

get-key function for overlap hashtable

Definition at line 456 of file hypergraph.c.

◆ SCIP_DECL_HASHKEYEQ()

SCIP_DECL_HASHKEYEQ ( overlapHashKeyEqPtr )

static

equality function for overlap hashtable

Definition at line 463 of file hypergraph.c.

References FALSE, SCIP_Hypergraph::overlapsvertices, SCIP_Hypergraph::overlapsverticesbeg, and TRUE.

◆ SCIP_DECL_HASHKEYVAL()

SCIP_DECL_HASHKEYVAL ( overlapHashKeyValPtr )

static

hash function for overlap hashtable

Definition at line 498 of file hypergraph.c.

References assert(), i, SCIP_Hypergraph::overlapsvertices, SCIP_Hypergraph::overlapsverticesbeg, SCIPhashFour, SCIPhashThree, and SCIPhashTwo.

◆ findOverlap()

SCIP_RETCODE findOverlap	(	SCIP_HYPERGRAPH *	hypergraph,
		int	nvertices,
		int *	vertices,
		int *	poverlap,
		SCIP_Bool	add,
		SCIP_Bool *	padded )

static

finds an overlap specified by a sorted vertex set, potentially adding it

Parameters

hypergraph	Hypergraph.
nvertices	Number of vertices.
vertices	Sorted array of vertices.
poverlap	Pointer for storing the overlap.
add	Whether a missing overlap set should be added.
padded	Whether a missing overlap set was added.

Definition at line 530 of file hypergraph.c.

References assert(), ensureNumOverlaps(), ensureNumOverlapsVertices(), FALSE, i, SCIP_Hypergraph::noverlaps, NULL, SCIP_Hypergraph::overlaphashtable, SCIP_Hypergraph::overlapsvertices, SCIP_Hypergraph::overlapsverticesbeg, SCIP_Bool, SCIP_CALL, SCIP_CALL_ABORT, SCIP_OKAY, SCIPhashtableInsert(), SCIPhashtableRetrieve(), and TRUE.

Referenced by SCIPhypergraphComputeOverlaps(), SCIPhypergraphIntersectEdges(), SCIPhypergraphIterNext(), and SCIPhypergraphOverlapFind().

◆ SCIPhypergraphComputeOverlaps()

SCIP_RETCODE SCIPhypergraphComputeOverlaps	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_DECL_HYPERGRAPH_OVERLAP((*handler))	,
		void *	userdata )

computes all overlaps and stores overlaps' vertices and all edges' overlaps

Requires SCIPhypergraphHasVertexEdges to be TRUE which results from SCIPhypergraphComputeVerticesEdges.

Parameters

hypergraph	The hypergraph.
userdata	Pointer passed to `handler`.

Definition at line 587 of file hypergraph.c.

References assert(), SCIP_Hypergraph::blkmem, BMSallocBlockMemoryArray, BMSfreeBlockMemoryArray, BMSreallocBlockMemoryArray, SCIP_Hypergraph::edgesoverlaps, SCIP_Hypergraph::edgesoverlapsbeg, SCIP_Hypergraph::edgesvertices, SCIP_Hypergraph::edgesverticesbeg, findOverlap(), SCIP_Hypergraph::hasoverlaps, SCIP_Hypergraph::hasvertexedges, i, MAX, SCIP_Hypergraph::memedgesoverlaps, SCIP_Hypergraph::memedgesoverlapsbeg, SCIP_Hypergraph::nedges, SCIP_Hypergraph::noverlaps, NULL, SCIP_Hypergraph::overlaphashtable, SCIP_Hypergraph::overlapsverticesbeg, SCIP_ALLOC, SCIP_Bool, SCIP_CALL, SCIP_ERROR, SCIP_Longint, SCIP_OKAY, SCIPdebugMessage, SCIPhashtableCreate(), SCIPhypergraphOverlapData(), SCIPsortLong(), TRUE, SCIP_Hypergraph::verticesedges, SCIP_Hypergraph::verticesedgesbeg, and w.

Referenced by constructHypergraph().

◆ SCIPhypergraphComputeVerticesEdges()

SCIP_RETCODE SCIPhypergraphComputeVerticesEdges ( SCIP_HYPERGRAPH * hypergraph )

computes each vertex' list of incident edges

Parameters

hypergraph The hypergraph.

Definition at line 811 of file hypergraph.c.

References assert(), SCIP_Hypergraph::blkmem, BMSallocBlockMemoryArray, BMSreallocBlockMemoryArray, SCIP_Hypergraph::edgesvertices, SCIP_Hypergraph::edgesverticesbeg, SCIP_Hypergraph::hasvertexedges, i, MAX, SCIP_Hypergraph::memvertices, SCIP_Hypergraph::memverticesedges, SCIP_Hypergraph::memverticesedgesbeg, SCIP_Hypergraph::nedges, SCIP_Hypergraph::nvertices, SCIP_ALLOC, SCIP_OKAY, SCIPdebugMessage, TRUE, SCIP_Hypergraph::verticesedges, and SCIP_Hypergraph::verticesedgesbeg.

Referenced by constructHypergraph().

◆ SCIPhypergraphOverlapFind()

SCIP_RETCODE SCIPhypergraphOverlapFind	(	SCIP_HYPERGRAPH *	hypergraph,
		int	nvertices,
		SCIP_HYPERGRAPH_VERTEX *	vertices,
		SCIP_HYPERGRAPH_OVERLAP *	poverlap )

finds the overlap corresponding to vertex set vertices; returns -1 if it is not found

Requires SCIPhypergraphHasOverlaps to be TRUE which results from SCIPhypergraphComputeOverlaps.

Parameters

hypergraph	The hypergraph.
nvertices	Number of vertices.
vertices	Sorted array of vertices.
poverlap	Pointer for storing the overlap.

Definition at line 906 of file hypergraph.c.

References assert(), FALSE, findOverlap(), SCIP_Hypergraph::hasoverlaps, NULL, SCIP_CALL, and SCIP_OKAY.

◆ SCIPhypergraphIntersectEdges()

SCIP_RETCODE SCIPhypergraphIntersectEdges	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_EDGE	first,
		SCIP_HYPERGRAPH_EDGE	second,
		SCIP_HYPERGRAPH_OVERLAP *	poverlap,
		SCIP_HYPERGRAPH_VERTEX *	pvertex )

finds the overlap or singleton vertex corresponding to the intersection of edges first and second

Requires SCIPhypergraphHasOverlaps to be TRUE which results from SCIPhypergraphComputeOverlaps.

Parameters

hypergraph	The hypergraph.
first	First edge to intersect.
second	Second edge to intersect.
poverlap	Pointer for storing the overlap.
pvertex	Pointer for storing the vertex.

Definition at line 929 of file hypergraph.c.

References assert(), SCIP_Hypergraph::blkmem, BMSallocBlockMemoryArray, BMSfreeBlockMemoryArray, SCIP_Hypergraph::edgesvertices, SCIP_Hypergraph::edgesverticesbeg, FALSE, findOverlap(), SCIP_Hypergraph::hasoverlaps, i, NULL, SCIP_ALLOC, SCIP_CALL, SCIP_OKAY, SCIPhypergraphEdgeSize(), and w.

◆ SCIPhypergraphComputeOverlapsEdges()

SCIP_RETCODE SCIPhypergraphComputeOverlapsEdges ( SCIP_HYPERGRAPH * hypergraph )

computes all overlaps' lists of incident edges

Requires SCIPhypergraphHasOverlaps to be TRUE which results from SCIPhypergraphComputeOverlaps.

Parameters

hypergraph The hypergraph.

Definition at line 990 of file hypergraph.c.

References assert(), SCIP_Hypergraph::blkmem, BMSallocBlockMemoryArray, BMSreallocBlockMemoryArray, SCIP_Hypergraph::edgesoverlaps, SCIP_Hypergraph::edgesoverlapsbeg, SCIP_Hypergraph::hasoverlaps, SCIP_Hypergraph::hasoverlapsedges, i, MAX, SCIP_Hypergraph::memoverlaps, SCIP_Hypergraph::memoverlapsedges, SCIP_Hypergraph::memoverlapsedgesbeg, SCIP_Hypergraph::nedges, SCIP_Hypergraph::noverlaps, SCIP_Hypergraph::overlapsedges, SCIP_Hypergraph::overlapsedgesbeg, SCIP_ALLOC, SCIP_OKAY, SCIPdebugMessage, and TRUE.

Referenced by constructHypergraph().

◆ SCIPhypergraphComputeVerticesOverlaps()

SCIP_RETCODE SCIPhypergraphComputeVerticesOverlaps ( SCIP_HYPERGRAPH * hypergraph )

computes all vertices' lists of incident overlaps

Requires SCIPhypergraphHasOverlaps.

Parameters

hypergraph The hypergraph.

Definition at line 1091 of file hypergraph.c.

References assert(), SCIP_Hypergraph::blkmem, BMSallocBlockMemoryArray, BMSreallocBlockMemoryArray, SCIP_Hypergraph::hasoverlaps, SCIP_Hypergraph::hasverticesoverlaps, i, MAX, SCIP_Hypergraph::memverticesoverlaps, SCIP_Hypergraph::memverticesoverlapsbeg, SCIP_Hypergraph::noverlaps, SCIP_Hypergraph::nvertices, SCIP_Hypergraph::overlapsvertices, SCIP_Hypergraph::overlapsverticesbeg, SCIP_ALLOC, SCIP_OKAY, SCIPdebugMessage, TRUE, SCIP_Hypergraph::verticesoverlaps, and SCIP_Hypergraph::verticesoverlapsbeg.

◆ SCIPhypergraphOverlapsDisjoint()

SCIP_Bool SCIPhypergraphOverlapsDisjoint	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_OVERLAP	overlap1,
		SCIP_HYPERGRAPH_OVERLAP	overlap2 )

returns whether overlaps overlap1 and overlap2 are disjoint

Parameters

hypergraph	The hypergraph.
overlap1	First overlap.
overlap2	Second overlap.

Definition at line 1187 of file hypergraph.c.

References assert(), FALSE, i, SCIP_Bool, SCIPhypergraphOverlapSize(), SCIPhypergraphOverlapVertices(), and TRUE.

Referenced by separateTwoFlower().

◆ SCIPhypergraphIsValid()

SCIP_Bool SCIPhypergraphIsValid	(	SCIP_HYPERGRAPH *	hypergraph,
		FILE *	file )

asserts that the hypergraph data structures are valid

Parameters

hypergraph	The hypergraph.
file	A file stream to print problems to (can be `NULL`).

Definition at line 1221 of file hypergraph.c.

References assert(), SCIP_Hypergraph::blkmem, BMSallocBlockMemoryArray, BMSfreeBlockMemoryArray, FALSE, i, SCIP_Hypergraph::nedges, NULL, SCIP_ALLOC_ABORT, SCIP_Bool, SCIPhypergraphEdgeSize(), SCIPhypergraphEdgesOverlapsBeyond(), SCIPhypergraphEdgesOverlapsFirst(), SCIPhypergraphEdgesOverlapsGetAtIndex(), SCIPhypergraphEdgeVertices(), SCIPhypergraphGetNEdges(), SCIPhypergraphGetNIncidences(), SCIPhypergraphGetNVertices(), SCIPhypergraphHasOverlaps(), SCIPhypergraphHasVertexEdges(), SCIPhypergraphOverlapSize(), SCIPhypergraphOverlapVertices(), SCIPhypergraphVertexEdgesBeyond(), SCIPhypergraphVertexEdgesFirst(), SCIPhypergraphVertexEdgesGetAtIndex(), SCIPsortLong(), TRUE, and valid.

Referenced by constructHypergraph().

◆ SCIPhypergraphIterInit()

SCIP_RETCODE SCIPhypergraphIterInit	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_ITER *	iterator )

initializes a hypergraph iterator's internal memory

Parameters

hypergraph	The hypergraph of this iterator.
iterator	Iterator to be initialized.

Definition at line 1469 of file hypergraph.c.

References SCIP_Hypergraph_Iter::adjacent, assert(), SCIP_Hypergraph_Iter::base, SCIP_Hypergraph::blkmem, BMSallocBlockMemoryArray, SCIP_Hypergraph_Iter::commonvertices, SCIP_Hypergraph_Iter::edgeidx, FALSE, SCIP_Hypergraph_Iter::findoverlaps, SCIP_Hypergraph_Iter::minoverlapsize, SCIP_Hypergraph_Iter::minvertex, NULL, SCIP_Hypergraph_Iter::onlylater, SCIP_ALLOC, SCIP_OKAY, SCIP_Hypergraph_Iter::sizecommonvertices, and SCIP_Hypergraph_Iter::vertexidx.

◆ SCIPhypergraphIterClear()

void SCIPhypergraphIterClear	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_ITER *	iterator )

frees a hypergraph iterator's internal memory

Parameters

hypergraph	The hypergraph of this iterator.
iterator	Iterator to be cleared.

Definition at line 1494 of file hypergraph.c.

References assert(), SCIP_Hypergraph::blkmem, BMSfreeBlockMemoryArray, SCIP_Hypergraph_Iter::commonvertices, and SCIP_Hypergraph_Iter::sizecommonvertices.

◆ SCIPhypergraphIterStart()

void SCIPhypergraphIterStart	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_ITER *	iterator,
		SCIP_HYPERGRAPH_EDGE	base,
		unsigned int	minoverlapsize,
		SCIP_Bool	onlylater,
		SCIP_Bool	findoverlaps )

initializes the iterator to the first adjacent edge of base

findoverlaps indicates whether the overlap corresponding to each edge intersection shall be determined. This requires SCIPhypergraphHasOverlaps.

Parameters

hypergraph	The hypergraph of this iterator.
iterator	Iterator to be initialized.
base	Base edge.
minoverlapsize	Minimum size of the overlap.
onlylater	Whether to only consider edges greater than `base`.
findoverlaps	Whether to compute the overlap sets.

Definition at line 1506 of file hypergraph.c.

References SCIP_Hypergraph_Iter::adjacent, assert(), SCIP_Hypergraph_Iter::base, SCIP_Hypergraph_Iter::edgeidx, SCIP_Hypergraph_Iter::findoverlaps, SCIP_Hypergraph::hasoverlaps, SCIP_Hypergraph::hasvertexedges, SCIP_Hypergraph_Iter::minoverlapsize, SCIP_Hypergraph_Iter::minvertex, SCIP_Hypergraph_Iter::ncommonvertices, SCIP_Hypergraph_Iter::onlylater, SCIP_Hypergraph_Iter::overlap, SCIP_Bool, SCIPhypergraphIterNext(), and SCIP_Hypergraph_Iter::vertexidx.

◆ SCIPhypergraphIterValid()

SCIP_Bool SCIPhypergraphIterValid ( SCIP_HYPERGRAPH_ITER * iterator )

returns whether the iterator is valid

Parameters

iterator Iterator.

Definition at line 1537 of file hypergraph.c.

References assert(), SCIP_Bool, and SCIP_Hypergraph_Iter::vertexidx.

◆ SCIPhypergraphIterNext()

void SCIPhypergraphIterNext	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_ITER *	iterator )

initializes the iterator to the first adjacent edge of base

Parameters

hypergraph	The hypergraph of this iterator.
iterator	Iterator.

Definition at line 1547 of file hypergraph.c.

Referenced by SCIPhypergraphIterStart().

◆ SCIPhypergraphIterBase()

SCIP_HYPERGRAPH_EDGE SCIPhypergraphIterBase ( SCIP_HYPERGRAPH_ITER * iterator )

returns the base edge

Parameters

iterator Iterator.

Definition at line 1685 of file hypergraph.c.

References SCIP_Hypergraph_Iter::base.

◆ SCIPhypergraphIterAdjacent()

SCIP_HYPERGRAPH_EDGE SCIPhypergraphIterAdjacent ( SCIP_HYPERGRAPH_ITER * iterator )

returns the current adjacent edge

Parameters

iterator Iterator.

Definition at line 1693 of file hypergraph.c.

References SCIP_Hypergraph_Iter::adjacent.

◆ SCIPhypergraphIterMinVertex()

SCIP_HYPERGRAPH_VERTEX SCIPhypergraphIterMinVertex ( SCIP_HYPERGRAPH_ITER * iterator )

returns the minimum vertex in the intersection of the base and the current adjacent edge

Parameters

iterator Iterator.

Definition at line 1701 of file hypergraph.c.

References SCIP_Hypergraph_Iter::minvertex.

◆ SCIPhypergraphIterOverlap()

SCIP_HYPERGRAPH_OVERLAP SCIPhypergraphIterOverlap ( SCIP_HYPERGRAPH_ITER * iterator )

returns the overlap for the intersection of the base and the current adjacent edge

If the intersection of the two edges has only one element, then -1 is returned, and if overlap information was not requested in SCIPhypergraphIterStart, then -2 is returned.

Parameters

iterator Iterator.

Definition at line 1714 of file hypergraph.c.

References SCIP_Hypergraph_Iter::overlap.

◆ SCIPhypergraphGetNVertices()

int SCIPhypergraphGetNVertices ( SCIP_HYPERGRAPH * hypergraph )

returns the number of vertices

Parameters

hypergraph The hypergraph.

Definition at line 1764 of file hypergraph.c.

References assert(), and SCIP_Hypergraph::nvertices.

Referenced by constructHypergraph(), prepareSeparation(), and SCIPhypergraphIsValid().

◆ SCIPhypergraphGetNEdges()

int SCIPhypergraphGetNEdges ( SCIP_HYPERGRAPH * hypergraph )

returns the number of edges

Parameters

hypergraph The hypergraph.

Definition at line 1774 of file hypergraph.c.

References assert(), and SCIP_Hypergraph::nedges.

Referenced by constructHypergraph(), prepareSeparation(), SCIPhypergraphIsValid(), separateOneFlower(), separateStandard(), and separateTwoFlower().

◆ SCIPhypergraphBlkmem()

BMS_BLKMEM * SCIPhypergraphBlkmem ( SCIP_HYPERGRAPH * hypergraph )

returns the hypergraph's block memory structure

Parameters

hypergraph The hypergraph.

Definition at line 1784 of file hypergraph.c.

References assert(), SCIP_Hypergraph::blkmem, and NULL.

◆ SCIPhypergraphGetNOverlaps()

int SCIPhypergraphGetNOverlaps ( SCIP_HYPERGRAPH * hypergraph )

returns the number of overlaps

Parameters

hypergraph The hypergraph.

Definition at line 1794 of file hypergraph.c.

References assert(), and SCIP_Hypergraph::noverlaps.

Referenced by constructHypergraph(), prepareSeparation(), and separate().

◆ SCIPhypergraphGetNIncidences()

int SCIPhypergraphGetNIncidences ( SCIP_HYPERGRAPH * hypergraph )

returns the number of edge-vertex incidences

returns the number of vertex-edge incidences.

Parameters

hypergraph The hypergraph.

Definition at line 1804 of file hypergraph.c.

References assert(), SCIP_Hypergraph::edgesverticesbeg, and SCIP_Hypergraph::nedges.

Referenced by SCIPhypergraphIsValid().

◆ SCIPhypergraphVertexData()

SCIP_HYPERGRAPH_VERTEXDATA * SCIPhypergraphVertexData	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_VERTEX	vertex )

returns additional data of vertex

Parameters

hypergraph	The hypergraph.
vertex	A vertex.

Definition at line 1814 of file hypergraph.c.

References assert(), NULL, SCIP_Hypergraph::sizevertexdata, and SCIP_Hypergraph::verticesdata.

Referenced by prepareSeparation(), separateOneFlower(), separateStandard(), and separateTwoFlower().

◆ SCIPhypergraphEdgeData()

SCIP_HYPERGRAPH_EDGEDATA * SCIPhypergraphEdgeData	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_EDGE	edge )

returns additional data of edge

Parameters

hypergraph	The hypergraph.
edge	An edge.

Definition at line 1826 of file hypergraph.c.

References assert(), SCIP_Hypergraph::edgesdata, NULL, and SCIP_Hypergraph::sizeedgedata.

Referenced by prepareSeparation(), separateOneFlower(), separateStandard(), and separateTwoFlower().

◆ SCIPhypergraphOverlapData()

SCIP_HYPERGRAPH_OVERLAPDATA * SCIPhypergraphOverlapData	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_OVERLAP	overlap )

returns additional data of overlap

Parameters

hypergraph	The hypergraph.
overlap	An overlap.

Definition at line 1838 of file hypergraph.c.

References assert(), NULL, SCIP_Hypergraph::overlapsdata, and SCIP_Hypergraph::sizeoverlapdata.

Referenced by prepareSeparation(), SCIPhypergraphComputeOverlaps(), separateOneFlower(), and separateTwoFlower().

◆ SCIPhypergraphEdgeSize()

int SCIPhypergraphEdgeSize	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_EDGE	edge )

returns the number of vertices of edge

Parameters

hypergraph	The hypergraph.
edge	An edge.

Definition at line 1850 of file hypergraph.c.

References assert(), and SCIP_Hypergraph::edgesverticesbeg.

Referenced by prepareSeparation(), SCIPhypergraphIntersectEdges(), SCIPhypergraphIsValid(), separateOneFlower(), separateStandard(), and separateTwoFlower().

◆ SCIPhypergraphEdgeVertices()

SCIP_HYPERGRAPH_VERTEX * SCIPhypergraphEdgeVertices	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_EDGE	edge )

returns the array of vertices of edge

The length of the array is SCIPhypergraphEdgeSize.

Parameters

hypergraph	The hypergraph.
edge	An edge.

Definition at line 1867 of file hypergraph.c.

References assert(), SCIP_Hypergraph::edgesvertices, and SCIP_Hypergraph::edgesverticesbeg.

Referenced by prepareSeparation(), SCIPhypergraphIsValid(), separateOneFlower(), separateStandard(), and separateTwoFlower().

◆ SCIPhypergraphHasVertexEdges()

SCIP_Bool SCIPhypergraphHasVertexEdges ( SCIP_HYPERGRAPH * hypergraph )

returns whether vertices' incident edges are known.

Use SCIPhypergraphComputeVerticesEdges to compute them.

Parameters

hypergraph The hypergraph.

Definition at line 1883 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasvertexedges, and SCIP_Bool.

Referenced by SCIPhypergraphIsValid().

◆ SCIPhypergraphVertexEdgesFirst()

int SCIPhypergraphVertexEdgesFirst	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_VERTEX	vertex )

returns an index for the first edge incident to vertex

Parameters

hypergraph	The hypergraph.
vertex	A vertex.

Definition at line 1893 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasvertexedges, and SCIP_Hypergraph::verticesedgesbeg.

Referenced by SCIPhypergraphIsValid().

◆ SCIPhypergraphVertexEdgesBeyond()

int SCIPhypergraphVertexEdgesBeyond	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_VERTEX	vertex )

returns an index beyond the last edge incident to vertex

Parameters

hypergraph	The hypergraph.
vertex	A vertex.

Definition at line 1905 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasvertexedges, and SCIP_Hypergraph::verticesedgesbeg.

Referenced by SCIPhypergraphIsValid().

◆ SCIPhypergraphVertexEdgesGetAtIndex()

SCIP_HYPERGRAPH_EDGE SCIPhypergraphVertexEdgesGetAtIndex	(	SCIP_HYPERGRAPH *	hypergraph,
		int	idx )

returns the edge corresponding to index that is incident to a vertex

See SCIPhypergraphVertexEdgesFirst and SCIPhypergraphVertexEdgesBeyond to obtain such indices for a vertex.

Parameters

hypergraph	The hypergraph.
idx	Index.

Definition at line 1921 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasvertexedges, and SCIP_Hypergraph::verticesedges.

Referenced by SCIPhypergraphIsValid().

◆ SCIPhypergraphHasOverlaps()

SCIP_Bool SCIPhypergraphHasOverlaps ( SCIP_HYPERGRAPH * hypergraph )

returns whether edges' overlaps and overlaps' vertices are known.

Use SCIPhypergraphComputeOverlaps to compute them.

Parameters

hypergraph The hypergraph.

Definition at line 1937 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasoverlaps, and SCIP_Bool.

Referenced by SCIPhypergraphIsValid().

◆ SCIPhypergraphOverlapSize()

int SCIPhypergraphOverlapSize	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_OVERLAP	overlap )

returns the number of vertices of overlap

Requires SCIPhypergraphHasOverlaps to be TRUE which results from SCIPhypergraphComputeOverlaps.

Parameters

hypergraph	The hypergraph.
overlap	Overlap.

Definition at line 1951 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasoverlaps, and SCIP_Hypergraph::overlapsverticesbeg.

Referenced by prepareSeparation(), SCIPhypergraphIsValid(), SCIPhypergraphOverlapsDisjoint(), separateOneFlower(), and separateTwoFlower().

◆ SCIPhypergraphOverlapVertices()

SCIP_HYPERGRAPH_VERTEX * SCIPhypergraphOverlapVertices	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_OVERLAP	overlap )

returns the array of sorted vertices of overlap

The length of the array is SCIPhypergraphOverlapSize. Requires SCIPhypergraphHasOverlaps to be TRUE which results from SCIPhypergraphComputeOverlaps.

Parameters

hypergraph	The hypergraph.
overlap	Overlap.

Definition at line 1969 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasoverlaps, SCIP_Hypergraph::overlapsvertices, and SCIP_Hypergraph::overlapsverticesbeg.

Referenced by prepareSeparation(), SCIPhypergraphIsValid(), SCIPhypergraphOverlapsDisjoint(), separateOneFlower(), and separateTwoFlower().

◆ SCIPhypergraphEdgesOverlapsFirst()

int SCIPhypergraphEdgesOverlapsFirst	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_EDGE	edge )

returns an index for the first overlap incident to edge

Parameters

hypergraph	The hypergraph.
edge	Edge.

Definition at line 1982 of file hypergraph.c.

References assert(), SCIP_Hypergraph::edgesoverlapsbeg, and SCIP_Hypergraph::hasoverlaps.

Referenced by prepareSeparation(), SCIPhypergraphIsValid(), separateOneFlower(), and separateTwoFlower().

◆ SCIPhypergraphEdgesOverlapsBeyond()

int SCIPhypergraphEdgesOverlapsBeyond	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_EDGE	edge )

returns an index beyond the last overlap incident to edge

Parameters

hypergraph	The hypergraph.
edge	Edge.

Definition at line 1995 of file hypergraph.c.

References assert(), SCIP_Hypergraph::edgesoverlapsbeg, and SCIP_Hypergraph::hasoverlaps.

Referenced by prepareSeparation(), SCIPhypergraphIsValid(), separateOneFlower(), and separateTwoFlower().

◆ SCIPhypergraphEdgesOverlapsGetAtIndex()

SCIP_HYPERGRAPH_OVERLAP SCIPhypergraphEdgesOverlapsGetAtIndex	(	SCIP_HYPERGRAPH *	hypergraph,
		int	idx )

returns the overlap corresponding to idx that is incident to an edge

returns the overlap corresponding to index that is incident to an edge

See SCIPhypergraphEdgesOverlapsFirst and SCIPhypergraphEdgesOverlapsBeyond to obtain such indices for an edge.

Parameters

hypergraph	The hypergraph.
idx	Index.

Definition at line 2013 of file hypergraph.c.

References assert(), SCIP_Hypergraph::edgesoverlaps, and SCIP_Hypergraph::hasoverlaps.

Referenced by prepareSeparation(), SCIPhypergraphIsValid(), separateOneFlower(), and separateTwoFlower().

◆ SCIPhypergraphHasOverlapsEdges()

SCIP_Bool SCIPhypergraphHasOverlapsEdges ( SCIP_HYPERGRAPH * hypergraph )

returns whether overlaps' incident edges are known.

Use SCIPhypergraphComputeOverlapsEdges to compute them.

Parameters

hypergraph The hypergraph.

Definition at line 2029 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasoverlapsedges, and SCIP_Bool.

◆ SCIPhypergraphOverlapsEdgesFirst()

int SCIPhypergraphOverlapsEdgesFirst	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_OVERLAP	overlap )

returns an index for the first edge incident to overlap

Parameters

hypergraph	The hypergraph.
overlap	Overlap.

Definition at line 2039 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasoverlapsedges, and SCIP_Hypergraph::overlapsedgesbeg.

◆ SCIPhypergraphOverlapsEdgesBeyond()

int SCIPhypergraphOverlapsEdgesBeyond	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_OVERLAP	overlap )

returns an index beyond the last edge incident to overlap

Parameters

hypergraph	The hypergraph.
overlap	Overlap.

Definition at line 2051 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasoverlapsedges, and SCIP_Hypergraph::overlapsedgesbeg.

◆ SCIPhypergraphOverlapsEdgesGetAtIndex()

SCIP_HYPERGRAPH_OVERLAP SCIPhypergraphOverlapsEdgesGetAtIndex	(	SCIP_HYPERGRAPH *	hypergraph,
		int	idx )

returns the edge corresponding to idx that is incident to an overlap

returns the edge corresponding to index that is incident to an overlap

See SCIPhypergraphOverlapsEdgesFirst and SCIPhypergraphOverlapsEdgesBeyond to obtain such indices for an overlap.

Parameters

hypergraph	The hypergraph.
idx	Index.

Definition at line 2068 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasoverlapsedges, and SCIP_Hypergraph::overlapsedges.

◆ SCIPhypergraphHasVertexOverlaps()

SCIP_Bool SCIPhypergraphHasVertexOverlaps ( SCIP_HYPERGRAPH * hypergraph )

returns whether vertices' incident overlaps are known

Use SCIPhypergraphComputeOverlaps to compute them.

Parameters

hypergraph The hypergraph.

Definition at line 2085 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasverticesoverlaps, and SCIP_Bool.

◆ SCIPhypergraphVertexOverlapsFirst()

int SCIPhypergraphVertexOverlapsFirst	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_VERTEX	vertex )

returns an index for the first overlap containing vertex

Parameters

hypergraph	The hypergraph.
vertex	A vertex.

Definition at line 2095 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasverticesoverlaps, and SCIP_Hypergraph::verticesoverlapsbeg.

◆ SCIPhypergraphVertexOverlapsBeyond()

int SCIPhypergraphVertexOverlapsBeyond	(	SCIP_HYPERGRAPH *	hypergraph,
		SCIP_HYPERGRAPH_VERTEX	vertex )

returns an index beyond the last overlap incident to vertex

Parameters

hypergraph	The hypergraph.
vertex	A vertex.

Definition at line 2107 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasverticesoverlaps, and SCIP_Hypergraph::verticesoverlapsbeg.

◆ SCIPhypergraphVertexOverlapsGetAtIndex()

SCIP_HYPERGRAPH_OVERLAP SCIPhypergraphVertexOverlapsGetAtIndex	(	SCIP_HYPERGRAPH *	hypergraph,
		int	idx )

returns the overlap corresponding to idx that is incident to a vertex

returns the overlap corresponding to index that is incident to a vertex

See SCIPhypergraphVertexOverlapsFirst and SCIPhypergraphVertexOverlapsBeyond to obtain such indices for a vertex.

Parameters

hypergraph	The hypergraph.
idx	Index.

Definition at line 2124 of file hypergraph.c.

References assert(), SCIP_Hypergraph::hasverticesoverlaps, and SCIP_Hypergraph::verticesoverlaps.

Detailed Description

Functions

Function Documentation

◆ ensureNumVertices()

◆ ensureNumEdges()

◆ ensureNumEdgesVertices()

◆ ensureNumOverlaps()

◆ ensureNumOverlapsVertices()

◆ SCIPhypergraphCreate()

◆ SCIPhypergraphFree()

◆ SCIPhypergraphClear()

◆ SCIPhypergraphAddVertex()

◆ SCIPhypergraphAddEdge()

◆ SCIP_DECL_HASHGETKEY()

◆ SCIP_DECL_HASHKEYEQ()

◆ SCIP_DECL_HASHKEYVAL()

◆ findOverlap()

◆ SCIPhypergraphComputeOverlaps()

◆ SCIPhypergraphComputeVerticesEdges()

◆ SCIPhypergraphOverlapFind()

◆ SCIPhypergraphIntersectEdges()

◆ SCIPhypergraphComputeOverlapsEdges()

◆ SCIPhypergraphComputeVerticesOverlaps()

◆ SCIPhypergraphOverlapsDisjoint()

◆ SCIPhypergraphIsValid()

◆ SCIPhypergraphIterInit()

◆ SCIPhypergraphIterClear()

◆ SCIPhypergraphIterStart()

◆ SCIPhypergraphIterValid()

◆ SCIPhypergraphIterNext()

◆ SCIPhypergraphIterBase()

◆ SCIPhypergraphIterAdjacent()

◆ SCIPhypergraphIterMinVertex()

◆ SCIPhypergraphIterOverlap()

◆ SCIPhypergraphGetNVertices()

◆ SCIPhypergraphGetNEdges()

◆ SCIPhypergraphBlkmem()

◆ SCIPhypergraphGetNOverlaps()

◆ SCIPhypergraphGetNIncidences()

◆ SCIPhypergraphVertexData()

◆ SCIPhypergraphEdgeData()

◆ SCIPhypergraphOverlapData()

◆ SCIPhypergraphEdgeSize()

◆ SCIPhypergraphEdgeVertices()

◆ SCIPhypergraphHasVertexEdges()

◆ SCIPhypergraphVertexEdgesFirst()

◆ SCIPhypergraphVertexEdgesBeyond()

◆ SCIPhypergraphVertexEdgesGetAtIndex()

◆ SCIPhypergraphHasOverlaps()

◆ SCIPhypergraphOverlapSize()

◆ SCIPhypergraphOverlapVertices()

◆ SCIPhypergraphEdgesOverlapsFirst()

◆ SCIPhypergraphEdgesOverlapsBeyond()

◆ SCIPhypergraphEdgesOverlapsGetAtIndex()

◆ SCIPhypergraphHasOverlapsEdges()

◆ SCIPhypergraphOverlapsEdgesFirst()

◆ SCIPhypergraphOverlapsEdgesBeyond()

◆ SCIPhypergraphOverlapsEdgesGetAtIndex()

◆ SCIPhypergraphHasVertexOverlaps()

◆ SCIPhypergraphVertexOverlapsFirst()

◆ SCIPhypergraphVertexOverlapsBeyond()

◆ SCIPhypergraphVertexOverlapsGetAtIndex()