SCIP
Solving Constraint Integer Programs
Solving Constraint Integer Programs
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.
Typedefs | |
| typedef struct _HEAD_ADJ | HEAD_ADJ |
| typedef struct _HEAD_ADJ HEAD_ADJ |
| TCLIQUE_GETNNODES | ( | tcliqueGetNNodes | ) |
| TCLIQUE_GETWEIGHTS | ( | tcliqueGetWeights | ) |
| TCLIQUE_ISEDGE | ( | tcliqueIsEdge | ) |
returns, whether the edge (node1, node2) is in the graph
Definition at line 82 of file tclique_graph.c.
References 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 125 of file tclique_graph.c.
References 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 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
| tcliquegraph | pointer to graph data structure |
Definition at line 201 of file tclique_graph.c.
References BMSfreeMemory, BMSfreeMemoryArray, BMSfreeMemoryArrayNull, and NULL.
Referenced by searchEcAggr().
|
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 228 of file tclique_graph.c.
References ALLOC_FALSE, BMSreallocMemoryArray, NULL, 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 254 of file tclique_graph.c.
References ALLOC_FALSE, BMSreallocMemoryArray, NULL, 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 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)
| tcliquegraph | graph data structure |
| node | node number to add |
| weight | weight 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
| tcliquegraph | graph data structure |
| node | node to set new weight |
| weight | new 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.
| tcliquegraph | graph data structure |
| node1 | start node of edge to add |
| node2 | end node of edge to add |
Definition at line 370 of file tclique_graph.c.
References ALLOC_FALSE, BMSallocMemoryArray, BMSclearMemoryArray, FALSE, nnodes, NULL, tcliqueEnsureSizeCachedEdges(), and TRUE.
Referenced by createTcliqueGraph(), and initTCliquegraph().
| TCLIQUE_Bool tcliqueFlush | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
inserts all cached edges into the data structures
| tcliquegraph | graph data structure |
Definition at line 407 of file tclique_graph.c.
References BMSfreeMemoryArray, FALSE, nnodes, 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
| 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 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
| tcliquegraph | graph data structure |
| filename | name of file to create |
| scaleval | value to unscale weights with |
| probname | name 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
| tcliquegraph | pointer 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
| tcliquegraph | pointer 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
| tcliquegraph | pointer 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
| tcliquegraph | pointer to graph data structure |
| node | given node |
Definition at line 796 of file tclique_graph.c.
References nnodes, 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
| tcliquegraph | pointer to graph data structure |
| node | given node |
Definition at line 820 of file tclique_graph.c.
References nnodes, NULL, tcliqueGetAdjnodes(), tcliqueGetDegrees(), and tcliqueGetNEdges().
Referenced by TCLIQUE_ISEDGE(), TCLIQUE_SELECTADJNODES(), and tcliquePrintGraph().
| void tcliquePrintGraph | ( | TCLIQUE_GRAPH * | tcliquegraph | ) |
prints graph data structure
| tcliquegraph | pointer to graph data structure |
Definition at line 852 of file tclique_graph.c.
References infoMessage, NULL, tcliqueGetDegrees(), tcliqueGetFirstAdjedge(), tcliqueGetLastAdjedge(), and tcliqueGetNEdges().