Detailed Description

includes complete graph methods, in particular for MST calculation

Author: Daniel Rehfeldt

#include "scip/scip.h"
#include "graph.h"

Data Structures
struct	complete_graph

struct	complete_graph_node_buffer

struct	complete_mst

Macros
#define	CGRAPH_EDGECOST_UNDEFINED_VALUE -1.0

Typedefs
typedef struct complete_graph	CGRAPH

typedef struct complete_graph_node_buffer	CNBUFF

typedef struct complete_mst	CMST

Functions
SCIP_Bool	cgraph_valid (const CGRAPH *)

SCIP_Bool	cgraph_isEmpty (const CGRAPH *)

SCIP_Bool	cgraph_idsInSync (const CGRAPH , const int , int)

SCIP_Bool	cgraph_idIsContained (const CGRAPH *, int)

SCIP_RETCODE	cgraph_init (SCIP , CGRAPH *, int)

void	cgraph_free (SCIP , CGRAPH *)

void	cgraph_clean (CGRAPH *)

SCIP_Bool	cgraph_node_hasAdjCosts (const CGRAPH *, int)

void	cgraph_node_append (CGRAPH *, int)

void	cgraph_node_applyMinAdjCosts (CGRAPH *, int, int)

void	cgraph_node_repositionTop (CGRAPH *, int)

void	cgraph_node_deleteTop (CGRAPH *)

void	cgraph_node_delete (CGRAPH *, int)

int	cgraph_node_getTopId (const CGRAPH *)

SCIP_Real	cgraph_edge_getCost (const CGRAPH *, int, int)

SCIP_Bool	cmst_isSync (const CGRAPH , const CMST )

SCIP_RETCODE	cmst_init (SCIP , CMST *, int)

void	cmst_free (SCIP , CMST *)

void	cmst_computeMst (const CGRAPH , int, CMST )

Macro Definition Documentation

◆ CGRAPH_EDGECOST_UNDEFINED_VALUE

#define CGRAPH_EDGECOST_UNDEFINED_VALUE -1.0

Definition at line 39 of file completegraph.h.

Referenced by cgraph_init(), cgraph_node_append(), cgraph_node_applyMinAdjCosts(), cgraph_node_deleteTop(), cgraph_valid(), completemst1(), completemst2(), completemst3(), completemst4(), and completemst5().

Typedef Documentation

◆ CGRAPH

typedef struct complete_graph CGRAPH

complete, undirected graph storage

◆ CNBUFF

typedef struct complete_graph_node_buffer CNBUFF

buffer that allows to (partially) restore a complete graph node todo need something more special here that takes dfs depth and a node identifier (which) as input applies corresponding part to graph... maybe whenever you store something you get an identifier back???

◆ CMST

typedef struct complete_mst CMST

complete, undirected graph MST storage; for computing an MST on a CGRAPH

Function Documentation

◆ 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_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_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_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_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_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_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().

SCIP

Detailed Description

Data Structures

Macros

Typedefs

Functions

Macro Definition Documentation

◆ CGRAPH_EDGECOST_UNDEFINED_VALUE

Typedef Documentation

◆ CGRAPH

◆ CNBUFF

◆ CMST

Function Documentation

◆ cgraph_valid()

◆ cgraph_isEmpty()

◆ cgraph_idsInSync()

◆ cgraph_idIsContained()

◆ cgraph_init()

◆ cgraph_free()

◆ cgraph_clean()

◆ cgraph_node_hasAdjCosts()

◆ cgraph_node_append()

◆ cgraph_node_applyMinAdjCosts()

◆ cgraph_node_repositionTop()

◆ cgraph_node_deleteTop()

◆ cgraph_node_delete()

◆ cgraph_node_getTopId()

◆ cgraph_edge_getCost()

◆ cmst_isSync()

◆ cmst_init()

◆ cmst_free()

◆ cmst_computeMst()