Scippy

SCIP

Solving Constraint Integer Programs

tclique_graph.c File Reference

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

typedef struct _HEAD_ADJ HEAD_ADJ

Function Documentation

TCLIQUE_GETNNODES ( tcliqueGetNNodes  )

gets number of nodes in the graph

Definition at line 66 of file tclique_graph.c.

References NULL.

TCLIQUE_GETWEIGHTS ( tcliqueGetWeights  )

gets weight of nodes in the graph

Definition at line 74 of file tclique_graph.c.

References NULL.

TCLIQUE_ISEDGE ( tcliqueIsEdge  )

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

Definition at line 82 of file tclique_graph.c.

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

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

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

TCLIQUE_Bool tcliqueCreate ( TCLIQUE_GRAPH **  tcliquegraph)

creates graph data structure

Parameters
tcliquegraphpointer to store graph data structure

Definition at line 175 of file tclique_graph.c.

References ALLOC_FALSE, BMSallocMemory, NULL, and TRUE.

Referenced by createTcliqueGraph(), initTCliquegraph(), and tcliqueLoadFile().

void tcliqueFree ( TCLIQUE_GRAPH **  tcliquegraph)

frees graph data structure

Parameters
tcliquegraphpointer to graph data structure

Definition at line 201 of file tclique_graph.c.

References BMSfreeMemory, BMSfreeMemoryArray, BMSfreeMemoryArrayNull, and NULL.

Referenced by searchEcAggr().

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

References ALLOC_FALSE, BMSreallocMemoryArray, NULL, and TRUE.

Referenced by tcliqueEnsureSizeNodes(), and tcliqueFlush().

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

References ALLOC_FALSE, BMSreallocMemoryArray, NULL, and TRUE.

Referenced by tcliqueAddEdge().

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

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

Referenced by 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 330 of file tclique_graph.c.

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

Referenced by createTcliqueGraph(), and initTCliquegraph().

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

Referenced by searchEcAggrWithCliques(), and updateWeightsTCliquegraph().

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

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

Referenced by createTcliqueGraph(), and initTCliquegraph().

TCLIQUE_Bool tcliqueFlush ( TCLIQUE_GRAPH tcliquegraph)

inserts all cached edges into the data structures

Parameters
tcliquegraphgraph data structure

Definition at line 407 of file tclique_graph.c.

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

Referenced by createTcliqueGraph(), and initTCliquegraph().

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

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

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

References FALSE, infoMessage, NULL, and TRUE.

int tcliqueGetNEdges ( TCLIQUE_GRAPH tcliquegraph)

gets number of edges in the graph

Parameters
tcliquegraphpointer to graph data structure

Definition at line 764 of file tclique_graph.c.

References NULL.

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

int* tcliqueGetDegrees ( TCLIQUE_GRAPH tcliquegraph)

gets degree of nodes in graph

Parameters
tcliquegraphpointer to graph data structure

Definition at line 774 of file tclique_graph.c.

References NULL.

Referenced by tcliqueGetLastAdjedge(), and tcliquePrintGraph().

int* tcliqueGetAdjnodes ( TCLIQUE_GRAPH tcliquegraph)

gets adjacent nodes of edges in graph

Parameters
tcliquegraphpointer to graph data structure

Definition at line 785 of file tclique_graph.c.

References NULL.

Referenced by tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().

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

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

Referenced by TCLIQUE_ISEDGE(), TCLIQUE_SELECTADJNODES(), and tcliquePrintGraph().

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

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

Referenced by TCLIQUE_ISEDGE(), TCLIQUE_SELECTADJNODES(), and tcliquePrintGraph().

void tcliquePrintGraph ( TCLIQUE_GRAPH tcliquegraph)

prints graph data structure

Parameters
tcliquegraphpointer to graph data structure

Definition at line 852 of file tclique_graph.c.

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