Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

includes complete graph methods, in particular for MST calculation

Author: Daniel Rehfeldt

Complete graph methods, in particular for MST calculation. Assumes a maximum size of the graph. Only sensible for small maximum sizes.

Definition in file completegraph.c.

#include "completegraph.h"
#include "portab.h"

Go to the source code of this file.

Macros
#define	NODE_ID_UNDEFINED -2

Functions
static int	getNnodesCurr (const CGRAPH *cgraph)

static int	getNnodesMax (const CGRAPH *cgraph)

static int	getEdgeStart (int nodepos, int nnodes_max)

static int	getEdgeEnd (int nodepos, int nnodes_curr, int nnodes_max)

static int	getPositionFromId (const CGRAPH *cgraph, int nodeid)

SCIP_Bool	cgraph_valid (const CGRAPH *cgraph)

SCIP_Bool	cgraph_idsInSync (const CGRAPH cgraph, const int ids, int nids)

SCIP_Bool	cgraph_idIsContained (const CGRAPH *cgraph, int id)

SCIP_RETCODE	cgraph_init (SCIP scip, CGRAPH *cgraph, int maxnnodes)

void	cgraph_free (SCIP scip, CGRAPH *cgraph)

void	cgraph_clean (CGRAPH *cgraph)

SCIP_Bool	cgraph_isEmpty (const CGRAPH *cgraph)

SCIP_Bool	cgraph_node_hasAdjCosts (const CGRAPH *cgraph, int nodepos)

void	cgraph_node_applyMinAdjCosts (CGRAPH *cgraph, int nodepos, int nodeid)

void	cgraph_node_append (CGRAPH *cgraph, int nodeid)

void	cgraph_node_repositionTop (CGRAPH *cgraph, int nodeid_new)

void	cgraph_node_deleteTop (CGRAPH *cgraph)

void	cgraph_node_delete (CGRAPH *cgraph, int nodeid)

int	cgraph_node_getTopId (const CGRAPH *cgraph)

SCIP_Real	cgraph_edge_getCost (const CGRAPH *cgraph, int nodeid_tail, int nodeid_head)

SCIP_Bool	cmst_isSync (const CGRAPH cgraph, const CMST cmst)

SCIP_RETCODE	cmst_init (SCIP scip, CMST *cmst, int maxnnodes)

void	cmst_free (SCIP scip, CMST *cmst)

void	cmst_computeMst (const CGRAPH cgraph, int mstroot, CMST cmst)

Macro Definition Documentation

◆ NODE_ID_UNDEFINED

#define NODE_ID_UNDEFINED -2

Definition at line 36 of file completegraph.c.

Referenced by cgraph_init(), cgraph_node_append(), cgraph_node_deleteTop(), and cgraph_valid().

Function Documentation

◆ getNnodesCurr()

static int getNnodesCurr ( const CGRAPH * cgraph )

inlinestatic

gets current number of nodes

Parameters

cgraph the graph

Definition at line 41 of file completegraph.c.

References complete_graph::nnodes_curr.

Referenced by cgraph_clean(), cgraph_idIsContained(), cgraph_node_applyMinAdjCosts(), cgraph_node_hasAdjCosts(), cgraph_node_repositionTop(), cgraph_valid(), cmst_computeMst(), and cmst_isSync().

◆ getNnodesMax()

static int getNnodesMax ( const CGRAPH * cgraph )

inlinestatic

gets maximum number of nodes

Parameters

cgraph the graph

Definition at line 53 of file completegraph.c.

References complete_graph::nnodes_max.

Referenced by cgraph_node_applyMinAdjCosts(), cgraph_node_repositionTop(), cgraph_valid(), cmst_computeMst(), and cmst_isSync().

◆ getEdgeStart()

static int getEdgeStart	(	int	nodepos,
		int	nnodes_max
	)

inlinestatic

gets start position in edge cost array

Parameters

nodepos	node position
nnodes_max	maximum number of nodes

Definition at line 66 of file completegraph.c.

Referenced by cgraph_node_append(), cgraph_node_applyMinAdjCosts(), cgraph_node_deleteTop(), cgraph_node_repositionTop(), cgraph_valid(), cmst_computeMst(), and cmst_isSync().

◆ getEdgeEnd()

static int getEdgeEnd	(	int	nodepos,
		int	nnodes_curr,
		int	nnodes_max
	)

inlinestatic

gets end position in edge cost array; NOT included!

Parameters

nodepos	node position
nnodes_curr	current number of nodes
nnodes_max	maximum number of nodes

Definition at line 80 of file completegraph.c.

Referenced by cgraph_node_append(), cgraph_node_deleteTop(), and cgraph_valid().

◆ getPositionFromId()

static int getPositionFromId	(	const CGRAPH *	cgraph,
		int	nodeid
	)

inlinestatic

gets position of node with specified id

Parameters

cgraph	new graph
nodeid	the node id

Definition at line 97 of file completegraph.c.

References cgraph_valid(), complete_graph::nnodes_curr, and complete_graph::nodeids.

Referenced by cgraph_node_repositionTop().

◆ cgraph_valid()

SCIP_Bool cgraph_valid ( const CGRAPH * cgraph )

is the graph valid?

Parameters

cgraph the graph

Definition at line 121 of file completegraph.c.

References CGRAPH_EDGECOST_UNDEFINED_VALUE, complete_graph::edgecosts, EQ, FALSE, FARAWAY, getEdgeEnd(), getEdgeStart(), getNnodesCurr(), getNnodesMax(), complete_graph::nnodes_active, NODE_ID_UNDEFINED, complete_graph::nodeids, SCIP_Real, SCIPdebugMessage, and TRUE.

Referenced by cgraph_clean(), cgraph_edge_getCost(), cgraph_init(), cgraph_isEmpty(), cgraph_node_append(), cgraph_node_applyMinAdjCosts(), cgraph_node_delete(), cgraph_node_deleteTop(), cgraph_node_getTopId(), cgraph_node_hasAdjCosts(), cgraph_node_repositionTop(), cmst_computeMst(), completegraph(), and getPositionFromId().

◆ cgraph_idsInSync()

SCIP_Bool cgraph_idsInSync	(	const CGRAPH *	cgraph,
		const int *	ids,
		int	nids
	)

is the graph in sync with given node id list?

Parameters

cgraph	the graph
ids	node ids
nids	number of ids

Definition at line 214 of file completegraph.c.

References FALSE, complete_graph::nnodes_curr, complete_graph::nodeids, SCIPdebugMessage, and TRUE.

◆ cgraph_idIsContained()

SCIP_Bool cgraph_idIsContained	(	const CGRAPH *	cgraph,
		int	id
	)

is node with given id in the graph??

Parameters

cgraph	the graph
id	the id

Definition at line 243 of file completegraph.c.

References FALSE, getNnodesCurr(), nnodes, complete_graph::nodeids, and TRUE.

Referenced by cgraph_node_append().

◆ cgraph_init()

SCIP_RETCODE cgraph_init	(	SCIP *	scip,
		CGRAPH **	cgraph,
		int	maxnnodes
	)

initialize complete, undirected graph

Parameters

scip	SCIP data structure
cgraph	new graph
maxnnodes	maximum number of nodes

Definition at line 266 of file completegraph.c.

References complete_graph::adjedgecosts, CGRAPH_EDGECOST_UNDEFINED_VALUE, cgraph_valid(), complete_graph::edgecosts, complete_graph::nnodes_active, complete_graph::nnodes_curr, complete_graph::nnodes_max, complete_graph::node_has_adjcosts, NODE_ID_UNDEFINED, complete_graph::nodeids, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, and SCIPdebugMessage.

Referenced by completegraph(), completemst1(), completemst2(), completemst3(), completemst4(), completemst5(), and sdmstGetWeight().

◆ cgraph_free()

void cgraph_free	(	SCIP *	scip,
		CGRAPH **	cgraph
	)

free complete graph

Parameters

scip	SCIP data structure
cgraph	new graph

Definition at line 310 of file completegraph.c.

References complete_graph::adjedgecosts, complete_graph::edgecosts, complete_graph::node_has_adjcosts, complete_graph::nodeids, SCIPfreeMemory, and SCIPfreeMemoryArray.

Referenced by completegraph(), completemst1(), completemst2(), completemst3(), completemst4(), completemst5(), and sdmstGetWeight().

◆ cgraph_clean()

void cgraph_clean ( CGRAPH * cgraph )

cleans, i.e. resets, graph

Parameters

cgraph new graph

Definition at line 331 of file completegraph.c.

References cgraph_isEmpty(), cgraph_node_deleteTop(), cgraph_valid(), and getNnodesCurr().

◆ cgraph_isEmpty()

SCIP_Bool cgraph_isEmpty ( const CGRAPH * cgraph )

is the graph empty?

Parameters

cgraph new graph

Definition at line 347 of file completegraph.c.

References cgraph_valid(), and complete_graph::nnodes_curr.

Referenced by cgraph_clean().

◆ cgraph_node_hasAdjCosts()

SCIP_Bool cgraph_node_hasAdjCosts	(	const CGRAPH *	cgraph,
		int	nodepos
	)

has the given node adjacency costs?

Parameters

cgraph	the complete graph
nodepos	the node position

Definition at line 358 of file completegraph.c.

References cgraph_valid(), getNnodesCurr(), and complete_graph::node_has_adjcosts.

Referenced by cmst_computeMst().

◆ cgraph_node_applyMinAdjCosts()

void cgraph_node_applyMinAdjCosts	(	CGRAPH *	cgraph,
		int	nodepos,
		int	nodeid
	)

applies adjacency costs to node, but only use if smaller than existing ones.

Parameters

cgraph	the complete graph
nodepos	the node position
nodeid	the node id (for debugging only)

Definition at line 371 of file completegraph.c.

References complete_graph::adjedgecosts, CGRAPH_EDGECOST_UNDEFINED_VALUE, cgraph_valid(), complete_graph::edgecosts, EQ, GE, getEdgeStart(), getNnodesCurr(), getNnodesMax(), complete_graph::node_has_adjcosts, complete_graph::nodeids, SCIP_Real, and TRUE.

Referenced by completemst1(), completemst2(), completemst3(), completemst4(), completemst5(), and sdmstGetWeight().

◆ cgraph_node_append()

void cgraph_node_append	(	CGRAPH *	cgraph,
		int	nodeid
	)

add node (at the end, so at position cgraph->nnodes_curr)

Parameters

cgraph	new graph
nodeid	the node id

Definition at line 416 of file completegraph.c.

References CGRAPH_EDGECOST_UNDEFINED_VALUE, cgraph_idIsContained(), cgraph_valid(), complete_graph::edgecosts, EQ, FALSE, FARAWAY, getEdgeEnd(), getEdgeStart(), complete_graph::nnodes_curr, complete_graph::nnodes_max, complete_graph::node_has_adjcosts, NODE_ID_UNDEFINED, complete_graph::nodeids, and SCIP_Real.

Referenced by completegraph(), completemst1(), completemst2(), completemst3(), completemst4(), completemst5(), and sdmstGetWeight().

◆ cgraph_node_repositionTop()

void cgraph_node_repositionTop	(	CGRAPH *	cgraph,
		int	nodeid_new
	)

replaces node with id 'nodeid_new' by top node

Parameters

cgraph	new graph
nodeid_new	the new node id

Definition at line 463 of file completegraph.c.

References BMScopyMemoryArray, cgraph_node_deleteTop(), cgraph_valid(), complete_graph::edgecosts, EQ, FARAWAY, getEdgeStart(), getNnodesCurr(), getNnodesMax(), getPositionFromId(), complete_graph::nodeids, and SCIP_Real.

Referenced by completemst1().

◆ cgraph_node_deleteTop()

void cgraph_node_deleteTop ( CGRAPH * cgraph )

deletes node at the top

Parameters

cgraph new graph

Definition at line 511 of file completegraph.c.

References CGRAPH_EDGECOST_UNDEFINED_VALUE, cgraph_valid(), complete_graph::edgecosts, EQ, getEdgeEnd(), getEdgeStart(), complete_graph::nnodes_curr, complete_graph::nnodes_max, NODE_ID_UNDEFINED, and complete_graph::nodeids.

Referenced by cgraph_clean(), cgraph_node_repositionTop(), completegraph(), completemst4(), and completemst5().

◆ cgraph_node_delete()

void cgraph_node_delete	(	CGRAPH *	cgraph,
		int	nodeid
	)

deletes node

Parameters

cgraph	new graph
nodeid	the node id

Definition at line 558 of file completegraph.c.

References cgraph_valid(), complete_graph::nnodes_curr, and complete_graph::nodeids.

◆ cgraph_node_getTopId()

int cgraph_node_getTopId ( const CGRAPH * cgraph )

gets id of node at the top

Parameters

cgraph new graph

Definition at line 581 of file completegraph.c.

References cgraph_valid(), complete_graph::nnodes_curr, and complete_graph::nodeids.

◆ cgraph_edge_getCost()

SCIP_Real cgraph_edge_getCost	(	const CGRAPH *	cgraph,
		int	nodeid_tail,
		int	nodeid_head
	)

Get edge cost. Note: quite slow, only use for debugging!

Parameters

cgraph	new graph
nodeid_tail	the node id
nodeid_head	the node id

Definition at line 595 of file completegraph.c.

References cgraph_valid().

◆ cmst_isSync()

SCIP_Bool cmst_isSync	(	const CGRAPH *	cgraph,
		const CMST *	cmst
	)

is the MST struct valid?

Parameters

cgraph	new graph
cmst	the MST

Definition at line 610 of file completegraph.c.

References complete_graph::edgecosts, EQ, FALSE, getEdgeStart(), getNnodesCurr(), getNnodesMax(), complete_mst::mstobj, nnodes, complete_mst::nnodes_max, complete_mst::predecessors, SCIP_Real, SCIPdebugMessage, and TRUE.

Referenced by cmst_computeMst().

◆ cmst_init()

SCIP_RETCODE cmst_init	(	SCIP *	scip,
		CMST **	cmst,
		int	maxnnodes
	)

initializes MST

Parameters

scip	SCIP data structure
cmst	the MST
maxnnodes	maximum number of nodes

Definition at line 660 of file completegraph.c.

References complete_mst::dist, graph_heap_create(), complete_mst::heap, complete_mst::mstobj, complete_mst::nnodes_max, NULL, complete_mst::predecessors, SCIP_CALL, SCIP_OKAY, SCIPallocMemory, SCIPallocMemoryArray, and SCIPdebugMessage.

Referenced by completemst1(), completemst2(), completemst3(), completemst4(), completemst5(), and sdmstGetWeight().

◆ cmst_free()

void cmst_free	(	SCIP *	scip,
		CMST **	cmst
	)

frees MST

Parameters

scip	SCIP data structure
cmst	MST

Definition at line 690 of file completegraph.c.

References complete_mst::dist, graph_heap_free(), complete_mst::heap, complete_mst::predecessors, SCIPfreeMemory, SCIPfreeMemoryArray, and TRUE.

Referenced by completemst1(), completemst2(), completemst3(), completemst4(), completemst5(), and sdmstGetWeight().

◆ cmst_computeMst()

void cmst_computeMst	(	const CGRAPH *	cgraph,
		int	mstroot,
		CMST *	cmst
	)

compute MST on given graph

Parameters

cgraph	the graph to run on
mstroot	root for the MST
cmst	the MST

Definition at line 711 of file completegraph.c.

References cgraph_node_hasAdjCosts(), cgraph_valid(), cmst_isSync(), CONNECT, complete_mst::dist, complete_graph::edgecosts, FARAWAY, getEdgeStart(), getNnodesCurr(), getNnodesMax(), graph_heap_correct(), graph_heap_deleteMinReturnNode(), graph_heap_isClean(), complete_mst::heap, LT, complete_mst::mstobj, dijkstra_heap::position, complete_mst::predecessors, SCIP_Real, dijkstra_heap::size, and UNKNOWN.

Referenced by completemst1(), completemst2(), completemst3(), completemst4(), completemst5(), and sdmstGetWeight().