graph data part of algorithm for maximum cliques
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.
typedef struct _HEAD_ADJ HEAD_ADJ |
TCLIQUE_GETNNODES | ( | tcliqueGetNNodes | ) |
gets number of nodes in the graph
Definition at line 76 of file tclique_graph.c.
TCLIQUE_GETWEIGHTS | ( | tcliqueGetWeights | ) |
gets weight of nodes in the graph
Definition at line 84 of file tclique_graph.c.
TCLIQUE_ISEDGE | ( | tcliqueIsEdge | ) |
returns, whether the edge (node1, node2) is in the graph
Definition at line 92 of file tclique_graph.c.
References assert(), FALSE, nnodes, 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 135 of file tclique_graph.c.
References assert(), i, nnodes, NULL, tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().
TCLIQUE_Bool tcliqueCreate | ( | TCLIQUE_GRAPH ** | tcliquegraph | ) |
creates graph data structure
tcliquegraph | pointer to store graph data structure |
Definition at line 185 of file tclique_graph.c.
References ALLOC_FALSE, assert(), BMSallocMemory, NULL, TCLIQUE_Bool, and TRUE.
Referenced by createConsStoreGraphAtRoot(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), SCIPcreateProbColoring(), and tcliqueLoadFile().
void tcliqueFree | ( | TCLIQUE_GRAPH ** | tcliquegraph | ) |
frees graph data structure
tcliquegraph | pointer to graph data structure |
Definition at line 211 of file tclique_graph.c.
References assert(), BMSfreeMemory, BMSfreeMemoryArray, BMSfreeMemoryArrayNull, and NULL.
Referenced by doSeachEcAggr(), preprocessGraph(), SCIP_DECL_CONSDELETE(), SCIP_DECL_CONSEXITSOL(), SCIP_DECL_PROBDELORIG(), and SCIP_DECL_PROBDELTRANS().
|
static |
ensures, that arrays concerning edges in graph data structure can store at least num entries
tcliquegraph | graph data structure |
num | minimum number of entries concerning edges to store |
Definition at line 238 of file tclique_graph.c.
References ALLOC_FALSE, assert(), BMSreallocMemoryArray, NULL, TCLIQUE_Bool, and TRUE.
Referenced by tcliqueEnsureSizeNodes(), and tcliqueFlush().
|
static |
ensures, that arrays concerning cached edges in graph data structure can store at least num entries
tcliquegraph | graph data structure |
num | minimum number of entries concerning cached edges to store |
Definition at line 264 of file tclique_graph.c.
References ALLOC_FALSE, assert(), BMSreallocMemoryArray, NULL, TCLIQUE_Bool, and TRUE.
Referenced by tcliqueAddEdge().
|
static |
ensures, that arrays concerning nodes in graph data structure can store at least num entries
tcliquegraph | graph data structure |
num | minimum number of entries concerning nodes to store |
Definition at line 291 of file tclique_graph.c.
References ALLOC_FALSE, assert(), BMSreallocMemoryArray, FALSE, i, NULL, TCLIQUE_Bool, 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)
tcliquegraph | graph data structure |
node | node number to add |
weight | weight of node to add |
Definition at line 340 of file tclique_graph.c.
References assert(), FALSE, MAX, TCLIQUE_Bool, tcliqueEnsureSizeNodes(), and TRUE.
Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().
void tcliqueChangeWeight | ( | TCLIQUE_GRAPH * | tcliquegraph, |
int | node, | ||
TCLIQUE_WEIGHT | weight ) |
changes weight of node in graph data structure
tcliquegraph | graph data structure |
node | node to set new weight |
weight | new weight of node (allready scaled) |
Definition at line 362 of file tclique_graph.c.
References assert().
Referenced by preprocessGraph(), SCIP_DECL_PRICERREDCOST(), 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.
tcliquegraph | graph data structure |
node1 | start node of edge to add |
node2 | end node of edge to add |
Definition at line 380 of file tclique_graph.c.
References ALLOC_FALSE, assert(), BMSallocMemoryArray, BMSclearMemoryArray, FALSE, nnodes, NULL, TCLIQUE_Bool, tcliqueEnsureSizeCachedEdges(), and TRUE.
Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().
TCLIQUE_Bool tcliqueFlush | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
inserts all cached edges into the data structures
tcliquegraph | graph data structure |
Definition at line 417 of file tclique_graph.c.
References assert(), BMSfreeMemoryArray, FALSE, i, nnodes, NULL, TCLIQUE_Bool, tcliqueEnsureSizeEdges(), and TRUE.
Referenced by COLORprobGetComplementaryGraph(), createTcliqueGraph(), initTCliquegraph(), preprocessGraph(), SCIP_DECL_CONSACTIVE(), SCIP_DECL_PROBTRANS(), and SCIPcreateProbColoring().
TCLIQUE_Bool tcliqueLoadFile | ( | TCLIQUE_GRAPH ** | tcliquegraph, |
const char * | filename, | ||
double | scaleval, | ||
char * | probname, | ||
int | sizeofprobname ) |
loads graph data structure from file
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 552 of file tclique_graph.c.
References assert(), BMSallocMemoryArray, FALSE, i, infoMessage, NULL, result, TCLIQUE_Bool, tcliqueCreate(), and TRUE.
TCLIQUE_Bool tcliqueSaveFile | ( | TCLIQUE_GRAPH * | tcliquegraph, |
const char * | filename, | ||
double | scaleval, | ||
const char * | probname ) |
saves graph data structure to file
tcliquegraph | graph data structure |
filename | name of file to create |
scaleval | value to unscale weights with |
probname | name of the problem |
Definition at line 729 of file tclique_graph.c.
References assert(), FALSE, i, infoMessage, NULL, TCLIQUE_Bool, and TRUE.
int tcliqueGetNEdges | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
gets number of edges in the graph
tcliquegraph | pointer to graph data structure |
Definition at line 773 of file tclique_graph.c.
References assert(), and NULL.
Referenced by tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and tcliquePrintGraph().
int * tcliqueGetDegrees | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
gets degree of nodes in graph
tcliquegraph | pointer to graph data structure |
Definition at line 783 of file tclique_graph.c.
References assert(), and NULL.
Referenced by greedyStableSet(), greedyStableSet(), preprocessGraph(), tcliqueGetLastAdjedge(), and tcliquePrintGraph().
int * tcliqueGetAdjnodes | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
gets adjacent nodes of edges in graph
tcliquegraph | pointer to graph data structure |
Definition at line 794 of file tclique_graph.c.
References assert(), and NULL.
Referenced by tcliqueGetFirstAdjedge(), and tcliqueGetLastAdjedge().
int * tcliqueGetFirstAdjedge | ( | TCLIQUE_GRAPH * | tcliquegraph, |
int | node ) |
gets pointer to first adjacent edge of given node in graph
tcliquegraph | pointer to graph data structure |
node | given node |
Definition at line 805 of file tclique_graph.c.
References assert(), 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().
int * tcliqueGetLastAdjedge | ( | TCLIQUE_GRAPH * | tcliquegraph, |
int | node ) |
gets pointer to last adjacent edge of given node in graph
tcliquegraph | pointer to graph data structure |
node | given node |
Definition at line 829 of file tclique_graph.c.
References assert(), 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().
void tcliquePrintGraph | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
prints graph data structure
tcliquegraph | pointer to graph data structure |
Definition at line 861 of file tclique_graph.c.
References assert(), i, infoMessage, NULL, tcliqueGetDegrees(), tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and tcliqueGetNEdges().