Scippy

SCIP

Solving Constraint Integer Programs

Detailed Description

graph data part of algorithm for maximum cliques

Author
Tobias Achterberg
Ralf Borndoerfer
Zoltan Kormos
Kati Wolter

Definition in file tclique_graph.c.

#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 76 of file tclique_graph.c.

References NULL.

◆ TCLIQUE_GETWEIGHTS()

TCLIQUE_GETWEIGHTS ( tcliqueGetWeights  )

gets weight of nodes in the graph

Definition at line 84 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 92 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 135 of file tclique_graph.c.

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

◆ tcliqueCreate()

TCLIQUE_Bool tcliqueCreate ( TCLIQUE_GRAPH **  tcliquegraph)

creates graph data structure

Parameters
tcliquegraphpointer to store graph data structure

Definition at line 185 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
tcliquegraphpointer to graph data structure

Definition at line 211 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
tcliquegraphgraph data structure
numminimum number of entries concerning edges to store

Definition at line 238 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
tcliquegraphgraph data structure
numminimum number of entries concerning cached edges to store

Definition at line 264 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
tcliquegraphgraph data structure
numminimum number of entries concerning nodes to store

Definition at line 291 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
tcliquegraphgraph data structure
nodenode number to add
weightweight of node to add

Definition at line 340 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
tcliquegraphgraph data structure
nodenode to set new weight
weightnew weight of node (allready scaled)

Definition at line 362 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
tcliquegraphgraph data structure
node1start node of edge to add
node2end node of edge to add

Definition at line 380 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
tcliquegraphgraph data structure

Definition at line 417 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
tcliquegraphpointer to store graph data structure
filenamename of file with graph data
scalevalvalue to scale weights (only integral part of scaled weights is considered)
probnamebuffer to store the name of the problem
sizeofprobnamesize of buffer to store the name of the problem

Definition at line 552 of file tclique_graph.c.

References BMSallocMemoryArray, 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
tcliquegraphgraph data structure
filenamename of file to create
scalevalvalue to unscale weights with
probnamename of the problem

Definition at line 728 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
tcliquegraphpointer to graph data structure

Definition at line 772 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
tcliquegraphpointer to graph data structure

Definition at line 782 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
tcliquegraphpointer to graph data structure

Definition at line 793 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
tcliquegraphpointer to graph data structure
nodegiven node

Definition at line 804 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
tcliquegraphpointer to graph data structure
nodegiven node

Definition at line 828 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
tcliquegraphpointer to graph data structure

Definition at line 860 of file tclique_graph.c.

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