Detailed Description

graph data part of algorithm for maximum cliques

Author: Tobias Achterberg; Ralf Borndoerfer; Zoltan Kormos; Kati Wolter

#include <stdio.h>
#include <string.h>
#include <assert.h>
#include "tclique/tclique.h"
#include "tclique/tclique_def.h"
#include "blockmemshell/memory.h"

Go to the source code of this file.

Typedefs
typedef struct _HEAD_ADJ	HEAD_ADJ

Functions
	TCLIQUE_GETNNODES (tcliqueGetNNodes)

	TCLIQUE_GETWEIGHTS (tcliqueGetWeights)

	TCLIQUE_ISEDGE (tcliqueIsEdge)

	TCLIQUE_SELECTADJNODES (tcliqueSelectAdjnodes)

TCLIQUE_Bool	tcliqueCreate (TCLIQUE_GRAPH **tcliquegraph)

void	tcliqueFree (TCLIQUE_GRAPH **tcliquegraph)

static TCLIQUE_Bool	tcliqueEnsureSizeEdges (TCLIQUE_GRAPH *tcliquegraph, int num)

static TCLIQUE_Bool	tcliqueEnsureSizeCachedEdges (TCLIQUE_GRAPH *tcliquegraph, int num)

static TCLIQUE_Bool	tcliqueEnsureSizeNodes (TCLIQUE_GRAPH *tcliquegraph, int num)

TCLIQUE_Bool	tcliqueAddNode (TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)

void	tcliqueChangeWeight (TCLIQUE_GRAPH *tcliquegraph, int node, TCLIQUE_WEIGHT weight)

TCLIQUE_Bool	tcliqueAddEdge (TCLIQUE_GRAPH *tcliquegraph, int node1, int node2)

TCLIQUE_Bool	tcliqueFlush (TCLIQUE_GRAPH *tcliquegraph)

TCLIQUE_Bool	tcliqueLoadFile (TCLIQUE_GRAPH *tcliquegraph, const char filename, double scaleval, char *probname, int sizeofprobname)

TCLIQUE_Bool	tcliqueSaveFile (TCLIQUE_GRAPH tcliquegraph, const char filename, double scaleval, const char *probname)

int	tcliqueGetNEdges (TCLIQUE_GRAPH *tcliquegraph)

int *	tcliqueGetDegrees (TCLIQUE_GRAPH *tcliquegraph)

int *	tcliqueGetAdjnodes (TCLIQUE_GRAPH *tcliquegraph)

int *	tcliqueGetFirstAdjedge (TCLIQUE_GRAPH *tcliquegraph, int node)

int *	tcliqueGetLastAdjedge (TCLIQUE_GRAPH *tcliquegraph, int node)

void	tcliquePrintGraph (TCLIQUE_GRAPH *tcliquegraph)

Typedef Documentation

◆ HEAD_ADJ

typedef struct _HEAD_ADJ HEAD_ADJ

Function Documentation

◆ TCLIQUE_GETNNODES()

TCLIQUE_GETNNODES ( tcliqueGetNNodes )

gets number of nodes in the graph

Definition at line 67 of file tclique_graph.c.

References NULL.

◆ TCLIQUE_GETWEIGHTS()

TCLIQUE_GETWEIGHTS ( tcliqueGetWeights )

gets weight of nodes in the graph

Definition at line 75 of file tclique_graph.c.

References NULL.

◆ TCLIQUE_ISEDGE()

TCLIQUE_ISEDGE ( tcliqueIsEdge )

returns, whether the edge (node1, node2) is in the graph

Definition at line 83 of file tclique_graph.c.

References FALSE, nnodes, NULL, tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and TRUE.

◆ TCLIQUE_SELECTADJNODES()

TCLIQUE_SELECTADJNODES ( tcliqueSelectAdjnodes )

selects all nodes from a given set of nodes which are adjacent to a given node and returns the number of selected nodes

Definition at line 126 of file tclique_graph.c.

References nnodes, NULL, tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().

◆ tcliqueCreate()

TCLIQUE_Bool tcliqueCreate ( TCLIQUE_GRAPH ** tcliquegraph )

creates graph data structure

Parameters

tcliquegraph pointer to store graph data structure

Definition at line 176 of file tclique_graph.c.

References ALLOC_FALSE, BMSallocMemory, NULL, and TRUE.

Referenced by createConsStoreGraphAtRoot(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), SCIPcreateProbColoring(), and tcliqueLoadFile().

◆ tcliqueFree()

void tcliqueFree ( TCLIQUE_GRAPH ** tcliquegraph )

frees graph data structure

Parameters

tcliquegraph pointer to graph data structure

Definition at line 202 of file tclique_graph.c.

References BMSfreeMemory, BMSfreeMemoryArray, BMSfreeMemoryArrayNull, and NULL.

Referenced by doSeachEcAggr(), preprocessGraph(), SCIP_DECL_CONSDELETE(), SCIP_DECL_PROBDELORIG(), and SCIP_DECL_PROBDELTRANS().

◆ tcliqueEnsureSizeEdges()

static TCLIQUE_Bool tcliqueEnsureSizeEdges	(	TCLIQUE_GRAPH *	tcliquegraph,
		int	num
	)

static

ensures, that arrays concerning edges in graph data structure can store at least num entries

Parameters

tcliquegraph	graph data structure
num	minimum number of entries concerning edges to store

Definition at line 229 of file tclique_graph.c.

References ALLOC_FALSE, BMSreallocMemoryArray, NULL, and TRUE.

Referenced by tcliqueEnsureSizeNodes(), and tcliqueFlush().

◆ tcliqueEnsureSizeCachedEdges()

static TCLIQUE_Bool tcliqueEnsureSizeCachedEdges	(	TCLIQUE_GRAPH *	tcliquegraph,
		int	num
	)

static

ensures, that arrays concerning cached edges in graph data structure can store at least num entries

Parameters

tcliquegraph	graph data structure
num	minimum number of entries concerning cached edges to store

Definition at line 255 of file tclique_graph.c.

References ALLOC_FALSE, BMSreallocMemoryArray, NULL, and TRUE.

Referenced by tcliqueAddEdge().

◆ tcliqueEnsureSizeNodes()

static TCLIQUE_Bool tcliqueEnsureSizeNodes	(	TCLIQUE_GRAPH *	tcliquegraph,
		int	num
	)

static

ensures, that arrays concerning nodes in graph data structure can store at least num entries

Parameters

tcliquegraph	graph data structure
num	minimum number of entries concerning nodes to store

Definition at line 282 of file tclique_graph.c.

References ALLOC_FALSE, BMSreallocMemoryArray, FALSE, NULL, tcliqueEnsureSizeEdges(), and TRUE.

Referenced by tcliqueAddNode().

◆ tcliqueAddNode()

TCLIQUE_Bool tcliqueAddNode	(	TCLIQUE_GRAPH *	tcliquegraph,
		int	node,
		TCLIQUE_WEIGHT	weight
	)

adds nodes up to the given node number to graph data structure (intermediate nodes have weight 0)

Parameters

tcliquegraph	graph data structure
node	node number to add
weight	weight of node to add

Definition at line 331 of file tclique_graph.c.

References FALSE, MAX, tcliqueEnsureSizeNodes(), and TRUE.

Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().

◆ tcliqueChangeWeight()

void tcliqueChangeWeight	(	TCLIQUE_GRAPH *	tcliquegraph,
		int	node,
		TCLIQUE_WEIGHT	weight
	)

changes weight of node in graph data structure

Parameters

tcliquegraph	graph data structure
node	node to set new weight
weight	new weight of node (allready scaled)

Definition at line 353 of file tclique_graph.c.

Referenced by preprocessGraph(), SCIP_DECL_PRICERREDCOST(), searchEcAggrWithCliques(), and updateWeightsTCliquegraph().

◆ tcliqueAddEdge()

TCLIQUE_Bool tcliqueAddEdge	(	TCLIQUE_GRAPH *	tcliquegraph,
		int	node1,
		int	node2
	)

adds edge (node1, node2) to graph data structure (node1 and node2 have to be contained in graph data structure)

New edges are cached, s.t. the graph data structures are not correct until a call to tcliqueFlush(); you have to make sure, that no double edges are inserted.

Parameters

tcliquegraph	graph data structure
node1	start node of edge to add
node2	end node of edge to add

Definition at line 371 of file tclique_graph.c.

References ALLOC_FALSE, BMSallocMemoryArray, BMSclearMemoryArray, FALSE, nnodes, NULL, tcliqueEnsureSizeCachedEdges(), and TRUE.

Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().

◆ tcliqueFlush()

TCLIQUE_Bool tcliqueFlush ( TCLIQUE_GRAPH * tcliquegraph )

inserts all cached edges into the data structures

Parameters

tcliquegraph graph data structure

Definition at line 408 of file tclique_graph.c.

References BMSfreeMemoryArray, FALSE, nnodes, NULL, tcliqueEnsureSizeEdges(), and TRUE.

Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().

◆ tcliqueLoadFile()

TCLIQUE_Bool tcliqueLoadFile	(	TCLIQUE_GRAPH **	tcliquegraph,
		const char *	filename,
		double	scaleval,
		char *	probname,
		int	sizeofprobname
	)

loads graph data structure from file

Parameters

tcliquegraph	pointer to store graph data structure
filename	name of file with graph data
scaleval	value to scale weights (only integral part of scaled weights is considered)
probname	buffer to store the name of the problem
sizeofprobname	size of buffer to store the name of the problem

Definition at line 543 of file tclique_graph.c.

References BMSallocMemoryArray, BMScopyMemoryArray, BMSfreeMemoryArray, FALSE, infoMessage, NULL, tcliqueCreate(), and TRUE.

◆ tcliqueSaveFile()

TCLIQUE_Bool tcliqueSaveFile	(	TCLIQUE_GRAPH *	tcliquegraph,
		const char *	filename,
		double	scaleval,
		const char *	probname
	)

saves graph data structure to file

Parameters

tcliquegraph	graph data structure
filename	name of file to create
scaleval	value to unscale weights with
probname	name of the problem

Definition at line 732 of file tclique_graph.c.

References FALSE, infoMessage, NULL, and TRUE.

◆ tcliqueGetNEdges()

int tcliqueGetNEdges ( TCLIQUE_GRAPH * tcliquegraph )

gets number of edges in the graph

Parameters

tcliquegraph pointer to graph data structure

Definition at line 776 of file tclique_graph.c.

References NULL.

Referenced by tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and tcliquePrintGraph().

◆ tcliqueGetDegrees()

int* tcliqueGetDegrees ( TCLIQUE_GRAPH * tcliquegraph )

gets degree of nodes in graph

Parameters

tcliquegraph pointer to graph data structure

Definition at line 786 of file tclique_graph.c.

References NULL.

Referenced by greedyStableSet(), preprocessGraph(), tcliqueGetLastAdjedge(), and tcliquePrintGraph().

◆ tcliqueGetAdjnodes()

int* tcliqueGetAdjnodes ( TCLIQUE_GRAPH * tcliquegraph )

gets adjacent nodes of edges in graph

Parameters

tcliquegraph pointer to graph data structure

Definition at line 797 of file tclique_graph.c.

References NULL.

Referenced by tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().

◆ tcliqueGetFirstAdjedge()

int* tcliqueGetFirstAdjedge	(	TCLIQUE_GRAPH *	tcliquegraph,
		int	node
	)

gets pointer to first adjacent edge of given node in graph

Parameters

tcliquegraph	pointer to graph data structure
node	given node

Definition at line 808 of file tclique_graph.c.

References nnodes, NULL, tcliqueGetAdjnodes(), and tcliqueGetNEdges().

Referenced by COLORprobGetComplementaryGraph(), getNViolatedEdges(), preprocessGraph(), runTabuCol(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), SCIP_DECL_READERWRITE(), TCLIQUE_ISEDGE(), TCLIQUE_SELECTADJNODES(), and tcliquePrintGraph().

◆ tcliqueGetLastAdjedge()

int* tcliqueGetLastAdjedge	(	TCLIQUE_GRAPH *	tcliquegraph,
		int	node
	)

gets pointer to last adjacent edge of given node in graph

Parameters

tcliquegraph	pointer to graph data structure
node	given node

Definition at line 832 of file tclique_graph.c.

References nnodes, NULL, tcliqueGetAdjnodes(), tcliqueGetDegrees(), and tcliqueGetNEdges().

Referenced by COLORprobGetComplementaryGraph(), getNViolatedEdges(), preprocessGraph(), runTabuCol(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), SCIP_DECL_READERWRITE(), TCLIQUE_ISEDGE(), TCLIQUE_SELECTADJNODES(), and tcliquePrintGraph().

◆ tcliquePrintGraph()

void tcliquePrintGraph ( TCLIQUE_GRAPH * tcliquegraph )

prints graph data structure

Parameters

tcliquegraph pointer to graph data structure

Definition at line 864 of file tclique_graph.c.

References infoMessage, NULL, tcliqueGetDegrees(), tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and tcliqueGetNEdges().

SCIP

Detailed Description

Typedefs

Functions

Typedef Documentation

◆ HEAD_ADJ

Function Documentation

◆ TCLIQUE_GETNNODES()

◆ TCLIQUE_GETWEIGHTS()

◆ TCLIQUE_ISEDGE()

◆ TCLIQUE_SELECTADJNODES()

◆ tcliqueCreate()

◆ tcliqueFree()

◆ tcliqueEnsureSizeEdges()

◆ tcliqueEnsureSizeCachedEdges()

◆ tcliqueEnsureSizeNodes()

◆ tcliqueAddNode()

◆ tcliqueChangeWeight()

◆ tcliqueAddEdge()

◆ tcliqueFlush()

◆ tcliqueLoadFile()

◆ tcliqueSaveFile()

◆ tcliqueGetNEdges()

◆ tcliqueGetDegrees()

◆ tcliqueGetAdjnodes()

◆ tcliqueGetFirstAdjedge()

◆ tcliqueGetLastAdjedge()

◆ tcliquePrintGraph()